25.06
이전 글에서 논리 게이트를 조합해 한 자리 이진수 덧셈을 수행하는 반가산기를 만들었습니다. 하지만 반가산기에는 한 가지 한계가 있습니다. 첫 자리를 계산할 때는 두 개의 입력만 고려하면 되지만, 그 다음 자리부터는 이전 자리에서 올라온 올림값(Carry)까지 함께 처리해야 하기 때문입니다.
아래에서 비트를 클릭해 두 자리 이진수 덧셈을 직접 해봅시다. 2의 자리를 계산할 때 올림값이 어떻게 전달되는지 확인할 수 있습니다.
1의 자리 반가산기
2의 자리 전가산기
이처럼 세 개의 입력값(A, B, 그리고 아래 자리에서 올라온 Carry)을 모두 처리할 수 있는 회로를 전가산기(full adder)라고 합니다.
전가산기의 진리표는 다음과 같습니다. 구분을 위해 이전 자리에서 올라온 올림값을 Cin으로, 다음 자리로 넘어가는 올림값을 Cout이라고 합니다.
| Cout | Sum | |||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
복잡해 보이지만 각 행을 이진수 덧셈이라고 생각해봅시다. 예를 들어 마지막 행은 1 + 1 + 1 = 11₂이므로 Sum은 1, Cout은 1이 됩니다.
전가산기는 반가산기와 OR 게이트를 활용해 만들 수 있습니다.
전가산기 하나로는 1비트 덧셈만 가능합니다. 그럼 4비트나 8비트처럼 여러 자리 숫자를 더하려면 어떻게 해야 할까요?
자릿수가 바뀐다고 덧셈의 방식이 바뀌는 것은 아니니 단순히 전가산기 여러 개를 차례대로 연결하면 됩니다. 각 자리마다 하나의 전가산기를 배치하고, 한 자리의 Carry-out을 다음 자리의 Carry-in으로 연결하는 것입니다.
전가산기 10개면 1000이 넘는, 30개면 10억이 넘는 수까지의 덧셈도 가능합니다. 아래 예제에서는 1112 + 12 = 10002를 계산합니다.
이런 방식을 리플 캐리 가산기라고 부릅니다. 올림이 물결(ripple)처럼 다음 자리로 차례차례 전파되기 때문입니다.
참고로, 덧셈뿐만 아니라 뺄셈과 곱셈도 모두 논리 게이트의 조합으로 만들 수 있습니다.
한 가지 문제가 남아있습니다. 지금까지 만든 회로들은 모두 계산 결과를 기억하지 못합니다. 계산이 끝나면 결과가 사라져버립니다. 실제 컴퓨터가 되려면 정보를 저장하고 기억할 수 있어야 합니다.
예를 들어, 1000번째 피보나치 수를 계산하고 싶다고 해봅시다. 피보나치 수열은 앞의 두 값을 계속 더해서 다음 값을 만들어가는 구조인데, 이전 계산 결과를 하나도 기억하지 못한다면 매번 처음부터 다시 계산해야 합니다. 그만큼 비효율적이고, 실질적인 프로그램도 만들 수 없게 됩니다.
다음 글에서는 이 문제를 해결해봅시다. 논리 게이트를 이용해서 정보를 저장하는 회로를 만들고, 메모리의 기본 원리를 이해해봅시다.