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

การออกแบบวงจรดิจิทัลลอจิก

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

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

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

การดำเนินการเริ่มต้นที่ขั้นตอนการลดขนาดประพจน์ลอจิก เพื่อลดความซับซ้อนของตารางค่าความจริงโดยการรวมประพจน์แยกไปเป็นประพจน์ผสมที่มีจำนวนพจน์ลดลง เช่น ( x ∨ y ) ∧ ( x ∨ z ) = x ∨ ( y ∧ z ) {\displaystyle (x\lor y)\land (x\lor z)=x\lor (y\land z)} ขั้นต่อไป นำประพจน์ที่ลดขนาดลงได้ไปเขียนลงในแมป ซึ่งเป็นแมปพื้นฐานที่ใช้สำหรับหาค่าลอจิกที่เหมาะสมที่สุด

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

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

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

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