เทคนิค SAR

เทคนิค SAR (Systematic Algebraic Reduction (SAR) Technique) คือ วิธีการในการลดรูปพีชคณิตแบบบูล (Boolean minimization) ที่มีความซับซ้อนยุ่งยากให้มีรูปแบบที่ง่ายขึ้น เพื่อช่วยในการลดความยุ่งยากของสมการลอจิก โดยทำสมการให้อยู่ในรูปของ Sum-of-product (SOP) แล้วนำกฎหรือทฤษฎีการลดรูปพีชคณิตมาใช้ในการลดรูปสมการ

ทฤษฎีในการลดรูปสมการ

• Adjacency theorem

คือ การรวมเทอมต่างๆ ในสมการให้เล็กลงหรือมีขนาดของเทอมน้อยลง ตัวอย่างเช่น

$\begin{array}{cc}XY+X\bar{Y}& =X(Y+\bar{Y})\\ & =X\cdot 1\\ & =X\end{array}$

• Idempotency theorem

คือ ทฤษฎีการรวมเทอมที่เหมือนกันให้เหลือเพียงเทอมเดียว ได้แก่

$X\cdot X=X$

$XYZ+X\bar{Y}Z+XYZ=XYZ+X\bar{Y}Z$

• Consensus theorem

คือ ทฤษฎีการรวมเทอม โดยจะทำการเพิ่มตัวที่ขาดในแต่ละเทอมให้ครบก่อน แล้วจึงทำการลดรูปสมการ ตัวอย่างเช่น

$\begin{array}{cc}XY+\bar{X}Z+YZ& =XY(Z+\bar{Z})+\bar{X}Z(Y+\bar{Y})+YZ(X+\bar{X})\\ & =XYZ+XY\bar{Z}+\bar{X}YZ+X\bar{Y}Z+XYZ+\bar{X}YZ\\ & =XYZ+XY\bar{Z}+\bar{X}YZ+\bar{X}\bar{Y}Z\\ & =XY(Z+\bar{Z})+\bar{X}Z(Y+\bar{Y})\\ & =XY\cdot 1+\bar{X}Z\cdot 1\\ & =XY+\bar{X}Z\end{array}$

การลดรูปสมการพีชคณิตด้วยเทคนิค SAR นั้นต้องทำสมการให้อยู่ในรูป SOP ก่อน แล้วจึงเปรียบเทียบเทอมทุกเทอม โดยใช้กฎทางตรรกศาสตร์ในการยุบเทอมให้มีขนาดลดลง

ขั้นตอนของลดรูปสมการ

1. ทำสมการให้อยู่ในรูป SOP
2. เปรียบเทียบเทอมแรกกับทุกเทอมถัดไปจนถึงเทอมสุดท้าย (โดยเปรียบเทียบแบบนี้กับเทอมที่ 2, 3, ..., n-1)
3. นำผลที่ได้จากการเปรียบเทียบมาเชื่อมด้วยเครื่องหมาย + (OR-gate)

ไฟล์:SAR Technique1.jpg

นอกจากใช้เทคนิค SAR ในการลดรูปสมการแล้วยังสามารถใช้วิธีการอื่นๆ ได้อีก เช่น แผนผัง Karnaugh map และ Quine–McCluskey algorithm เป็นต้น

ดูเพิ่ม

• http://cset.sp.utoledo.edu/eet3350/lesson4suppl.html แม่แบบ:Webarchive