카르노 맵(Karnaugh Map) — K-Map 간소화 가이드

카르노 맵(Karnaugh map), 또는 K-Map은 불 대수식을 손으로 복잡하게 계산하지 않고 더 간단하게 만들기 위한 격자표입니다. 진리표의 출력값을 격자에 배치한 뒤, 서로 인접한 $1$들을 묶고, 각 묶음마다 더 단순한 항 하나를 씁니다.

중요한 점은 적용 조건입니다. K-Map은 보통 변수 개수가 2개, 3개, 4개인 작은 함수에서 가장 실용적입니다. 변수 수가 늘어나면 맵이 읽기 어려워지고, 보통은 다른 방법이 더 적합합니다.

카르노 맵이 보여주는 것

K-Map은 진리표와 같은 정보를 담고 있지만, 일반적인 이진수 순서가 아니라 그레이 코드(Gray code) 순서로 칸을 배치합니다. 이렇게 배치하면 서로 이웃한 칸은 정확히 하나의 변수만 다르게 됩니다.

바로 이 한 변수 차이가 핵심입니다. 인접한 두 칸이 모두 $1$이면, 변하는 그 변수는 간소화된 항에서 사라질 수 있습니다.

묶기를 통해 변수가 사라지는 원리

이 시각적 규칙은 다음과 같은 불 대수 항등식에서 나옵니다.

$$XY + X\overline{Y} = X$$

두 항은 $Y$만 다르므로 $Y$는 소거되고, 공통 부분인 $X$만 남습니다. K-Map을 사용하면 이런 소거 패턴을 격자에서 바로 찾을 수 있습니다.

카르노 맵 예제

다음과 같다고 합시다.

$$F(A,B,C) = \sum m(1,3,4,5,7)$$

이는 최소항 $1$, $3$, $4$, $5$, $7$에서 $F=1$이라는 뜻입니다.

변수 3개짜리 K-Map에서는 행에 $A$, 열에 $BC$를 두고, 열 순서는 그레이 코드 $00$, $01$, $11$, $10$을 사용합니다.

$$\begin{array}{c|cccc} A \backslash BC & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array}$$

먼저 가능한 가장 큰 올바른 묶음부터 찾습니다. 가운데 두 열에 있는 네 개의 $1$은 하나의 묶음을 이룹니다. 이 네 칸에서는 $C=1$이 고정되어 있고 $A$와 $B$는 변하므로, 이 묶음은 다음처럼 간소화됩니다.

$$C$$

아직 덮이지 않은 $1$이 하나 남아 있습니다. 최소항 $4$로, $(A,B,C)=(1,0,0)$입니다. 이것을 인접한 최소항 $5$, 즉 $(1,0,1)$와 짝지을 수 있습니다.

이 두 칸에서는 $A=1$과 $B=0$이 고정되어 있고 $C$만 변하므로, 이 쌍은 다음처럼 간소화됩니다.

$$A\overline{B}$$

따라서 간소화된 식은

$$F(A,B,C) = C + A\overline{B}$$

입니다.

이 더 짧은 식은 원래의 최소항 목록과 동치입니다.

올바른 K-Map 묶음의 규칙

묶음의 크기는 $1$, $2$, $4$, $8$처럼 2의 거듭제곱이어야 합니다.

가능한 한 가장 큰 올바른 묶음을 사용하세요. 큰 묶음일수록 보통 더 많은 변수를 제거할 수 있습니다.

맵은 가장자리가 이어진다는 점을 기억하세요. 왼쪽과 오른쪽 가장자리는 서로 인접하고, 위쪽과 아래쪽 가장자리도 서로 인접합니다.

대각선 방향의 칸들은 인접하지 않습니다.

더 크거나 더 단순한 묶음을 만드는 데 도움이 된다면, 묶음이 서로 겹쳐도 됩니다.

카르노 맵에서 자주 하는 실수

일반적인 이진수 순서를 사용하는 경우

행이나 열을 $00$, $01$, $10$, $11$로 표시하면 인접 관계가 틀어집니다. K-Map은 이웃한 칸이 오직 한 비트만 다르도록 반드시 그레이 코드 순서를 사용해야 합니다.

3칸짜리 묶음을 만드는 경우

3칸 묶음은 절대 올바르지 않습니다. 묶음의 크기는 반드시 2의 거듭제곱이어야 합니다.

가장자리 연결 인접을 놓치는 경우

가장 좋은 간소화 중 일부는 맵의 반대편 가장자리에 있는 칸들을 함께 사용하는 경우입니다. 가장자리 연결 규칙을 잊으면 답이 필요 이상으로 길어지는 경우가 많습니다.

모든 $1$을 정확히 하나의 묶음에만 넣으려는 경우

그것은 규칙이 아닙니다. 어떤 칸을 다시 사용하는 것이 더 큰 묶음을 만들고 최종 식을 더 짧게 만드는 가장 좋은 방법일 수 있습니다.

카르노 맵은 언제 쓰는가

K-Map은 불 대수 간소화를 시각적으로 처리할 수 있게 해 주기 때문에 디지털 논리와 컴퓨터공학 입문에서 자주 사용됩니다. 특히 논리 회로를 그리거나 구현하기 전에 더 간단한 sum-of-products 식이 필요할 때 유용합니다.

또한 직관을 기르는 데도 좋습니다. 큰 설계는 소프트웨어가 처리하더라도, K-Map을 배우면 어떤 불 대수 항들이 결합되고 어떤 항들은 결합되지 않는지 더 쉽게 이해할 수 있습니다.

비슷한 문제를 풀어보세요

$F(A,B,C)=\sum m(0,2,4,6,7)$를 직접 간소화해 보세요. 맵을 그리고, 먼저 가장 큰 올바른 묶음을 만든 뒤, 각 묶음에서 값이 변하지 않는 변수만 남기면 됩니다.

한 단계 더 나아가고 싶다면 don't-care 값을 포함한 버전도 시도해 보세요. 그리고 더 큰 올바른 묶음을 만드는 데 도움이 될 때만 그것들을 사용해 보세요.