부울 대수와 카르노 맵

안전 회로의 식이 $A B+A\overline{B}$라고 합시다. 잘 보면 B가 0이든 1이든 A가 1이기만 하면 출력이 1이므로, 이 회로는 결국 A 하나와 같습니다. 식을 이렇게 줄이면 게이트가 줄어 회로가 작고 싸지며 이해하기도 쉬워집니다. 다만 줄인 식은 보기에 짧기만 해서는 안 되고, 모든 입력에서 원래 식과 똑같은 출력을 내야 합니다. 이 글에서는 게이트와 진리표의 회로를 식으로 적고, 그 식을 법칙과 카르노 맵으로 줄이는 방법을 다룹니다.

회로를 줄이는 법칙

회로의 식에서는 AND를 곱 $AB$로, OR를 합 $A+B$로, NOT을 윗줄 $\overline{A}$로 씁니다. 기호는 수의 계산과 같지만 값이 0과 1뿐이라 법칙이 다릅니다. $A+A=A$, $AA=A$이고, $A+\overline{A}=1$, $A\overline{A}=0$입니다. 그래서 처음의 식은 $AB+A\overline{B}=A(B+\overline{B})=A\cdot1=A$로 줄어듭니다. 한 변수만 다른 두 곱을 더하면 그 변수가 사라진다는 이 계산이 회로를 줄이는 기본 도구입니다.

드모르간 법칙(De Morgan's laws)은 $\overline{AB}=\overline{A}+\overline{B}$와 $\overline{A+B}=\overline{A}\,\overline{B}$입니다. 식 전체를 뒤집을 때는 AND와 OR를 서로 바꾸면서 각 입력도 뒤집어야 합니다. $\overline{AB}$를 $\overline{A}\,\overline{B}$로 바꾸는 실수가 흔한데, 입력이 A = 0, B = 1이면 앞의 식은 1이고 뒤의 식은 0이라 다릅니다. 흡수 법칙 $A+AB=A$는 A가 이미 1이면 B와 상관없이 OR의 결과가 1이라는 뜻입니다. 이 법칙들의 전체 목록과 증명은 이산수학 교재의 부울 대수와 논리 회로에 있습니다.

카르노 맵으로 이웃을 찾는다

법칙으로 식을 줄이려면 합칠 수 있는 짝을 찾아야 하는데, 변수가 많아지면 쉽지 않습니다. 카르노 맵(Karnaugh map, K-map)은 진리표를 한 비트만 다른 입력끼리 이웃하도록 다시 배치해, 합칠 수 있는 짝을 눈으로 찾게 해 줍니다. 3변수 맵에서는 A를 행으로, BC를 열로 놓되 열의 순서를 00, 01, 11, 10으로 적습니다. 이진수 순서 00, 01, 10, 11로 적으면 01과 10이 이웃하게 되는데, 두 비트가 달라 합칠 수 없으므로 맵의 의미가 사라집니다.

이 함수는 오른쪽 두 열의 네 칸이 1입니다. 네 칸을 하나의 2 × 2 묶음으로 잡으면, 묶음 안에서 A와 C는 0과 1을 모두 지나고 B만 1로 그대로이므로 출력은 B입니다. 묶음은 1, 2, 4, 8칸처럼 2의 거듭제곱 크기의 직사각형이어야 하고, 0인 칸을 넣으면 안 되며, 모든 1을 어떤 묶음에든 넣어야 합니다. 같은 칸이 여러 묶음에 들어가는 것은 괜찮고, 묶음이 클수록 곱의 변수가 줄어듭니다.

끝과 끝이 이어진 묶음

맵의 왼쪽 끝 열 00과 오른쪽 끝 열 10도 한 비트만 다르므로 이웃입니다. 맵을 원통처럼 말아 양 끝을 붙였다고 생각하면 됩니다. A, B, C 순서의 입력 000, 010, 101, 111에서만 1인 함수 F로 이 경우를 보겠습니다.

A = 0 행에서는 양 끝 열 00과 10의 두 칸이 1이고, 두 칸은 끝과 끝이 이어진 이웃입니다. 이 묶음에서 B만 바뀌고 A = 0, C = 0은 그대로이므로 곱은 $\overline{A}\,\overline{C}$입니다. A = 1 행에서는 가운데 01과 11의 두 칸이 1이고, B만 바뀌며 A = 1, C = 1이 그대로이므로 곱은 $AC$입니다. 두 묶음을 OR로 합치면 $F=\overline{A}\,\overline{C}+AC$이고, A와 C가 같을 때만 1이며 B는 출력에 아무 영향이 없습니다.

대각선으로만 맞닿은 두 칸은 두 비트가 다르므로 묶을 수 없고, 가운데의 0까지 넣어 네 칸을 묶는 것도 안 됩니다. 어떤 입력이 실제로 일어나지 않거나 출력이 무엇이든 상관없다면, 그 칸을 무관 조건(don't care)으로 표시하고 묶음을 키우는 데 쓸 수 있습니다. 하지만 실제로 들어오는 입력을 무관 조건으로 바꾸면 회로가 그 입력에서 틀린 값을 냅니다. 카르노 맵의 더 많은 예와 4변수 맵은 이산수학 교재의 카르노 맵으로 식 줄이기에서 다룹니다.

줄인 식을 모든 입력에서 확인하기

변수가 몇 개뿐이라면 가능한 입력을 모두 넣어 원래 식과 줄인 식을 비교하는 것이 가장 확실한 검사입니다. 3변수이면 여덟 가지뿐입니다.

from itertools import product


def rows(n):
    return list(product((0, 1), repeat=n))


print(all((a & b) | (a & (1 - b)) == a for a, b in rows(2)))

ones = {(0, 0, 0), (0, 1, 0), (1, 0, 1), (1, 1, 1)}
for a, b, c in rows(3):
    f = ((1 - a) & (1 - c)) | (a & c)
    print(a, b, c, int((a, b, c) in ones), f)

True
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
0 1 1 0 0
1 0 0 0 0
1 0 1 1 1
1 1 0 0 0
1 1 1 1 1

product((0, 1), repeat=n)은 n개 입력의 모든 조합을 만듭니다. 첫 줄은 $AB+A\overline{B}$가 네 입력 모두에서 A와 같다는 결과입니다. 나머지 여덟 줄은 입력 A, B, C, 원래 함수의 값, 줄인 식 $\overline{A}\,\overline{C}+AC$의 값을 차례로 적은 것인데, 넷째 열과 다섯째 열이 모든 행에서 같습니다. 입력 하나만 넣어 보는 것으로는 이런 확신을 얻을 수 없습니다. 다만 이 검사는 출력 값이 같은지만 확인할 뿐, 게이트를 거치는 지연이나 소비 전력까지 같다는 뜻은 아닙니다.

정리

• 회로의 식에서 곱은 AND, 합은 OR, 윗줄은 NOT이며, $A+A=A$, $A+\overline{A}=1$처럼 수와 다른 법칙이 있습니다.
• 한 변수만 다른 두 곱을 더하면 그 변수가 사라지고, 드모르간 법칙은 전체를 뒤집을 때 AND와 OR를 바꾸고 각 입력도 뒤집습니다.
• 카르노 맵은 열과 행을 00, 01, 11, 10 순서로 놓아 이웃한 칸이 한 비트만 다르게 만들며, 끝과 끝도 이웃입니다.
• 묶음은 2의 거듭제곱 크기의 직사각형으로 1만 덮고, 묶음 안에서 바뀌지 않는 변수만 곱으로 남깁니다.
• 줄인 식은 모든 입력에서 원래 식과 같은지 확인해야 하며, 변수가 적으면 모든 조합을 넣어 비교합니다.

연습 문제

1. 두 식 가운데 맞는 것

$F=\overline{A}B+AB$를 줄이고 진리표로 확인하세요. 또 $G=\overline{A+B}$와 같은 식이 $\overline{A}+\overline{B}$와 $\overline{A}\,\overline{B}$ 가운데 어느 것인지 고르고, 틀린 식의 반례를 드세요.

2. 양 끝을 잇는 묶음

입력 001, 011, 100, 110에서만 1인 3변수 함수 G를 A 행, BC 열의 맵에 채우고, 두 묶음으로 식을 줄이세요.

3. 겹치는 묶음

$Y=\overline{A}BC+ABC+A\overline{B}C$를 카르노 맵으로 줄이세요.

식을 줄인 뒤에는 묶음의 크기, 0이 들어갔는지, 모든 1을 덮었는지를 확인하고 모든 입력에서 검산해 보세요. 다음 글 가산기·MUX·디코더에서는 이렇게 만든 게이트들을 이어 덧셈과 선택을 하는 회로를 만듭니다.