ตัวแก้แผนผังคาร์นอฟ (K-Map)

การลดรูปฟังก์ชันบูลีนด้วยแผนผังคาร์นอฟ

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

Solver รองรับฟังก์ชันแบบ 2, 3, 4 และ 5 ตัวแปร คุณสามารถเริ่มจาก K-Map ตารางความจริง นิพจน์บูลีน minterm หรือ maxterm ได้โดยตรง

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

ค่า 0, 1 และ X หมายถึงอะไร?

แต่ละช่องสามารถมีค่า:

• 1 เมื่อฟังก์ชันเป็นจริง;
• 0 เมื่อฟังก์ชันเป็นเท็จ;
• X เมื่อเอาต์พุตของชุดอินพุตนั้นไม่สำคัญ.

X คือเงื่อนไข don't-care สามารถนำมาใช้ได้หากช่วยสร้างกลุ่มที่ใหญ่ขึ้นและทำให้นิพจน์สั้นลง แต่ไม่จำเป็นต้องใช้ทุกครั้ง

จากตารางความจริงไปยัง K-Map

ตารางความจริง แสดงชุดอินพุตทั้งหมดและค่าเอาต์พุตของแต่ละชุด

K-Map ใช้ข้อมูลเดียวกัน แต่จัดเรียงด้วย Gray code ทำให้ช่องที่อยู่ติดกันต่างกันเพียงหนึ่งตัวแปร

ตัวอย่าง:

A'B'

A'B

มีเพียง B ที่เปลี่ยนค่า

ดังนั้นสองเทอมนี้สามารถลดรูปเป็น:

A'

ตัวแปรที่เปลี่ยนภายในกลุ่มจะหายไปจากเทอมที่ลดรูปแล้ว

หลักการเดียวกันนี้ใช้กับกลุ่มขนาดใหญ่ขึ้นด้วย

Minterm, Maxterm และนิพจน์บูลีน

ถ้าโจทย์ให้ดัชนี minterm มาแล้ว คุณไม่จำเป็นต้องกรอกทุกช่องด้วยตนเอง

เช่น:

Σm(1,3,5,7)

ระบุ minterm ที่ฟังก์ชันมีค่า 1

ส่วน:

ΠM(0,2,4,6)

ระบุ maxterm ที่ฟังก์ชันมีค่า 0

นอกจากนี้ยังสามารถป้อนนิพจน์บูลีนโดยตรงได้

Solver จะประเมินนิพจน์และสร้างตารางความจริง K-Map minterm และ maxterm ที่สอดคล้องกัน

จึงสามารถตรวจสอบรูปแบบต่าง ๆ ของฟังก์ชันเดียวกันได้โดยไม่ต้องสร้างใหม่ทีละแบบ

การจัดกลุ่มใน K-Map

กลุ่มที่ถูกต้องต้องมีจำนวนช่องเป็นกำลังของสอง:

1, 2, 4, 8, 16

โดยทั่วไป กลุ่มที่ใหญ่ขึ้นจะช่วยลดจำนวน literal ในเทอมสุดท้าย

ขอบของ K-Map ยังถือว่าอยู่ติดกันทางตรรกะ

ช่องด้านซ้ายสามารถจัดกลุ่มกับช่องด้านขวา และขอบบนสามารถเชื่อมกับขอบล่างได้

ดังนั้นช่องทั้งสี่มุมก็สามารถรวมเป็นกลุ่มเดียวได้

กลุ่มสามารถซ้อนทับกันได้ หากช่วยให้ได้ผลลัพธ์ที่เรียบง่ายกว่า

Solver จะแสดงกลุ่มเหล่านี้บน K-Map โดยตรง เพื่อให้ตรวจสอบความสัมพันธ์กับนิพจน์ผลลัพธ์ได้ง่าย

SOP และ POS

ในรูปแบบ SOP (Sum of Products) การลดรูปจะอ้างอิงช่องที่มีค่า 1 เป็นหลัก

ตัวอย่าง:

A'B + BC

ส่วน POS (Product of Sums) จะเริ่มจากช่องที่มีค่า 0

ตัวอย่าง:

(A + B')(B + C)

SOP ไม่ได้สั้นกว่า POS เสมอไป

ฟังก์ชันบางแบบอาจมี SOP ที่ง่ายกว่า ขณะที่บางแบบมี POS ที่ใช้เทอมน้อยกว่า

หากโจทย์ไม่ได้กำหนดรูปแบบ สามารถเปรียบเทียบทั้งสองผลลัพธ์ได้

Quine-McCluskey และ Petrick's Method

สำหรับ K-Map ขนาดเล็ก การเลือกกลุ่มที่เหมาะสมมักทำได้ด้วยสายตา

แต่เมื่อมี 4 หรือ 5 ตัวแปร อาจมีหลายวิธีในการครอบคลุมเซลล์ที่ถูกต้อง

Solver ใช้ Quine-McCluskey เพื่อค้นหา implicant อย่างเป็นระบบ

Implicant ที่ไม่สามารถขยายให้ใหญ่ขึ้นได้เรียกว่า prime implicant

บาง prime implicant มีความสำคัญ เพราะครอบคลุม minterm ที่ไม่มี prime implicant อื่นครอบคลุมได้

หากยังมีหลายทางเลือกหลังจากขั้นตอนนี้ Petrick's Method จะใช้เพื่อวิเคราะห์ชุดที่เหลือ

วิธีนี้เหมาะกับกรณีที่ดู K-Map เพียงอย่างเดียวแล้วตัดสินใจได้ยากว่าควรเลือกกลุ่มใด

K-Map แบบ 2 ถึง 5 ตัวแปร

K-Map แบบ 2 ตัวแปร มี 4 ช่อง

แบบ 3 ตัวแปร มี 8 ช่อง และทำให้เห็นแนวคิดเรื่องการเชื่อมขอบได้ชัดขึ้น

แผนผังคาร์นอฟแบบ 4 ตัวแปร มี 16 ช่อง และพบได้บ่อยในวิชาดิจิทัลลอจิก

แบบ 5 ตัวแปร มีชุดอินพุตทั้งหมด 32 แบบ การแก้ด้วยมืออาจซับซ้อนขึ้นเมื่อมี don't-care หรือ prime implicant หลายชุด

Solver จะรักษา K-Map ตารางความจริง นิพจน์ minterm และ maxterm ให้สอดคล้องกันในทุกขนาดที่รองรับ

วงจรลอจิกและการส่งออก PDF

หลังจากลดรูปแล้ว ผลลัพธ์สามารถแสดงเป็น วงจรลอจิก ได้

จึงสามารถเห็นความสัมพันธ์ระหว่างนิพจน์ SOP หรือ POS กับเกต AND, OR และ NOT ได้ง่ายขึ้น

ยังสามารถตรวจสอบจำนวนเทอม literal และจำนวนเกตได้อีกด้วย

หากต้องการเก็บคำตอบไว้ สามารถส่งออกเป็น PDF พร้อม K-Map กลุ่ม ขั้นตอน และแผนผังวงจรได้