ตัวย่อตรรกะพจน์เอสเปรสโซ่
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ตัวย่อตรรกะพจน์เอสเปรสโซ่ (อังกฤษ: 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