가산기·MUX·디코더

CPU가 하는 덧셈과, 여러 값 가운데 하나를 골라 계산 회로로 보내는 일은 모두 게이트를 이어 만든 작은 회로로 할 수 있습니다. 이 회로들은 지금의 입력만으로 출력이 정해지고, 이전에 무슨 값이 들어왔는지는 기억하지 않습니다. 이런 회로를 조합 논리 회로(combinational logic circuit)라고 합니다. 이 글에서는 부울 대수와 카르노 맵으로 다룬 식을 이어, 덧셈 회로와 선택 회로를 만듭니다. 값을 기억하는 회로는 다음 장에서 다룹니다.

반가산기와 전가산기

한 비트 A와 B를 더하면 결과는 0, 1, 2 가운데 하나라서 두 비트가 필요합니다. 아래 자리인 합 S는 두 입력이 다를 때 1이므로 $S=A\oplus B$, 곧 XOR이고, 위로 넘기는 자리올림 C는 둘 다 1일 때만 1이므로 $C=AB$입니다. 이 회로를 반가산기(half adder)라고 합니다. 1 + 1은 합 0, 자리올림 1, 곧 이진수 10입니다.

여러 비트를 더하려면 각 자리에서 아래 자리가 넘긴 자리올림까지 세 비트를 더해야 합니다. 이 회로가 전가산기(full adder)이고, 입력은 A, B, 자리올림 입력 $C_{in}$, 출력은 합 S와 자리올림 출력 $C_{out}$입니다. 합은 세 입력 가운데 1이 홀수 개일 때 1이므로 $S=A\oplus B\oplus C_{in}$이고, 자리올림은 1이 두 개 이상일 때 1이므로 $C_{out}=AB+C_{in}(A\oplus B)$입니다. 이 식은 "A와 B가 모두 1이거나, 둘 가운데 하나만 1이고 아래에서 자리올림이 왔을 때"로 읽을 수 있습니다.

표의 각 행에서 $2C_{out}+S$가 A + B + $C_{in}$과 같다는 것을 확인할 수 있습니다. 예를 들어 마지막 행은 1 + 1 + 1 = 3 = 이진수 11입니다.

전가산기를 이어 여러 비트를 더한다

전가산기 네 개를 나란히 두고, 각 자리의 자리올림 출력을 바로 위 자리의 자리올림 입력에 이으면 4비트 덧셈 회로가 됩니다. 자리올림이 아래에서 위로 물결처럼 전해진다고 해서 리플 캐리 가산기(ripple-carry adder)라고 부릅니다. 0111 + 0001을 더하면 맨 아래 자리에서 생긴 자리올림이 위 자리로 차례로 넘어가 결과가 1000이 됩니다.

맨 아래 자리는 1 + 1 + 0이라 합 0과 자리올림 1을 내고, 그 자리올림을 받은 다음 두 자리는 1 + 0 + 1이라 다시 합 0과 자리올림 1을 냅니다. 맨 위 자리는 0 + 0 + 1이라 합 1이 되고 자리올림은 0입니다. 위 자리는 아래 자리의 자리올림이 정해져야 자기 결과를 정할 수 있으므로, 이 회로는 자리 수에 비례하는 시간이 걸립니다. 32비트나 64비트 가산기에서는 이 기다림이 길어지므로, 실제 CPU는 각 자리가 자리올림을 만들어 낼지 그대로 전할지를 미리 계산해 자리올림을 한꺼번에 구하는 자리올림 예측 가산기(carry-lookahead adder) 같은 방식을 씁니다.

여러 입력 가운데 하나를 고른다

멀티플렉서(multiplexer, MUX)는 여러 데이터 입력 가운데 선택 신호가 가리키는 하나를 출력으로 내보냅니다. 2:1 MUX는 선택 신호 s가 0이면 $D_0$을, 1이면 $D_1$을 내보내므로 식은 $Y=\overline{s}D_0+sD_1$입니다. 입력이 4개이면 하나를 가리키는 데 선택 비트가 2개, 8개이면 3개 필요합니다. 일반적으로 $2^n$개 입력에는 선택 비트 n개가 필요합니다.

디코더(decoder)는 n비트 번호를 받아 $2^n$개 출력 가운데 그 번호에 해당하는 하나만 1로 만듭니다. 2:4 디코더에 10을 넣으면 출력 $Y_2$만 1이 됩니다. 메모리에서 주소로 칸 하나를 고를 때 이런 회로를 씁니다. 인코더(encoder)는 반대로 1인 입력의 위치를 번호로 바꾸는데, 입력이 둘 이상 동시에 1이면 결과가 정해지지 않으므로, 가장 우선순위가 높은 입력의 번호를 내는 우선순위 인코더(priority encoder)를 따로 씁니다. 디멀티플렉서(demultiplexer)는 MUX와 반대로 입력 하나를 선택된 출력 하나로 보냅니다.

두 값을 비교하는 비교기(comparator)도 조합 회로입니다. 같은지는 게이트와 진리표에서 본 것처럼 자리마다 XNOR를 두고 AND로 모으면 됩니다. 크기를 비교할 때는 가장 높은 자리부터 내려가며 처음으로 다른 자리를 찾아, 그 자리가 1인 쪽이 더 크다고 판단합니다. 부호 있는 수라면 맨 앞 비트의 뜻이 달라지므로 부호를 따로 고려해야 합니다.

from itertools import product


def full_adder(a, b, carry_in):
    s = a ^ b ^ carry_in
    carry_out = (a & b) | (carry_in & (a ^ b))
    return s, carry_out


def ripple_add(x, y, width=4, show=False):
    carry, total = 0, 0
    for i in range(width):
        a, b = (x >> i) & 1, (y >> i) & 1
        s, next_carry = full_adder(a, b, carry)
        if show:
            print(f"{i}번 자리: {a} + {b} + 올림 {carry} -> 합 {s}, 올림 {next_carry}")
        total |= s << i
        carry = next_carry
    return total, carry


print(ripple_add(0b0111, 0b0001, show=True))
print(all(ripple_add(x, y) == ((x + y) & 0b1111, (x + y) >> 4)
          for x, y in product(range(16), repeat=2)))


def mux2(s, d0, d1):
    return ((1 - s) & d0) | (s & d1)


def mux4(s1, s0, d):
    return mux2(s1, mux2(s0, d[0], d[1]), mux2(s0, d[2], d[3]))


def decoder2(a1, a0):
    return [int(2 * a1 + a0 == k) for k in range(4)]


d = [0, 1, 1, 0]
print([mux4(s1, s0, d) for s1, s0 in product((0, 1), repeat=2)], decoder2(1, 0))

0번 자리: 1 + 1 + 올림 0 -> 합 0, 올림 1
1번 자리: 1 + 0 + 올림 1 -> 합 0, 올림 1
2번 자리: 1 + 0 + 올림 1 -> 합 0, 올림 1
3번 자리: 0 + 0 + 올림 1 -> 합 1, 올림 0
(8, 0)
True
[0, 1, 1, 0] [0, 0, 1, 0]

full_adder는 위의 두 식을 그대로 옮긴 것이고, ripple_add는 아래 자리부터 전가산기를 하나씩 거치며 자리올림을 다음 자리로 넘깁니다. 처음 네 줄은 그림의 네 단계와 같은 과정이고, 결과는 저장값 8과 자리올림 0입니다. 둘째 print는 4비트 입력 256쌍 모두에서 이 회로의 결과가 덧셈의 아래 네 비트와 자리올림과 같은지 확인한 것입니다. mux4는 2:1 MUX 세 개를 두 단으로 이어 4:1 MUX를 만들었는데, 선택 신호를 00부터 11까지 바꾸어 가며 출력하면 데이터 입력 d가 그대로 나옵니다. decoder2(1, 0)은 번호 2에 해당하는 출력만 1입니다.

정리

• 조합 논리 회로는 지금의 입력만으로 출력이 정해지는 회로입니다.
• 반가산기는 $S=A\oplus B$, $C=AB$이고, 전가산기는 아래 자리의 자리올림까지 더해 $S=A\oplus B\oplus C_{in}$, $C_{out}=AB+C_{in}(A\oplus B)$를 냅니다.
• 리플 캐리 가산기는 전가산기의 자리올림을 위 자리로 차례로 넘기므로 자리 수에 비례하는 시간이 걸리고, 자리올림 예측 가산기는 이 기다림을 줄입니다.
• MUX는 선택 신호로 입력 하나를 고르며 $2^n$개 입력에 선택 비트 n개가 필요하고, 디코더는 n비트 번호를 $2^n$개 출력 가운데 하나로 바꿉니다.
• 인코더는 1인 입력의 위치를 번호로 바꾸며, 여러 입력이 동시에 1일 수 있으면 우선순위 인코더를 씁니다.

연습 문제

1. 고른 다음 더한다

4비트 가산기의 A 입력은 6이고, B 입력 앞의 MUX는 s = 0이면 3을, s = 1이면 10을 고릅니다. s의 두 값에서 각각 수학적인 합, 저장되는 아래 4비트, 자리올림을 구하세요. 입력 8개 가운데 하나를 고르는 MUX에는 선택 비트가 몇 개 필요한가요?

2. 디코더의 출력

2:4 디코더에 입력 01과 11을 넣으면 출력은 각각 무엇인가요? 3비트 번호를 받는 디코더의 출력은 몇 개인가요?

3. 자리올림을 기다리는 시간

전가산기 하나에서 자리올림 입력이 바뀐 뒤 자리올림 출력이 안정되기까지 게이트 2단의 지연이 걸린다고 합시다. 32비트 리플 캐리 가산기에서 맨 아래 자리의 자리올림이 맨 위 자리의 출력까지 전해지는 데 게이트 몇 단의 지연이 걸리나요?

덧셈 회로의 결과가 이상하면 자리마다 입력 두 비트와 아래에서 온 자리올림을 적고 한 자리씩 따라가 보세요. 다음 장의 래치·플립플롭·클록에서는 이렇게 계산한 결과를 정해진 순간에 기억해 두는 회로를 다룹니다.