Quine–McCluskey Method (카르노 맵의 대안적 논리식 최소화 방법)

Quine–McCluskey 방법(줄여서 Q-M 방법)은 논리 회로의 불 대수식을 체계적으로 최소화하는 알고리즘적 방법이다.
카르노 맵(K-map)은 시각적으로 간단하지만, 입력 변수가 많아지면(5개 이상) 사람이 직접 최소항을 묶기 어렵다.
그럴 때 Q-M 방법은 컴퓨터가 자동으로 수행할 수 있는 체계적인 절차로 대체된다.

---

기본 개념

Q-M 방법은 크게 두 단계로 구성된다.

1. 소항(Minterm)을 그룹화하고, 인접항을 결합하여 프라임 임플리컨트(Prime Implicant, PI)를 찾는 단계
2. PI 중에서 필요한 것만 남기는 최소 커버(Minimum Cover) 선택 단계

---

Step 1: Minterm Grouping (그룹화)

주어진 불함수의 1이 되는 Minterm 번호를 이진수로 변환한 뒤,
그 이진수에서 1의 개수에 따라 그룹으로 나눈다.

예시 : f(A,B,C) = Σ(0,1,2,5,6,7)

이항 변환 :

Minterm	Binary	1의 개수
0	000	0
1	001	1
2	010	1
5	101	2
6	110	2
7	111	3

→ 그룹화 :

• G0: 000
• G1: 001, 010
• G2: 101, 110
• G3: 111

---

Step 2: Combine Adjacent Groups (결합 단계)

서로 1개의 비트만 다른 항을 결합한다.
다른 비트 위치에는 ‘–’를 넣어 don’t care로 표시한다.

예시:
000 + 001 → 00–
001 + 101 → –01
010 + 110 → –10
101 + 111 → 1–1
110 + 111 → 11–

이 과정을 반복하며 더 이상 결합이 불가능할 때까지 수행한다.
결합되지 않은 항은 Prime Implicant (PI) 로 남는다.

---

Step 3: Prime Implicant Chart 작성

모든 PI를 행, minterm을 열로 하는 표를 만든다.
각 PI가 어떤 minterm을 포함하는지 표시한다.

PI	0	1	2	5	6	7
00–	✔	✔
–10			✔		✔
1–1				✔		✔

---

Step 4: Essential Prime Implicant 선택

특정 minterm을 유일하게 포함하는 PI는 반드시 포함해야 한다.
이것을 Essential Prime Implicant (EPI) 라 부른다.

이후 남은 minterm은 최소 커버 조합을 통해 덜 중요한 PI 중 일부를 선택해 완성한다.

---

최종 결과

위 예시에서 최소화 결과는 다음과 같다.

f(A,B,C) = A'C' + AC + B'C

---

Q-M 방법의 장점과 한계

구분	장점	단점
장점	- 체계적, 알고리즘 기반 → 자동화 가능 - K-map보다 확장성 높음	- 변수 수가 많을수록 계산량 급증 (2ⁿ 규모) - 실제로는 컴퓨터가 수행 (인간이 수동으로 하기엔 복잡)
적용 예시	- 4~10변수 논리함수 최적화 - 컴퓨터 기반 논리 합성 툴 (EDA Tool)

---

요약

단계	설명
1	Minterm을 1의 개수로 그룹화
2	인접 그룹끼리 결합, don’t care(-) 도입
3	Prime Implicant 표 작성
4	Essential PI 선택 및 최소 커버 결정

Quine–McCluskey 방법은 불 대수식을 체계적으로 최소화하는 절차적 알고리즘으로,
K-map의 논리적 확장이며 컴퓨터가 수행하기 적합한 논리 최적화 방식이다.