컴퓨터가 큰 정수를 더하는 출발점은 한 자리 2진수 덧셈입니다. 입력 비트 A와 B만 더하면 0+0=0, 0+1=1, 1+0=1, 1+1=10₂입니다. 마지막 경우에는 현재 자리의 합 0과 다음 자리로 넘길 올림수 1이 동시에 생깁니다. 실제 여러 자리 덧셈에서는 바로 오른쪽 자리에서 넘어온 올림수까지 더해야 합니다. A, B, 이전 자리 올림수 Cin을 받아 합 S와 다음 자리 올림수 Cout을 내는 조합 논리회로가 전가산기(full adder)입니다.
0과 1을 계산하는 불 대수
불 대수(Boolean algebra)는 참·거짓 또는 1·0처럼 두 값을 다루는 대수 체계입니다. 디지털 회로에서는 AND를 두 입력이 모두 1일 때만 1, OR를 하나 이상 1일 때 1, NOT을 입력을 뒤집는 연산으로 사용합니다. XOR(배타적 OR)은 두 입력이 서로 다를 때 1입니다. XOR은 올림을 제외한 1비트 덧셈과 같아서 0⊕0=0, 0⊕1=1, 1⊕0=1, 1⊕1=0입니다.
NIST 용어 정의에서도 XOR은 같은 길이의 비트열을 자리별로 더하되 올림을 버리는 modulo 2 덧셈으로 설명됩니다. 따라서 합의 최하위 비트를 구할 때 XOR가 자연스럽게 등장합니다. 반면 올림은 적어도 두 입력이 1인지 확인해야 하므로 AND와 OR 조합이 필요합니다.
반가산기는 두 비트만 더합니다
반가산기(half adder)는 A와 B라는 두 입력만 받습니다. 합 비트 H는 A XOR B이고 올림 비트 C는 A AND B입니다. 1+1일 때 XOR 결과는 0이고 AND 결과는 1이므로 두 출력을 나란히 읽으면 10₂가 됩니다.
반가산기: H=A⊕B, C=A·B
| A | B | 합 H=A⊕B | 올림 C=A·B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
반가산기에는 이전 자리에서 넘어온 올림수를 넣을 입력이 없습니다. 여러 자리 수의 맨 오른쪽처럼 Cin이 항상 0인 자리에는 쓸 수 있지만, 나머지 자리를 일반적으로 처리하기에는 부족합니다. 세 번째 입력을 포함하는 전가산기가 필요한 이유입니다.
전가산기의 8가지 입력을 모두 적은 진리표
A, B, Cin은 각각 0 또는 1이므로 가능한 입력은 2³=8가지입니다. 세 입력의 정수 합은 0부터 3까지입니다. 그 값을 2진수 두 자리 CoutS로 표현하면 전가산기의 출력이 됩니다. 합이 0이면 00, 1이면 01, 2이면 10, 3이면 11입니다.
| A | B | Cin | 정수 합 | Cout | S |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 2 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 2 | 1 | 0 |
| 1 | 1 | 0 | 2 | 1 | 0 |
| 1 | 1 | 1 | 3 | 1 | 1 |
S 열을 보면 입력에서 1의 개수가 홀수일 때 1입니다. XOR은 결합법칙이 성립하므로 세 입력을 차례로 XOR하면 이 패턴이 그대로 나옵니다. 세 입력이 모두 1일 때 1⊕1=0이고 다시 0⊕1=1입니다.
합 출력: S=A⊕B⊕Cin
올림 출력은 다수결 함수입니다
Cout 열은 세 입력 가운데 적어도 두 개가 1일 때 1입니다. 두 비트 이상이 켜져 있으면 정수 합이 2 또는 3이어서 2진수의 2¹ 자리가 생기기 때문입니다. 입력 쌍 A·B, A·Cin, B·Cin 가운데 하나라도 둘 다 1인지 검사한 뒤 OR하면 됩니다.
올림 출력: Cout=(A·B)+(A·Cin)+(B·Cin)
여기서 점은 AND, 더하기 기호는 불 대수의 OR를 뜻합니다. 일반 정수 덧셈 식이 아닙니다. 같은 기능을 Cout=(A·B)+Cin·(A⊕B)로도 쓸 수 있습니다. 먼저 A와 B를 더해 둘 다 1이면 첫 올림 A·B가 생기고, A와 B 중 하나만 1인 상태에서 Cin이 1이면 두 번째 올림 Cin·(A⊕B)이 생긴다는 해석입니다.
반가산기 두 개로 전가산기를 만드는 과정
- 첫 번째 반가산기에 A와 B를 넣어 중간 합 H₁=A⊕B와 올림 C₁=A·B를 만듭니다.
- 두 번째 반가산기에 H₁과 Cin을 넣어 최종 합 S=H₁⊕Cin과 두 번째 올림 C₂=H₁·Cin을 만듭니다.
- 두 올림 C₁과 C₂를 OR해 Cout=C₁+C₂를 만듭니다.
이 구성에는 XOR 게이트 두 개, AND 게이트 두 개, OR 게이트 한 개가 사용됩니다. 논리식을 다른 형태로 최소화하거나 NAND 게이트만으로 변환할 수도 있으므로 실제 반도체의 트랜지스터 수와 지연은 표준 셀 라이브러리 및 회로 설계에 따라 달라집니다. ‘전가산기는 언제나 정확히 다섯 개 게이트’라는 뜻은 아닙니다.
1+1+1이 11₂가 되는 회로 추적
A=1, B=1, Cin=1을 넣어 보겠습니다. 첫 XOR은 1⊕1=0을 내고 첫 AND는 1·1=1을 냅니다. 두 번째 XOR은 중간 합 0과 Cin 1을 계산해 S=1을 냅니다. 두 번째 AND는 0·1=0입니다. 마지막 OR는 두 올림 1과 0을 합쳐 Cout=1을 냅니다. 출력 CoutS는 11₂이며 십진수로 3입니다.
전가산기를 이어 붙이면 여러 자리 수를 더할 수 있습니다
n비트 두 수를 더하려면 각 자리에 전가산기를 하나씩 놓고 낮은 자리의 Cout을 바로 왼쪽 자리의 Cin에 연결합니다. 가장 낮은 자리 Cin에는 0을 넣습니다. 올림이 물결처럼 한 자리씩 전달되므로 리플 캐리 가산기(ripple-carry adder)라고 부릅니다.
예를 들어 4비트 1011₂(11)과 0110₂(6)을 더하면 오른쪽부터 계산합니다. 1+0+0은 합 1·올림 0, 다음 1+1+0은 합 0·올림 1, 다음 0+1+1은 합 0·올림 1, 마지막 1+0+1은 합 0·올림 1입니다. 마지막 올림까지 앞에 붙이면 10001₂, 즉 17입니다.
| 자리(오른쪽부터) | A | B | Cin | S | Cout |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 1 | 0 | 1 |
| 3 | 1 | 0 | 1 | 0 | 1 |
리플 캐리의 속도 한계
각 전가산기의 합과 올림은 이전 자리 올림에 의존합니다. 최하위 자리에서 발생한 올림이 최상위 자리까지 전파되려면 여러 게이트를 연속으로 지나야 합니다. 비트 수가 늘면 최악의 전파 지연도 대체로 길어집니다. 회로는 신호가 도착하는 데 시간이 필요하므로 논리식이 맞는 것만으로는 고속 가산기가 되지 않습니다.
캐리 룩어헤드 가산기는 각 자리에서 올림을 생성하는 조건 Gᵢ=AᵢBᵢ와 전달하는 조건 Pᵢ=Aᵢ⊕Bᵢ를 이용해 여러 자리의 올림을 병렬적으로 계산합니다. 캐리 선택, 캐리 스킵, 병렬 접두 가산기 등도 같은 지연 문제를 줄이기 위한 구조입니다. 전가산기는 이 복잡한 가산기의 기본 논리 단위이지만 실제 CPU의 산술 회로는 성능과 면적, 전력 소비에 맞춰 더 정교하게 구성됩니다.
부호 없는 오버플로와 2의 보수 오버플로는 다릅니다
n비트 부호 없는 정수 덧셈에서는 최상위 자리 Cout이 1이면 표현 범위 0부터 2ⁿ-1을 넘었습니다. 예를 들어 4비트 1111₂+0001₂는 출력 네 비트만 보면 0000이고 Cout이 1입니다. 전체 다섯 비트를 보존하면 10000₂=16입니다.
2의 보수 부호 있는 정수에서는 최종 Cout만으로 오버플로를 판단하지 않습니다. 같은 부호의 두 수를 더했는데 결과 부호가 달라지면 오버플로입니다. 회로식으로는 최상위 비트로 들어가는 올림과 나오는 올림을 XOR한 값으로 검출할 수 있습니다. 같은 전가산기 배열을 쓰더라도 숫자를 부호 있게 해석하는지에 따라 상태 플래그의 의미가 달라집니다.
전가산기는 기억장치가 아니라 조합회로입니다
전가산기의 출력은 현재 입력 A, B, Cin만으로 정해집니다. 이전 계산 결과를 기억하지 않으므로 조합 논리회로입니다. 레지스터와 클록을 붙여 여러 단계의 결과를 저장하거나 파이프라인을 만들 수 있지만, 그 기억 기능은 전가산기 자체가 아니라 플립플롭과 순차회로에서 옵니다.
자주 생기는 오해
- XOR만으로 2진수 덧셈 전체를 할 수 있는 것은 아닙니다. XOR은 합 비트를 만들지만 자리 올림은 별도로 계산해야 합니다.
- OR와 XOR은 다릅니다. 입력이 둘 다 1이면 OR는 1, XOR은 0입니다.
- 반가산기는 이전 자리 올림 입력이 없고 전가산기는 Cin을 포함합니다.
- 불 대수의 + 기호는 문맥에 따라 OR를 뜻합니다. 정수 덧셈 기호와 섞어 읽지 않아야 합니다.
- 전가산기의 논리 기능과 실제 회로의 속도·전력·트랜지스터 수는 별개의 설계 문제입니다.
불 대수와 전가산기 핵심 정리
전가산기는 세 입력 비트 A, B, Cin의 합을 두 출력 Cout과 S로 표현합니다. 합 비트는 세 입력에서 1의 개수가 홀수인지 나타내므로 S=A⊕B⊕Cin입니다. 올림 비트는 세 입력 가운데 둘 이상이 1인지 나타내므로 Cout=AB+ACin+BCin입니다. 반가산기 두 개와 OR 게이트 하나로 같은 기능을 구성할 수 있습니다.
이 한 자리 회로를 낮은 자리부터 이어 붙이면 여러 비트 정수를 더할 수 있습니다. 단순한 리플 캐리 구조는 이해하기 쉽지만 올림이 순서대로 지나가야 해서 비트 수가 클수록 지연이 커집니다. 그래서 고속 프로세서는 올림을 미리 계산하는 여러 가산기 구조를 사용합니다. 그 바닥에는 0과 1, XOR·AND·OR로 표현한 동일한 불 대수 규칙이 놓여 있습니다.