การปรับแต่งตรรกะคือกระบวนการค้นหาตัวแทนที่เทียบเท่าของวงจรตรรกะ ที่กำหนด ภายใต้ข้อจำกัดที่ระบุอย่างน้อยหนึ่งข้อ กระบวนการนี้เป็นส่วนหนึ่งของการสังเคราะห์ตรรกะที่ใช้ในอิเล็กทรอนิกส์ดิจิทัลและ การ ออกแบบ วงจรรวม

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

ในแง่ของพีชคณิตบูลีนการหาค่าที่เหมาะสมที่สุดของนิพจน์บูลีน ที่ซับซ้อน คือกระบวนการค้นหานิพจน์ที่เรียบง่ายกว่า ซึ่งเมื่อประเมินแล้วจะให้ผลลัพธ์เดียวกันกับนิพจน์เดิม

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

ด้วยการเกิดขึ้นของการสังเคราะห์ตรรกะหนึ่งในความท้าทายที่ใหญ่ที่สุดที่ อุตสาหกรรม การออกแบบอัตโนมัติทางอิเล็กทรอนิกส์ (EDA) เผชิญคือการค้นหาการแสดงวงจรที่ง่ายที่สุดของคำอธิบายการออกแบบที่กำหนด^{[ nb 1 ]} ในขณะที่การเพิ่มประสิทธิภาพตรรกะสองระดับมีมานานแล้วในรูปแบบของอัลกอริทึม Quine–McCluskeyตามมาด้วยตัวลดตรรกะแบบฮิวริสติก Espressoความหนาแน่นของชิปที่พัฒนาอย่างรวดเร็วและการนำภาษาคำอธิบายฮาร์ดแวร์ มาใช้กันอย่างแพร่หลาย สำหรับการอธิบายวงจร ทำให้โดเมนการเพิ่มประสิทธิภาพตรรกะเป็นทางการอย่างที่เป็นอยู่ในปัจจุบัน รวมถึงLogic Friday (อินเทอร์เฟซกราฟิก), Minilog และ ESPRESSO-IISOJS (ตรรกะหลายค่า) ^{[ 3 ]}

วิธีการลดรูปวงจรตรรกะสามารถนำไปใช้กับการลดรูปนิพจน์บูลีนได้ เช่นกัน

ในปัจจุบัน การปรับปรุงประสิทธิภาพตรรกะแบ่งออกเป็นหลายประเภท:

โดยพิจารณาจากการแสดงวงจร

การเพิ่มประสิทธิภาพตรรกะสองระดับ

การเพิ่มประสิทธิภาพตรรกะหลายระดับ

โดยพิจารณาจากลักษณะวงจร

การเพิ่มประสิทธิภาพตรรกะแบบลำดับ

การเพิ่มประสิทธิภาพตรรกะเชิงผสม

ขึ้นอยู่กับประเภทของการดำเนินการ

วิธีการเพิ่มประสิทธิภาพเชิงกราฟิก

วิธีการเพิ่มประสิทธิภาพแบบตาราง

วิธีการเพิ่มประสิทธิภาพเชิงพีชคณิต

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

• แผนภาพออยเลอร์ (หรือวงกลมออยเลอร์ ) (1768) โดยเลออนฮาร์ด พี. ออยเลอร์ (1707–1783)
• แผนภาพเวนน์ (1880) โดยจอห์น เวนน์ (1834–1923)
• แผนที่คาร์นอห์ (ค.ศ. 1953) โดยมอริซ คาร์นอห์

วิธีการลดรูป (ทำให้ง่ายขึ้น) ของนิพจน์บูลีนแบบเดียวกันที่ระบุไว้ด้านล่างนี้ สามารถนำไปใช้กับการปรับปรุงวงจรให้เหมาะสมที่สุดได้เช่นกัน

สำหรับกรณีที่ฟังก์ชันบูลีนถูกกำหนดโดยวงจร (นั่นคือ เราต้องการหาวงจรเทียบเท่าที่มีขนาดเล็กที่สุดเท่าที่จะเป็นไปได้) ปัญหาการลดขนาดวงจรที่ไม่จำกัดขอบเขตนั้นถูกคาดการณ์ไว้เป็นเวลานานว่ามีความซับซ้อนเชิงเวลา-completeซึ่งเป็นผลลัพธ์ที่ได้รับการพิสูจน์ในที่สุดในปี 2008 ^{[ 4 ]}แต่มีฮิวริสติกที่มีประสิทธิภาพ เช่นแผนที่ Karnaughและอัลกอริทึม Quine–McCluskeyที่ช่วยอำนวยความสะดวกในกระบวนการนี้ ${\displaystyle \Sigma _{2}^{P}}$

วิธีการลดค่าฟังก์ชันบูลีน ได้แก่:

• อัลกอริทึมควิน-แมคคลัสกีย์
• วิธีการของเพทริค

ใน เอกสารทางวิชาการมักเรียกวิธีการสังเคราะห์ที่แม่นยำ ว่า "การสังเคราะห์ที่แม่นยำ " เนื่องจากความซับซ้อนในการคำนวณ การสังเคราะห์ที่แม่นยำจึงทำได้เฉพาะกับฟังก์ชันบูลีนขนาดเล็กเท่านั้น แนวทางล่าสุดจะแปลงปัญหาการเพิ่มประสิทธิภาพให้เป็นปัญหาความพึงพอใจของบูลีน^{[ 5 ] [ 6 ]}วิธีนี้ช่วยให้สามารถค้นหาการสังเคราะห์วงจรที่เหมาะสมที่สุดโดยใช้ตัวแก้ปัญหา SATได้

วิธีการ ฮิวริสติกใช้กฎที่กำหนดไว้แล้วเพื่อแก้ปัญหาชุดย่อยที่มีประโยชน์ในทางปฏิบัติจากชุดปัญหาที่เป็นไปได้ขนาดใหญ่กว่ามาก วิธีการฮิวริสติกอาจไม่ได้ให้คำตอบที่เหมาะสมที่สุดในทางทฤษฎี แต่หากมีประโยชน์ ก็จะช่วยให้ได้ผลลัพธ์การปรับให้เหมาะสมที่สุดตามที่ต้องการโดยใช้ความพยายามน้อยที่สุด ตัวอย่างของระบบคอมพิวเตอร์ที่ใช้วิธีการฮิวริสติกสำหรับการปรับตรรกะให้เหมาะสมที่สุดคือโปรแกรมลด ค่าตรรกะแบบฮิวริสติก Espresso

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

ถ้าเรามีฟังก์ชันสองฟังก์ชันคือF ₁และF ₂ :

${\displaystyle F_{1}=AB+AC+AD,\,}$

${\displaystyle F_{2}=A'B+A'C+A'E.\,}$

การแสดงผลแบบ 2 ระดับข้างต้นใช้เทอมผลคูณหกเทอมและทรานซิสเตอร์ 24 ตัวใน CMOS Rep.

การแสดงผลที่เทียบเท่ากันในเชิงฟังก์ชันในระบบหลายระดับอาจเป็นดังนี้:

P = B + C​

F ₁ = AP + AD .

F ₂ = A'P + A'E .

แม้ว่าจำนวนระดับในที่นี้จะมี 3 ระดับ แต่จำนวนพจน์ผลิตภัณฑ์และตัวอักษรโดยรวมจะลดลงเนื่องจากการใช้พจน์ B + C ร่วมกัน

ในทำนองเดียวกัน เราแยกแยะความแตกต่างระหว่างวงจรเชิงผสมและวงจรเชิงลำดับวงจรเชิงผสมสร้างเอาต์พุตโดยอาศัยอินพุตปัจจุบันเท่านั้น สามารถแสดงได้ด้วยความสัมพันธ์ แบบบูลีน ตัวอย่างเช่นตัวเข้ารหัสลำดับความสำคัญ ตัวถอดรหัสไบนารี ตัวมัลติเพล็กเซอร์และตัวดีมัลติเพล็กเซอร์

วงจรลำดับสร้างเอาต์พุตโดยอาศัยทั้งอินพุตปัจจุบันและอินพุตในอดีต โดยอาศัยสัญญาณนาฬิกาเพื่อแยกแยะอินพุตก่อนหน้าออกจากอินพุตปัจจุบัน วงจรเหล่านี้สามารถแสดงได้ด้วยเครื่องสถานะจำกัด ตัวอย่างเช่นฟลิปฟลอปและตัวนับ

แม้ว่าจะมีหลายวิธีในการลดขนาดวงจร แต่ตัวอย่างนี้เป็นการลดขนาด (หรือทำให้ง่ายขึ้น) ฟังก์ชันบูลีน ฟังก์ชันบูลีนที่ดำเนินการโดยวงจรมีความสัมพันธ์โดยตรงกับนิพจน์พีชคณิตที่ใช้ในการสร้างฟังก์ชัน^{[ 7 ]} พิจารณาวงจรที่ใช้ในการแสดงเห็นได้ชัดว่ามีการใช้การปฏิเสธสองครั้ง การเชื่อมสองครั้ง และการแยกหนึ่งครั้งในข้อความนี้ ซึ่งหมายความว่าในการสร้างวงจรจะต้องใช้อินเวอร์เตอร์ สองตัว เกต ANDสองตัวและเกต OR หนึ่ง ตัว ${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)}$

วงจรสามารถลดรูป (ย่อส่วน) ได้โดยการใช้กฎของพีชคณิตบูลีนหรือใช้สัญชาตญาณ เนื่องจากตัวอย่างระบุว่าเป็นจริงเมื่อเป็นเท็จ และในทางกลับกัน จึงสรุปได้ว่า หมายความว่าในแง่ของเกตตรรกะความไม่เท่ากันหมายถึงเกต XOR (เอกซ์คลูซีฟออร์) ดังนั้น. ดังนั้นวงจรทั้งสองที่แสดงด้านล่างจึงเทียบเท่ากัน ซึ่งสามารถตรวจสอบได้โดยใช้ตารางความจริง : ${\displaystyle A}$${\displaystyle B}$${\displaystyle A\neq B}$${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}$

• แผนภาพการตัดสินใจแบบไบนารี (BDD)
• ไม่สนใจสภาพ
• ผู้เกี่ยวข้องหลัก
• ความซับซ้อนของวงจร — การประเมินความซับซ้อนของวงจร
• การประกอบฟังก์ชัน
• การแยกส่วนฟังก์ชัน
• ประตูใช้งานไม่เต็มประสิทธิภาพ
• ความซ้ำซ้อนทางตรรกะ
• แผนภูมิย่อขนาดฮาร์วาร์ด(Wikiversity) (Wikibooks)

• ลินด์, แลร์รี เฟรเดอริก; เนลสัน, จอห์น คริสโตเฟอร์ คันลิฟฟ์ (1977). การวิเคราะห์และการออกแบบระบบดิจิทัลแบบลำดับ . สำนักพิมพ์แมคมิลแลน . ISBN 0-33319266-4.(146 หน้า)
• เดอ มิเชลี, จิโอวานนี (1994). การสังเคราะห์และการปรับปรุงประสิทธิภาพของวงจรดิจิทัล . แมคกรอว์-ฮิลล์ . ISBN 0-07-016333-2.(หมายเหตุ: บทที่ 7-9 ครอบคลุมการเพิ่มประสิทธิภาพวงจรแบบสองระดับเชิงคอมบินาทอริก การเพิ่มประสิทธิภาพวงจรแบบหลายระดับเชิงคอมบินาทอริก และการเพิ่มประสิทธิภาพวงจรแบบลำดับ ตามลำดับ)
• Hachtel, Gary D.; Somenzi, Fabio (2006) [1996]. อัลกอริทึมการ สังเคราะห์และตรวจสอบตรรกะ Springer Science & Business Media ISBN 978-0-387-31005-3.
• โคฮาวี, ซวี; จา, นิราช เค. (2009). "4–6" ทฤษฎีการสลับและจำกัดออโตมาตะ (ฉบับที่ 3) สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ . ไอเอสบีเอ็น 978-0-521-85748-2.
• Rutenbar, Rob A. การลดค่าต่ำสุดหลายระดับ ตอนที่ 1: แบบจำลองและวิธีการ (PDF) (สไลด์บรรยาย). มหาวิทยาลัยคาร์เนกีเมลลอน (CMU). การบรรยายครั้งที่ 7. เก็บถาวร(PDF)จากต้นฉบับเมื่อ 2018-01-15 . เรียกดูเมื่อ2018-01-15 ;Rutenbar, Rob A. การลดขนาดหลายระดับ ตอนที่ 2: การแยก Cube/Cokernel (PDF) (สไลด์บรรยาย). มหาวิทยาลัยคาร์เนกีเมลลอน (CMU). การบรรยายครั้งที่ 8. เก็บถาวร(PDF)จากต้นฉบับเมื่อ 2018-01-15 . เรียกดูเมื่อ2018-01-15 .