콰인-매클러스키 알고리즘 문서 원본 보기

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

알고리즘은 다음 두 단계로 구성된다.
# 주어진 함수의 후보항(Prime Implicants)들을 모두 구한다.
# 후보항들을 이용해서 후보항 표에서 필수항(Essential Prime Implicant)을 구한다.

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

==예제==
===1 단계: 후보항 찾기===
다음 함수를 최소화 해보자:
:''f''(''A'', ''B'', ''C'', ''D'') = <math>\Sigma</math>(4, 8, 9, 10, 11, 12, 14, 15)

      <u>A B C D   f</u>
  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)을 얻는다.

<math>f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD</math>

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

{| cellpadding="10", border="1"
|-
! 1의 개수 !! 최소항 !! 2진수 표기
|-
! rowspan="2" | 1
| m4 || 0100
|-
| m8 || 1000
|-
! rowspan="3" | 2
| m9 || 1001
|-
| m10 || 1010
|-
| m12 || 1100
|-
! rowspan="2" | 3
| m11 || 1011
|-
| m14 || 1110
|-
! 4
| m15 || 1111
|}

여기서 [[최소항]]을 다른 [[최소항]]과 결합한다. 만일 두 항이 한 자리만 차이난다면, 그 자리를 -로 대체한다(이것은 그 자리가 영향을 끼치지 않는다는 것을 의미한다). 더 이상 결합하지 못하는 항(pi = prime implicant)들은 *로 표시하였다.
{| cellpadding="5", border="1"
|-
|  || section || 후보항 || bit 표기 || pi
|-
| rowspan="8" | 크기가 1인 후보항
| rowspan="2" | 1 || m4 || 0100 || 
|-
| m8 || 1000 ||
|-
| rowspan="3" | 2 || m9 || 1001 || 
|-
| m10 || 1010 || 
|-
| m12 || 1100 || 
|-
| rowspan="2" | 3 || m11 || 1011 || 
|-
| m14 || 1110 || 
|-
| 4 || m15 || 1111 || 
|-
| rowspan="10" | 크기가 2인 후보항
| rowspan="4" | 1 || m(4,12) || -100 || *
|-
| m(8,9) || 100- || 
|-
| m(8,10) || 10-0 ||
|-
| m(8,12) || 1-00 || 
|-
| rowspan="4" | 2 || m(9,11) || 10-1 || 
|-
| m(10,11) || 101- || 
|-
| m(10,14) || 1-10 || 
|-
| m(12,14) || 11-0 ||
|-
| rowspan="2" | 3 || m(11,15) || 1-11 || 
|-
| m(14,15) || 111- || 
|-
| rowspan="3" | 크기가 4인 후보항
| rowspan="2" | 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)를 만든다. 이전 과정에서 얻은 최후의 후보항들을 표에 세로로 늘어놓고, 가로로는 앞에서 얻었던 [[최소항]]들을 나열한다.

{| border="1" cellpadding="3"
| || 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)이 있다. 이 예제에서 최소 후보항은 모든 최소항을 표현해내므로 아래와 같은 식을 얻을 수 있다.

<math>f_{A,B,C,D} = BC'D' + AB' + AC</math>

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

<math>f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD</math>

== 외부 링크 ==
* {{언어링크|en}} [https://web.archive.org/web/20060517214533/http://134.193.15.25/vu/course/cs281/lectures/simplification/quine-McCluskey.html 콰인-매클러스키 알고리즘 강좌]
* {{언어링크|en}} [http://www.dei.isep.ipp.pt/~acc/bfunc/ 불린 함수 단순화] {{웹아카이브|url=https://web.archive.org/web/20120712042144/http://www.dei.isep.ipp.pt/~acc/bfunc/}}
* {{언어링크|en}} [https://web.archive.org/web/20080130134530/http://www25.brinkster.com/denshade/QuineMcCluskey.html 자바 애플릿]
* {{언어링크|en}} [http://cheeseshop.python.org/pypi/qm/0.1 파이썬 구현]

{{전거 통제}}

[[분류:불 대수]]