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

ตัวแก้แผนผังคาร์นอฟ (K-Map Solver) ช่วยลดรูปฟังก์ชันตรรกะบูลีนตั้งแต่ 2 ถึง 5 ตัวแปร และแสดงภาพการลดรูปเป็นแผนผัง K-map แบบคลาสสิกพร้อมการจัดกลุ่มรหัสสี ป้อน Minterms, Maxterms หรือใช้ตารางความจริงแบบโต้ตอบ — ตัวแก้ปัญหาจะใช้อัลกอริทึม Quine-McCluskey ในการประมวลผล ค้นหา Prime Implicant ทุกตัว ระบุตัวที่จำเป็น (Essential) และสร้างนิพจน์ Sum-of-Products (SOP) หรือ Product-of-Sums (POS) ที่สั้นที่สุดพร้อมคำอธิบายทีละขั้นตอน คลิกที่ชิป Prime Implicant เพื่อดูการเน้นกลุ่มเซลล์และวิธีที่การจัดกลุ่มช่วยลดรูปวงจร

แผนผังคาร์นอฟคืออะไร?

แผนผังคาร์นอฟ (คิดค้นโดย Maurice Karnaugh ในปี 1953) คือการแสดงภาพตารางความจริงที่จัดวางเพื่อให้เซลล์ที่ต่างกันเพียงตัวแปรเดียวอยู่ติดกันทางกายภาพ เคล็ดลับสำคัญคือ การเรียงลำดับแบบ Gray-code ของแถวและคอลัมน์: เช่น 00, 01, 11, 10 ซึ่งจะต่างกันทีละ 1 บิตเสมอ ความต่อเนื่องนี้ช่วยให้คุณมองเห็นกลุ่มของเลข 1 (หรือ 0) ที่สามารถรวมเป็นเทอมเดียวที่ง่ายขึ้นได้

สำหรับตัวแปรอินพุต n ตัว แผนผัง K-map จะมี 2^n เซลล์ โดยแผนผัง 4 ตัวแปรจะเป็นตาราง 4×4 ขนาด 16 เซลล์ ส่วนแผนผัง 5 ตัวแปรจะวาดเป็นตาราง 4×4 สองอันวางติดกัน

SOP vs POS: ควรเลือกรูปแบบไหน

Sum of Products (SOP)

SOP จะจัดกลุ่ม เซลล์เลข 1 แต่ละกลุ่มจะกลายเป็นผลคูณ (AND) ของตัวแปร และทุกกลุ่มจะถูกนำมา OR กัน ตัวอย่าง: AB'C + BD รูปแบบ SOP มักเป็นค่าเริ่มต้นเพราะสอดคล้องโดยตรงกับเครือข่ายเกตแบบ AND–OR

Product of Sums (POS)

POS จะจัดกลุ่ม เซลล์เลข 0 แต่ละกลุ่มจะกลายเป็นผลรวม (OR) ของตัวแปรที่กลับค่า และทุกผลรวมจะถูกนำมา AND กัน ตัวอย่าง: (A + B')(C + D') รูปแบบ POS มักจะสั้นกว่าเมื่อฟังก์ชันมีเลข 1 มากกว่าเลข 0

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

กฎการจัดกลุ่มสำหรับแผนผังคาร์นอฟ

• กลุ่มต้องเป็นกำลังของสองเท่านั้น: กลุ่มต้องมีจำนวน 1, 2, 4, 8 หรือ 16 เซลล์ ไม่อนุญาตให้จัดกลุ่มขนาด 3 หรือ 5
• รูปทรงสี่เหลี่ยม: เซลล์ในกลุ่มต้องเป็นรูปสี่เหลี่ยม (แนวนอน แนวตั้ง หรือล้อมรอบขอบแผนผัง)
• การเชื่อมต่อแบบวนรอบ: แถวบนสุดถือว่าติดกับแถวล่างสุด และคอลัมน์ซ้ายสุดติดกับคอลัมน์ขวาสุด นี่คือเหตุผลที่การเรียงลำดับแบบ Gray-code มีความสำคัญ
• เลือกกลุ่มที่ใหญ่ที่สุดก่อน: กลุ่มที่ใหญ่กว่าจะกำจัดตัวแปรได้มากกว่า ทำให้เทอมสั้นลง กลุ่ม 8 เซลล์จะลดตัวแปรได้ 3 ตัว; กลุ่ม 4 เซลล์ลดได้ 2 ตัว; กลุ่ม 2 เซลล์ลดได้ 1 ตัว
• ทุกเลข 1 (หรือ 0) ต้องถูกครอบคลุม: ต้องมีอย่างน้อยหนึ่งกลุ่มที่ครอบคลุมแต่ละเซลล์เลข 1 (สำหรับ SOP) หรือเลข 0 (สำหรับ POS)
• การซ้อนทับกันสามารถทำได้: เลข 1 ตัวเดียวกันสามารถอยู่ในหลายกลุ่มได้หากช่วยให้สร้างกลุ่มที่ใหญ่ขึ้นได้
• Don't-cares มีความยืดหยุ่น: สามารถนำมารวมในกลุ่มได้หากช่วยให้ได้กลุ่มที่ใหญ่ขึ้น แต่ไม่จำเป็นต้องครอบคลุมทั้งหมด

Prime Implicants และ Essential Prime Implicants

Prime implicant คือกลุ่มที่ไม่สามารถขยายให้ใหญ่กว่านี้ได้อีกแล้ว เพราะหากขยายไปจะไปครอบคลุมเซลล์เลข 0 (สำหรับ SOP) ตัวแก้ปัญหาจะแสดง Prime implicant ทั้งหมดที่พบ จากนั้นจะเลือก Minimal cover หรือชุดของกลุ่มที่เล็กที่สุดที่ครอบคลุมทุก Minterm ที่ต้องการ

Essential prime implicant จะถูกทำเครื่องหมายว่า ESSENTIAL เมื่อมันเป็น Prime implicant เพียงตัวเดียว ที่ครอบคลุม Minterm บางตัว นิพจน์ที่ลดรูปที่สุดทุกแบบต้องรวมกลุ่มที่เป็น Essential เหล่านี้ไว้เสมอ

เงื่อนไข Don't-Care

Don't-care (แสดงเป็น X ใน K-map) คือชุดของอินพุตที่เอาต์พุตไม่มีความสำคัญ — อาจเป็นเพราะไม่มีทางเกิดขึ้นในวงจรจริงหรือค่าของมันไม่มีผลใดๆ อัลกอริทึมมีอิสระที่จะมอง X แต่ละตัวว่าเป็น 0 หรือ 1 ก็ได้ เพื่อให้ได้นิพจน์ที่ง่ายที่สุด ในทางปฏิบัติ Don't-cares มักช่วยลดจำนวนเกตลงได้ 30–60% ตัวอย่างที่พบบ่อยคือวงจรถอดรหัสเลขฐานสิบที่ใช้เพียง 10 จาก 16 รูปแบบของอินพุต 4 บิต ทำให้รูปแบบที่ 10–15 กลายเป็น Don't-cares

อัลกอริทึม Quine-McCluskey

K-map เป็นวิธีการเชิงภาพ แต่สำหรับตัวแปรมากกว่า 4–5 ตัวจะเริ่มใช้งานยาก อัลกอริทึม Quine-McCluskey (QM) คือวิธีการแบบตารางที่เทียบเท่ากัน มีความแม่นยำทางคณิตศาสตร์และปรับขนาดได้ ตัวแก้ปัญหานี้ใช้ QM ภายใน:

1. แสดงรายการ Minterm ในรูปแบบฐานสอง จัดกลุ่มตามจำนวนบิตที่เป็น 1
2. รวมคู่ จากกลุ่มที่อยู่ติดกัน (ที่ต่างกันเพียง 1 บิต) โดยแทนที่บิตที่ต่างกันด้วยเครื่องหมายขีด (dash) เช่น 0011 + 0111 → 0-11
3. ทำซ้ำ จนกว่าจะไม่สามารถรวมได้อีก เทอมที่เหลือคือ Prime implicants
4. สร้างตาราง Prime implicant — ระบุกลุ่มที่จำเป็น (Essential) ที่ครอบคลุม Minterm เฉพาะตัว
5. ใช้วิธี Petrick หรือการค้นหาแบบละเอียด เพื่อหาชุดกลุ่มเพิ่มเติมที่เล็กที่สุดเพื่อครอบคลุม Minterm ที่ยังเหลืออยู่

วิธีใช้งานเครื่องคำนวณนี้

1. เลือกจำนวนตัวแปร: 2, 3, 4 หรือ 5 แผนผังจะปรับโดยอัตโนมัติ
2. เลือกวิธีการป้อนข้อมูล:
   • Minterms: ใส่ดัชนีที่ F = 1 (เช่น 1, 3, 5, 7) และ Don't-cares
   • Maxterms: ใส่ดัชนีที่ F = 0 ตัวแก้ปัญหาจะมองส่วนที่เหลือเป็น 1 โดยอัตโนมัติ
   • ตารางความจริง: คลิกแต่ละแถวเพื่อเปลี่ยนเอาต์พุตระหว่าง 0, 1 และ X เหมาะสำหรับการออกแบบตรรกะด้วยมือ
3. เลือกรูปแบบผลลัพธ์ SOP หรือ POS เปรียบเทียบทั้งสองแบบโดยการสลับโหมด เพื่อดูว่าแบบไหนสั้นกว่า
4. คลิก แก้ปัญหา แผนผัง K-map จะปรากฏพร้อมสีสันแสดงกลุ่มต่างๆ คลิกที่ชิปเพื่อดูการเน้นกลุ่ม
5. ตรวจสอบขั้นตอน: รายละเอียด Quine-McCluskey จะแสดงให้เห็นว่า Prime implicant แต่ละตัวมาจากไหนและอันไหนสำคัญ

ตัวอย่าง: ฟังก์ชัน 4 ตัวแปรพร้อม Don't-Cares

พิจารณา F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5)

หากไม่มี Don't-cares นิพจน์ SOP จะมีหลายเทอม แต่ถ้าเรามอง {0, 2} เป็น 1 จะช่วยให้สร้างกลุ่ม 4 เซลล์ A'B' (ครอบคลุม 0, 1, 2, 3) และถ้ามอง 5 เป็น 1 จะช่วยขยายกลุ่ม CD การลดรูปที่ได้คือ:

ใช้ตัวอักษรเพียง 4 ตัว — ลดลงจากเดิมที่อาจต้องใช้มากกว่า 10 ตัวหากไม่ใช้เทคนิค Don't-care คุณสามารถลองตัวอย่างนี้ได้จากปุ่ม "4 ตัวแปร พร้อม Don't-Cares" ด้านบน

ทำไมต้องลดรูปฟังก์ชันบูลีน?

• ใช้เกตน้อยลง = ลดต้นทุนฮาร์ดแวร์, ใช้พื้นที่ชิปน้อยลง และประหยัดพลังงาน
• วงจรทำงานเร็วขึ้น: ลดความหน่วงของเกตในเส้นทางวิกฤต (Critical Path)
• เอกสารอ่านง่ายขึ้น: นิพจน์ที่สั้นช่วยให้ตรวจสอบและบำรุงรักษาได้ง่าย
• พื้นฐานของการออกแบบดิจิทัล: เครื่องมือสังเคราะห์ FPGA ทุกตัวใช้อัลกอริทึมที่พัฒนามาจาก Quine-McCluskey (เช่น Espresso-II)

ข้อจำกัดและเมื่อควรใช้เครื่องมืออื่น

• ตัวแปรมากกว่า 5 ตัว: K-map จะเริ่มดูสับสน เครื่องมือนี้รองรับสูงสุด 5 ตัวแปรโดยการแยกเป็นสองตาราง หากมากกว่านั้นควรพึ่งพาขั้นตอน Quine-McCluskey หรือเครื่องมือสังเคราะห์ระดับสูง
• Hazards และ Glitches: การลดรูปขั้นต่ำอาจทำให้เกิด Static Hazards สำหรับการออกแบบที่ปราศจาก Hazard อาจต้องเพิ่มกลุ่มที่ซ้ำซ้อน (Redundant) ซึ่งเครื่องมือนี้จะระบุไว้แต่จะไม่เพิ่มให้โดยอัตโนมัติ
• การลดรูปหลายเอาต์พุต: หากมีหลายฟังก์ชันที่ใช้ตัวแปรร่วมกัน การลดรูปร่วมกัน (Shared gates) จะประหยัดกว่า เครื่องมือนี้จะลดรูปทีละหนึ่งฟังก์ชันเท่านั้น

คำถามที่พบบ่อย

แผนผังคาร์นอฟคืออะไร?

แผนผังคาร์นอฟ (K-map) คือวิธีการเชิงภาพในการลดรูปนิพจน์บูลีน เซลล์จะถูกจัดเรียงเพื่อให้เซลล์ที่อยู่ติดกันแตกต่างกันเพียงตัวแปรเดียว (Gray code) การจัดกลุ่มเลข 1 เป็นสี่เหลี่ยมขนาด 1, 2, 4, 8 หรือ 16 จะแสดงนิพจน์ที่สั้นที่สุด

SOP และ POS แตกต่างกันอย่างไร?

SOP (Sum of Products) จัดกลุ่มเซลล์เลข 1 และนำมา OR กัน เช่น A'B + CD ส่วน POS (Product of Sums) จัดกลุ่มเซลล์เลข 0 และนำมา AND กัน เช่น (A + B')(C' + D)

Don't-cares คืออะไรและทำไมต้องใช้?

เทอม Don't-care (X) คืออินพุตที่เอาต์พุตไม่มีผลต่อระบบ ตัวแก้ปัญหาจะเลือกให้เป็น 0 หรือ 1 เพื่อให้นิพจน์ง่ายที่สุด ซึ่งช่วยลดจำนวนตัวอักษรได้อย่างมาก

Prime Implicant คืออะไร?

Prime implicant คือกลุ่มเซลล์ 1 ที่ใหญ่ที่สุดที่ไม่สามารถขยายได้อีก ส่วน Essential prime implicant คือกลุ่มที่จำเป็นต้องมีเพราะมันครอบคลุม Minterm บางตัวที่ไม่ซ้ำกับกลุ่มอื่น

อัลกอริทึม Quine-McCluskey ทำงานอย่างไร?

เป็นวิธีการแบบตารางที่เหมาะสำหรับตัวแปรจำนวนมาก โดยจะรวมเทอมฐานสองที่ต่างกันหนึ่งบิตเข้าด้วยกันซ้ำๆ จนได้ Prime implicants แล้วจึงเลือกชุดที่ครอบคลุมน้อยที่สุด

ตัวแก้ K-map นี้รองรับกี่ตัวแปร?

รองรับ 2 ถึง 5 ตัวแปร K-map 5 ตัวแปรจะแสดงเป็นแผนผัง 4x4 สองอัน (สำหรับ A=0 และ A=1)

อ่านเพิ่มเติม

• Karnaugh Map — Wikipedia
• Quine-McCluskey Algorithm — Wikipedia
• Petrick's Method — Wikipedia