Quine-McCluskey วิธีตาราง

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

วิธีตาราง Quine-McClukey เป็นวิธีการแบบตารางตามแนวคิดของนัยสำคัญ เรารู้ว่าprime implicant เป็นคำศัพท์ผลิตภัณฑ์ (หรือผลรวม) ซึ่งไม่สามารถลดได้อีกโดยรวมกับเงื่อนไขผลิตภัณฑ์ (หรือผลรวม) อื่น ๆ ของฟังก์ชันบูลีนที่กำหนด

วิธีการแบบตารางนี้มีประโยชน์ในการรับนัยสำคัญโดยใช้เอกลักษณ์บูลีนต่อไปนี้ซ้ำ ๆ

xy + xy '= x (y + y') = x.1 = x

ขั้นตอนของ Quine-McCluskey Tabular Method

ทำตามขั้นตอนเหล่านี้เพื่อลดความซับซ้อนของฟังก์ชันบูลีนโดยใช้วิธีตาราง Quine-McClukey

Step 1 - จัดเรียงเงื่อนไขขั้นต่ำที่กำหนดในไฟล์ ascending orderและสร้างกลุ่มตามจำนวนกลุ่มที่มีอยู่ในการแทนค่าไบนารี ดังนั้นจะมีat most ‘n+1’ groups หากมีตัวแปรบูลีน 'n' ในฟังก์ชันบูลีนหรือบิต 'n' ในรูปแบบไบนารีที่เทียบเท่ากับเงื่อนไขขั้นต่ำ

Step 2 - เปรียบเทียบเงื่อนไขขั้นต่ำที่มีอยู่ใน successive groups. หากมีการเปลี่ยนแปลงในตำแหน่งบิตเดียวให้ใช้คู่ของพจน์ต่ำสุดสองคำนั้น วางสัญลักษณ์ '_' นี้ไว้ในตำแหน่งบิตที่แตกต่างกันและเก็บบิตที่เหลือไว้ตามเดิม

Step 3 - ทำซ้ำขั้นตอนที่ 2 ด้วยเงื่อนไขที่สร้างขึ้นใหม่จนกว่าเราจะได้รับทั้งหมด prime implicants.

Step 4 - กำหนดรูปแบบ prime implicant table. ประกอบด้วยชุดของแถวและคอลัมน์ นัยสำคัญสามารถวางไว้ในแถวที่ชาญฉลาดและคำต่ำสุดสามารถวางในคอลัมน์ที่ชาญฉลาด วาง '1' ในเซลล์ที่ตรงกับเงื่อนไขขั้นต่ำที่ครอบคลุมในแต่ละนัยที่สำคัญ

Step 5- ค้นหานัยสำคัญที่สำคัญโดยสังเกตแต่ละคอลัมน์ หากคำศัพท์ขั้นต่ำครอบคลุมโดยนัยเฉพาะเพียงคำเดียวแสดงว่าเป็นessential prime implicant. นัยเฉพาะที่สำคัญเหล่านั้นจะเป็นส่วนหนึ่งของฟังก์ชันบูลีนแบบง่าย

Step 6- ลดตารางนัยเฉพาะที่สำคัญโดยการลบแถวของนัยสำคัญที่สำคัญแต่ละตัวและคอลัมน์ที่ตรงกับเงื่อนไขขั้นต่ำที่ครอบคลุมในนัยสำคัญที่สำคัญนั้น ทำซ้ำขั้นตอนที่ 5 สำหรับ Reduced prime implicant table หยุดกระบวนการนี้เมื่อเงื่อนไขขั้นต่ำทั้งหมดของฟังก์ชันบูลีนที่กำหนดสิ้นสุดลง

ตัวอย่าง

ขอให้เรา simplify ฟังก์ชันบูลีนต่อไปนี้ $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right) $ โดยใช้ Quine-McClukey วิธีการแบบตาราง

ฟังก์ชันบูลีนที่กำหนดอยู่ใน sum of min termsแบบฟอร์ม. มีตัวแปร 4 ตัวคือ W, X, Y & Z เงื่อนไขขั้นต่ำที่กำหนดคือ 2, 6, 8, 9, 10, 11, 14 และ 15 ลำดับจากน้อยไปหามากของเงื่อนไขขั้นต่ำเหล่านี้ขึ้นอยู่กับจำนวนของคำที่มีอยู่ใน การเทียบเท่าไบนารีคือ 2, 8, 6, 9, 10, 11, 14 และ 15 ตารางต่อไปนี้แสดงสิ่งเหล่านี้min terms and their equivalent binary การเป็นตัวแทน

GA3
ชื่อกลุ่ม เงื่อนไขขั้นต่ำ X Z
GA1 2 0 0 1 0
8 1 0 0 0
GA2 6 0 1 1 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
14 1 1 1 0
GA4 15 1 1 1 1

เงื่อนไขขั้นต่ำที่กำหนดจะถูกจัดเรียงเป็น 4 กลุ่มตามจำนวนของคำที่มีอยู่ในการเทียบเท่าไบนารี ตารางต่อไปนี้แสดงความเป็นไปได้merging of min terms จากกลุ่มที่อยู่ติดกัน

GB3
ชื่อกลุ่ม เงื่อนไขขั้นต่ำ X Z
GB1 2,6 0 - 1 0
2,10 - 0 1 0
8,9 1 0 0 -
8,10 1 0 - 0
GB2 6,14 - 1 1 0
9,11 1 0 - 1
10,11 1 0 1 -
10,14 1 - 1 0
11,15 1 - 1 1
14,15 1 1 1 -

เงื่อนไขขั้นต่ำซึ่งแตกต่างกันในตำแหน่งบิตเดียวจากกลุ่มที่อยู่ติดกันจะถูกรวมเข้าด้วยกัน บิตที่แตกต่างกันนั้นจะแสดงด้วยสัญลักษณ์นี้ '-' ในกรณีนี้มีสามกลุ่มและแต่ละกลุ่มมีคำศัพท์ขั้นต่ำสองคำผสมกัน ตารางต่อไปนี้แสดงความเป็นไปได้merging of min term pairs จากกลุ่มที่อยู่ติดกัน

ชื่อกลุ่ม เงื่อนไขขั้นต่ำ X Z
GB1 2,6,10,14 - - 1 0
2,10,6,14 - - 1 0
8,9,10,11 1 0 - -
8,10,9,11 1 0 - -
GB2 10,11,14,15 1 - 1 -
10,14,11,15 1 - 1 -

กลุ่มคำศัพท์ขั้นต่ำที่ต่อเนื่องกันซึ่งแตกต่างกันในตำแหน่งบิตเดียวเท่านั้นที่จะรวมเข้าด้วยกัน บิตที่แตกต่างกันนั้นจะแสดงด้วยสัญลักษณ์นี้ '-' ในกรณีนี้มีสองกลุ่มและแต่ละกลุ่มมีคำศัพท์ขั้นต่ำสี่คำผสมกัน คำศัพท์ขั้นต่ำ 4 คำที่รวมกันเหล่านี้มีอยู่ในสองแถว ดังนั้นเราสามารถลบแถวที่ซ้ำกันได้ ตารางที่ลดลงหลังจากลบแถวที่ซ้ำซ้อนแสดงอยู่ด้านล่าง

ชื่อกลุ่ม เงื่อนไขขั้นต่ำ X Z
GC1 2,6,10,14 - - 1 0
8,9,10,11 1 0 - -
GC2 10,11,14,15 1 - 1 -

ไม่สามารถรวมการผสมคำศัพท์ขั้นต่ำเพิ่มเติมจากกลุ่มที่อยู่ติดกันได้เนื่องจากมีความแตกต่างกันในตำแหน่งมากกว่าหนึ่งบิต มีสามแถวในตารางด้านบน ดังนั้นแต่ละแถวจะให้ 1 นัยสำคัญ ดังนั้นไฟล์prime implicants คือ YZ ', WX' & WY

prime implicant table ดังแสดงด้านล่าง

เงื่อนไขขั้นต่ำ / นัยสำคัญ 2 6 8 9 10 11 14 15
YZ’ 1 1 1 1
WX’ 1 1 1 1
WY 1 1 1 1

นัยที่สำคัญถูกวางไว้ในแถวที่ชาญฉลาดและเงื่อนไขขั้นต่ำจะอยู่ในคอลัมน์ที่ชาญฉลาด 1s ถูกวางไว้ในเซลล์ทั่วไปของแถวนัยที่สำคัญและคอลัมน์ระยะต่ำสุดที่เกี่ยวข้อง

เงื่อนไขขั้นต่ำ 2 และ 6 ครอบคลุมโดยนัยเฉพาะหลักเดียวเท่านั้น YZ’. ดังนั้นมันคือessential prime implicant. นี่จะเป็นส่วนหนึ่งของฟังก์ชันบูลีนแบบง่าย ตอนนี้ลบแถวนัยที่สำคัญนี้และคอลัมน์ระยะต่ำที่เกี่ยวข้อง ตารางนัยสำคัญที่ลดลงแสดงไว้ด้านล่าง

เงื่อนไขขั้นต่ำ / นัยสำคัญ 8 9 11 15
WX’ 1 1 1
WY 1 1

เงื่อนไขขั้นต่ำ 8 และ 9 ครอบคลุมโดยนัยเฉพาะหลักเดียวเท่านั้น WX’. ดังนั้นมันคือessential prime implicant. นี่จะเป็นส่วนหนึ่งของฟังก์ชันบูลีนแบบง่าย ตอนนี้ลบแถวนัยที่สำคัญนี้และคอลัมน์ระยะต่ำที่เกี่ยวข้อง ตารางนัยสำคัญที่ลดลงแสดงไว้ด้านล่าง

เงื่อนไขขั้นต่ำ / นัยสำคัญ 15
WY 1

ระยะต่ำสุด 15 จะครอบคลุมโดยนัยสำคัญเพียงตัวเดียว WY. ดังนั้นมันคือessential prime implicant. นี่จะเป็นส่วนหนึ่งของฟังก์ชันบูลีนแบบง่าย

ในโจทย์ตัวอย่างนี้เรามีนัยสำคัญสามประการและทั้งสามมีความจำเป็น ดังนั้นไฟล์simplified Boolean function คือ

f(W,X,Y,Z) = YZ’ + WX’ + WY.