한양과기고 에듀테크 수업도구 대시보드

카르노 맵 (Karnaugh Map)

변수 4개짜리 논리 함수의 진리표에는 16줄이 있다. 이걸 AND/OR/NOT 게이트로 그대로 만들면 항이 너무 많다. 카르노 맵은 진리표를 격자로 접어 놓은 것으로, 이웃한 칸은 변수가 딱 하나만 다르도록 배치한다(그레이 코드 순서 00 · 01 · 11 · 10). 그래서 값이 1인 칸이 2·4·8칸짜리 직사각형으로 뭉치면, 그 그룹 안에서 변하는 변수는 지워버리고 공통 변수만 남긴다 — 이렇게 눈으로 논리식을 최소화한다. 아래 맵에서 칸을 눌러 0 → 1 → X(무정의)로 바꿔 보면 최소 SOP 식이 즉시 갱신된다.

4변수 카르노 맵 — 칸을 눌러 그룹이 접히는 걸 보자

행은 AB, 열은 CD 이고 둘 다 그레이 코드 순서다. 왼끝↔오른끝, 위끝↔아래끝도 변수 하나 차이라서 모서리를 넘어(wrap) 뭉칠 수 있다. 아래 색칠된 항(chip)에 마우스를 올리면 그 그룹이 맵에서 강조된다.

1의 개수 (minterm)

무정의 X

곱항 수

리터럴 수

그룹 만드는 규칙

직사각형 & 2의 거듭제곱: 묶는 칸 수는 1, 2, 4, 8, 16 만 가능하고 모양은 직사각형이어야 한다. 대각선·L자는 안 된다.
클수록 좋다: 8칸 그룹은 리터럴 1개, 4칸은 2개, 2칸은 3개, 1칸은 4개. 그룹이 커질수록 변하는 변수가 많아져 더 많이 지워진다.
겹쳐도 된다: 한 칸이 여러 그룹에 속해도 괜찮다. 대신 모든 1은 최소 한 그룹에 들어가야 한다.
모서리 wrap: 맵의 상하·좌우 끝은 이어져 있다. 네 모서리 칸도 하나의 4칸 그룹이 된다.
무정의(X, don't-care): 출력을 신경 안 쓰는 입력. 그룹을 키우는 데 도움되면 1처럼 쓰고, 아니면 무시한다(0 취급).
필수 그룹 먼저: 오직 한 그룹으로만 덮을 수 있는 1(essential prime implicant)을 먼저 확정하고, 남은 1을 가장 적은 그룹으로 덮는다.

왜 되는가 — 인접 = 변수 하나 차이

불 대수의 핵심 항등식 하나로 설명된다. 어떤 변수 X에 대해:

# 결합(combining) 정리
Y·X + Y·X' = Y·(X + X') = Y·1 = Y

# 예) 2칸 그룹: minterm 5 (A'BC'D) 와 minterm 7 (A'BCD)
#     → C 만 0↔1 로 다름 → C 를 지운다 → A'BD

# 4칸 그룹이면 위 규칙을 두 번 적용 → 변수 2개가 사라짐

카르노 맵의 배치가 "이웃 = 1비트 차이"이기 때문에, 격자에서 붙어 있는 칸을 묶는 것이 곧 위 정리를 적용하는 것과 같다. 사람이 계산 없이 눈으로 최소화할 수 있는 이유다. 컴퓨터는 같은 일을 퀸–맥클러스키(Quine–McCluskey) 표 방법이나 Espresso 휴리스틱으로 한다.

그룹 크기	사라지는 변수	남는 리터럴	예
1칸	0개	4개	A'BC'D
2칸	1개	3개	A'BD
4칸	2개	2개	BD
8칸	3개	1개	B
16칸	4개	0개 (F=1)	1

어디에 쓰나

조합 논리 회로 설계: 7-세그먼트 디코더, 다수결 회로, 우선순위 인코더 등을 최소 게이트로 구현.
비용 절감: 게이트·트랜지스터 수가 줄면 칩 면적·전력·지연이 줄어든다.
해저드 제거: 겹치는 그룹을 일부러 추가하면 입력이 바뀔 때 생기는 순간적인 글리치(정적 해저드)를 없앨 수 있다.
한계: 변수 5~6개까지가 사람이 다룰 수 있는 실질적 한계다. 그 이상은 소프트웨어(Espresso)나 FPGA 합성 툴이 담당한다.