แผนผังคาร์โนห์ (Karnaugh Map) — คู่มือย่อรูป K-Map

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

เงื่อนไขสำคัญคือ K-map เหมาะที่สุดกับฟังก์ชันขนาดเล็ก โดยทั่วไปคือมีตัวแปรสอง สาม หรือสี่ตัว เมื่อจำนวนตัวแปรมากขึ้น แผนผังจะอ่านยากขึ้น และมักมีวิธีอื่นที่เหมาะกว่า

แผนผังคาร์โนห์แสดงอะไร

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

ความต่างเพียงตัวแปรเดียวนี่เองคือประเด็นสำคัญ ถ้าช่องที่ติดกันสองช่องมีค่าเป็น $1$ ทั้งคู่ ตัวแปรที่เปลี่ยนค่านั้นสามารถตัดออกจากพจน์ที่ย่อรูปแล้วได้

การจัดกลุ่มช่วยตัดตัวแปรออกได้อย่างไร

กฎเชิงภาพนี้มาจากเอกลักษณ์ของพีชคณิตบูลีน เช่น

$$XY + X\overline{Y} = X$$

สองพจน์นี้ต่างกันแค่ที่ $Y$ ดังนั้น $Y$ จึงหายไป และเหลือส่วนที่เหมือนกันคือ $X$ K-map ช่วยให้คุณมองเห็นรูปแบบการตัดทอนนี้ได้โดยตรงบนกริด

ตัวอย่างแผนผังคาร์โนห์

สมมติว่า

$$F(A,B,C) = \sum m(1,3,4,5,7)$$

นั่นหมายความว่า $F=1$ สำหรับมินเทอม $1$, $3$, $4$, $5$ และ $7$

สำหรับ K-map แบบ $3$ ตัวแปร ให้ใช้ $A$ เป็นแถว และใช้ $BC$ เป็นคอลัมน์ตามลำดับ Gray code คือ $00$, $01$, $11$, $10$:

$$\begin{array}{c|cccc} A \backslash BC & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array}$$

เริ่มจากกลุ่มที่ถูกต้องและมีขนาดใหญ่ที่สุดก่อน ค่า $1$ สี่ตัวในสองคอลัมน์ตรงกลางรวมกันเป็นหนึ่งกลุ่ม ในสี่ช่องนี้ $C=1$ คงที่ ส่วน $A$ และ $B$ เปลี่ยนค่า ดังนั้นกลุ่มนี้จึงย่อรูปได้เป็น

$$C$$

ยังมีค่า $1$ อีกหนึ่งตัวที่ยังไม่ถูกครอบคลุม คือมินเทอม $4$ ซึ่งคือ $(A,B,C)=(1,0,0)$ ให้จับคู่กับมินเทอมข้างเคียงคือ $5$ ซึ่งคือ $(1,0,1)$

ในคู่นี้ $A=1$ และ $B=0$ คงที่ ส่วน $C$ เปลี่ยนค่า ดังนั้นคู่นี้จึงย่อรูปได้เป็น

$$A\overline{B}$$

ดังนั้นนิพจน์ที่ย่อรูปแล้วคือ

$$F(A,B,C) = C + A\overline{B}$$

นิพจน์ที่สั้นกว่านี้สมมูลกับรายการมินเทอมเดิม

กฎของการจัดกลุ่มที่ถูกต้องใน K-Map

ใช้กลุ่มที่มีขนาดเป็นกำลังของสอง เช่น $1$, $2$, $4$, $8$ เป็นต้น

ใช้กลุ่มที่ถูกต้องและมีขนาดใหญ่ที่สุดเท่าที่ทำได้ กลุ่มที่ใหญ่กว่ามักช่วยตัดตัวแปรออกได้มากกว่า

อย่าลืมว่าแผนผังมีการวนรอบ ขอบซ้ายกับขอบขวาถือว่าติดกัน และขอบบนกับขอบล่างก็ติดกัน

ช่องที่อยู่แนวทแยงกันไม่ถือว่าติดกัน

การซ้อนทับกันทำได้ ถ้ามันช่วยให้เกิดการจัดกลุ่มที่ใหญ่ขึ้นหรือง่ายขึ้น

ข้อผิดพลาดที่พบบ่อยในแผนผังคาร์โนห์

ใช้ลำดับไบนารีปกติ

ถ้าคุณติดป้ายแถวหรือคอลัมน์เป็น $00$, $01$, $10$, $11$ ความเป็นช่องข้างเคียงจะผิด K-map ต้องใช้ลำดับ Gray code เพื่อให้ช่องที่อยู่ติดกันต่างกันเพียง 1 บิต

จัดกลุ่มเป็นสามช่อง

กลุ่มที่มีสามช่องไม่ถูกต้องเสมอ ขนาดของกลุ่มต้องเป็นกำลังของสอง

ลืมความเป็นช่องข้างเคียงแบบวนรอบ

การย่อรูปที่ดีที่สุดบางครั้งใช้ช่องที่อยู่คนละขอบของแผนผัง ถ้าคุณลืมกฎการวนรอบ คำตอบมักจะยาวเกินความจำเป็น

พยายามบังคับให้ค่า $1$ ทุกตัวอยู่ในเพียงหนึ่งกลุ่มเท่านั้น

นี่ไม่ใช่กฎ การใช้ช่องเดิมซ้ำอาจเป็นวิธีที่ดีที่สุดในการสร้างกลุ่มที่ใหญ่ขึ้น และทำให้นิพจน์สุดท้ายสั้นลง

ใช้แผนผังคาร์โนห์เมื่อไร

K-map พบได้บ่อยในวิชาลอจิกดิจิทัลและวิศวกรรมคอมพิวเตอร์เบื้องต้น เพราะมันเปลี่ยนการย่อรูปบูลีนให้เป็นกระบวนการที่มองเห็นได้ชัด โดยเฉพาะเมื่อคุณต้องการนิพจน์แบบ sum-of-products ที่ง่ายขึ้นก่อนจะวาดหรือสร้างวงจรลอจิก

มันยังช่วยสร้างความเข้าใจเชิงสัญชาตญาณได้ดี แม้ว่าซอฟต์แวร์จะจัดการงานออกแบบขนาดใหญ่ได้ การเรียน K-map ก็ช่วยให้เห็นได้ง่ายขึ้นว่าทำไมพจน์บูลีนบางพจน์จึงรวมกันได้ และบางพจน์จึงรวมกันไม่ได้

ลองทำโจทย์ที่คล้ายกัน

ลองย่อรูป $F(A,B,C)=\sum m(0,2,4,6,7)$ ด้วยตัวเอง วาดแผนผัง จัดกลุ่มที่ถูกต้องและใหญ่ที่สุดก่อน แล้วเก็บไว้เฉพาะตัวแปรที่คงที่ในแต่ละกลุ่ม

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