배우기 › 주제 7

2진 가산기: 반가산기, 전가산기, 리플 캐리 가산기

읽는 시간 8분 · bitGateLab 팀

덧셈은 컴퓨터에서 가장 중요한 연산입니다. 덧셈으로 뺄셈과 곱셈을 하고, 메모리 주소를 계산하고, 사건의 횟수를 셉니다. 여기서는 가산기를 처음부터 만들어 봅니다. 먼저 한 비트짜리 반가산기, 그다음 캐리를 받는 전가산기, 이어서 여러 비트를 줄줄이 이은 가산기를 만들고, 마지막으로 같은 회로가 2의 보수를 이용해 뺄셈을 하는 방법을 알아봅니다.

손으로 하는 2진 덧셈

두 비트를 더하는 규칙은 네 가지입니다. 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 그리고 1 + 1 = 10₂, 즉 결과는 0이고 다음 자리로 캐리(자리올림) 1이 넘어갑니다. 여기에 캐리까지 들어오면 1 + 1 + 1 = 11₂로, 결과 1에 캐리 1입니다. 10진수에서와 마찬가지로 오른쪽에서 왼쪽으로 한 자리씩 더하면서 캐리를 왼쪽으로 넘깁니다.

반가산기

반가산기는 두 비트 A와 B를 더해 두 개의 출력, 즉 합 S와 캐리 C를 내보냅니다.

S 열은 XOR의 진리표이고 C 열은 AND의 진리표입니다. 따라서:

S = A ⊕ B    C = AB

"반"가산기라고 부르는 이유는 앞자리에서 넘어오는 캐리를 받는 입력이 없기 때문입니다. 그래서 최하위 비트에만 쓸 수 있습니다.

전가산기

전가산기는 세 비트, 즉 A, B, 그리고 캐리 입력 C_in을 더합니다. 합 S와 캐리 출력 C_out을 내보냅니다. (C_out, S) 쌍이 입력에 들어 있는 1의 개수를 2진수로 나타낸 것이라는 점을 눈여겨보세요.

S는 1의 개수가 홀수일 때 1입니다: S = Σm(1, 2, 4, 7) = A ⊕ B ⊕ C_in. C_out은 1이 둘 이상일 때 1입니다: C_out = Σm(3, 5, 6, 7). 이를 간소화하면 다수결 함수가 됩니다.

C_out = AB + AC_in + BC_in

S의 카르노 맵에서 묶어 보려고 하면 어떤 1도 1인 이웃이 없다는 것을 알게 됩니다. XOR 특유의 체스판 무늬이며, 곱의 합으로는 간소화되지 않습니다.

반가산기 두 개로 만드는 전가산기

실용적인 구성 방법은 반가산기 두 개와 OR 하나를 잇는 것입니다.

1. 첫 번째 반가산기: P = A ⊕ B, G = AB.
2. P와 C_in을 받는 두 번째 반가산기: S = P ⊕ C_in, 그리고 부분 캐리 P·C_in.
3. C_out = G + P·C_in = AB + (A ⊕ B)C_in.

이 식은 다수결 식과 동치입니다. A와 B가 모두 1이면 AB가 이미 캐리를 만들고, 둘 중 정확히 하나만 1이면 캐리는 C_in에 달려 있습니다. G를 캐리 생성 신호, P를 캐리 전파 신호라고 합니다.

리플 캐리 가산기

비트 수가 n인 수를 더하려면 전가산기 n개를 한 줄로 연결합니다. 각 단의 C_out이 다음 단의 C_in으로 들어갑니다. 첫 단의 C_in은 0으로 두고, 마지막 단의 C_out이 최종 캐리입니다. 이 구조를 리플 캐리 가산기(ripple carry)라고 하는데, 캐리가 물결처럼 한 단씩 "전파"되기 때문입니다. 74HC 계열에는 이렇게 연결된 전가산기 네 개가 들어 있는 칩(74HC283)이 있습니다.

대가는 시간입니다. 3번 단은 2번 단의 캐리가 도착할 때까지 최종 결과를 낼 수 없고, 2번 단은 다시 1번 단의 캐리를 기다립니다. 각 단이 캐리를 만드는 데 게이트 두 단계가 걸린다면, n비트 가산기는 최악의 경우 게이트 지연의 2n배 정도가 걸립니다. 64비트에서는 너무 느리므로, 프로세서는 G와 P 신호로부터 캐리를 병렬로 계산하는 캐리 룩어헤드 가산기를 사용합니다. 시뮬레이터의 타이밍도에서 출력이 단계적으로 바뀌다가 안정되는 모습을 볼 수 있습니다.

같은 가산기로 뺄셈하기

앞서 수 체계에서 설명했듯이, 2의 보수에서 B의 음수는 B + 1입니다. 따라서:

A − B = A + B + 1

이를 구현하려면 B의 각 비트에 XOR를 하나씩 두고, XOR의 다른 입력을 제어선 M에 연결하고, M을 첫 단의 C_in에도 연결하면 됩니다. M = 0이면 XOR들이 B를 그대로 통과시키고 C_in = 0이므로 회로는 덧셈을 합니다. M = 1이면 XOR들이 B를 반전하고 C_in = 1이 "+1"을 더해 주므로 회로는 뺄셈을 합니다.

흔한 실수

• 중간 단에 반가산기를 쓰는 것. 캐리를 받는 단에는 모두 전가산기가 필요합니다.
• 첫 단의 C_in을 플로팅 상태로 두는 것. 덧셈을 하려면 0에, 가감산기에서는 M에 연결해야 합니다.
• 최종 캐리와 오버플로를 혼동하는 것. 부호 있는 수에서 최종 캐리는 버리며, 오버플로는 C₃ ⊕ C₄로 검출합니다.
• 뺄셈에서 "+1"을 잊고 인버터만 연결하는 것: 결과가 하나 작게 나옵니다.
• S = A + B + C_in을 OR로 쓰는 것. 한 비트의 합은 OR가 아니라 XOR입니다.

시뮬레이터에서 해 보기

편집기에서 가산기를 만들어 보는 것은 게이트와 산술을 잇는 가장 좋은 다리입니다. 한 비트에서 시작해 네 비트까지 키워 보세요.

1. 입력 두 개, XOR 하나, AND 하나를 놓고 반가산기 그림처럼 연결합니다. 진리표를 생성합니다.
2. 반가산기 두 개와 OR 하나로 전가산기를 만들고, 8개 행을 이 글의 표와 대조해 확인합니다.
3. 전가산기를 네 번 복사해 캐리를 이어 줍니다. 첫 C_in은 0으로 둡니다.
4. 입력을 1011과 0110으로 바꾸고 출력이 0001, 최종 캐리가 1인지 확인합니다.
5. 타이밍도를 열고, 캐리가 네 단을 모두 지나가게 만드는 입력(예: 1111 + 0001)으로 바꾼 뒤 출력이 안정되는 과정을 관찰합니다.

연습문제

1. 전가산기의 S와 C_out을 구하세요. 입력은 A = 1, B = 0, C_in = 1입니다.
   정답

   1이 두 개이므로 S = 0, C_out = 1입니다(1 + 0 + 1 = 10₂).

2. 4비트 가산기로 0111 + 0101을 더하고 각 단의 캐리를 쓰세요.
   정답

   0번 단: 1 + 1 = 0, 캐리 1. 1번 단: 1 + 0 + 1 = 0, 캐리 1. 2번 단: 1 + 1 + 1 = 1, 캐리 1. 3번 단: 0 + 0 + 1 = 1, 캐리 0. 결과 1100 = 12 (7 + 5).

3. 4비트 가감산기로 6 − 3을 계산하고 M의 값을 쓰세요.
   정답

   M = 1. 0110 + 1100 + 1 = 1 0011. 캐리를 버리면 0011 = 3.

4. 4비트 부호 있는 수로 해석할 때 0111 + 0101에서 오버플로가 일어납니까?
   정답

   예. 7 + 5 = 12는 −8부터 +7까지의 범위에 들어가지 않습니다. 결과 1100은 −4로 읽히게 됩니다. 캐리는 C₃ = 1, C₄ = 0이고 V = 1 ⊕ 0 = 1입니다.