게이트와 진리표

문이 닫혀 있고 안전 센서가 정상일 때만 기계가 움직이게 하려 합니다. 두 조건을 각각 참이면 1, 거짓이면 0으로 나타내면, 기계를 움직이는 신호는 두 입력이 모두 1일 때만 1이 되는 출력으로 정확히 적을 수 있습니다. 이런 입력과 출력의 관계를 전기 회로로 만든 기본 부품이 논리 게이트(logic gate)입니다. 이 글에서는 기본 게이트들을 진리표로 비교하고, 여러 비트에 게이트를 한꺼번에 적용하는 방법을 다룹니다.

진리표로 게이트를 정의한다

진리표(truth table)는 가능한 입력 조합을 모두 나열하고 각 조합의 출력을 적은 표입니다. 입력이 n개이면 조합이 $2^n$가지이므로, 입력 A와 B 두 개이면 네 행입니다. AND는 두 입력이 모두 1일 때, OR는 하나라도 1일 때, XOR(배타적 OR)는 두 입력이 서로 다를 때 출력이 1입니다. NOT은 입력 하나를 받아 뒤집습니다.

NAND, NOR, XNOR는 각각 AND, OR, XOR의 출력을 뒤집은 게이트입니다. XNOR는 두 입력이 같을 때 1이라서 두 비트가 같은지 확인하는 데 씁니다. NAND 하나만으로, 또는 NOR 하나만으로 다른 모든 게이트를 만들 수 있어서 두 게이트를 범용 게이트(universal gate)라고 부릅니다. 예를 들어 NAND의 두 입력에 같은 A를 넣으면 NOT A가 됩니다. 실제 칩은 NAND나 NOR를 기본 부품으로 많이 쓰며, 왜 이 둘만으로 충분한지는 이산수학 교재의 부울 대수와 논리 회로에서 증명합니다.

진리표가 말해 주지 않는 것

실제 회로에서 0과 1은 전압의 범위로 나타냅니다. 어떤 전압 이하는 0, 어떤 전압 이상은 1로 읽고, 그 사이의 애매한 범위는 쓰지 않도록 설계합니다. 그래서 잡음이 조금 섞여도 0과 1을 혼동하지 않습니다.

또 입력이 바뀐 뒤 출력이 새 값으로 안정되기까지는 짧은 시간이 걸리는데, 이것을 전파 지연(propagation delay)이라고 합니다. 진리표는 입력이 안정된 뒤의 출력을 말해 줄 뿐, 입력이 바뀌는 순간 출력이 어떻게 흔들리는지는 말해 주지 않습니다. 게이트를 여러 단 거치면 지연이 쌓이므로, 이 지연이 회로를 얼마나 빨리 돌릴 수 있는지를 정합니다. 이 문제는 래치·플립플롭·클록에서 다시 다룹니다.

여러 비트에 한꺼번에 적용하기

CPU는 게이트를 비트마다 나란히 두어, 8비트나 64비트 값의 모든 자리에 같은 연산을 한 번에 합니다. 이것을 비트 단위 연산(bitwise operation)이라 하고, 원하는 자리만 1로 둔 값을 함께 써서 특정 비트만 골라 다루는 방법을 비트 마스크(bit mask)라고 합니다. A = 10010010과 마스크 00001111로 세 가지 일을 할 수 있습니다.

OR는 마스크가 1인 자리를 무조건 1로, AND는 마스크가 0인 자리를 무조건 0으로 만들고 나머지 자리는 그대로 둡니다. XOR는 마스크가 1인 자리만 뒤집습니다. 특정 비트가 1인지 검사하려면 그 비트를 맨 아래로 시프트한 뒤 1과 AND합니다.

두 패턴의 XOR는 서로 다른 자리만 1이 됩니다. 그래서 두 값이 같은지는 XOR의 모든 비트가 0인지로 판단할 수 있습니다. 다만 XOR의 결과가 다르다는 뜻의 1 하나로 나오는 것은 아니며, 0000 XOR 1000은 1000입니다. 회로에서 "하나라도 다른가"를 한 비트로 얻으려면 XOR의 출력들을 다시 OR로 모읍니다.

a = 0b10010010
low4 = 0b00001111
print(f"{a | low4:08b} {a & ~low4 & 0xFF:08b} {a ^ low4:08b}")
print((a >> 4) & 1, (a >> 2) & 1, a ^ a == 0)
print(~a, f"{~a & 0xFF:08b}")

10011111 10010000 10011101
1 0 True
-147 01101101

|, &, ^는 비트 단위 OR, AND, XOR이고, ~는 모든 비트를 뒤집는 NOT입니다. 첫 줄은 표의 세 결과입니다. 둘째 줄은 A의 4번 비트가 1, 2번 비트가 0이라는 것과, 자기 자신과의 XOR가 0이라는 것을 보여 줍니다. 비트 번호는 오른쪽 끝을 0번으로 셉니다.

셋째 줄은 주의할 점을 보여 줍니다. Python의 정수에는 정해진 폭이 없어서 ~a가 8비트 패턴 01101101이 아니라 음수 −147이 됩니다. 앞쪽에 끝없이 0이 있다고 보고 모두 뒤집기 때문입니다. 그래서 첫 줄에서도 ~low4를 쓴 뒤 & 0xFF로 8비트만 남겼습니다. 또 Python의 and, or, not은 참과 거짓을 판단하는 논리 연산자라서, 비트 단위 연산과 다르게 동작한다는 점도 구별해야 합니다.

정리

• 진리표는 입력 조합 $2^n$가지마다 출력을 적어 게이트를 정의하며, AND는 모두 1, OR는 하나라도 1, XOR는 서로 다를 때 1입니다.
• NAND, NOR, XNOR는 AND, OR, XOR의 출력을 뒤집은 것이고, NAND와 NOR는 하나만으로 모든 게이트를 만들 수 있는 범용 게이트입니다.
• 실제 회로는 0과 1을 전압의 범위로 나타내고, 출력이 안정되기까지 전파 지연이 있습니다. 진리표는 안정된 뒤의 관계만 말해 줍니다.
• 비트 마스크와 OR로 비트를 켜고, AND로 끄고, XOR로 뒤집으며, 시프트와 AND로 한 비트를 검사합니다.

연습 문제

1. 경고등의 진리표

센서 A와 B 가운데 하나라도 위험을 알리면 경고등 Y가 켜지고, 두 센서의 보고가 서로 다를 때만 점검등 Z가 켜집니다. Y와 Z의 진리표를 쓰세요.

2. 한 비트만 바꾸기

8비트 값 10100101에서 2번 비트만 1로 만든 결과와, 7번 비트만 0으로 만든 결과를 각각 구하세요. 비트 번호는 오른쪽 끝이 0번입니다.

3. 같은 값인지 확인하는 회로

4비트 값 두 개가 같은지 한 비트로 알려 주는 회로를 게이트로 설명하세요.

비트 연산의 결과가 이상하면 비트 번호를 오른쪽 끝부터 0으로 적고, 마스크의 각 자리가 무엇을 하는지 한 칸씩 확인해 보세요. 다음 글 부울 대수와 카르노 맵에서는 게이트로 만든 회로를 더 적은 게이트로 줄이는 방법을 다룹니다.