카르노 맵으로 식 줄이기

진리표에서 출력이 1인 행의 최소항을 모두 더하면 식은 맞지만 길어집니다. 부울 대수와 논리 회로에서 $xy+x\bar y=x$처럼 한 변수만 다른 두 곱을 합치면 그 변수가 사라지는 것을 보았는데, 이런 짝을 진리표에서 일일이 찾기는 어렵습니다. 1953년 Maurice Karnaugh가 제안한 카르노 맵(Karnaugh map)은 한 비트만 다른 입력들이 서로 이웃 칸에 오도록 진리표를 다시 배치해, 합칠 수 있는 짝을 눈으로 찾게 해 줍니다. 이 글은 선택 심화입니다.

이웃한 칸은 한 비트만 다르다

변수가 2개이면 x를 행으로, y를 열로 하는 2 × 2 칸에 출력을 적습니다. 변수가 3개이면 x를 두 행으로, yz를 네 열로 놓고, 변수가 4개이면 xy를 네 행으로, zw를 네 열로 놓습니다. 이때 두 비트짜리 머리글을 00, 01, 10, 11의 이진수 순서가 아니라 00, 01, 11, 10 순서로 적는데, 이웃한 두 값이 언제나 한 비트만 다른 이 순서를 Gray 코드(Gray code)라고 합니다.

from itertools import product


def gray(bits):
    return [format(i ^ (i >> 1), f"0{bits}b") for i in range(2 ** bits)]


def one_bit_apart(a, b):
    return sum(p != q for p, q in zip(a, b)) == 1


for order in (gray(2), ["00", "01", "10", "11"]):
    print(order, [one_bit_apart(order[i], order[(i + 1) % 4]) for i in range(4)])


def minterms(f, n):
    return [i for i, values in enumerate(product((0, 1), repeat=n)) if f(*values)]


print(minterms(lambda x, y, z: 1 - z, 3))
print(minterms(lambda x, y, z, w: (1 - x) & (1 - z), 4))

['00', '01', '11', '10'] [True, True, True, True]
['00', '01', '10', '11'] [True, False, True, False]
[0, 2, 4, 6]
[0, 1, 4, 5]

i ^ (i >> 1)은 i와 i를 한 자리 오른쪽으로 민 값의 XOR로, i번째 Gray 코드를 만드는 식입니다. format(..., "02b")는 그 값을 두 자리 이진수 문자열로 바꿉니다. 둘째 줄의 검사는 i번째와 다음 값이 한 비트만 다른지 보는데, (i + 1) % 4로 마지막 값과 첫 값도 비교합니다. Gray 순서에서는 마지막 10과 첫 00까지 모두 한 비트 차이지만, 이진수 순서에서는 01과 10, 11과 00이 두 비트씩 다릅니다. 그래서 카르노 맵에서는 왼쪽 끝 열과 오른쪽 끝 열도 이웃이고, 4변수 맵에서는 위쪽 끝 행과 아래쪽 끝 행도 이웃입니다. 뒤의 두 줄은 아래 예에서 줄인 식이 맞는지 확인하는 데 씁니다.

묶음 하나가 곱 하나가 된다

이웃한 1인 칸 두 개는 한 변수만 다르므로 그 변수가 빠진 곱 하나로 합쳐집니다. 같은 이유로 네 칸이 두 변수만 바꾸며 직사각형을 이루면 두 변수가 빠지고, 8칸이면 세 변수가 빠집니다. 그래서 묶음은 1, 2, 4, 8, 16칸처럼 2의 거듭제곱 크기의 직사각형이어야 하고, 묶음 안에서 값이 바뀌지 않는 변수만 곱으로 남습니다. 대각선으로만 맞닿은 칸은 두 비트가 다르므로 묶을 수 없습니다.

묶을 때는 세 가지를 지킵니다. 묶음에 0인 칸이 들어가면 안 되고, 1인 칸은 모두 어떤 묶음에든 들어가야 하며, 같은 칸이 여러 묶음에 들어가는 것은 괜찮습니다. 묶음이 클수록 곱의 변수가 줄고, 묶음이 적을수록 더하는 곱이 줄어 식이 짧아집니다.

그림은 3변수 함수 F가 최소항 0, 2, 4, 6에서 1인 경우입니다. 이 입력들은 000, 010, 100, 110이라 yz가 00과 10인 양 끝 열에 있고, 두 끝 열은 이웃이므로 네 칸을 하나로 묶을 수 있습니다. 묶음 안에서 x와 y는 바뀌고 z는 언제나 0이므로 $F=\bar z$입니다. 코드의 셋째 줄이 $\bar z$가 1인 입력을 계산해 0, 2, 4, 6을 내놓은 것으로 확인됩니다.

4변수 함수가 최소항 0, 1, 4, 5에서 1이면 입력은 0000, 0001, 0100, 0101입니다. x = 0과 z = 0은 그대로이고 y와 w가 바뀌므로 네 칸을 묶어 $F=\bar x\bar z$입니다. 2변수 함수가 01과 11에서 1이면 두 칸은 x만 다르고 y = 1이 그대로이므로 F = y이며, 이것은 앞 글의 $\bar xy+xy=y$를 그림으로 계산한 것입니다. 끝을 넘어가는 묶음이 헷갈리면, 이처럼 묶음 안의 입력을 비트로 적어 바뀌지 않는 변수를 찾으면 됩니다.

무관 조건

어떤 입력은 실제로 절대 들어오지 않거나, 들어와도 출력이 무엇이든 상관없을 수 있습니다. 이런 칸에는 0이나 1 대신 d를 적고 무관 조건(don't care condition)이라고 합니다. d는 묶음을 크게 만드는 데 도움이 되면 1처럼 묶음에 넣고, 도움이 안 되면 0처럼 두고 묶지 않아도 됩니다.

십진 숫자 0부터 9를 4비트 xyzw로 받아, 5 이상이면 1을 내는 회로를 생각해 봅시다. 출력이 1인 입력은 5부터 9까지이고, 10부터 15까지의 비트 조합은 십진 숫자가 아니므로 들어오지 않는다고 약속할 수 있습니다. d를 쓰지 않으면 가장 짧은 식이 $x\bar y\bar z+\bar xyw+\bar xyz$이지만, 10부터 15까지를 d로 두고 묶음에 넣으면 $x+yw+yz$로 줄어듭니다. 다만 이 식은 10부터 15까지에서도 1을 내므로, 그런 입력이 정말 들어오지 않을 때만 쓸 수 있습니다. 실제로 들어올 수 있는 입력을 확인하지 않고 d로 두면 회로가 틀린 값을 낼 수 있습니다.

카르노 맵은 변수가 4개, 많아야 5~6개일 때까지 손으로 쓰기 좋습니다. 그보다 많으면 칸의 수가 너무 많아지므로, 같은 원리를 표로 계산하는 Quine–McCluskey 방법이나 이를 개선한 프로그램을 씁니다. 회로 설계의 관점에서 카르노 맵을 연습하는 문제는 컴퓨터 구조 교재에서 더 볼 수 있습니다.

정리

• 카르노 맵은 머리글을 Gray 순서 00, 01, 11, 10으로 놓아, 이웃한 칸이 언제나 한 비트만 다르게 만든 진리표입니다.
• 왼쪽 끝과 오른쪽 끝, 위쪽 끝과 아래쪽 끝도 이웃이며, 대각선으로만 맞닿은 칸은 이웃이 아닙니다.
• 1, 2, 4, 8, 16칸의 직사각형 묶음 하나가 곱 하나가 되고, 묶음 안에서 바뀌지 않는 변수만 남습니다.
• 묶음에 0을 넣지 않고, 모든 1을 덮으며, 겹치는 묶음은 허용합니다.
• 무관 조건 d는 묶음을 키우는 데 쓸 수 있지만, 그 입력이 정말 일어나지 않을 때만 유효합니다.

연습 문제

1. 네 칸 묶기

3변수 함수 F가 최소항 1, 3, 5, 7에서 1일 때 식을 줄이세요. 변수 순서는 x, y, z입니다.

2. 이웃이 아닌 두 칸

3변수 함수에서 최소항 0과 3만 1일 때, 두 칸을 하나로 묶을 수 있나요?

3. 네 모서리

4변수 맵에서 네 모서리 칸, 곧 최소항 0, 2, 8, 10이 1이고 나머지가 0일 때 식을 줄이세요. 행은 xy, 열은 zw입니다.

묶음을 정한 뒤에는 묶음의 크기, 0이 들어갔는지, 모든 1을 덮었는지를 확인하고, 줄인 식이 처음 진리표와 같은지 모든 입력에서 검산해 보세요. 다음 장의 합과 곱의 법칙, 중복 세기에서는 이런 경우를 빠짐없이, 겹치지 않게 세는 방법을 다룹니다.