เทคนิค SAR

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

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

• Adjacency theorem

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

${\begin{aligned}XY+X{\overline {Y}}&{}=X(Y+{\overline {Y}})\\&{}=X\cdot 1\\&{}=X\end{aligned}}$

• Idempotency theorem

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

$X\cdot X=X$

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

• Consensus theorem

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

${\begin{aligned}XY+{\overline {X}}Z+YZ&{}=XY(Z+{\overline {Z}})+{\overline {X}}Z(Y+{\overline {Y}})+YZ(X+{\overline {X}})\\&{}=XYZ+XY{\overline {Z}}+{\overline {X}}YZ+X{\overline {Y}}Z+XYZ+{\overline {X}}YZ\\&{}=XYZ+XY{\overline {Z}}+{\overline {X}}YZ+{\overline {X}}{\overline {Y}}Z\\&{}=XY(Z+{\overline {Z}})+{\overline {X}}Z(Y+{\overline {Y}})\\&{}=XY\cdot 1+{\overline {X}}Z\cdot 1\\&{}=XY+{\overline {X}}Z\end{aligned}}$

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

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

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

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

ดูเพิ่ม

• http://cset.sp.utoledo.edu/eet3350/lesson4suppl.html เก็บถาวร 2010-06-19 ที่ เวย์แบ็กแมชชีน