앞자리가 뒷자리한테 넘기는 것

이전 글에서 논리 게이트를 조합해 한 자리 이진수 덧셈을 수행하는 반가산기를 만들었다. 하지만 반가산기에는 한 가지 한계가 있다. 첫 자리를 계산할 때는 두 개의 입력만 고려하면 되지만, 그 다음 자리부터는 이전 자리에서 올라온 올림값(Carry) 까지 함께 처리해야 하기 때문이다.

전가산기

아래에서 비트를 클릭해 두 자리 이진수 덧셈을 직접 해보자. 2의 자리를 계산할 때 올림값이 어떻게 전달되는지 확인할 수 있다.

이처럼 세 개의 입력값(A, B, 그리고 아래 자리에서 올라온 Carry)을 모두 처리할 수 있는 회로를 전가산기(full adder) 라고 한다.

전가산기의 진리표는 다음과 같다. 구분을 위해 이전 자리에서 올라온 올림값을 Cin으로, 다음 자리로 넘어가는 올림값을 Cout이라고 한다.

복잡해 보이지만 각 행을 이진수 덧셈이라고 생각해보자. 예를 들어 마지막 행은 1 + 1 + 1 = 11₂이므로 Sum은 1, Cout은 1이 된다.

전가산기는 반가산기와 OR 게이트를 활용해 만들 수 있다.

여러 자리 덧셈

전가산기 하나로는 1비트 덧셈만 가능하다. 그럼 4비트나 8비트처럼 여러 자리 숫자를 더하려면 어떻게 해야 할까?

자릿수가 바뀐다고 덧셈의 방식이 바뀌는 것은 아니니 단순히 전가산기 여러 개를 차례대로 연결하면 된다. 각 자리마다 하나의 전가산기를 배치하고, 한 자리의 Carry-out을 다음 자리의 Carry-in으로 연결하는 것이다.

전가산기 10개면 1000이 넘는, 30개면 10억이 넘는 수까지의 덧셈도 가능하다. 아래 예제에서는 111₂ + 1₂ = 1000₂를 계산한다.

이런 방식을 리플 캐리 가산기라고 부른다. 올림이 물결(ripple)처럼 다음 자리로 차례차례 전파되기 때문이다.

마무리

참고로, 덧셈뿐만 아니라 뺄셈과 곱셈도 모두 논리 게이트의 조합으로 만들 수 있다.

• 뺄셈은 2의 보수를 이용해 덧셈처럼 처리할 수 있고,
• 곱셈은 여러 자리의 덧셈을 반복해서 구현할 수 있다.

한 가지 문제가 남아있다. 지금까지 만든 회로들은 모두 계산 결과를 기억하지 못한다. 계산이 끝나면 결과가 사라져버린다. 실제 컴퓨터가 되려면 정보를 저장하고 기억할 수 있어야 한다.

예를 들어, 1000번째 피보나치 수를 계산하고 싶다고 해보자. 피보나치 수열은 앞의 두 값을 계속 더해서 다음 값을 만들어가는 구조인데, 이전 계산 결과를 하나도 기억하지 못한다면 매번 처음부터 다시 계산해야 한다. 그만큼 비효율적이고, 실질적인 프로그램도 만들 수 없게 된다.

다음 글에서는 이 문제를 해결해보자. 논리 게이트를 이용해서 정보를 저장하는 회로를 만들고, 메모리의 기본 원리를 이해해보자.