[디지털 논리] 5 콰인-맥클러스키 알고리즘(Quine_McCluskey Algorithm)

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

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

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

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

• 주어진 함수의 주함축항들을 모두 구한다
• 후보항들을 이용해서 주함축함 표에서 필수 주함축항을 구한다

최소항 결합 원리

이 알고리즘의 핵심은 정확히 하나의 변수만 다를 때 합친다는 단순한 원리에서 시작한다

결합의 기본 논리 두 개의 항이 정확히 한 변수에서만 차이가 날 때 결합할 수 있다. 논리식으로 보면 다음과 같다.

• 2개 변수: $XY+X{Y}^{\prime }=X$
• 3개 변수: $XYZ+XY{Z}^{\prime }=XY$ 이 모든 가능한 최소항 쌍을 하나하나 비교해야 한다

이진 표기법과 대시(-) 활용 알고리즘에서는 대수식보다는 컴퓨터가 처리하기 쉬운 이진수 표기를 주고 사용한다

• **이진수 표기 예시:

• 결과값에서 나타나는 대시의 의미는 두 항을 결합하면서 사라진 변수를 의미한다

주함축함 도출

이 단계의 목적은 비교 횟수를 줄이기 위해 최소항들을 2진수 내 1의 개수에 따라 그룹화하는 것이다

예시: $f(a,b,c,d)=\sum m(0,1,2,5,6,7,8,9,10,14)$

오직 인접한 그룹끼리만 비교하여 비트가 하나만 다른 경우를 찾아 결합한다. 그리고 이제 주함축함(PI)를 찾아낸다

중복항 제거

모든 PI를 다 더한다고 해서 가장 간소화된 식은 아니다. 여기서는 합의 정리를 사용하여 중복되는 항을 제거한다

예시:

• 찾아낸 PI들을 나열하고, 다른 항들의 조합으로 중복된 항들을 지워나간다
• 최종 결과: $f=a^{\prime }bd+b^{\prime }{c}^{\prime }+c{d}^{\prime }$

주함축항 차트

필수 주함축항(EPI) 찾기: 이 단계의 핵심은 수많은 주함축항 중에서 식에 반드시 포함되어야 하는 항이 무엇인지 찾아내는 것이다

• 찾는 방법
  • 세로 열을 하나씩 확인한다
  • x가 단 하나만 표시된 열을 찾는다
  • 해당 x가 속한 가로 행의 주함축항이 바로 필수 주함축함($\otimes$)이 된다
  • 예시:

최소 식 구성하기: 필수 주함축항을 먼저 선택한 후, 아직 커버되지 않은 남은 최소항들을 어떻게 처리할지 결정하는 단계이다

방법:

• 먼저 모든 EPI을 선택한다
• 선택된 필수 주함축항들이 커버하는 모든 최소항을 지운다
• 남은 최소항들이 무엇인지 확인한다
• 남은 최소항들을 가장 적은 수의 주함축항으로 커버할 수 있는 조합을 선택한다
• 예시

• 최종 간소화된 식: $f=b^{\prime }{c}^{\prime }+c{d}^{\prime }+a^{\prime }bd$

예시

주함축항 추출

첫 번째 해법

• 차트 특징: 모든 열(최소항)에 ‘x’가 2개씩 있다. 즉, 어떤 최소항을 단독으로 책임지는 필수항이 하나도 없는 ‘순환 구조(Cyclic)’ 상태이다
• 첫 번째 결과 식: $F=a^{\prime }{b}^{\prime }+b{c}^{\prime }+ac$

또 다른 최소 해법

• 0번 열을 포함하는(커버하는) 또 다른 주함축항부터 다시 시작해 보면

• 또 다른 최소 해법: $F=a^{\prime }{c}^{\prime }+b^{\prime }c+ab$

페트릭 방법(Petric’s Method)

이 방법의 핵심은 모든 최소항이 적어도 하나의 주함축항에 의해 덮여야 한다는 조건을 하나의 커다란 논리식 P로 만드는 것이다

페트릭 방법 정의

주함축항 차트로부터 모든 최소 곱들의 합(SOP)을 결정하는 체계적인 기술이다

논리식 P 구성 방법:

• 각 최소항(Minterm) 열을 본다
• 해당 최소항을 포함하는 주함축항들을 합(+)으로 묶는다
• 모든 최소항에 대한 합들을 다시 곱($\cdot$)으로 연결한다
• 예시:

• 결과적으로 $P=(P_1+P_2)(P_1+P_3)(P_2+P_4)(P_3+P_5)(P_4+P_6)(P_5+P_6)=1$ 이라는 식이 완성된다

식 전개 및 최적해 선택 세워진 식 P를 불 대수 법칙을 이용해 전개하여 가장 단순한 조합을 찾는 과정이다

• 계산 과정:
  • 분배 법칙 사용: $(X+Y)(X+Z)=X+YZ$ 법칙을 사용해 괄호를 줄여나간다
  • 전개: 모든 항을 곱하여 전개한다
  • 중복 제거: $X+XY=X$ (흡수 법칙)를 사용하여 불필요하게 긴 항들을 지운다

예시:

• 단순화된 결과: $P=P_1{P}_4{P}_5+P_1{P}_2{P}_5{P}_6+P_2{P}_3{P}_4{P}_5+P_1{P}_3{P}_4{P}_6+P_2{P}_3{P}_6$
• 최종 선택
  • 가장 경제적인 식을 원하므로, 주함축항의 개수가 가장 적은 조합을 고른다
  • 기서는 3개의 항만 사용하는 $P_1,P_4,P_5$ 또는 **$P_2,P_3,P_6$**가 최적의 선택이다
• 최종 논리식:
  • $F=a^{\prime }{b}^{\prime }+b{c}^{\prime }+ac$ (첫 번째 조합)
  • $F=a^{\prime }{c}^{\prime }+b^{\prime }c+ab$ (두 번째 조합)

불완전 정의 함수

무관항을 포함한 결합 이 단계에서는 식을 최대한 간소화하기 위해 무관항을 최소항처럼 취급하여 그룹화한다

• 함수 정의: $F(A,B,C,D)=\sum m(2,3,7,9,11,13)+\sum d(1,10,15)$
• 핵심 원리: 첫 번째 비교 단계(Column 1)를 작성할 때는 무관항($d$)을 일반 최소항($m$)과 똑같이 포함시켜서 비교한다
  • 무관항을 포함해야 더 많은 비트를 ’-‘로 처리하여 더 큰 묶음(주함축항)을 만들 수 있기 때문이다
• 결과: 결합 과정을 거쳐 4개의 주함축항(PI)이 추출된다
• 예시:

주함축항 차트 작성* 여기서 가장 중요한 규칙이 나온다. 주함축항 차트를 만들 때는 무관항을 고려하지 않는다

• 핵심 원리: 차트의 가로축(열)에는 오직 원래의 최소항($m$)들만 적습니다. 무관항($d$)은 적지 않다. 왜냐하면 무관항은 식을 줄이는 ‘도구’일 뿐, 우리가 반드시 결과식에 포함시켜야 하는 ‘의무’는 없기 때문이다
• 예시: