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 การเป็นตัวแทน
| ชื่อกลุ่ม | เงื่อนไขขั้นต่ำ | ว | 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 จากกลุ่มที่อยู่ติดกัน
| ชื่อกลุ่ม | เงื่อนไขขั้นต่ำ | ว | 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.