논리 게이트와 가산기

트랜지스터 스위치 몇 개로 만든 AND·OR·XOR 게이트를 엮으면, CPU가 덧셈을 하는 가산기(Adder) 회로가 된다.

0과 1만 아는 기계가 어떻게 계산할까? 컴퓨터 안에는 논리 게이트라는 아주 작은 부품이 수십억 개 들어 있다. 각 게이트는 전기 신호(0V / 3.3V = 0 / 1)를 입력받아 정해진 규칙대로 하나의 출력을 낸다. 이 게이트들을 잘 연결하면 이진수 덧셈을 하는 회로를 만들 수 있고, 그것을 여러 개 이어 붙이면 32비트·64비트 정수 덧셈기가 된다. 아래에서 직접 스위치를 눌러 보자.

1. 기본 논리 게이트

입력값을 눌러 바꿔 보면 각 게이트의 출력이 어떻게 달라지는지 볼 수 있다.

입력 A0 B0

게이트	의미	기호식	현재 출력
AND	둘 다 1이면 1	A · B	0
OR	하나라도 1이면 1	A + B	0
XOR	서로 다르면 1	A ⊕ B	0
NAND	AND의 반대	(A · B)'	1
NOR	OR의 반대	(A + B)'	1
NOT	A를 뒤집음	A'	1

NAND 하나만 있으면 다른 모든 게이트를 만들 수 있어서 "만능 게이트"라고 부른다.

2. 반가산기 (Half Adder)

한 자리 이진수 두 개를 더한다. 결과는 합(Sum)과 자리올림(Carry) 두 비트다. 1 + 1 = 10₂ 이므로 합은 0, 자리올림은 1이 된다.

입력 A0 B0

출력 S0 C0

A	B	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

S = A ⊕ B (XOR), C = A · B (AND)

3. 전가산기 (Full Adder)

반가산기는 아랫자리에서 넘어온 자리올림을 받지 못한다. 입력을 세 개(A, B, 그리고 아랫자리 자리올림 C_in)로 늘린 것이 전가산기다. 반가산기 두 개와 OR 게이트 하나로 만든다.

입력 A0 B0 C_in0

출력 S0 C_out0

S = A ⊕ B ⊕ C_in · C_out = (A · B) + (C_in · (A ⊕ B))

4. 리플 캐리 가산기 (4비트)

전가산기를 일렬로 연결하면 여러 자리 이진수를 더할 수 있다. 각 자리의 자리올림(C_out)이 바로 윗자리의 C_in으로 흘러 들어간다. 이 자리올림이 물결(ripple)처럼 오른쪽에서 왼쪽으로 한 칸씩 전파되기 때문에 "리플 캐리"라고 부른다.

A 0 1 1 1 = 7

B 0 1 0 1 = 5

왜 CPU 속도와 관련 있을까? 4비트는 자리올림이 최대 4번 전파되지만, 64비트 정수라면 최악의 경우 자리올림이 64칸을 순서대로 지나가야 해서 느리다. 그래서 실제 CPU는 자리올림을 미리 병렬로 예측하는 캐리 룩어헤드 가산기(Carry Lookahead Adder) 같은 더 빠른 회로를 쓴다. 원리는 같지만 지연 시간이 훨씬 짧다.

코드로 보는 전가산기

def full_adder(a, b, cin):
    s1 = a ^ b                 # 첫 번째 XOR
    sum_ = s1 ^ cin            # 두 번째 XOR  → 합
    cout = (a & b) | (cin & s1)  # 자리올림
    return sum_, cout

def ripple_add(A, B, n):       # A, B: 비트 리스트 (LSB first)
    carry, out = 0, []
    for i in range(n):
        s, carry = full_adder(A[i], B[i], carry)
        out.append(s)
    return out, carry          # carry = 오버플로 비트

한눈에 정리

구성 요소	입력	출력	쓰임
논리 게이트	1~2 비트	1 비트	모든 디지털 회로의 기본 블록
반가산기	A, B	S, C	가장 낮은 자리 덧셈
전가산기	A, B, C_in	S, C_out	중간 자리 덧셈
리플 캐리 가산기	n비트 × 2	n비트 + 오버플로	정수 덧셈기 (ALU의 일부)