K-Map more than 5 input

จากวิกิพีเดีย สารานุกรมเสรี

บทความนี้ได้รับแจ้งว่ามีลักษณะไม่เป็นสารานุกรม
เนื่องด้วยการใช้ถ้อยคำ รูปแบบการเขียน เนื้อหา หรือมีลักษณะคล้ายคู่มือ หรือเอกสารต้นฉบับ ซึ่งไม่ตรงตามนโยบายของวิกิพีเดีย
คุณสามารถช่วยแก้ไขปัญหานี้ได้ด้วยการกดที่ปุ่ม แก้ไข หรือย้ายบทความนี้ไปยังโครงการพี่น้องที่เหมาะสม
ดูรายละเอียดเพิ่มเติมได้ที่ เงื่อนไขในการนับว่าเป็นสารานุกรม อะไรที่ไม่ใช่วิกิพีเดีย โครงการพี่น้อง บทความคัดสรร และ นโยบายวิกิพีเดีย
ภาพ:Splitsection.gif มีการแนะนำว่า ส่วนด้านล่างนี้ของบทความควรย้ายไปที่โครงการ วิกิตำรา (พูดคุย)

[แก้] การแก้ไขปัญหาด้วยวิธี K-Map ในกรณีที่มีมากกว่า 5 ตัวแปร

ใช้สำหรับแก้ไขปัญหาในกรณีที่มีตัวแปรตั้งแต่ 6 ตัวแปรขึ้นไป แบ่งออกเป็น

1.Quine-McCluskey algorithm

สามารถทำงานได้ดีจนถึง 12 ตัวแปร ซึ่งให้ความสำคัญกับความถูกต้องของข้อมูล แต่มีข้อเสียคือ สามารถทำงานได้ช้า

2.Espresso program

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

•ใช้ Q-M technique ในการลดรูป function

เช่น f(A,B,C,D) = ∑m (2,4,6,8,9,10,12,13,15)
ซึ่งเราสามารถแปลงเป็นเลขฐานสองได้ดังนี้
2 = 0 0 1 0
4 = 0 1 0 0
นำค่าที่แปลงเป็เลขฐานสองขนาดสี่บิทมาใส่ใน k map
นำค่าที่แปลงเป็เลขฐานสองขนาดสี่บิทมาใส่ใน k map
6 = 0 1 1 0
8 = 1 0 0 0
9 = 1 0 0 1
10 = 1 0 1 0
12 = 1 1 0 0
13 = 1 1 0 1
15 = 1 1 1 1

และนำมาใส่ใน K-Map

[แก้] วิธีการลดรูป

ขั้นตอนที่1.

สร้างรายการใน list โดยให้เป็น list1 ซึ่ง 2 ,4,8 จะเป็นกลุ่มที่มีค่าต่างกัน 1 bit 6,9,10,12 เป็นกลุ่มที่ต่างกัน 2 bit
13 และ 15 เป็นกลุ่มที่มี ค่าเดียว ต่างกัน 3 bit และ 4 bit ตามลำดับ

ขั้นตอนที่2.

ทำการเปรียบเทียบเทอมที่มี่ค่าต่างกัน 1 bit โดยเริ่มจับคู่จาก 2-4 ,2-8,2-6…ไปเรื่อยๆจะพบว่า 2-6 และ 2-10
มีค่า ต่างกัน 1 bit นำไปใส่ใน list 2 เริ่มทำการจับคู่เพื่อหาบิทที่แตกต่างกันใหม่
โดยเริ่มที่ 4-8,4-6,4-9,… ไปเรื่อยๆจะพบว่า 4-6,4-12 มีค่าต่างกัน bit นำไปใส่ใน list 2
ทำเช่นนี้ไปเรื่อยๆจนถึงคู่สุดท้ายคือ 13-15 หากมีคู่ใดที่แตกต่างกัน 1 bit ก็นำไปใส่ใน list 2
เปรียบเทียบ list 2 โดยดูว่ามีค่าใดบ้างที่ต่างกัน ซึ่งเราจะพบว่า (8,9) , (9,12) , (9,13) , (12,13)
แตกต่างกัน 1 bit แต่ 8,9,12,13 ซ้ำกันเราจึงนำมารวมกันใน list 3 เลย

ขั้นตอนที่3.


สร้างตารางเพื่อนำค่าที่เราเปรียบเทียบแล้วมาใส่ โดย
P1 นำมาจาก list 3 มีเทอมที่เปรียบเทียบได้แก่ 8,9,12,13
P2 นำมาจาก list 2 มีเทอมที่เปรียบเทียบได้แก่ 2,6
P3 นำมาจาก list 2 มีเทอมที่เปรียบเทียบได้แก่ 2,10
ทำเช่นนี้ไปเรื่อยๆ จนครบ(จนถึง P7)
จะพบว่า ใน P1 มี 9 และ P7 มี15 ซึ่งเป็นค่าที่ไม่ซ้ำ ดังนั้นเราจึงจำเป็นต้องเก็บ P1 และ P7 ไว้ทำให้ 8,9,12,13,15
ถูกลดรูปไปด้วย ซึ่งทำให้เหลือ P2 ถึง P6 ที่ต้องพิจารณา



ทำการจับคู่ ซึ่งในที่นี้จับคู่ P3 และ P4 เพราะทำให้ได้ครบทุกเทอม ( ครบทั้ง 2,4,6,10 )
ดังนั้น จากขั้นตอนที่สามนี้จะทำให้เราสามารถลดรูปได้เหลือแค่ P1,P3,P4,P7
ซึ่งเราตรวจสอบแล้ว P1,P3,P4,P7 สามารถให้ค่าครบทุกค่า (2,4,6,8,9,10,12,13,15 )

ขั้นตอนที่4.

จะได้ว่า f (A,B,C,D) = P1+P3+P4+P7
= 1-0 + -010 + 01-0 + 11-1
=

และเมื่อเราเปรียบเทียบ จาก K-map ที่เราสร้างเมื่อตอนต้นแล้ว เราจะพบว่า
สี่ขั้นตอนที่ผ่านมาสามารถทำให้เราลดรูป K – map ได้ง่ายและแม่นยำมากยิ่งขึ้น


ตรวจสอบจาก K Map จะเห็นว่าสามารถลดรูปได้อย่างถูกต้อง
ตรวจสอบจาก K Map จะเห็นว่าสามารถลดรูปได้อย่างถูกต้อง