01 카르노 맵이란?
불 대수보다 빠르고 직관적인 논리식 간소화 도구
디지털 회로 설계에서 논리식을 간소화하는 것은 매우 중요합니다. 불 대수(Boolean Algebra)를 직접 이용하는 방법은 복잡하고 실수하기 쉬우며, 간소화 여부를 검증하기 어렵다는 단점이 있습니다.
카르노 맵(Karnaugh Map)은 1953년 모리스 카르노(Maurice Karnaugh)가 소개한 방법으로, 함수의 최소항(minterm)들을 표의 각 칸에 배치하여 시각적으로 간소화를 수행할 수 있게 해줍니다.
📖 카르노 맵 핵심 개념
· 최소항(minterm) : 모든 변수가 포함된 곱(AND)의 항
· 무관항(don't care) : 입력이 결과에 영향을 미치지 않는 최소항으로 x 또는 d로 표시
· 그룹핑(Grouping) : 인접한 1들을 2의 거듭제곱(1, 2, 4, 8, 16) 개씩 묶는 것
02 카르노 맵 간소화 6가지 규칙
반드시 지켜야 할 그룹핑의 핵심 원칙
✅ 카르노 맵 간소화 6가지 규칙
① 인접한 1을 1, 2, 4, 8, 16개의 2의 거듭제곱 단위로 그룹을 지어 묶을 수 있다.
② 바로 이웃한 항들끼리 묶을 수 있다.
③ 반드시 직사각형 또는 정사각형의 형태로 묶어야 한다.
④ 변수를 최대한 줄이기 위해 최대한 크게 묶는다.
⑤ 간소화에 도움이 된다면 이미 묶인 1을 중복하여 묶어도 된다.
⑥ 무관항(don't care)은 그룹을 크게 만드는 데 도움이 되면 묶고, 그렇지 않으면 묶지 않는다.
✓ 핵심 원리
한 변수에서 서로 다른 값(0과 1)이 묶이면 그 변수는 제거됩니다.
예) A=0 행의 두 칸을 묶으면 → A가 제거되어 F = A
예) B=0과 B=1이 함께 묶이면 → B가 제거됩니다.
⚠️ 양쪽 끝은 서로 연결되어 있다!
카르노 맵은 토러스(원통형) 구조입니다. 좌측 끝 열과 우측 끝 열, 상단 행과 하단 행은 서로 인접한 것으로 간주합니다.
예) BC=00 열과 BC=10 열은 서로 묶을 수 있습니다.
03 2변수 · 3변수 카르노 맵
변수 수에 따른 맵 구성과 간소화 예제
▶ 2변수 카르노 맵
2변수(A, B) 카르노 맵은 2×2 격자로 구성되며, 최소항 m0~m3을 배치합니다. 열과 행의 순서는 한 비트씩만 변하는 그레이 코드(Gray Code) 순서(00→01→11→10)로 배열합니다.
| B↓ \ A→ | A (A=0) | A (A=1) |
| B (B=0) | m₀ (AB) | m₂ (AB) |
| B (B=1) | m₁ (AB) | m₃ (AB) |
▶ 3변수 카르노 맵
3변수(A, B, C) 카르노 맵은 2행 × 4열로 구성됩니다. 열 헤더(BC)는 00→01→11→10 순으로 배열합니다. 이때 11과 10의 순서를 주의해야 합니다(그레이 코드 순서).
| A \ BC | 00 | 01 | 11 | 10 |
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
▶ 3변수 간소화 예제
| 예제 | 카르노 맵 (그룹핑) | 결과 및 설명 | |||||||||||||||
| 예제 1 Σm(0,1,2,3) |
|
F = A A=0 행의 4칸을 하나로 크게 묶습니다. B와 C가 모두 제거됩니다. |
|||||||||||||||
| 예제 2 Σm(0,2,4,6) |
|
F = C 양쪽 끝 열(BC=00, 10)이 연결된 특성을 이용하여 4칸을 묶습니다. |
|||||||||||||||
| 예제 3 Σm(3,7) |
|
F = BC BC=11 열의 위아래 2칸을 묶습니다. A가 제거됩니다. |
|||||||||||||||
| 예제 4 Σm(3,5,6,7) |
|
F = AB + BC + AC m7(111)을 중심으로 각각 2칸씩 총 3번 중복하여 묶습니다. |
04 4변수 카르노 맵
4×4 격자로 최대 16개의 최소항을 처리
4변수(A, B, C, D) 카르노 맵은 4행 × 4열로 구성됩니다. 행 헤더(AB)와 열 헤더(CD) 모두 그레이 코드 순서(00→01→11→10)를 따릅니다.
| AB \ CD | 00 | 01 | 11 | 10 |
| 00 | 0 | 1 | 3 | 2 |
| 01 | 4 | 5 | 7 | 6 |
| 11 | 12 | 13 | 15 | 14 |
| 10 | 8 | 9 | 11 | 10 |
▶ 4변수 간소화 예제
| 예제 | 카르노 맵 (그룹핑) | 결과 및 설명 | |||||||||||||||||||||||||
| 중앙 4칸 Σm(5,7,13,15) |
|
F = BD 중앙의 2×2 형태 4칸을 묶습니다. A와 C가 제거됩니다. |
|||||||||||||||||||||||||
| 네 모서리 Σm(0,2,8,10) |
|
F = BD 상하/좌우 끝이 연결된 특성을 이용해 네 모서리의 1을 4칸 그룹으로 묶습니다. |
|||||||||||||||||||||||||
| 8칸 묶음 C=0 열 8칸 |
|
F = C CD=00, CD=10 열은 서로 이웃하므로 8칸을 하나로 묶어 변수 3개를 제거합니다. |
|||||||||||||||||||||||||
| 무관항(X) Σm(8,9) + d(10,11) |
|
F = AB 무관항(X) 2개를 1로 취급하여 AB=10 행의 4칸을 크게 묶어 간소화합니다. |
▶ 선택적 카르노 맵 (두 가지 정답이 가능한 경우)
어떤 카르노 맵은 묶는 방법에 따라 두 가지 이상의 동등하게 간소화된 정답이 존재할 수 있습니다. 또한 무관항(x)을 어떻게 활용하느냐에 따라서도 결과가 달라집니다.
✓ 무관항 활용 전략
무관항은 간소화에 유리할 때만 1로 취급하여 그룹에 포함시킵니다.
간소화에 도움이 되지 않으면 그냥 두면 됩니다.
무관항이 있을 때는 더 큰 그룹을 형성할 수 있는 기회를 항상 확인하세요!
05 논리식에서 카르노 맵 작성하기
SOP 논리식을 최소항으로 전개하여 맵에 배치
SOP(Sum of Products) 형태의 논리식이 주어졌을 때, 모든 항이 최소항(minterm) 형태가 아닐 수 있습니다. 생략된 변수를 찾아 최소항으로 전개해야 합니다.
📌 전개 방법 예시
F(A,B,C) = ABC + AB + AB
AB = AB(C + C) = ABC + ABC
AB = AB(C + C) = ABC + ABC
∴ F = ABC + ABC + ABC + ABC + ABC
= Σm(0, 1, 2, 3, 7)
이렇게 최소항으로 변환한 뒤, 해당 번호의 칸에 1을 채워 카르노 맵을 완성합니다. 위 예시에서 최종 간소화 결과는 F = A + BC가 됩니다.
06 QM(퀸-맥클러스키) 알고리즘
5변수 이상의 대규모 논리식 간소화에 적합한 체계적 알고리즘
퀸-맥클러스키(Quine-McCluskey, QM) 알고리즘은 1956년 Willard Van Orman Quine과 Edward J. McCluskey가 개발한 논리식 간소화 방법입니다. 변수가 4개 이하일 때는 카르노 맵이 유용하지만, 입력 변수가 5개 이상이 되면 맵이 지나치게 복잡해지기 때문에 QM 알고리즘이 훨씬 유용하며 컴퓨터로 자동화하기에 적합합니다.
▶ QM 알고리즘의 8단계 과정
| 단계 | 내용 |
| 1 | 진리표에서 출력이 1인 최소항을 모두 찾는다. |
| 2 | 최소항 중 입력변수에 1이 나타나는 개수(인덱스)에 따라 그룹을 만든다. |
| 3 | 인접 그룹끼리 비교하여 한 비트만 다른 항을 찾아 결합하고 표시(✓)한다. |
| 4 | ③을 더 이상 결합이 불가능할 때까지 반복한다. |
| 5 | 표시되지 않은 항들이 주항(PI, Prime Implicants)이 된다. |
| 6 | PI 차트를 만들어 필수주항(EPI, Essential Prime Implicants)을 찾는다. |
| 7 | EPI에 포함되는 PI들을 제거한다. |
| 8 | 나머지 항에 대해 최소 개수의 SOP식을 선택한다. |
▶ QM 알고리즘 처리 흐름
| ① 입력 최소항의 합(민텀 목록) |
→ | ② PI 도출 AB+AB=A 규칙으로 주항 목록 생성 |
→ | ③ PI 차트 EPI 선별 후 최소 SOP 도출 |
▶ QM 알고리즘 간소화 예제
예제: F(A, B, C) = Σm(0, 1, 4, 5) 를 QM 알고리즘으로 간소화해봅니다.
1단계: 한 비트 차이 결합표 (Column 1 ~ 3)
| 칼럼 1 | 칼럼 2 | 칼럼 3 | ||||||||
| 인덱스 | 10진수 | A B C | 인덱스 | 10진수 | A B C | 10진수 | A B C | |||
| 0 | (0) | 0 0 0 | ✓ | 0 | (0,1) | 0 0 - | (0,1,4,5) (0,4,1,5) |
- 0 - - 0 - |
||
| 1 | (1) | 0 0 1 | ✓ | (0,4) | - 0 0 | |||||
| (4) | 1 0 0 | ✓ | 1 | (1,5) | - 0 1 | |||||
| 2 | (5) | 1 0 1 | ✓ | (4,5) | 1 0 - | |||||
2단계: 주항(PI) 차트 및 최종 선택
| 주항(PI) | 변수 형태 | 0 | 1 | 4 | 5 |
|---|---|---|---|---|---|
| (0,1,4,5) *EPI | B (- 0 -) | O | O | O | O |
✓ 도출된 하나의 주항이 모든 최소항(0, 1, 4, 5)을 커버하는 유일한 필수 주항(EPI)이 됩니다.
최종 결론 : F(A, B, C) = B
⚠️ QM 알고리즘에서 결합 불가 조건
두 항을 비교할 때 두 비트 이상이 다르면 결합할 수 없습니다.
예) 0111과 1011 → 두 비트(첫째, 둘째)가 다르므로 결합 불가
✓ 카르노 맵 vs QM 알고리즘 선택 기준
· 변수 4개 이하 → 카르노 맵이 직관적으로 빠름
· 변수 5개 이상 → QM 알고리즘이 체계적이고 정확함
· 프로그래밍으로 자동화가 필요한 경우 → QM 알고리즘
📌 핵심 정리
· 카르노 맵 : 최소항을 그레이 코드 순서 격자에 배치하여 시각적으로 간소화
· 그룹핑 원칙 : 2의 거듭제곱 개수, 직사각형/정사각형, 최대한 크게 묶기
· 양 끝 연결 : 카르노 맵의 좌우/상하 끝은 서로 인접한 것으로 취급
· 무관항(don't care) : 간소화에 유리할 때만 1로 활용
· 논리식 → 카르노 맵 : 생략된 변수를 보수 항으로 전개하여 최소항 추출
· QM 알고리즘 : 인덱스 기반 그룹화 → 한 비트 결합 반복 → PI/EPI 추출 → 최소 SOP
· 적용 기준 : 4변수 이하 카르노 맵, 5변수 이상 QM 알고리즘 권장
태그 : 카르노맵Karnaugh Map논리식간소화QM알고리즘불대수디지털공학최소항그레이코드주항EPI논리회로설계
'학과 수업 노트 > 디지털공학' 카테고리의 다른 글
| 4. 불 대수 (0) | 2026.03.27 |
|---|---|
| 3. 논리 게이트 (1) (0) | 2026.03.19 |
| 2. 디지털 코드 (0) | 2026.03.15 |
| 1. 디지털 시스템의 이해 (0) | 2026.03.09 |