콰인-매클러스키 알고리즘

콰인-매클러스키 알고리즘(Quine-McCluskey algorithm)은 논리식을 최소화하는 알고리즘이다. 내부적으로는 카노 맵과 동일하지만, 그림을 그려서 맞추는 카노 맵과 달리 표를 사용하기 때문에 컴퓨터에서 쉽게 돌릴 수 있다. 또한 논리함수의 최소 형태를 결정론적으로 구할 수 있다.

알고리즘은 다음 두 단계로 구성된다.

1. 주어진 함수의 후보항(Prime Implicants)들을 모두 구한다.
2. 후보항들을 이용해서 후보항 표에서 필수항(Essential Prime Implicant)을 구한다.

복잡도

카노 맵과 달리, 콰인-매클러스키 알고리즘을 사용하면 변수가 4개를 넘더라도 효율적으로 논리 최적화할 수 있다. 그러나 논리 최적화 문제가 기본적으로 NP-완전이므로, 콰인-매클러스키 알고리즘은 변수의 개수가 제한된 경우에만 효율적으로 실행할 수 있다. 콰인-매클러스키 알고리즘의 실제 실행시간은 입력에 대해 지수적으로 증가한다. n 개의 변수가 있을 때, 후보항 개수의 상한은 3ⁿ/n임을 보일 수 있다. n = 32이면 6.1 * 10¹⁴, 즉 617조 개의 후보항이 존재한다. 변수의 개수가 많을 때는 발견법으로 풀 수밖에 없다.

예제

1 단계: 후보항 찾기

다음 함수를 최소화 해보자:

f(A, B, C, D) = ${\displaystyle \Sigma }$(4, 8, 9, 10, 11, 12, 14, 15)

     A B C D   f
 m0  0 0 0 0   0
 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   0
 m6  0 1 1 0   0
 m7  0 1 1 1   0
 m8  1 0 0 0   1
 m9  1 0 0 1   1
m10  1 0 1 0   1
m11  1 0 1 1   1
m12  1 1 0 0   1
m13  1 1 0 1   0
m14  1 1 1 0   1
m15  1 1 1 1   1

최소항(minterm)들의 합으로 표현하면, 쉽게 곱의 합 정규형 표현(canonical sum of products expression)을 얻는다.

${\displaystyle f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+ABCD'+ABCD}$

물론 이것은 최소가 아닐것이다. 따라서 모든 최소항들을 일단 최소항 표에 넣어 최적화 한다.

1의 개수	최소항	2진수 표기
1	m4	0100
	m8	1000
2	m9	1001
	m10	1010
	m12	1100
3	m11	1011
	m14	1110
4	m15	1111

여기서 최소항을 다른 최소항과 결합한다. 만일 두 항이 한 자리만 차이난다면, 그 자리를 -로 대체한다(이것은 그 자리가 영향을 끼치지 않는다는 것을 의미한다). 더 이상 결합하지 못하는 항(pi = prime implicant)들은 *로 표시하였다.

	section	후보항	bit 표기	pi
크기가 1인 후보항	1	m4	0100
		m8	1000
	2	m9	1001
		m10	1010
		m12	1100
	3	m11	1011
		m14	1110
	4	m15	1111
크기가 2인 후보항	1	m(4,12)	-100	*
		m(8,9)	100-
		m(8,10)	10-0
		m(8,12)	1-00
	2	m(9,11)	10-1
		m(10,11)	101-
		m(10,14)	1-10
		m(12,14)	11-0
	3	m(11,15)	1-11
		m(14,15)	111-
크기가 4인 후보항	1	m(8,9,10,11)	10--	*
		m(8,10,12,14)	1--0	*
	2	m(10,11,14,15)	1-1-	*

2 단계: 후보항 표

더는 어떤 항도 결합할 수 없을 때, 필수항 표(essential prime implicant table)를 만든다. 이전 과정에서 얻은 최후의 후보항들을 표에 세로로 늘어놓고, 가로로는 앞에서 얻었던 최소항들을 나열한다.

	4	8	9	10	11	12	14	15
m(4,12)*	X					X
m(8,9,10,11)*		X	X	X	X
m(8,10,12,14)*		X		X		X	X
m(10,11,14,15)*				X	X		X	X

필수항을 *로 표시하였다. 만일 후보항을 더 이상 없앨 수 없다면 남은 후보항은 필수항이다. 3번째의 항은 1, 2가 표현하는 최소항에 의해 표현되므로 없앨 수 있다. 1, 3, 4번 항을 택하는 것도 다른 답이 된다. 가끔 후보항들이 모든 최소항을 표현해내지 못할 때가 있는데, 그럴 때는 추가 과정이 필요하다. 가장 간단한 "추가 과정"은 모두 시도해보는 것이지만, 더 체계적인 방법으로 페트릭의 방법(Petrick's Method)이 있다. 이 예제에서 최소 후보항은 모든 최소항을 표현해내므로 아래와 같은 식을 얻을 수 있다.

${\displaystyle f_{A,B,C,D}=BC'D'+AB'+AC}$

위의 식은 원래의 식과 논리적으로 동치이다.

${\displaystyle f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+ABCD'+ABCD}$

외부 링크

• (영어) 콰인-매클러스키 알고리즘 강좌
• (영어) 불린 함수 단순화 보관됨 2012-07-12 - 웨이백 머신
• (영어) 자바 애플릿
• (영어) 파이썬 구현