ผู้ใช้:Lknlookin/ทดลองเขียน

ขั้นตอนวิธีของควิน-แม็กคลัสกีย์ (อังกฤษ: Quine-McCluskey algorithm) เป็นหนึ่งในขั้นตอนวิธีที่ใช้สำหรับการลดรูปนิพจน์ตรรกศาสตร์ให้อยู่ในรูปอย่างง่ายที่มีประสิทธิภาพสูง พัฒนาโดย ดับเบิลยู.วี. ควิน (W.V.Quine) และเอ็ดเวิด เจ. แมกคลัสกีย์ (Edward J. McCluskey)

วิธีการทำงาน

วิธีการนี้มีขั้นตอนการทำงานเหมือนกับการทำแผนผังคาร์โนห์ (Karnaugh map หรือ K-map) แต่มีความยืดหยุ่นมากกว่า ในด้านการนำไปประยุกต์เพื่อสร้างโปรแกรมคอมพิวเตอร์อย่างมีประสิทธิภาพ และด้านการใช้งานกับนิพจน์ตรรกศาสตร์ที่มีตัวแปรเป็นจำนวนมาก
ขั้นตอนการทำงาน แบ่งออกเป็นสองขั้นตอน ดังนี้:

1. รวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอม
2. สร้างตารางเพื่อหานิพจน์ตรรกศาสตร์ในรูปอย่างง่าย

ข้อจำกัด

ถึงแม้วิธีการนี้จะได้ผลดีกว่ากว่าแผนผังคาร์โนห์เมื่อใช้ลดนิพจน์ตรรกศาสตร์ที่มีตัวแปรมากกว่าสี่ตัวก็ตาม แต่เวลาที่ใช้ในการทำงานจะเพิ่มมากขึ้นอย่างรวดเร็วตามจำนวนของตัวแปร (เพิ่มขึ้นในอัตราส่วนแบบฟังก์ชันเลขชี้กำลัง) โดยสามารถแสดงในรูปแบบของฟังก์ชันขอบเขตสูงสุดของตัวแปร $n$ ตัว ได้เป็น ${\frac {3^{n}}{n}}$ ซึ่งหากนิพจน์ตรรกศาสตร์มีจำนวนตัวแปรเท่ากับ 32 ตัว หรือ $n=32$ อาจจะมีเทอมที่ไม่สามารถจับคู่ได้มากกว่า $6.5\times 1015$ เทอม ดังนั้นหากต้องการลดนิพจน์ตรรกศาสตร์ที่มีจำนวนตัวแปรมากๆ ควรใช้วิธีการอื่นแทน เช่น การใช้โปรแกรมเอสเปรสโซ่ เป็นต้น

ขั้นตอนวิธีนี้ เป็นขั้นตอนวิธีปัญหา เอ็นพี-แบบยาก เพราะมีอัตราการทำงานเติบโตในรูปของฟังก์ชันเอกซ์โพเน็นเชียล

ปัญหาที่เกี่ยวข้อง

• วิธีการของแพททริก

ตัวอย่างขั้นตอนการทำงาน

ลดรูปนิพจน์ตรรกศาสตร์ต่อไปนี้:

$f(A,B,C,D)=\sum m(4,5,6,8,9,10,13)+d(0,7,15)\,$

รวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอม

เนื่องจากนิพจน์ตรรกศาสตร์ดังกล่าว มีตัวแปรจำนวน 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 กลุ่ม ดังนั้นในการรวมเทอมที่มีรูปแบบคล้ายกัน เราจะพิจารณาแต่ละกลุ่มเทียบกันโดยใช้วิธีการเขียนตาราง ดังนี้

1. เขียนค่าของ ABCD ที่ต้องการพิจารณาลงในคอลัมน์เริ่มต้นของตาราง (คอลัมน์ที่ 1)
2. เปรียบเทียบค่า ABCD ที่ต่างกันเพียง 1 บิต (ค่าของกลุ่มติดกันที่แบ่งไว้ข้างต้น) เพื่อยุบรวมเป็นตัวเดียว โดยแทนตัวที่ต่างกันด้วย "-" และแทนตัวที่เหมือนกันด้วยตัวเลขนั้นๆ เขียนผลลัพธ์ลงในคอลัมน์ถัดไป (คอลัมน์ที่ 2) ตัวอย่างเช่น เปรียบเทียบ 0000 กับ 0100 แล้วรวมเป็น 0-00, เปรียบเทียบ 0000 กับ 1000 แล้วรวมเป็น -000 เป็นต้น
3. เมื่อยุบรวมพจน์เรียบร้อยแล้ว ให้ทำการเขียนเครื่องหมายถูก "/" หากยุบไม่ได้ก็ใส่เครื่องหมายดอกจัน "*" ไว้ด้านหลังพจน์ที่ถูกยุบรวมแล้ว
4. ทำการเปรียบเทียบค่า 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" ในตารางตามช่องที่มีตัวเลขในแถวและคอลัมน์เหมือนกัน

ขั้นตอนที่ 1

	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" เพียงแถวเดียว แล้วทำการเลือกแถวนั้นๆ เนื่องจากเป็นแถวที่จำเป็นต้องเลือก หากไม่เลือกจะทำให้ไม่ครอบคลุมครบทุกคอลัมน์
• ทำเครื่องหมายทั้งในแนวแถวและคอลัมน์ที่เลือก

ขั้นตอนที่ 2

	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" ที่อยู่ในคอลัมน์เดียวกันทั้งหมด เพื่อแสดงว่าคอลัมน์นั้นๆ ได้ถูกครอบคลุมโดยแถวที่เลือกไปแล้ว

ขั้นตอนที่ 3

	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

	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

ดังนั้น นิพจน์ตรรกศาสตร์ในรูปอย่างง่าย คือ :$f_{A,B,C,D}=AB'D'+AC'D+A'B$

รหัสเทียม

ตัวอย่างรหัสเทียม

ตัวอย่างรหัสเทียมสำหรับการทำงานของขั้นตอนวิธีควิน-แมกคลัสกีย์

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

ตัวอย่างโปรแกรม

ตัวอย่างโปรแกรมที่เขียนในภาษาซี

#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
using namespace std;

int MIN_BITS = 4;		//minimum bits to print
vector<unsigned> input_values;	
bool show_mid = false;		//show middle process

struct B_number{
	unsigned number;
	unsigned dashes;
	bool used;
};

vector<vector<B_number> > table;	//original table
vector<vector<B_number> > p_group;	//mid process table
vector<vector<B_number> > final_group;	//final table
vector<B_number> printed_numbers; //avoid printing the same final numbers 

//----------------------------------------------------------
unsigned count_1s(unsigned number); //count the number of 1s in a number
void print_binary(unsigned number);//print the number in binary
void create_table();		//create original table sorted by the number of 1s
void print_table();		//print the table
B_number init_B_number(unsigned n,int d, bool u);//initialize a B_number
void create_p_group();		//create mid process table
void print_p_group();		//print it
void print_p_binary(unsigned n, unsigned d);//print the mid table (with -'s)
void create_final_group();		//create final table
void print_final_group();		//print final table with -'s and unused terms
bool is_printed(B_number n);		//dont print terms that were already printed
void init();				//start the table making and printing
void getinput();			//get input from user
unsigned count_bits(unsigned n);	//min bits to represent a number
//----------------------------------------------------------

int main(int argc, char *argv[]) {

	/* allow command line calling with arguments -m -b X
	   where X is a number. order or -m and -b X does not
	   matter*/
	cout<<"\nQMCS - Quine McCluskey Simplifier\n";
	if(argc >= 2)
	{
		string arg = argv[1];
		if(arg.find("-m") != -1) {
			show_mid = true;
			if(argc>=3) {
				arg = argv[2];
				if(arg.find("-b") != -1)
					MIN_BITS = atoi(argv[3]);
			}
		}
		else if(arg.find("-h") != -1) {
			cout<<"-b X\tminimum bits should be X.\n"
			    <<"-m  \tshow mid process computation.\n"
			    <<"-h  \tshow this.\n";
			return 0;
		
		}
		else {
			if(arg.find("-b") != -1  && argc >=3)
				MIN_BITS = atoi(argv[2]);

			if(argc >=4) {
			       	arg = argv[3];
				if(arg.find("-m") != -1) 
					show_mid = true;
			}
			else
			{
				cout<<"Invalid argument\n"
				    <<"-b X\tminimum bits should be X.\n"
				    <<"-m  \tshow mid process computation.\n"
				    <<"-h  \tshow this.\n";
				return 0;
			}
		}
	}

	getinput();
	init();
	
	return 0;
	
}

/* counts 1s by getting the LSB (%2) and then shifting until 0 */
unsigned count_1s(unsigned number) {
	short bit =0;
	int count = 0;
	while(number>0)	{
		bit = number%2;
		number>>=1;
		if(bit) {
			count++;
		}
	}
	return count;
}
/*get LSB, arrange it in array, the print array in reverse order so MSB is on
the left */
void print_binary(unsigned number) {
	unsigned bits[MIN_BITS];
	int count = 0;
	
	while(number>0||count<MIN_BITS)	{
		bits[count] = number%2;
		number>>= 1;
		count++;
	}
	for(int i=count-1;i>=0;i--)
		cout<<bits[i];
}
/*creating first table: append current number to the array located in
table[number of 1s f this number]*/
void create_table() {
	short tmp;
	B_number temp_num;
	for(int i=0;i<input_values.size();i++) {
		tmp = count_1s(input_values[i]);
		if(tmp+1>table.size())
			table.resize(tmp+1);
		
		temp_num = init_B_number(input_values[i],0,false);
		table[tmp].push_back(temp_num);
	}
}

void print_table() {
	
	cout<<endl<<"COMPUTING:"<<endl;
	for(int i=0;i<table.size();i++)	{
		cout<<i;
		for(int j=0;j<table[i].size();j++) {
			cout<<"\tm"<<table[i][j].number<<"\t";
			print_binary(table[i][j].number);
			cout<<endl;
		}
		cout<<"\n-------------------------------------"<<endl;
	}
}
/* initialize a B_number variable - like a constructor */
B_number init_B_number(unsigned	n,int d, bool u) {
	B_number num;
	num.number = n;
	num.dashes = d;
	num.used = u;
	return num;
}
/*like the original table, but the paring of numbers from the original table-
dashes are represented by a 1. for example original A=0011 B=1011, new number 
is -011 which is represented as C.number=A&B=0011,C.dashes=A^B=1000*/
void create_p_group() {
	short tmp;
	B_number temp_num;
	unsigned temp_number, temp_dashes;
	for(int i=0;i<table.size()-1;i++) {
		for(int j=0;j<table[i].size();j++) {
			for(int k=0;k<table[i+1].size();k++) {
				temp_number = table[i][j].number & table[i+1][k].number;
				temp_dashes = table[i][j].number ^ table[i+1][k].number;
				
				if(count_1s(temp_dashes)==1) {
					table[i][j].used = true;
					table[i+1][k].used = true;
					
					
					tmp = count_1s(temp_number);
					
					if(tmp+1>p_group.size())
						p_group.resize(tmp+1);
					
					temp_num = init_B_number(temp_number, temp_dashes, false);
					p_group[tmp].push_back(temp_num);
				}
			}
		}
	}
}

void print_p_group() {
	cout<<endl<<"MID PROCESS COMPUTATION:"<<endl;
	
	for(int i=0;i<p_group.size();i++) {
		cout<<i;
		for(int j=0;j<p_group[i].size();j++) {
			cout<<"\t\t";
			print_p_binary(p_group[i][j].number,p_group[i][j].dashes);
			cout<<endl;
		}
		cout<<"\n-------------------------------------"<<endl;
	}
	
}
/*print a number such as -001; this allocates bits in an array dash=2 then 
prints reverse array */
void print_p_binary(unsigned n, unsigned d) {
	unsigned bits[MIN_BITS];
	int count = 0;
	
	while(n>0||count<MIN_BITS) {
		if(!(d%2))
			bits[count] = n%2;
		else
			bits[count] = 2;
		
		n >>= 1;
		d >>= 1;
		count++;
	}
	for(int i=count-1;i>=0;i--) {
		if(bits[i]!=2)
			cout<<bits[i];
		else
			cout<<"-";
	}
}
/*creates final table. works like p_group(). example; in p_group you have: 
A=-001 B=-011 -> C= -0-1 which will be represented as 
C.number=A&B=0001&0011=0001, and C.dashes=A^B^A.dashes=0001^0011^1000=1010. 
Computation is done only when A.dashes = b.dashes*/
void create_final_group() {
	short tmp;
	B_number temp_num;
	unsigned temp_number, temp_dashes;
	for(int i=0;i<p_group.size()-1;i++) {
		for(int j=0;j<p_group[i].size();j++) {
			for(int k=0;k<p_group[i+1].size();k++) {
				if(p_group[i][j].dashes == p_group[i+1][k].dashes) {
					temp_number = p_group[i][j].number & p_group[i+1][k].number;
					temp_dashes = p_group[i][j].number ^ p_group[i+1][k].number;
					if(count_1s(temp_dashes)==1) {
						temp_dashes^= p_group[i][j].dashes;
						
						p_group[i][j].used = true;
						p_group[i+1][k].used = true;
						
						tmp = count_1s(temp_number);
						
						if(tmp+1>final_group.size())
							final_group.resize(tmp+1);
						
						temp_num = init_B_number(temp_number, temp_dashes, true);
						final_group[tmp].push_back(temp_num);
					}
				}
			}
		}
	}
}
/*print all the values from the final table, except for duplicates.
  print all the unused numbers from original table and mid process table*/
void print_final_group() {
	cout<<endl<<"FINAL:\n-------------------------------------"<<endl;
	int i,j;
	for(i=0;i<final_group.size();i++) {
		for(j=0;j<final_group[i].size();j++) {
			if(!is_printed(final_group[i][j])) {
				print_p_binary(final_group[i][j].number,final_group[i][j].dashes);
				cout<<endl;
				printed_numbers.push_back(final_group[i][j]);
			}
		}
	}
	for(i=0;i<p_group.size();i++) {
		for(j=0;j<p_group[i].size();j++) {
			if(!p_group[i][j].used) {
				print_p_binary(p_group[i][j].number,p_group[i][j].dashes);
				cout<<endl;
			}
		}
	}
	for(i=0;i<table.size();i++) {
		for(j=0;j<table[i].size();j++) {
			if(!table[i][j].used) {
				print_p_binary(table[i][j].number,table[i][j].dashes);
				cout<<endl;
			}
		}
	}
	cout<<"-------------------------------------"<<endl;
}
/*used to avoid printing duplicates that can exist in the final table*/
bool is_printed(B_number n) {
	for(int i=0;i<printed_numbers.size();i++)
		if(n.number==printed_numbers[i].number && n.dashes == printed_numbers[i].dashes)
			return true;
	
	return false;
}
/*initialize all table*/
void init() {
	table.resize(1);
	p_group.resize(1);
	final_group.resize(1);
	create_table();
	print_table();
	create_p_group();
	if(show_mid)
		print_p_group();
	create_final_group();
	print_final_group();
}

void getinput() {
	unsigned in;
	int num_bits=0;
	cout<<"\nInput value followed by ENTER[^D ends input]\n> ";
	while(cin>>in) {
		input_values.push_back(in);
		num_bits = count_bits(in);	
		if(num_bits>MIN_BITS)
			MIN_BITS = num_bits;
		cout<<"> ";
	}
}
/*return min number of bits a number is represented by. used for best output*/
unsigned count_bits(unsigned n) {
	short bit =0;
	int count = 0;
	while(n>0) {
		bit = n%2;
		n>>=1;
		count++;
	}
	return count;
}

ดูเพิ่ม

• นิพจน์
• ตรรกศาสตร์
• แผนผังคาร์โนห์
• พีชคณิตแบบบูล
• POS และ SOP
• วงจรเชิงผสม
• ตารางค่าความจริง

อ้างอิง

• 85-89.http://www.freebookzone.com/fetch.php?bkcls=hw_logic&bkidx=7 Contemporary Logic Design

เชื่อมต่อภายนอก

• การลดทอนฟังก์ชัน
• การลดรูปสมการบูลลีน
• Quine-McCluskey Algorithm
• Minimization
• ตัวอย่างขั้นตอนวิธีของควินและแมกคลัสกีย์
• รหัสเทียมของขั้นตอนวิธีควินและแมกคลัสกีย์
• เกี่ยวกับควิน-แม็กคลัสกีย์
• โปรแกรมลดรูปแบบควิน-แม็กคลัสกีย์แบบออนไลน์
• ตัวอย่างโปรแกรมภาษาซี
• ตัวอย่างโปรแกรมออนไลน์

ความรู้สึกต่อขั้นตอนวิธี

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