K-Map more than 5 input

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

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

[แก้] การแก้ไขปัญหาด้วยวิธี 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

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 ได้ง่ายและแม่นยำมากยิ่งขึ้น