ตัวย่อตรรกะพจน์เอสเปรสโซ่
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ตัวย่อตรรกะพจน์เอสเปรสโซ่ (อังกฤษ: Espresso heuristic logic minimizer) คือโปรแกรมที่มีขั้นตอนวิธีเอาลดรูปสมการบูลีนให้อยู่ในรูปที่เล็กที่สุด เพื่อลดความซับซ้อนของวงจรอิเล็คทรอนิกส์ เอสเปรสโซ่ถูกพัฒนาขึ้นที่ไอบืเอ็มโดยโรเบิร์ต เบรย์ตัน และเผยแพร่เมื่อปี พ.ศ. 2529 และได้ถูกพัฒนาต่อมาอีกหลายครั้ง
บทนำ แก้
ปัจจุบันอุปกรณ์ดิจิทัลอิเล็กทรอนิกส์ได้เข้ามามีบทบาทอย่างมากในชีวิตประจำวัน ส่วนมากจะถูกฝังอยู่ในเครื่องใช้ไฟฟ้าต่างๆ ซึ่งจะประกอบด้วยบล็อกจำนวนมาก (อุปกรณ์แปลงค่าบูลลีนในวงจรดิจิทัล) เพื่อให้วงจรสามารถทำงานตรงตามความต้องการ โดยสรุปแล้วอุตสาหกรรมการผลิตอุปกรณ์ดิจิทัลอิเล็กทรอนิกส์เป็นการนำวิธีการทางลอจิกมาใช้อย่างมีประสิทธิภาพ
การออกแบบวงจรดิจิทัลลอจิก แก้
ระบบดิจิทัลทุกระบบจะมีองค์ประกอบสำคัญสองอย่าง คือ หน่วยความจำทำหน้าที่เก็บข้อมูล และ ส่วนวงจรรวมทำหน้าที่แปลงข้อมูลที่หน่วยความจำเก็บไว้ เนื่องจากหน่วยความจำเป็นวงจรลอจิกมาตรฐานนำไปใช้คำนวณไม่ได้ ดังนั้นการออกแบบวงจรดิจิทัลจะลดลงเหลือเพียงออกแบบวงจรรวมเกตและการเชื่อมต่อเกต
โดยทั่วไปการสังเคราะห์วงจรลอจิกจากภาษาระดับสูงสามารถทำได้ด้วยมือ แต่ในการใช้งานส่วนใหญ่จะใช้คอมพิวเตอร์ในการสังเคราะห์ โดยในบทความนี้จะพูดถึงวิธีการออกแบบสำหรับวงจรลอจิกรวมแบบสั้นๆ
จุดเริ่มต้นในการออกแบบวงจรดิจิทัลลอจิก คือ วิเคราะห์ระบบทั้งวงจรที่จะสร้างเพื่อดูว่าต้องมีฟังก์ชันการทำงานใดบ้าง บางส่วนสามารถระบุได้ในรูปแบบขั้นตอนวิธีหรือโดยสมการลอจิก แต่อาจจะเขียนในรูปแบบของตารางค่าความจริงได้ เช่น ตารางสำหรับโปรแกรมควบคุม 7-Segment(ตัวแสดงผล 7 ส่วน) ที่ทำการแปลงรหัสไบนารีสำหรับค่าของเลขฐานสิบหลักเดียวไปเป็นสัญญาณที่ทำให้ส่วนของ 7-Segment สว่างตามลำดับ
| Digit Code Segments | ||||||||
|---|---|---|---|---|---|---|---|---|
| เลข | ฐานสอง | A | B | C | D | E | F | G |
 |
000000 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
 |
000001 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
 |
000010 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
 |
000011 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
 |
000100 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
 |
000101 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
 |
000110 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
 |
000111 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
 |
001000 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
 |
001001 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
การดำเนินการเริ่มต้นที่ขั้นตอนการลดขนาดประพจน์ลอจิก เพื่อลดความซับซ้อนของตารางค่าความจริงโดยการรวมประพจน์แยกไปเป็นประพจน์ผสมที่มีจำนวนพจน์ลดลง เช่น ขั้นต่อไป นำประพจน์ที่ลดขนาดลงได้ไปเขียนลงในแมป ซึ่งเป็นแมปพื้นฐานที่ใช้สำหรับหาค่าลอจิกที่เหมาะสมที่สุด
วิธีการลดรูปฟังก์ชันบูลีนด้วยมือ แก้
วิธีการลดรูปฟังก์ชันบูลีนด้วยมือวิธีหนึ่งที่ทำได้ง่ายคือ การใช้แผนผังคาร์โนห์ (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)
ขั้นตอนการทำงาน แก้
- EXPAND (ขยาย implicant ให้มีขนาดใหญ่ที่สุด โดยคุณภาพของผลลัพธ์ขึ้นกับลำดับของการขยาย implicant)
- ถ้า implicant ใดอยู่ภายใต้การขยายตัวของ implicant อื่นให้เอาออกจากการพิจารณา
- IRREDUNDANT COVER (หา prime implicant จากขั้นตอนที่ 1. เหมือนกับวิธีควิน-แมคคลัสกี้)
- REDUCE (ทำการลด prime implicant ให้มีขนาดเล็กที่สุด โดยยังคงครอบคลุม ON-set[กลุ่มที่ค่าความจริงเป็น 1 อยู่ติดกัน])
- Loop ไปเริ่มขั้นตอนที่ 1. ใหม่ จนกว่าการทำงานครั้งใหม่นี้จะให้คำตอบที่ดีกว่าเก่า
รหัสเทียม แก้
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