ดูต้นฉบับสำหรับ ตัวย่อตรรกะพจน์เอสเปรสโซ่

{{ลิงก์ไปภาษาอื่น}}
'''ตัวย่อตรรกะพจน์เอสเปรสโซ่''' ({{langx|en|Espresso heuristic logic minimizer}}) คือโปรแกรมที่มีขั้นตอนวิธีเอาลดรูปสมการบูลีนให้อยู่ในรูปที่เล็กที่สุด เพื่อลดความซับซ้อนของวงจรอิเล็คทรอนิกส์ เอสเปรสโซ่ถูกพัฒนาขึ้นที่ไอบืเอ็มโดยโรเบิร์ต เบรย์ตัน และเผยแพร่เมื่อปี พ.ศ. 2529 และได้ถูกพัฒนาต่อมาอีกหลายครั้ง

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

=== การออกแบบวงจรดิจิทัลลอจิก ===
ระบบดิจิทัลทุกระบบจะมีองค์ประกอบสำคัญสองอย่าง คือ หน่วยความจำทำหน้าที่เก็บข้อมูล และ ส่วนวงจรรวมทำหน้าที่แปลงข้อมูลที่หน่วยความจำเก็บไว้ เนื่องจากหน่วยความจำเป็นวงจรลอจิกมาตรฐานนำไปใช้คำนวณไม่ได้ ดังนั้นการออกแบบวงจรดิจิทัลจะลดลงเหลือเพียงออกแบบวงจรรวมเกตและการเชื่อมต่อเกต

โดยทั่วไปการสังเคราะห์วงจรลอจิกจากภาษาระดับสูงสามารถทำได้ด้วยมือ แต่ในการใช้งานส่วนใหญ่จะใช้คอมพิวเตอร์ในการสังเคราะห์ โดยในบทความนี้จะพูดถึงวิธีการออกแบบสำหรับวงจรลอจิกรวมแบบสั้นๆ

จุดเริ่มต้นในการออกแบบวงจรดิจิทัลลอจิก คือ วิเคราะห์ระบบทั้งวงจรที่จะสร้างเพื่อดูว่าต้องมีฟังก์ชันการทำงานใดบ้าง บางส่วนสามารถระบุได้ในรูปแบบขั้นตอนวิธีหรือโดยสมการลอจิก แต่อาจจะเขียนในรูปแบบของตารางค่าความจริงได้ เช่น ตารางสำหรับโปรแกรมควบคุม [[:en:7_segment|7-Segment]](ตัวแสดงผล 7 ส่วน) ที่ทำการแปลงรหัสไบนารีสำหรับค่าของเลขฐานสิบหลักเดียวไปเป็นสัญญาณที่ทำให้ส่วนของ 7-Segment สว่างตามลำดับ
[[ไฟล์:7 segment display labeled.svg|thumb|right|150px|<center>แสดงจุดต่างๆ ของ จอดิจิทัล 7 ส่วน</center>]]
{| class="infobox" style="background: white"
!Digit Code Segments
|-
!เลข
![[เลขฐานสอง|ฐานสอง]]
!A
!B
!C
!D
!E
!F
!G
|-
|[[ไฟล์:7-segment abcdef.svg]]||000000||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1||0
|-
|[[ไฟล์:7-segment bc.svg]]||000001||0||style="background: green"|1||style="background: green"|1||0||0||0||0
|-
|[[ไฟล์:7-segment abdeg.svg]]||000010||style="background: green"|1||style="background: green"|1||0||style="background: green"|1||style="background: green"|1||0||style="background: green"|1
|-
|[[ไฟล์:7-segment abcdg.svg]]||000011||style="background: green"|1||style="background: green"|1||style="background: green"|1||0||0||style="background: green"|1||style="background: green"|1
|-
|[[ไฟล์:7-segment bcfg.svg]]||000100||0||style="background: green"|1||style="background: green"|1||0||0||style="background: green"|1||style="background: green"|1
|-
|[[ไฟล์:7-segment acdfg.svg]]||000101||style="background: green"|1||0||style="background: green"|1||style="background: green"|1||0||style="background: green"|1||style="background: green"|1
|-
|[[ไฟล์:7-segment acdefg.svg]]||000110||style="background: green"|1||0||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1
|-
|[[ไฟล์:7-segment abc.svg]]||000111||style="background: green"|1||style="background: green"|1||style="background: green"|1||0||0||0||0
|-
|[[ไฟล์:7-segment abcdefg.svg]]||001000||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1
|-
|[[ไฟล์:7-segment abcdfg.svg]]||001001||style="background: green"|1||style="background: green"|1||style="background: green"|1||style="background: green"|1||0||style="background: green"|1||style="background: green"|1
|}<center>{{เทาเล็ก|ตารางแสดงการเปิด-ปิด LED ตาม[[#ไฟล์:7 segment display labeled.svg|ภาพด้านบน]]}}</center><br>
การดำเนินการเริ่มต้นที่ขั้นตอนการลดขนาดประพจน์ลอจิก เพื่อลดความซับซ้อนของตารางค่าความจริงโดยการรวมประพจน์แยกไปเป็นประพจน์ผสมที่มีจำนวนพจน์ลดลง เช่น <math>(x \lor y) \land (x \lor z) = x \lor (y \land z)</math> ขั้นต่อไป นำประพจน์ที่ลดขนาดลงได้ไปเขียนลงในแมป ซึ่งเป็นแมปพื้นฐานที่ใช้สำหรับหาค่าลอจิกที่เหมาะสมที่สุด

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

วิธีการลดรูปฟังก์ชันบูลีนด้วยมือวิธีหนึ่งที่ทำได้ง่ายคือ การใช้แผนผังคาร์โนห์ ([[:en:Karnaugh_map|Karnaugh map]]) ซึ่งวิธีนี้จะยากและมีแนวโน้มที่จะผิดพลาดได้ และไม่เหมาะกับสมการบูลีนที่มีตัวแปรมากกว่า 6 ตัว และที่ใช้ได้จริงๆ นั้นใช้กับตัวแปรเพียง 4 ตัวเท่านั้น ในขณะที่สมการบูลีนตั้งต้นหนึ่งสมการ เมื่อผ่านการทำแผนผังคาร์โนห์สามารถให้คำตอบได้หลายแบบ แม้กระทั่งสมการที่ยากต่อการนำไปใช้ นอกจากนี้การใช้แผนผังคาร์โนห์ ยังไม่เหมาะที่จะนำไปใช้ในรูปแบบโปรแกรมคอมพิวเตอร์ แต่เนื่องจากฟังก์ชันลอจิกที่ใช้ในปัจจุบันมีตัวแปรจำนวนมาก การลดรูปด้วยมือทำได้ลำบากมากและยังมีความเสี่ยงสูงที่จะผิดพลาด จึงต้องใช้คอมพิวเตอร์ในการลดรูป

วิธีการแรกที่นิยมใช้กันมาก คือ วิธีทำเป็นตารางที่พัฒนาโดย [[ควีน-แมคคลัสกี้]] เริ่มต้นโดยการเขียน [[minterm]] สำหรับฟังก์ชันที่มีการใช้งาน ในรูปของตารางค่าความจริงเรียงจากน้อยไปมาก จับคู่ minterm ที่มีจำนวนบิตต่างกันเพียง 1 บิต ซึ่งจะสามารถลดตัวแปรลงไปได้หนึ่งตัว (ลด [[:en:Implicant#Prime_implicant|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. ใหม่ จนกว่าการทำงานครั้งใหม่นี้จะให้คำตอบที่ดีกว่าเก่า

=== รหัสเทียม ===
<pre>
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 กลับ
}
</pre>

=== ตัวอย่างการใช้งาน ===
<pre>
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
</pre>

=== ซอฟต์แวร์ที่นำวิธีการเอสเปรสโซ่ไปใช้งาน ===

==== Minilog ====
คือ โปรแกรมลดรูปตรรกะพจน์ที่เอาวิธีการเอสเปรสโซ่ไปใช้งาน มันสามารถสร้างบล็อกที่เป็นเกตสองชั้นที่มีอินพุตและเอาต์พุตมากถึง 40 ตัว หรือสร้าง synchronous state machine ได้ถึง 256 สถานะ สามารถดาวน์โหลดโปรแกรมมินิลอคได้ที่ [http://cid-b7034765ca89b294.skydrive.live.com/browse.aspx/Quick-Install Publicad] (โปรแกรมมินิลอคได้รวมอยู่ใน Publicad toolkit)

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

=== Espresso sources ===
ต้นฉบับของโปรแกรมเอสเปรสโซ่สามารถใช้งานได้ที่เว็บไซต์ของมหาวิทยาลัยเบิร์กเลย์ ที่ [http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/index.htm Pubs/Downloads/Espresso]

== อ้างอิง, ดูเพิ่มเติม ==
# http://webstaff.kmutt.ac.th/~iauaroen/ENE232/Minimization.pdf{{ลิงก์เสีย|date=มกราคม 2022 |bot=InternetArchiveBot |fix-attempted=yes }}
# http://www.kmitl.ac.th/~ksjirasa/Lecture/AdvDigital/lec01_add.pdf{{ลิงก์เสีย|date=กันยายน 2021 |bot=InternetArchiveBot |fix-attempted=yes }}
# http://www.engr.sjsu.edu/caohuut/EE270/Documents/Espresso.pdf{{ลิงก์เสีย|date=กันยายน 2021 |bot=InternetArchiveBot |fix-attempted=yes }}
# http://users.eecs.northwestern.edu/~haizhou/303/Lec03.ppt