카르노 맵: 시각적 부울 간소화

요약: 카르노 맵(K-맵)은 진리표를 인접 셀이 정확히 한 변수만 다른 그레이 코드 2D 격자에 배치합니다. 인접한 1들을 2의 거듭제곱 크기의 직사각형으로 묶으면 최소 곱의 합(Sum-of-Products) 식이 바로 얻어집니다 — 대수 계산이 필요 없습니다. K-맵은 4개 변수까지 함수를 신뢰성 있게 최소화하며, 5–6 변수에는 퀸-맥클러스키(Quine–McCluskey)를, 그 이상에는 ESPRESSO 스타일 알고리즘 합성을 사용합니다.

부울 법칙을 사용한 대수적 간소화는 효과가 있지만, 적절한 순간에 적절한 인수분해를 찾아내는 데 달려 있습니다. 한 번의 기회를 놓치면 최적이 아닌 결과로 끝납니다. 변수가 네 개 이상인 식의 경우, 가능한 조작 수가 폭발적으로 증가합니다.

카르노 맵(K-맵)은 대수적 간소화를 시각적 패턴 인식으로 변환해 이 문제를 해결합니다. 1953년 벨 연구소 물리학자 모리스 카르노(Maurice Karnaugh)가 개발했으며, 진리표를 인접 셀이 정확히 한 변수만 다른 2차원 격자로 배치합니다. 격자 위에서 인접한 1들을 묶으면 곧바로 최소 곱의 합 식이 얻어집니다 — 대수적 조작이 필요 없습니다.

AND 게이트 컴포넌트 다이어그램

시각적 진리표: K-맵이란?

본질적으로 카르노 맵은 변장한 진리표입니다. 진리표가 입력과 출력을 선형적이고 수직적인 방식으로 나열하는 반면, K-맵은 이를 2차원 격자로 재배치합니다. 이는 단순한 장식이 아닙니다. K-맵의 천재성은 셀의 특정한 배치 방식에 있습니다.

표준 진리표에서 행은 이진 카운트(00, 01, 10, 11)를 따릅니다. K-맵에서는 행과 열이 **그레이 코드(Gray code)**라는 순서를 따릅니다. 그레이 코드 시퀀스에서는 — 가로로 이동하든 세로로 이동하든 — 인접한 숫자가 단 하나의 비트만 다릅니다. **논리적 인접성(logical adjacency)**으로 알려진 이 속성이 간소화를 추진하는 엔진입니다. ‘1’을 담은 인접 셀들을 묶으면, 시각적으로 변하는(따라서 결과에 영향을 미치지 않는) 변수를 식별하고 제거하여 최소 부울 항을 남기게 됩니다.

현대 ALU 설계에 사용되는 복잡한 4-변수 맵에 뛰어들기 전에, 입력 $A$ 와 $B$ 에 대한 기본 2-변수 맵을 살펴봅시다. 이는 가능한 네 개의 민텀을 나타내는 $2^2 = 4$ 개의 셀로 구성됩니다.

	$B=0$ ( $\overline{B}$ )	$B=1$ ( $B$ )
$A=0$ ( $\overline{A}$ )	$m_0$ ( $\overline{A}\overline{B}$ )	$m_1$ ( $\overline{A}B$ )
$A=1$ ( $A$ )	$m_2$ ( $A\overline{B}$ )	$m_3$ ( $AB$ )

인접성에 주목하세요: $m_0$ 에서 $m_1$ 로 이동할 때 변수 $B$ 만 변합니다. $m_1$ 에서 $m_3$ 으로 이동할 때 변수 $A$ 만 변합니다. 격자 상의 이 물리적 근접성은 게이트 수를 줄이기 위해 활용할 수 있는 논리적 관계를 나타냅니다.

기본 논리 실전 보기

묶기의 기술: 맵에서 최소 논리로

K-맵 사용의 목표는 가능한 한 큰 직사각형 그룹으로 맵의 모든 ‘1’을 덮는 것입니다. 그러나 함정이 있습니다: 각 그룹의 셀 수는 2의 거듭제곱(1, 2, 4, 8, 16 등)이어야 합니다. 여러분이 그리는 각 그룹은 간소화된 곱 항에 대응합니다. 최종 최적화된 식은 단순히 “곱의 합”(그 그룹들의 결과를 OR한 것)입니다.

묶기 규칙은 엄격하지만 직관적입니다. 기계적으로 따르기만 하면 최소 결과가 보장됩니다.

모든 ‘1’을 덮어라: 맵의 모든 ‘1’은 최소한 하나의 그룹에 속해야 합니다. 묶이지 않은 ‘1’은 있을 수 없습니다.
2의 거듭제곱만: 그룹은 정확히 $2^k$ 개의 셀을 포함해야 합니다: 1, 2, 4, 8, 또는 16. 3, 5, 6개의 그룹은 만들 수 없습니다. 1이 6개인 영역은 4개와 2개의 겹치는 그룹으로 덮어야 합니다.
그룹 크기를 최대화하라: 더 큰 그룹은 더 많은 변수를 제거합니다. 2개 그룹은 1개의 변수를, 4개 그룹은 2개를, 8개 그룹은 3개를 제거합니다. 항상 가능한 가장 큰 그룹을 먼저 찾으세요.
겹침이 허용된다: 단일 ‘1’은 여러 그룹에 속할 수 있습니다. 더 큰 그룹을 만들기 위해 겹침을 적극적으로 활용하세요.
직사각형 모양만: 그룹은 직사각형(정사각형 포함)이어야 합니다. L자, T자, 대각선 모양은 유효하지 않습니다.
맵은 둘러 감긴다: 가장 왼쪽 열은 가장 오른쪽 열과 인접합니다. 맨 위 행은 맨 아래 행과 인접합니다. 맵을 토러스(torus)로 상상하세요 — 네 모서리는 서로 인접합니다.

심층 분석: 4-변수 K-맵

실제 시나리오를 다뤄 봅시다. 4비트 입력이 특정 조건과 일치할 때 신호를 발화해야 하는 CONTROL_UNIT의 특정 논리를 설계한다고 가정합시다. 우리의 함수는 $F(A,B,C,D) = \Sigma m(0, 2, 5, 7, 8, 10, 13, 15)$ 입니다.

$\Sigma m$ 표기는 “이진 입력이 이 십진값과 같을 때 출력이 HIGH”라는 약식 표현입니다. 먼저 16-셀 격자를 채웁니다.

	$CD=00$	$CD=01$	$CD=11$	$CD=10$
$AB=00$	1 ( $m_0$ )	0	0	1 ( $m_2$ )
$AB=01$	0	1 ( $m_5$ )	1 ( $m_7$ )	0
$AB=11$	0	1 ( $m_{13}$ )	1 ( $m_{15}$ )	0
$AB=10$	1 ( $m_8$ )	0	0	1 ( $m_{10}$ )

이제 패턴을 찾습니다.

그룹 1: 네 모서리

$m_0, m_2, m_8, m_{10}$ 의 ‘1’들을 보세요. 맵이 수평과 수직 양쪽으로 둘러 감기기 때문에, 이 네 모서리는 실제로 인접합니다! 하나의 4개 그룹을 형성합니다.

변수 A: 0에서 1로 변합니다. (버림)
변수 B: 0으로 유지됩니다. ( $\overline{B}$ 유지)
변수 C: 0에서 1로 변합니다. (버림)
변수 D: 0으로 유지됩니다. ( $\overline{D}$ 유지)
결과: $\overline{B}\overline{D}$

그룹 2: 중앙 블록

$m_5, m_7, m_{13}, m_{15}$ 에서 가운데에 완벽한 2x2 정사각형이 있습니다.

변수 A: 0에서 1로 변합니다. (버림)
변수 B: 1로 유지됩니다. ( $B$ 유지)
변수 C: 0에서 1로 변합니다. (버림)
변수 D: 1로 유지됩니다. ( $D$ 유지)
결과: $BD$

모든 ‘1’이 덮였습니다. 최종 간소화된 식은:

F = \overline{B}\overline{D} + BD

이는 XNOR 게이트의 부울 정의입니다 — 여덟 개의 4-입력 AND 게이트로 이루어진 난장판이 단일 컴포넌트로 줄어듭니다.

XNOR 게이트 컴포넌트 다이어그램

XNOR 간소화 회로 탐색

흔한 함정: 왜 그레이 코드가 양보할 수 없는가

흔한 오류는 K-맵을 표준 이진 순서 — 00, 01, 10, 11 — 로 그리는 것입니다. 그러지 마세요.

표준 이진을 사용하면 인접성 원칙이 깨집니다. 01에서 10으로의 점프를 보세요. 두 비트가 모두 변합니다( $0 \to 1$ 및 $1 \to 0$ ). 이 두 인접 셀에 ‘1’이 있다면, 한 개 이상의 변수가 변하기 때문에 간소화할 수 없습니다. 그레이 코드 시퀀스(00, 01, 11, 10)는 맵에서 여러분이 내딛는 모든 단일 단계가 정확히 한 변수의 변화를 나타내도록 보장합니다. 이것이 수학이 시각적으로 작동하게 하는 “마법”입니다. 그레이 코드 없이 K-맵은 그저 혼란스러운 표일 뿐이며, 그레이 코드와 함께라면 계산기가 됩니다.

OSCILLOSCOPE_8CH로 검증하기

디지털 공학에서 가장 만족스러운 순간 중 하나는 여러분의 “작은” 회로가 “큰” 회로와 정확히 같은 일을 한다는 것을 증명하는 것입니다. digisim.io에서는 이를 실시간으로 할 수 있습니다.

무차별 대입 구성: 여덟 개의 AND 게이트와 하나의 거대한 OR 게이트로 원래의 민텀을 표현합니다.
최적화 구성: 그 아래에 단일 XNOR 게이트(또는 2-AND-1-OR 등가물)를 배치합니다.
입력 동기화: 동일한 네 개의 INPUT_SWITCH 컴포넌트를 양쪽 회로에 연결합니다.
분석: 무차별 대입 회로의 출력을 OSCILLOSCOPE_8CH의 채널 1에, 최적화된 출력을 채널 2에 연결합니다.

스위치를 16가지 조합 모두로 토글하면, OSCILLOSCOPE_8CH의 파형은 동일합니다. 그러나 전파 지연( $t_{pd}$ )을 보면, 최적화된 회로가 훨씬 빨리 반응하는 것을 알게 됩니다. 고속 CPU 프로젝트에서 그 나노초가 1MHz 클록과 10MHz 클록의 차이입니다.

실제 응용: 교실을 넘어서

K-맵은 시험을 통과하기 위한 것만이 아닙니다 — 하드웨어 기술의 일용할 양식입니다.

1. ALU 제어 논리

전형적인 8비트 CPU에서 ALU(Arithmetic Logic Unit, 산술 논리 장치)는 “opcode”에 따라 더하기, 빼기, 비트 AND를 수행할지 알아야 합니다. 이 opcode는 4비트 폭일 수 있습니다. 엔지니어들은 K-맵을 사용해 그 4비트 opcode를 받아 ADDER_8BIT 또는 COMPARATOR_8BIT의 특정 제어 라인을 활성화하는 디코더 논리를 설계합니다. 이 논리를 최소화함으로써 “명령어 디코드” 시간을 줄이며, 이는 CPU 성능의 결정적 병목입니다.

2. 유한 상태 기계 (FSM)

교통 신호 컨트롤러든 복잡한 프로토콜 핸들러든, FSM은 “다음 상태 논리”에 의존합니다. 이 논리는 현재 상태(REGISTER에 저장)와 현재 입력을 살펴 다음 상태가 무엇이어야 하는지 결정합니다. 이러한 진리표는 빠르게 거대해집니다. K-맵은 설계자가 이러한 신호를 라우팅하는 가장 효율적인 방법을 찾도록 해 주며, 최종 구현에서 종종 수십 개의 게이트를 절약합니다.

ALU 컴포넌트 다이어그램

흔한 함정

피해야 할 일반적 실수:

부동 입력: 모든 AND 게이트의 모든 입력은 무언가에 연결되어야 합니다. 부동 입력은 시뮬레이터에서는 예측 가능하게 동작할 수 있지만, 실제 하드웨어에서는 노이즈를 받습니다.
둘러 감김 놓치기: 모서리와 가장자리를 확인하세요. 가장 우아한 간소화 중 일부는 네 모서리나 맨 위/맨 아래 행을 묶는 데서 나옵니다.
중복 그룹: 모든 1이 덮이면, 멈추세요. “예뻐 보여서” 추가 그룹을 더하는 것은 회로에 불필요한 게이트를 넣고 K-맵의 목적을 무너뜨립니다.

Don’t Care 조건의 힘

많은 실제 설계에서 특정 입력 조합은 절대 발생할 수 없습니다. 예를 들어, BCD(Binary-Coded Decimal) 시스템은 4비트로 0-9 숫자를 표현하므로, 조합 1010부터 1111까지는 절대 나타나지 않습니다. K-맵에서는 이러한 불가능한 입력을 0이나 1 대신 $X$ (don’t care)로 표시합니다.

핵심: 각 $X$ 를 더 큰 그룹을 형성하는 데 도움이 되는 0이나 1 중 어느 것으로든 취급할 수 있습니다. 이러한 입력은 실제로 발생하지 않으므로, 회로가 어떻게 출력하든 상관없습니다.

예: 4-변수 함수가 셀 0, 2, 8, 10에서 1을, 셀 1과 3에서 don’t care를 갖는다고 가정합시다. don’t care 없이는 네 개의 1(모서리)이 $\overline{B}\overline{D}$ 로 묶입니다. 그러나 셀 1과 3을 1로 취급함으로써, 맨 위 행에서 4개의 더 큰 그룹( $\overline{A}\overline{B}$ )을 형성할 수 있고, 원래의 모서리 그룹과 함께 잠재적으로 더 단순한 전체 식을 얻을 수 있습니다. Don’t care 조건은 실제 설계에서 최종 게이트 수를 자주 20-30% 줄여 줍니다.

다음 단계

이 글은 Boolean Algebra Fundamentals 시리즈의 일부입니다. 관련 자료:

부울 대수 마스터하기 — K-맵 묶기 뒤에 있는 대수적 항등식.
곱의 합(SOP) 마스터하기 — K-맵이 만들어 내는 표준형.
합의 곱: SOP를 넘어 — 쌍대 최소화.
드 모르간 법칙 — 형태 간 변환에 사용되는 변환 규칙.

카르노 맵은 복잡한 대수적 작업을 시각적 퍼즐로 바꿉니다. 최대 4개 변수 함수에 대해 K-맵은 최소 SOP(또는 POS) 식을 신뢰성 있게 만들어 냅니다. 5–6개 변수에서는 K-맵도 여전히 사용 가능하지만 다루기 어려우며, 퀸-맥클러스키 같은 알고리즘 방식이 이를 대체합니다.

작업 예시의 무차별 대입 회로와 최적화된 회로를 만들고, 오실로스코프에서 파형이 일치하는 것을 관찰하세요. 검증하려면 새 회로 시작하기.