카르노 맵(Karnaugh Map)

Karnaugh Map은 불 대수(Boolean Algebra) 의 복잡한 식을 시각적으로 간단히 표현하고 최소화하기 위해 사용된다.
즉, 복잡한 논리식을 게이트 수가 최소가 되는 형태로 단순화하기 위한 방법이다.

논리식의 최소화는 왜 필요할까?
회로가 간단해질수록

• 전력 소모가 줄고,
• 연산 속도가 빨라지고,
• 비용이 감소한다.

그래서 실제 회로 설계나 FPGA, CPU의 논리 회로 최적화 단계에서 필수적으로 사용된다.

---

기본 개념

K-Map은 진리표(Truth Table) 를 기반으로 만들어진다.
하지만 진리표가 단순히 표 형태라면,
K-Map은 같은 정보를 2차원 평면상의 격자(grid) 형태로 배치한 것이다.

각 칸(cell)은 하나의 Minterm(곱의 항, AND 형태)을 나타내며,
칸 안에는 출력 값(1 또는 0)이 적힌다.

그 후 인접한 칸끼리 묶어(그룹핑) 논리식을 단순화한다.

---

구조

(1) 2변수 K-Map

A/B	0	1
0	m₀	m₁
1	m₂	m₃

→ 4칸의 격자, 각각 A와 B의 조합(00, 01, 11, 10)을 나타낸다.
(순서에 주의: 그레이 코드(Gray code) 순서로 배치된다.)

예시로 진리표가 다음과 같다고 하자.

A	B	F
0	0	0
0	1	1
1	0	1
1	1	1

이를 K-map으로 나타내면:

A\B	0	1
0	0	1
1	1	1

이제 인접한 1들을 묶는다.
오른쪽 열의 1 (두 개) → 공통변수는 B=1
아래쪽 행의 1 (두 개) → 공통변수는 A=1

즉,

F=A+B

로 단순화된다.

---

(2) 3변수 K-Map

3변수(A, B, C)는 총 8개의 조합이 있다.
이를 2×4 격자로 그린다.

AB/C	00	01	11	10
0	m₀	m₁	m₃	m₂
1	m₄	m₅	m₇	m₆

각 칸은 A, B, C의 조합에 해당하며, 1인 칸을 묶어서 최소화한다.

---

(3) 4변수 K-Map

4변수(A, B, C, D)는 16칸으로 구성된다.
보통은 4×4 형태로 그려진다.

AB/CD	00	01	11	10
00	m₀	m₁	m₃	m₂
01	m₄	m₅	m₇	m₆
11	m₁₂	m₁₃	m₁₅	m₁₄
10	m₈	m₉	m₁₁	m₁₀

---

그룹핑(Grouping) 규칙

K-Map의 핵심은 인접한 1들을 묶는 것이다.
묶음(Group)은 반드시 2의 거듭제곱 개수(1, 2, 4, 8, 16...)여야 한다.

• 1개 묶음 → 최소 항 그대로
• 2개 묶음 → 1개의 변수가 소거
• 4개 묶음 → 2개의 변수가 소거
• 8개 묶음 → 3개의 변수가 소거

인접의 개념에는 가로/세로/가장자리 연결(랩 어라운드) 도 포함된다.
즉, 맵의 가장 왼쪽과 오른쪽, 위와 아래는 실제로 연결되어 있다 (토러스 구조).

그룹핑 원칙 요약:

1. 가능한 한 큰 그룹으로 묶는다.
2. 1은 반드시 한 번 이상 묶여야 한다.
3. 그룹들은 중복되어도 된다.
4. 묶음의 크기는 반드시 2ⁿ개여야 한다.

---

예시 — 3변수 K-Map 최소화

예를 들어 다음 식을 보자.

F(A,B,C)=Σ(1,3,5,7)

즉, 1, 3, 5, 7번 칸이 1인 상태다.

AB/C	00	01	11	10
0	0	1	1	0
1	0	1	1	0

→ 1들이 오른쪽 두 열(01, 11)에 걸쳐 있다.
따라서 공통되는 부분은 C=1

결과적으로

F=C

로 단순화된다.

즉, 네 개의 항을 단 하나의 변수로 줄였다.
이것이 K-map의 강력한 단순화 효과다.

---

Don’t Care 조건

실제 회로에서는 특정 입력 조합이 절대 발생하지 않거나,
결과가 무의미한 경우가 있다.
이런 항을 Don’t Care(‘X’) 라고 표시한다.

K-map에서 ‘X’는 1로 취급할 수도, 0으로 취급할 수도 있다.
즉, 필요에 따라 유리한 방향으로 묶어서 회로를 더 간단하게 만들 수 있다.

---

K-Map과 Boolean Algebra의 관계

방식	특징	장점
Boolean 대수식 단순화	식 변형을 통해 최소화	체계적이지만 복잡함
Karnaugh Map	시각적으로 그룹핑	빠르고 직관적

3~4변수까지는 K-map이 효율적이고,
5변수 이상부터는 Quine–McCluskey Algorithm 같은 컴퓨터 기반 최소화 기법이 사용된다.

---

실제 회로 설계에서의 활용

K-map으로 얻은 최소 논리식은 AND, OR, NOT 게이트로 직접 구현할 수 있다.
예를 들어,

F=AB‾+BC

라면 다음과 같은 회로로 표현된다.

• AND 게이트 2개
• OR 게이트 1개
• NOT 게이트 1개

K-map은 결국 "게이트 수를 최소화하여 하드웨어 비용을 절감하는 방법"이다.

---

요약 정리

항목	설명
목적	논리식(Truth Table)을 최소 논리식으로 단순화
구조	2D 격자 형태 (Gray Code 순서)
핵심 아이디어	인접한 1들을 그룹화하여 불필요한 변수 제거
장점	시각적, 빠름, Boolean 식보다 직관적
한계	5변수 이상에서는 비효율적

 

Karnaugh Map은 논리식을 시각적으로 ‘묶어서 단순화’하는 지도다.

복잡한 불 논리식을 단순한 형태로 바꾸어,
하드웨어 회로를 더 효율적이고 경제적으로 구현할 수 있게 해준다.