เทคนิค SAR
จากวิกิพีเดีย สารานุกรมเสรี
[แก้] เทคนิค SAR (SAR Technique)
เทคนิค SAR คือ วิธีการในการลดรูปพีชคณิตที่มีความซับซ้อนยุ่งยากให้มีรูปแบบที่ง่ายขึ้น เพื่อช่วยในการลดความยุ่งยากของสมการลอจิก โดยจะทำสมการให้อยู่ในรูปของ Standard SOP แล้วนำกฎหรือทฤษฎีการลดรูปพีชคณิตมาใช้ในการลดรูปสมการ
[แก้] ทฤษฎีที่นำมาใช้ในการลดรูปสมการ
- Adjacency theorem
คือ การรวมเทอมต่างๆ ในสมการให้เล็กลงหรือมีขนาดของเทอมน้อยลง เช่น
ตัวอย่าง XY + XY'= X พิสูจน์ XY + XY'= X(Y+Y') (จากกฎ A+A'= 1) = X(1) (จากกฎ X•1 = X) = X
- Idempotency theorem
คือ ทฤษฎีการรวมหรือยุบเทอมที่เหมือนกันให้เหลือเพียงเทอมเดียว เช่น
-
- X • X = X
- XYZ + XY'Z + XYZ = XYZ + XY'Z
- Consensus theorem
คือ ทฤษฎีการรวมเทอม โดยจะทำการเพิ่มตัวที่ขาดในแต่ละเทอมให้ครบก่อน แล้วจึงทำการลดรูปสมการ เช่น
ตัวอย่าง XY + X'Z + YZ = XY + X'Z พิสูจน์ XY + X'Z + YZ = XY(Z+Z') + X'Z(Y+Y') +YZ(X+X') (เพิ่มตัวแปรที่ขาดในแต่ละเทอม) = XYZ + XYZ' + X'YZ + XY'Z + XYZ + X'YZ (ใช้ Idempotency theorem) = XYZ +XYZ' + X'YZ + X'Y'Z = XY(Z+Z') + X'Z(Y+Y') (ใช้ Adjacency theorem) = XY(1) + X'Z(1) (ใช้กฎ A+A' = 1) = XY + X'Z
ในการลดรูปสมการพีชคณิตด้วย SAR Technique นั้น จะต้องทำสมการให้อยู่ในรูป Standard SOP ก่อน แล้วทำการเปรียบเทียบเทอมทุกเทอม โดยใช้กฎข้างต้นในการยุบเทอมให้มีขนาดลดลง
- ขั้นตอนของ SAR Technique
- ทำสมการให้อยู่ในรูป Standard SOP
- เปรียบเทียบเทอมแรกกับทุกเทอมถัดไปจนถึงเทอมสุดท้าย (โดยจะเปรียบเทียบแบบนี้กับเทอมที่ 2,3,...,n-1)
- นำผลที่ได้จากการเปรียบเทียบมาเชื่อมด้วยเครื่องหมาย + (or gate)
นอกจากใช้ SAR Technique ในการลดรูปสมการแล้วยังสามารถใช้วิธีการอื่นๆ ได้อีก เช่น แผนผัง K-map Quine-McClusey Technique(Q-M technique)