1. 퀸 맥클러스키 방법 (Quine-McCluskey 방법)
ㅇ 특징
- 카르노맵은 그림을 그려 사용하지만, 이 방식은 도표를 사용함
- 사실상, 내부적인 간략화 원리는 카르노맵과 동일
- 비록, 처리과정이 다소 복잡하고 시각화에 불편하지만,
- 그러나, 좀더 단계적이고 체계적이어서,
. 알고리즘 및 프로그래밍화 용이
- 특히, 항의 수가 많아 카르노맵 사용이 어려운 경우에 유리함
ㅇ 기본 원리
- 간략화 원리
. 각 항을 2진수로 표현
. 서로 인접한 항끼리 비교하여, 단 하나의 비트만 다른 경우에,
해당 변수를 제거하고 대시('-') 처리함
즉, 간략화된 변수는 대시 처리
. 여기서, 더 이상 간단히 되지 않는 항은, 주항 (PI, Primary Implicant)이 됨
- 인덱스 분류
. 2진수로 표현된 항에 포함된 1의 개수
. 각 항을 2진수로 나타냈을 때, 포함된 1의 개수를 기준으로 그룹화함
. 인접 그룹끼리만 결합 가능함 (1개짜리 그룹과 2개짜리 그룹 등)
ㅇ 크게, 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) 최종 간략식 완성