1. 퀸 맥클러스키 방법 (Quine-McCluskey 방법)
ㅇ 최소항을 2진수로 체계적으로 결합하여, 부울식의 간략화에 이르는,
- 도표 기반의 불 대수 간략화 방법 (카르노 맵의 알고리즘적 방법)
* 여기서 "표(table) 형태"라는 말은,
. 카르노 맵처럼 인접한 칸을 눈으로 찾는 것이 아니라,
. 행·열 형식의 표에 최소항을 정리하고, 단계적으로 비교·결합하는 방식을 말함
2. 퀸 맥클러스키 방법의 특징
ㅇ 카르노 맵은 그림을 이용하지만, 퀸-맥클러스키 방법은 도표를 이용함
- 인접한 최소항을 결합하여 간략화한다는 원리는 카르노 맵과 동일
- 처리 과정은 다소 복잡하고 시각성은 떨어짐
- 그러나 절차가 단계적이고 체계적이어서 알고리즘 구현 및 프로그래밍에 용이
- 특히, 변수나 최소항의 수가 많아 카르노 맵 적용이 어려운 경우에 유리함
3. 퀸 맥클러스키 방법에서, 부울식의 간략화 例) : (부울 변수 3개인 경우)
ㅇ 최소항 번호 목록
- A'B'C' => 0 0 0 => m0
- A'B'C => 0 0 1 => m1
- A'B C' => 0 1 0 => m2
- A'B C => 0 1 1 => m3
- A B'C' => 1 0 0 => m4
- A B'C => 1 0 1 => m5
- A B C' => 1 1 0 => m6
- A B C => 1 1 1 => m7
ㅇ 예로써,
- F(A,B,C) = A'B'C' + A'B'C + A'BC' + AB'C + ABC' + ABC
= ∑ m(0,1,2,5,6,7)
ㅇ 1의 개수별로 도표에 분류
- 0개 : (000)
- 1개 : (001), (010)
- 2개 : (101), (110)
- 3개 : (111)
ㅇ 도표 내 인접 그룹 간에 1 비트만 다른 최소항끼리 결합
- (000) + (001) → (00-) : m0, m1
- (000) + (010) → (0-0) : m0, m2
- (001) + (101) → (-01) : m1, m5
- (010) + (110) → (-10) : m2, m6
- (101) + (111) → (1-1) : m5, m7
- (110) + (111) → (11-) : m6, m7
* 이들 6개가, 더 이상 서로 결합할 수 없는 항으로,
. 주항 또는 주요 소항(Prime Implicant)이라고 함
* 여기서, 모든 최소항(m0,m1,m2,m5,m6,m7)을 덮도록,
. 필요한 주요 소항만 선택하면 됨
ㅇ 예를 들어, 다음 네 개를 선택 가능
- (00-) : m0, m1
- (0-0) : m0, m2
- (1-1) : m5, m7
- (11-) : m6, m7
ㅇ 이에 대응하는 최소 부울식은, F = A'B' + A'C' + AC + AB
- 다만, 퀸 맥클러스키 방법에서는, 하나의 부울 함수에 대해,
. 최소 해가 둘 이상 나오는 경우도 흔함
- 위 예도 선택 방법에 따라 다른 조합의 주요 소항으로,
. 동일한 최소 항 개수의 해를 얻을 수 있음
ㅇ 결국, 퀸 맥클러스키 방법에서는,
- 각 최소항을 2진수로 표현한 후,
- 1의 개수별로 도표에 분류하고,
- 1 비트만 다른 최소항끼리 반복적으로 결합하여,
- 최종적으로 최소 부울식을 구함
4. 퀸 맥클러스키 방법의 기본 원리
ㅇ 간략화 원리
- 각 항을 2진수로 표현
- 서로 인접한 항끼리 비교하여, 단 하나의 비트만 다른 경우에,
. 해당 변수를 제거하고 대시('-') 처리함
. 즉, 간략화된 변수는 대시 처리
- 여기서, 더 이상 간단히 되지 않는 항은,
. 주항 (PI, Primary Implicant)이 됨
ㅇ 인덱스 분류
- 2진수로 표현된 항에 포함된 1의 개수
- 각 항을 2진수로 나타냈을 때, 포함된 1의 개수를 기준으로 그룹화함
- 인접 그룹끼리만 결합 가능함 (1개짜리 그룹과 2개짜리 그룹 등)
5. 퀸 맥클러스키 방법의 단계별 구성
ㅇ 크게, 2 단계 구성 (expansion, covering)
- 주항 결정 (PI 식별 단계 : Expansion 단계)
. 2진수 표현과 인덱스 분류를 이용해 가능한 모든 결합을 수행하여,
. 더 이상 결합할 수 없는 항(주항, PI)을 식별함
- 최소화 과정 (PI 선택 단계 : Covering 단계)
. 주항들 중 필수 주항(Essential Prime Implicant)을 먼저 선택하고,
. 나머지 항들은 필요한 최소 개수의 주항으로 덮어(cover),
. 최종 간략식을 완성함
ㅇ 흐름 순서의 상세 내역
- 1) 모든 항을 2진수로 표현
- 2) 1의 개수에 따라 그룹화
- 3) 인접 그룹끼리 비교하여 가능한 결합 수행
. 하나의 비트만 다른 경우 : 대시('-')로 표시하고 결합
- 4) 결합된 항은 체크(mark)하고,
. 체크되지 않은 항은 주항(Prime Implicant, PI)으로 기록
- 5) 결합을 반복 → 더 이상 결합할 수 없을 때까지
- 6) 모든 주항(PI)들을 수집
- 7) 주항들을 사용해 최종 식을 최소화
. 필수 주항(Essential Prime Implicant)을 먼저 선택
. 나머지는 최소한의 주항 조합으로 커버
- 8) 최종 간략식 완성