ตัวย่อตรรกะพจน์เอสเปรสโซ่

บทนำ

ปัจจุบันอุปกรณ์ดิจิทัลอิเล็กทรอนิกส์ได้เข้ามามีบทบาทอย่างมากในชีวิตประจำวัน ส่วนมากจะถูกฝังอยู่ในเครื่องใช้ไฟฟ้าต่างๆ ซึ่งจะประกอบด้วยบล็อกจำนวนมาก (อุปกรณ์แปลงค่าบูลลีนในวงจรดิจิทัล) เพื่อให้วงจรสามารถทำงานตรงตามความต้องการ โดยสรุปแล้วอุตสาหกรรมการผลิตอุปกรณ์ดิจิทัลอิเล็กทรอนิกส์เป็นการนำวิธีการทางลอจิกมาใช้อย่างมีประสิทธิภาพ

วิธีการลดรูปฟังก์ชันบูลีนด้วยมือ

วิธีการลดรูปฟังก์ชันบูลีนด้วยมือวิธีหนึ่งที่ทำได้ง่ายคือ การใช้แผนผังคาร์โนห์ (Karnaugh map) ซึ่งวิธีนี้จะยากและมีแนวโน้มที่จะผิดพลาดได้ และไม่เหมาะกับสมการบูลีนที่มีตัวแปรมากกว่า 6 ตัว และที่ใช้ได้จริงๆ นั้นใช้กับตัวแปรเพียง 4 ตัวเท่านั้น ในขณะที่สมการบูลีนตั้งต้นหนึ่งสมการ เมื่อผ่านการทำแผนผังคาร์โนห์สามารถให้คำตอบได้หลายแบบ แม้กระทั่งสมการที่ยากต่อการนำไปใช้ นอกจากนี้การใช้แผนผังคาร์โนห์ ยังไม่เหมาะที่จะนำไปใช้ในรูปแบบโปรแกรมคอมพิวเตอร์ แต่เนื่องจากฟังก์ชันลอจิกที่ใช้ในปัจจุบันมีตัวแปรจำนวนมาก การลดรูปด้วยมือทำได้ลำบากมากและยังมีความเสี่ยงสูงที่จะผิดพลาด จึงต้องใช้คอมพิวเตอร์ในการลดรูป
วิธีการแรกที่นิยมใช้กันมาก คือ วิธีทำเป็นตารางที่พัฒนาโดย ควีน-แมคคลัสกี้ เริ่มต้นโดยการเขียน minterm สำหรับฟังก์ชันที่มีการใช้งาน ในรูปของตารางค่าความจริงเรียงจากน้อยไปมาก จับคู่ minterm ที่มีจำนวนบิตต่างกันเพียง 1 บิต ซึ่งจะสามารถลดตัวแปรลงไปได้หนึ่งตัว (ลด Prime Implicant) ทำซ้ำไปเรื่อยๆ จนไม่สามารถจับคู่ต่อไปได้ นำผลที่ได้จากการลดตัวแปรในขั้นตอนที่ผ่านมาแล้ว มาทำการจับคู่ไปเรื่อยๆ จนไม่สามารถจับคู่ได้อีก (ลด Essentail Prime Implicant) จะได้สมการของบูลีนที่มีตัวแปรน้อยที่สุด
แม้ว่าขั้นตอนวิธีการของควีน-แมคคลัสกี้จะเหมาะที่จะนำไปทำเป็นโปรแกรมคอมพิวเตอร์มาก แต่การหาคำตอบนั้นด้อยประสิทธิภาพในแง่ของเวลาที่ใช้ในการประมวลผลและการใช้หน่วยความจำ การเพิ่มตัวแปรเพียง 1 ตัวไปยังฟังก์ชันจะส่งผลให้ต้องเพิ่มเวลาที่ใช้ในการประมวลผลและการใช้หน่วยความจำ เกือบถึง 2 เท่า เพราะว่าความยาวของตารางค่าความจริงมีการเพิ่มขึ้นเป็นแบบเอกโพเนนเชียลกับจำนวนตัวแปร ดังนั้นยิ่งคำตอบที่ได้มีพจน์บูลีนมากขึ้น จำนวนบล็อกที่ต้องใช้ในวงจรก็เพิ่มขึ้นตามไปด้วย เป็นผลให้วิธีการของควีน-แมคคลัสกี้สามารถใช้ได้จริงเฉพาะงานบางอย่างเท่านั้น

วิธีการเอสเปรสโซ่

มีการเปลี่ยนแปลงขั้นตอนวิธีของเอสเปรสโซ่อย่างมากที่ถูกพัฒนาโดยเบรตันจากมหาลัยเบิร์กเลย์แคลิฟอร์เนีย แทนที่จะเขียนฟังก์ชันบูลีนในรูปของ minterm ตัวโปรแกรมจะทำการสร้าง cube แทนการเขียนพจน์ของฟังก์ชันบูลีนที่กำลังทำการลดรูปในรูปของ 1,0,x(don't care) แม้ว่าการลดรูปคำตอบไม่สามารถรับประกันว่าจะได้คำตอบที่อยู่ในรูปสั้นสุดจริง แต่เมื่อเปรียบเทียบกับวิธีอื่นแล้ว วิธีนี้จะประสิทธิภาพมากกว่า เพราะมีการลดการใช้หน่วยความจำและระยะเวลาในการคำนวณ เหมือนกับที่ชื่อของวิธีการนี้คือเอสเปรสโซ่กาแฟที่ชงสดอย่างทันทีทันใด นอกจากนั้นยังมีการควบคุมอย่างหนักที่จำกัดจำนวนของตัวแปร จำนวนพจน์ของคำตอบที่ได้ และจำนวนบล็อกที่ต้องใช้ ซึ่งโดยทั่วไปตัวแปร 10 ตัว ก็จะให้คำตอบ 10 พจน์ที่พร้อมใช้งาน
เมื่อส่งตารางค่าความจริงที่จะใช้งานให้กับโปรแกรมเอสเปรสโซ่ ก็จะได้ตารางคำตอบที่ย่อแล้วกลับมา โดยคำตอบจะอยู่ในรูปของ ON-cover(ฟังก์ชันบูลีนที่คืนค่า 1) หรือไม่ก็ OFF-cover(ฟังก์ชันบูลีนที่คืนค่า 0) ของฟังก์ชัน ขึ้นอยู่กับว่าจะเลือกใช้ SoP หรือ PoS โดยปกติแล้ว product term จะใช้ฟังก์ชันเอาต์พุตร่วมกันมากเท่าที่จะใช้ได้ แต่โปรแกรมสามารถจองฟังก์ชันเอาต์พุตที่แยกกันแต่ละอันได้ เพื่อให้เกิดประสิทธิภาพในการสร้างอาเรย์ลอจิกสองมิติอย่างเช่น PLA (Programmable Logic Array) หรือ PAL (Programmable Array Logic)
วิธีการเอสเปรสโซ่ได้ถูกพิสูจน์แล้วว่า มันประสบความสำเร็จอย่างมากที่รวมขั้นตอนการลดรูปฟังก์ชันลอจิกเข้าด้วยกันเป็นเครื่องมือสังเคราะห์ลอจิกเสมือนจริงที่ทันสมัย สำหรับการนำฟังก์ชันไปใช้ใน Multi-level logic นั้น คำตอบที่ผ่านการลดรูปแล้วคือคำตอบที่เหมาะสมที่สุดแล้ว โดยการแยกตัวประกอบและทำตารางไปยังเซลล์ลอจิกพื้นฐานในเทคโนโลยีที่ต้องการทั้งที่เกี่ยกับ FPGA (Field Programmable Gate Array) หรือ ASIC (Application Specific Integrated Circuit)

รหัสเทียม

Epresso ( Fon, Fdc ) { // รับฟังก์ชันบูลีนในรูปของ ON-set กับ DC-set

Foff = Complement ( Fon, Fdc ); // สร้าง OFF-set จากฟังก์ชันที่รับเข้ามา เก็บไว้ใช้ต่อไป
F = Expand ( Fon, Foff ); // สร้าง cube อันแรก เก็บลง F
F = Irredundant ( F, Fdc ); // กำจัด cube ที่ซ้ำซ้อนออก
E = Essentials ( F, Fdc ); // หา essential implicant
F = F - E; // ลบ essential implicant ออกจากการทำงาน เพราะไม่สามารถย่อได้อีก
Fdc = Fdc - E; // แล้วนำ essential implicant ไปเก็บไว้ใน DC-set ชั่วคราว

While ( Cost ( F ) ) { // ทำอีกรอบเมื่อ F ยังลดลงเรื่อยๆ
F = Reduce ( F, Fdc );
F = Expand ( F, Foff );
F = Irredundant ( F, Fdc );
}

F = F + E; //เติม essential implicant ที่ลบออกกลับเข้ามา

return ( F ); // ส่ง essential implicant กลับ
}

ตัวอย่างการใช้งาน

f (A,B,C,D) =  m (4,5,6,8,9,10,13) + d (0,7,15)

Espresso Input Espresso Output
.i 4 -- # inputs .i 4
.o 1 -- # outputs .o 1
.ilb a b c d -- input names .ilb a b c d
.ob f -- output name .ob f
.p 10 -- number of product terms .p 3
0100 1 -- A'BC'D' true 1-01 1 -- A C' D
0101 1 -- A'BC'D true 10-0 1 -- A B' D'
0110 1 -- A'BCD' true 01-- 1 -- A' B
1000 1 -- AB'C'D' true .e
1001 1 -- AB'C'D true
1010 1 -- AB'CD' true f = A C' D + A B' D' + A' B
1101 1 -- ABC'D true
0000 - -- A'B'C'D' don't care
0111 - -- A'BCD don't care
1111 - -- ABCD don't care
.e -- end of list

Minilog

คือ โปรแกรมลดรูปตรรกะพจน์ที่เอาวิธีการเอสเปรสโซ่ไปใช้งาน มันสามารถสร้างบล็อกที่เป็นเกตสองชั้นที่มีอินพุตและเอาต์พุตมากถึง 40 ตัว หรือสร้าง synchronous state machine ได้ถึง 256 สถานะ สามารถดาวน์โหลดโปรแกรมมินิลอคได้ที่ Publicad (โปรแกรมมินิลอคได้รวมอยู่ใน Publicad toolkit)

Logic Friday

คือโปรแกรมแจกฟรีบนวินโดวส์ที่ทำ GUI ให้กับเอสเปรสโซ่ ซึ่งผู้ใช้สามารถป้อนฟังก์ชันบูลีนได้หลายแบบ เช่น ตารางค่าความจริง, สมการ, แผนภาพเกต สามารถดาวน์โหลดโปรแกรมลอจิกฟรายเดย์ได้ที่ sontrak

Espresso sources

ต้นฉบับของโปรแกรมเอสเปรสโซ่สามารถใช้งานได้ที่เว็บไซต์ของมหาวิทยาลัยเบิร์กเลย์ ที่ Pubs/Downloads/Espresso