카르노맵(Karnaugh Map, K-map)은 부울 함수를 시각적으로 간소화하는 방법이다. 대수적으로 식을 정리하면 어떤 항을 묶어야 최소화되는지 한눈에 보이지 않지만, 카르노맵에서는 인접한 1들을 묶기만 하면 최소항이 자동으로 도출된다.
카르노맵은 진리표를 2차원 격자로 재배치한 것이다. 행과 열의 순서가 Gray 코드 순서로 되어 있어서, 격자 위에서 상하좌우로 인접한 셀은 항상 입력 변수 1개만 다르다.
2변수 함수 f(A, B)의 카르노맵은 2×2이다.
| A\B | 0 | 1 |
|---|---|---|
| 0 | m₀ | m₁ |
| 1 | m₂ | m₃ |
m₀ = A̅B̅, m₁ = A̅B, m₂ = AB̅, m₃ = AB에 대응된다. 각 셀에 함수값(0 또는 1)을 채운 뒤 인접한 1들을 묶으면 간소화된 식을 얻는다.
3변수는 2×4, 4변수는 4×4 격자가 된다. 5변수 이상은 3차원으로 확장하거나 맵 두 장을 겹쳐 비교해야 해서 실용적이지 않고, 보통 Quine-McCluskey 알고리즘을 쓴다.
인접항 묶기
카르노맵 간소화의 핵심은 인접한 1들을 가능한 한 크게 묶는 것이다.
- 묶을 수 있는 셀의 개수는 반드시 2의 거듭제곱(1, 2, 4, 8, …)이어야 한다.
- 묶음이 직사각형 형태여야 한다.
- 묶음이 클수록 제거되는 변수가 많아져 식이 간단해진다. 2ᵏ개의 셀을 묶으면 k개의 변수가 소거된다.
- 맵의 가장자리는 반대쪽 가장자리와 연결되어 있다. 왼쪽 끝과 오른쪽 끝, 위쪽 끝과 아래쪽 끝이 인접하다. 맵을 원통처럼 말아놓은 것과 같다.
- 하나의 셀이 여러 묶음에 포함될 수 있다.
- 모든 1이 최소한 하나의 묶음에 포함되어야 한다.
묶음에서 변하지 않는 변수만 남기면 그것이 해당 묶음의 곱항(product term)이 되고, 모든 묶음의 곱항을 OR하면 최소 곱의 합(minimum SOP) 식이 된다.
예시: 3변수
f(A, B, C) = ∑m(0, 2, 4, 5, 6)을 간소화해보자.
| A\BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 |
여기서 행은 A, 열은 BC이며 열 순서가 Gray 코드(00, 01, 11, 10)이다.
1이 있는 위치: (0,00), (0,10), (1,00), (1,01), (1,10).
- 묶음 1: (0,00), (0,10), (1,00), (1,10) — 4셀 묶음. A와 B가 변하고 C=0만 고정이므로 C̅가 된다.
- 묶음 2: (1,00), (1,01) — 2셀 묶음. C가 변하고 A=1, B=0이 고정이므로 AB̅가 된다.
결과: f = C̅ + AB̅
예시: 4변수
f(A, B, C, D) = ∑m(0, 1, 2, 5, 8, 9, 10)을 간소화해보자.
| AB\CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 0 | 1 |
| 01 | 0 | 1 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 |
| 10 | 1 | 1 | 0 | 1 |
- 묶음 1: 네 모서리 (00,00), (00,10), (10,00), (10,10) — B=0, D=0이 고정. B̅D̅
- 묶음 2: (00,00), (00,01), (10,00), (10,01) — B=0, C=0이 고정. B̅C̅
- 묶음 3: (00,01), (01,01) — C=0, D=1이 고정, A=0. A̅C̅D
결과: f = B̅D̅ + B̅C̅ + A̅C̅D
Don’t Care 조건
실제 회로 설계에서는 특정 입력 조합이 절대 발생하지 않는 경우가 있다. 예를 들어 BCD에서 1010~1111은 사용하지 않는 코드이다. 이런 경우 해당 셀의 출력을 0으로 고정할 필요 없이, 1로 취급하면 더 큰 묶음을 만들 수 있어 회로가 간단해진다.
don’t care는 맵에 X로 표기한다. 묶음을 만들 때 X를 1로 포함시키면 유리하면 포함하고, 아니면 무시한다.
f(A, B, C, D) = ∑m(1, 3, 7, 11, 15)에 don’t care d(0, 2, 5)가 있다고 하자.
| AB\CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | X | 1 | 1 | X |
| 01 | 0 | X | 1 | 0 |
| 11 | 0 | 0 | 1 | 0 |
| 10 | 0 | 0 | 0 | 0 |
don’t care를 활용하면:
- (00,00), (00,01), (00,11), (00,10)을 묶어 A̅B̅
- (00,01), (00,11), (01,01), (01,11)을 묶어 A̅D
- CD=11 열: m₃=1, m₇=1, m₁₅=1, m₁₁=1 → 4셀 묶음 → CD
결과: f = A̅B̅ + CD
don’t care 없이 간소화했다면 항이 더 많았을 것이다.
곱의 합과 합의 곱
지금까지 설명한 것은 1을 묶어 최소 곱의 합(SOP)을 구하는 방법이다. 반대로 0을 묶으면 최소 합의 곱(POS) 식을 얻는다. 0을 묶을 때 변하지 않는 변수를 합(OR)항으로 만들고, 모든 묶음의 합항을 AND하면 된다. SOP와 POS 중 항의 수가 적은 쪽을 고르면 게이트 수를 줄일 수 있다.
참고