ขั้นตอนวิธีของควิน-แม็กคลัสกีย์
บทความนี้ต้องการการจัดหน้า จัดหมวดหมู่ ใส่ลิงก์ภายใน หรือเก็บกวาดเนื้อหา ให้มีคุณภาพดีขึ้น คุณสามารถปรับปรุงแก้ไขบทความนี้ได้ และนำป้ายออก พิจารณาใช้ป้ายข้อความอื่นเพื่อชี้ชัดข้อบกพร่อง |
ขั้นตอนวิธีของควิน-แม็กคลัสกีย์ (อังกฤษ: Quine-McCluskey algorithm) เป็นหนึ่งในขั้นตอนวิธีที่ใช้สำหรับการลดรูปนิพจน์ตรรกศาสตร์ให้อยู่ในรูปอย่างง่ายที่มีประสิทธิภาพสูง พัฒนาโดย ดับเบิลยู.วี. ควิน (W.V.Quine) และเอ็ดเวิด เจ. แมกคลัสกีย์ (Edward J. McCluskey)
ขั้นตอนวิธีของควิน-แม็กคลัสกีย์เป็นขั้นตอนวิธีที่ช่วยในการลดรูปนิพจน์ตรรกะได้เมื่อข้อมูลขาเข้าที่มีปริมาณตัวแปรจำนวนมาก แต่ในการทำงานยังมีข้อจำกัดในเรื่องของเวลาอยู่ จึงควรดูขนาดของข้อมูลขาเข้า ว่ามีขนาดเท่าไหร่ และสมควรที่จะใช้วิธีการนี้หรือไม่ หากไม่สมควรควรจะเลือกใช้วิธีการอื่นที่สามารถลดนิพจน์ตรรกะได้ เช่น วิธีการเอกเพรซโซ่ ซึ่งเป็นวิธีการที่จะใช้ผ่านโปรแกรม[ต้องการอ้างอิง]
วิธีการทำงาน แก้
วิธีการนี้มีขั้นตอนการทำงานเหมือนกับการทำแผนผังคาร์โนห์ (Karnaugh map หรือ K-map) แต่มีความยืดหยุ่นมากกว่า ในด้านการนำไปประยุกต์เพื่อสร้างโปรแกรมคอมพิวเตอร์อย่างมีประสิทธิภาพ และด้านการใช้งานกับนิพจน์ตรรกศาสตร์ที่มีตัวแปรเป็นจำนวนมาก
ขั้นตอนการทำงาน แบ่งออกเป็นสองขั้นตอน ดังนี้:
- รวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอม
- สร้างตารางเพื่อหานิพจน์ตรรกศาสตร์ในรูปอย่างง่าย
รหัสเทียม แก้
ตัวอย่างรหัสเทียม แก้
- ตัวอย่างรหัสเทียมสำหรับการทำงานของขั้นตอนวิธีควิน-แมกคลัสกีย์
Function QM1 ( levels ) returns primes
put { } (empty set) into primes
for each level level do
irredundant level (remove duplicates from level)
put { } (empty set) into nonprimes
for every term term in level from 1 to the size of level –1 do
for every term compterm in level from term + 1 to the size of level do
put –1 into differentLiteral as a flag
for every literal literal from 1 to NUMINPUTS do
if literal literal of term ? literal literal of compterm then
if differentLiteral = –1 then
(there was no previous difference)
put literal into differentLiteral
else (there was a previous difference)
put –1 into differentLiteral as a flag
break (get out of this comparison loop)
end if
end if
end for of literal
if differentLiteral ? –1 then (there was exactly one difference)
add term to nonprimes
add compterm to nonprimes
add term with 2 in literal differentLiteral to level level + 1
end for of compterm
end for of term
if the size of nonprimes > 0 then
add all terms not in nonprimes to primes
else
break (get out of loop for levels)
end if
end for of level
return primes
ข้อจำกัด แก้
- ถึงแม้วิธีการนี้จะได้ผลดีกว่ากว่าแผนผังคาร์โนห์เมื่อใช้ลดนิพจน์ตรรกศาสตร์ที่มีตัวแปรมากกว่าสี่ตัวก็ตาม แต่เวลาที่ใช้ในการทำงานจะเพิ่มมากขึ้นอย่างรวดเร็วตามจำนวนของตัวแปร (เพิ่มขึ้นในอัตราส่วนแบบฟังก์ชันเลขชี้กำลัง) โดยสามารถแสดงในรูปแบบของฟังก์ชันขอบเขตสูงสุดของตัวแปร ตัว ได้เป็น ซึ่งหากนิพจน์ตรรกศาสตร์มีจำนวนตัวแปรเท่ากับ 32 ตัว หรือ อาจจะมีเทอมที่ไม่สามารถจับคู่ได้มากกว่า เทอม ดังนั้นหากต้องการลดนิพจน์ตรรกศาสตร์ที่มีจำนวนตัวแปรมากๆ ควรใช้วิธีการอื่นแทน เช่น การใช้โปรแกรมเอสเปรสโซ่ เป็นต้น
- ขั้นตอนวิธีนี้ เป็นขั้นตอนวิธีปัญหา เอ็นพี-แบบยาก เพราะมีอัตราการทำงานเติบโตในรูปของฟังก์ชันเอกซ์โพเน็นเชียล
ปัญหาที่เกี่ยวข้อง แก้
- วิธีการของแพททริก
ตัวอย่างขั้นตอนการทำงาน แก้
ลดรูปนิพจน์ตรรกศาสตร์ต่อไปนี้:
รวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอม แก้
- เนื่องจากนิพจน์ตรรกศาสตร์ดังกล่าว มีตัวแปรจำนวน 4 ตัว ได้แก่ A, B, C และ D ดังนั้นจึงสามารถสร้างตารางค่าความจริงได้ทั้งหมด 16 กรณี ดังนี้
A | B | C | D | - | f | |
m0 | 0 | 0 | 0 | 0 | - | x |
m1 | 0 | 0 | 0 | 1 | - | 0 |
m2 | 0 | 0 | 1 | 0 | - | 0 |
m3 | 0 | 0 | 1 | 1 | - | 0 |
m4 | 0 | 1 | 0 | 0 | - | 1 |
m5 | 0 | 1 | 0 | 1 | - | 1 |
m6 | 0 | 1 | 1 | 0 | - | 1 |
m7 | 0 | 1 | 1 | 1 | - | x |
m8 | 1 | 0 | 0 | 0 | - | 1 |
m9 | 1 | 0 | 0 | 1 | - | 1 |
m10 | 1 | 0 | 1 | 0 | - | 1 |
m11 | 1 | 0 | 1 | 1 | - | 0 |
m12 | 1 | 1 | 0 | 0 | - | 0 |
m13 | 1 | 1 | 0 | 1 | - | 1 |
m14 | 1 | 1 | 1 | 0 | - | 0 |
m15 | 1 | 1 | 1 | 1 | - | x |
ในการรวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอมนั้น จะพิจารณาจากเทอมที่มีค่าของ A,B,C และ D ต่างกันเพียง 1 บิต ตัวอย่างเช่น 0000 กับ 0100 (ต่างกันที่บิตที่สอง) หรือ 0000 กับ 1000 (ต่างกันที่บิตที่หนึ่ง) เป็นต้น ดังนั้นเพื่อให้ง่ายต่อการพิจารณา จะทำการแบ่งกลุ่มที่มีค่าของ A,B,C และ D ต่างกันเพียง 1 บิตโดยแบ่งตามจำนวนของเลข 1 ในค่า A,B,C และ D ดังนี้
จำนวนเลข 1 ใน A,B,C,D | m | ค่าของ A,B,C,D |
---|---|---|
0 | m0 | 0000 |
1 | m4 | 0100 |
m8 | 1000 | |
2 | m5 | 0101 |
m6 | 0110 | |
m9 | 1001 | |
m10 | 1010 | |
3 | m7 | 0111 |
m13 | 1101 | |
4 | m15 | 1111 |
จากตารางด้านบน จะเห็นว่าเราสามารถแบ่งกลุ่มที่มีค่าของ A,B,C,D ต่างกันเพียง 1 บิทได้เป็น 5 กลุ่ม ดังนั้นในการรวมเทอมที่มีรูปแบบคล้ายกัน เราจะพิจารณาแต่ละกลุ่มเทียบกันโดยใช้วิธีการเขียนตาราง ดังนี้
- เขียนค่าของ ABCD ที่ต้องการพิจารณาลงในคอลัมน์เริ่มต้นของตาราง (คอลัมน์ที่ 1)
- เปรียบเทียบค่า ABCD ที่ต่างกันเพียง 1 บิต (ค่าของกลุ่มติดกันที่แบ่งไว้ข้างต้น) เพื่อยุบรวมเป็นตัวเดียว โดยแทนตัวที่ต่างกันด้วย "-" และแทนตัวที่เหมือนกันด้วยตัวเลขนั้นๆ เขียนผลลัพธ์ลงในคอลัมน์ถัดไป (คอลัมน์ที่ 2) ตัวอย่างเช่น เปรียบเทียบ 0000 กับ 0100 แล้วรวมเป็น 0-00, เปรียบเทียบ 0000 กับ 1000 แล้วรวมเป็น -000 เป็นต้น
- เมื่อยุบรวมพจน์เรียบร้อยแล้ว ให้ทำการเขียนเครื่องหมายถูก "/" หากยุบไม่ได้ก็ใส่เครื่องหมายดอกจัน "*" ไว้ด้านหลังพจน์ที่ถูกยุบรวมแล้ว
- ทำการเปรียบเทียบค่า ABCD ไปเรื่อยๆ เพื่อยุบรวมพจน์จนกระทั่งไม่สามารถยุบรวมได้อีก
คอลัมน์ที่ 1 | คอลัมน์ที่ 2 | คอลัมน์ที่ 3 |
---|---|---|
0000 / | 0-00 * | 01-- * |
- | -000 * | |
0100 / | -1-1 * | |
1000 / | 010- / | |
- | 01-0 / | |
0101 / | 100- * | |
0110 / | 10-0 * | |
1001 / | ||
1010 / | 01-1 / | |
- | -101 / | |
0111 / | 011- / | |
1101 / | 1-01 * | |
- | ||
1111 / | -111 / | |
11-1 / |
จากตารางด้านบน แสดงให้เห็นว่าพจน์ที่ไม่สามารถยุบรวมได้อีก มีทั้งหมด 7 พจน์ ได้แก่ 0-00, -000, 100-, 10-0, 1-01, 01-- และ -1-1
สร้างตารางเพื่อหานิพจน์ตรรกศาสตร์ในรูปอย่างง่าย แก้
การสร้างตาราง แก้
การสร้างตารางในเบื้องต้น มีขั้นตอนดังนี้
- สำหรับแต่ละแถว คือ พจน์ที่ไม่สามารถยุบรวมได้อีก ที่ได้หามาแล้วในขั้นตอนที่ 1
- สำหรับแต่ละคอลัมน์ คือ พจน์ที่มีค่าฟังก์ชันเป็น 1
- ทำเครื่องหมายกากบาท "X" ในตารางตามช่องที่มีตัวเลขในแถวและคอลัมน์เหมือนกัน
4 | 5 | 6 | 8 | 9 | 10 | 13 | |
---|---|---|---|---|---|---|---|
0,4 (0-00) | X | ||||||
0,8 (-000) | X | ||||||
8,9 (100-) | X | X | |||||
8,10 (10-0) | X | X | |||||
9,13 (1-01) | X | X | |||||
4,5,6,7 (01--) | X | X | X | ||||
5,7,13,15 (-1-1) | X | X |
การหารูปอย่างง่ายของนิพจน์ตรรกศาสตร์ แก้
หลังจากสร้างตารางเสร็จเรียบร้อยแล้ว หลักการในการหารูปอย่างง่ายของนิพจน์ตรรกศาสตร์ คือการเลือกแถวให้น้อยที่สุด โดยเลือกให้ครอบคลุมทุกคอลัมน์
- ในการเลือกแถวเบื้องต้นนั้น จะทำการตรวจสอบคอลัมน์ที่มีเครื่องหมาย "X" เพียงแถวเดียว แล้วทำการเลือกแถวนั้นๆ เนื่องจากเป็นแถวที่จำเป็นต้องเลือก หากไม่เลือกจะทำให้ไม่ครอบคลุมครบทุกคอลัมน์
- ทำเครื่องหมายทั้งในแนวแถวและคอลัมน์ที่เลือก
4 | 5 | 6 | 8 | 9 | 10 | 13 | |
0,4 (0-00) | X | ||||||
0,8 (-000) | X | ||||||
8,9 (100-) | X | X | |||||
8,10 (10-0) | X | X | |||||
9,13 (1-01) | X | X | |||||
4,5,6,7 (01--) | X | X | X | ||||
5,7,13,15 (-1-1) | X | X |
- จากนั้นให้ทำเครื่องหมายให้กับ "X" ที่อยู่ในคอลัมน์เดียวกันทั้งหมด เพื่อแสดงว่าคอลัมน์นั้นๆ ได้ถูกครอบคลุมโดยแถวที่เลือกไปแล้ว
4 | 5 | 6 | 8 | 9 | 10 | 13 | |
0,4 (0-00) | X | ||||||
0,8 (-000) | X | ||||||
8,9 (100-) | X | X | |||||
8,10 (10-0) | X | X | |||||
9,13 (1-01) | X | X | |||||
4,5,6,7 (01--) | X | X | X | ||||
5,7,13,15 (-1-1) | X | X |
- เลือกแถวที่ครอบคลุม "X" ในคอลัมน์ที่เหลืออยู่ แล้วทำเครื่องหมายสำหรับแถวนั้น (หากมีหลายแถวจะต้องเลือกแถวที่ครอบคลุมคอลัมน์ได้มากที่สุด)
- ผลที่ได้จะมีจำนวนแถวที่เลือกน้อยที่สุด และครอบคลุมส่วนที่เหลือทั้งหมดได้
4 | 5 | 6 | 8 | 9 | 10 | 13 | |
0,4 (0-00) | X | ||||||
0,8 (-000) | X | ||||||
8,9 (100-) | X | X | |||||
8,10 (10-0) | X | X | |||||
9,13 (1-01) | X | X | |||||
4,5,6,7 (01--) | X | X | X | ||||
5,7,13,15 (-1-1) | X | X |
ดังนั้น นิพจน์ตรรกศาสตร์ในรูปอย่างง่าย คือ :
ดูเพิ่ม แก้
อ้างอิง แก้
- 85-89.http://www.freebookzone.com/fetch.php?bkcls=hw_logic&bkidx=7 Contemporary Logic Design
เชื่อมต่อภายนอก แก้
- การลดทอนฟังก์ชัน
- การลดรูปสมการบูลลีน[ลิงก์เสีย]
- Quine-McCluskey Algorithm เก็บถาวร 2016-03-04 ที่ เวย์แบ็กแมชชีน
- Minimization[ลิงก์เสีย]
- ตัวอย่างขั้นตอนวิธีของควินและแมกคลัสกีย์
- รหัสเทียมของขั้นตอนวิธีควินและแมกคลัสกีย์ เก็บถาวร 2015-09-19 ที่ เวย์แบ็กแมชชีน
- เกี่ยวกับควิน-แม็กคลัสกีย์
- โปรแกรมลดรูปแบบควิน-แม็กคลัสกีย์แบบออนไลน์ เก็บถาวร 2006-10-02 ที่ เวย์แบ็กแมชชีน
- ตัวอย่างโปรแกรมภาษาซี
- ตัวอย่างโปรแกรมออนไลน์ เก็บถาวร 2006-10-02 ที่ เวย์แบ็กแมชชีน