반가산기와 전가산기: 덧셈 회로 만들기

컴퓨터는 덧셈밖에 못하는 바보라는 걸 깨달았습니다

처음 컴퓨터 구조를 공부할 때, 가장 충격적이었던 사실이 있습니다. 컴퓨터는 사실 덧셈밖에 못합니다. 유튜브도 보여주고, 3D 게임도 돌리고, 인공지능으로 그림도 그리지만, 그 가장 깊은 심연을 들여다보면 오직 단 하나의 연산만이 존재합니다. 바로 덧셈(Addition)이죠.

뺄셈은 어떻게 하냐고요? 2의 보수를 취해서 더합니다 ($A + (-B)$). 곱셈은? 덧셈을 여러 번 반복합니다 ($A \times 3 = A + A + A$). 나눗셈은? 뺄셈을 반복하는데, 뺄셈 자체가 덧셈의 변형이니까 결국 덧셈입니다. 지수나 로그 같은 복잡한 연산도? 테일러 급수로 근사하여 덧셈과 곱셈으로 바꿉니다.

결국 컴퓨터의 성능을 결정짓는 가장 핵심적인 부품은 "누가누가 덧셈을 더 빨리 하느냐"를 결정하는 가산기(Adder)입니다. CPU의 심장인 ALU(Arithmetic Logic Unit)에서도 가장 많은 면적을 차지하는 것이 바로 이 가산기죠.

제가 처음 이걸 배울 때는 "논리 게이트 몇 개로 어떻게 덧셈을 하지?"라는 의문이 들었습니다. 그런데 막상 파고들어 보니, 이게 정말 정교하게 설계된 예술 작품이더군요.

논리 게이트 - 0과 1을 요리하는 도구들

가산기를 설계하려면, 논리 회로의 기본 부품 3가지를 완벽하게 이해해야 합니다. 처음엔 이것들이 그냥 추상적인 개념인 줄 알았는데, 실제로는 트랜지스터 몇 개로 만들어지는 물리적인 회로더군요.

XOR 게이트 - 덧셈의 핵심

가장 중요한 게이트입니다. 이름 그대로 "배타적(Exclusive)"입니다. "너랑 나랑 다르면 1, 같으면 0"이라는 규칙이죠.

0 XOR 0 = 0 (같으니까 0)
1 XOR 1 = 0 (같으니까 0)
0 XOR 1 = 1 (다르니까 1)

처음엔 "이게 왜 중요하지?"라고 생각했는데, 이것이 바로 1비트 덧셈의 "합(Sum)"과 완벽하게 일치한다는 걸 깨달았을 때 무릎을 탁 쳤습니다. 1+1=0 (올림수 발생, 1의 자리는 0)이라는 게 XOR 결과와 똑같잖아요!

AND 게이트 - 올림수의 핵심

"너도 1이고 나도 1이어야 1"이라는 단순한 규칙입니다. 1 AND 1 = 1이고, 나머진 다 0이죠. 이것은 덧셈의 "올림(Carry)"과 일치합니다. 둘 다 1일 때만 윗자리로 1이 올라가니까요.

OR 게이트 - 최종 결합

"둘 중 하나라도 1이면 1"이라는 규칙입니다. 나중에 올림수들을 합칠 때 사용합니다.

이 세 가지 게이트만 있으면, 우리는 덧셈 회로를 만들 수 있습니다. 처음엔 믿기지 않았는데, 직접 만들어보니 정말 되더군요.

반가산기 - 반쪽짜리 계산기

가장 단순한 덧셈인 1비트 두 개(A, B)를 더하는 상황을 생각해봤다. 진리표를 만들어보면:

A	B	합 (Sum)	올림 (Carry)	설명
0	0	0	0	0 + 0 = 0
0	1	1	0	0 + 1 = 1
1	0	1	0	1 + 0 = 1
1	1	0	1	1 + 1 = 2 (이진수 10)

이 진리표를 보면 패턴이 딱 보입니다. Sum은 A와 B가 다를 때만 1이니까 XOR 게이트를 쓰면 되고, Carry는 A와 B가 모두 1일 때만 1이니까 AND 게이트를 쓰면 됩니다.

graph LR
    InputA[입력 A] --> XOR
    InputB[입력 B] --> XOR
    InputA --> AND
    InputB --> AND
    XOR --> Sum[Sum: 합]
    AND --> Carry[Carry: 올림]

이것을 반가산기(Half Adder)라고 부릅니다. 그런데 왜 "반(Half)"일까요? 처음엔 이름이 이상하다고 생각했는데, 치명적인 단점이 있기 때문이더군요. "아랫자리에서 올라온 올림수(Carry In)"를 받을 입력 핀이 없습니다.

우리가 십진수 덧셈 15 + 28을 할 때를 생각해보세요. 일의 자리(5+8=13)에서 1이 올라갑니다. 십의 자리(1+2)를 계산할 때, 아까 올라온 1을 더해서 1+1+2=4가 되어야 하죠. 하지만 반가산기는 이 "올라온 1"을 처리할 능력이 없습니다. 그래서 맨 끝자리(LSB) 계산 외에는 쓸모가 없는 겁니다.

전가산기 - 진짜 덧셈 회로를 만들었습니다

진정한 가산기가 되려면 입력이 3개여야 합니다. A(더해지는 수), B(더하는 수), C_in(아랫자리에서 올라온 올림수). 이 세 개를 모두 처리할 수 있어야 진짜 가산기죠.

경우의 수가 8가지($2^3$)나 되는데, 그 중 핵심은 "1의 개수"입니다. 1이 1개면 (예: 1+0+0): Sum=1, Carry=0. 1이 2개면 (예: 1+1+0): Sum=0, Carry=1. 1이 3개면 (예: 1+1+1): Sum=1, Carry=1 (결과 3, 이진수 11).

전가산기는 새로 만드는 게 아니라, 반가산기 두 개를 연결해서 만듭니다. 이게 정말 천재적인 발상이더군요.

1단계: A와 B를 더합니다 (반가산기 1) → 중간 합, 중간 올림 1 생성
2단계: 중간 합과 C_in을 더합니다 (반가산기 2) → 최종 합(Sum) 완성!, 중간 올림 2 생성
3단계: 중간 올림 1과 중간 올림 2를 OR 게이트로 합칩니다 → 최종 올림(C_out) 완성!

이 블록 하나가 있으면 우리는 드디어 1비트 덧셈을 완벽하게 수행할 수 있습니다. 이제 이걸 연결하기만 하면 됩니다.

리플 캐리 가산기 - 연결의 미학, 그리고 한계

4비트 덧셈(1011 + 0011)을 하려면 전가산기 4개를 일렬로 세우면 됩니다. Adder 0은 첫 번째 비트를 계산하고 올림수($C_1$)를 Adder 1에게 토스합니다. Adder 1은 받아서 계산하고 올림수($C_2$)를 Adder 2에게 토스하고... 이렇게 계속됩니다.

마치 올림수(Carry)가 잔잔한 호수에 돌을 던진 것처럼 물결(Ripple)쳐서 퍼져나간다고 해서 "Ripple Carry Adder(RCA)"라고 부릅니다. 이름이 참 시적이죠.

치명적인 문제 - 속도

이 방식은 만들기는 쉽지만, 현대 컴퓨터에서는 절대 사용 불가능한 치명적인 단점이 있습니다. 바로 전파 지연(Propagation Delay)입니다.

64비트 CPU를 상상해보세요. 전가산기 64명이 일렬로 서 있습니다. 맨 마지막 64번째 가산기는 63번째 가산기가 올림수를 줄 때까지 아무것도 못하고 기다려야 합니다. 63번째는 62번째를, 62번째는 61번째를... 결국 1번부터 64번까지 순차적으로 계산이 끝나야만 하죠.

만약 전가산기 하나가 계산하는 데 1나노초(ns)가 걸린다면, 64비트 덧셈에는 64ns가 걸립니다. 현대 CPU(3GHz)는 0.33ns마다 한 번씩 클럭이 뛰는데, 덧셈 한 번에 64ns가 걸린다면 CPU는 약 200클럭 동안 멈춰 있어야 합니다. 컴퓨터 속도가 1980년대로 퇴보하는 거죠.

제가 처음 이걸 배울 때 "그럼 어떻게 해결하지?"라고 생각했는데, 엔지니어들은 천재적인 해결책을 찾아냈더군요.

캐리 룩어헤드 가산기 - 속도의 혁명

엔지니어들은 고민에 빠졌습니다. "앞자리 계산이 끝날 때까지 기다리지 않고, 미리 올림수가 생길지 알 수 있는 방법은 없을까?"

천재적인 발상이 등장합니다. 바로 CLA(Carry Lookahead Adder)입니다. 각 자리의 입력값(A, B)만 보면, 굳이 계산을 안 해봐도 올림수(Carry)의 운명을 알 수 있다는 논리죠.

두 가지 운명

Generate (G) - 생성: "나는 무조건 올림수를 만든다."
- $A=1, B=1$이면, 아랫자리에서 뭐가 올라오든 상관없이 무조건 $1+1=2$ 이상이 되므로 올림수가 발생합니다
- $G = A \cdot B$ (AND 게이트)
Propagate (P) - 전파: "나는 올림수가 오면 그대로 뒷사람에게 넘긴다."
- $A=1, B=0$ 이거나 $A=0, B=1$이면, 합은 1입니다. 이때 아랫자리에서 올림수 1이 오면 $1+1=2$가 되어 올림수가 발생합니다. 즉, 받은 걸 그대로 토스(Propagate)하는 거죠
- $P = A \oplus B$ (XOR 게이트)

마법의 수식

이 논리를 이용하면, 4번째 자리의 올림수($C_4$)를 1, 2, 3번째 가산기를 거치지 않고 수학 공식으로 한 방에 예측할 수 있습니다.

$$C_4 = G_3 + P_3(G_2 + P_2(G_1 + P_1(G_0 + P_0C_0)))$$

복잡해 보이지만 핵심은 "병렬 처리"입니다. 기다릴 필요 없이, 모든 자리의 올림수를 동시에(Simultaneously) 계산해버립니다. 물론 회로가 엄청나게 복잡해지고 전기도 많이 먹지만, 속도는 비약적으로 빨라집니다.

현대의 인텔/AMD CPU는 이보다 더 발전된 Prefix Adder (Kogge-Stone, Brent-Kung) 알고리즘을 사용하여, 64비트 덧셈을 거의 1클럭 내외에 해치워버립니다. 처음 이걸 알았을 때 정말 놀라웠습니다.

2의 보수 - 컴퓨터가 뺄셈을 하는 법

CPU 설계를 뜯어보면 뺄셈기(Subtractor)라는 부품은 존재하지 않습니다. 그런데 어떻게 5 - 3을 계산할까요? 컴퓨터는 뺄셈을 "음수 더하기"로 바꿔서 처리합니다. 5 + (-3) 이렇게요.

여기서 2의 보수(Two's Complement)라는 천재적인 개념이 등장합니다. 처음엔 이게 왜 작동하는지 이해가 안 갔는데, 직접 계산해보니 정말 신기하더군요.

5 - 3 계산 과정 (4비트 기준)

3을 2진수로: 0011
1의 보수 (뒤집기): 1100 (모든 비트를 반전)
2의 보수 (1 더하기): 1101 (이것이 컴퓨터가 인식하는 -3입니다)
덧셈 수행:
```
  0101 (5)
+ 1101 (-3)
-------
 10010
```
오버플로우 버림: 우리는 4비트 컴퓨터니까, 맨 앞의 1은 저장할 공간이 없어서 사라집니다
최종 결과: 0010 (십진수 2)

기가 막히지 않나요? 뺄셈 회로를 따로 만들 필요 없이, 기존 가산기에 "NOT 게이트" 하나만 붙이면 뺄셈까지 공짜로 처리되는 겁니다. 이것이 컴퓨터 공학의 효율성이죠.

하드웨어 엔지니어의 코딩: Verilog

"회로 설계"라고 하면 납땜질을 상상하시나요? 21세기의 하드웨어 설계는 코딩입니다. Verilog나 VHDL 같은 언어로 코드를 짜면, 컴파일러가 알아서 트랜지스터 회로도로 변환(Synthesis)해줍니다.

전가산기(Full Adder) 코드 예시:

module FullAdder (
    input a, b, cin,
    output sum, cout
);
    // XOR 두 번으로 합 구하기
    assign sum = a ^ b ^ cin; 

    // (A&B) 이거나, (C_in & (A^B)) 이면 올림 발생
    assign cout = (a & b) | (cin & (a ^ b)); 
endmodule

소프트웨어 개발자가 if-else를 칠 때, 하드웨어 엔지니어는 비트의 흐름을 assign 합니다. 처음엔 낯설었는데, 알고 보니 논리적으로는 똑같더군요.

양자 컴퓨터의 덧셈 - 되돌릴 수 있는가?

번외로, 미래의 기술인 양자 컴퓨터(Quantum Computer) 이야기를 해보죠. 기존의 AND, OR, XOR 게이트는 치명적인 특징이 있습니다. 바로 정보의 파괴(Irreversible)입니다.

A AND B = 0이라는 결과만 보고 원래 A, B가 무엇인지 알 수 있나요? (0,0), (0,1), (1,0) 셋 중 하나겠지만, 정확히는 모릅니다. 정보가 사라진 거죠. 정보가 사라진다는 건 열(Heat)이 발생한다는 뜻입니다. (란다우어의 원리)

양자 컴퓨터에서는 상태를 중첩(Superposition)시키기 위해 정보가 파괴되면 안 됩니다. 그래서 토폴리 게이트(Toffoli Gate) 같은 가역 게이트(Reversible Gate)를 사용하여, 결과값만 보고도 입력값을 100% 역추적할 수 있는 특수한 덧셈 회로를 만듭니다. 이것은 기존 반도체와는 완전히 다른 차원의 설계죠.

AI 시대의 가산기 - 정밀도를 버리고 속도를 취하다

최근 엔비디아(NVIDIA) H100 같은 AI 전용 칩셋에서는 재미있는 현상이 벌어지고 있습니다. 기존 CPU가 64비트 정밀도(double)에 집착했다면, AI 칩은 거꾸로 8비트(INT8, FP8) 덧셈으로 회귀하고 있습니다.

왜 퇴보하는가?

딥러닝 모델(GPT-4 등)은 파라미터가 수천억 개입니다. 이걸 64비트로 계산하면 속도도 느리고 메모리도 터집니다. 연구 결과, 인공지능의 신경망 연산은 "대충 맞아도 된다"는 것이 밝혀졌습니다. 소수점 15자리까지 정확할 필요 없이, 큰 흐름만 맞으면 고양이 사진을 개라고 인식하지 않는다는 거죠.

FP8의 등장

그래서 최신 GPU에는 8비트 부동소수점(FP8) 전용 가산기가 대거 탑재됩니다. 32비트보다 4배 많은 데이터를 한 번에 처리 가능하고 (Throughput 4배 증가), 전력 소모도 감소합니다. 결과적으로 챗GPT 같은 거대 언어 모델의 추론 속도가 비약적으로 빨라지죠.

가산기의 역사는 4비트(Intel 4004) → 64비트(Modern CPU) → 8비트(AI GPU)로 돌고 도는 셈입니다. 물론, 겉모습만 8비트지 내부적으로는 수천 개의 코어가 병렬로 돌아가는 Systolic Array 구조를 띱니다.

이러한 저정밀도 연산의 유행은 흥미롭게도 뉴로모픽(Neuromorphic) 컴퓨팅과도 연결됩니다. 인간의 뇌가 시냅스 신호를 처리할 때 완벽한 디지털 정확도보다는 적당한 아날로그 신호의 합을 사용하는 것과 유사하기 때문입니다. 결국 극한의 효율을 추구하는 AI 하드웨어는 점점 인간의 뇌 구조를 닮아가고 있습니다.

정리하면서 - 1나노초의 예술

우리가 편하게 작성하는 total = price + tax 라는 코드 한 줄. 엔터키를 누르는 순간, CPU 내부에서는 수십억 개의 트랜지스터가 일제히 문을 열고 닫으며 전자를 이동시킵니다. 전가산기들의 치열한 릴레이 이어달리기, 혹은 CLA의 천재적인 병렬 예측 덕분에 우리는 0.000000001초 만에 정확한 결과를 얻습니다.

가산기는 단순한 계산기가 아닙니다. 인류가 논리(Logic)를 물리적인 실체(Physics)로 구현해낸, 공학의 가장 아름다운 결정체입니다. 처음엔 "그냥 덧셈 회로네"라고 생각했는데, 깊이 파고들수록 이게 얼마나 정교하게 설계된 예술 작품인지 알게 됐습니다.

XOR 게이트 하나, AND 게이트 하나가 모여서 1+1=2라는 마법을 만들어내고, 이것이 수십억 번 반복되어 우리가 사용하는 모든 디지털 기기를 움직입니다. 이 단순함 속의 복잡함, 복잡함 속의 단순함이 컴퓨터 공학의 아름다움이 아닐까 싶습니다.