덧셈하는 회로의 탄생

계산은 어디서 시작될까

앞 장에서 우리는 논리 게이트를 배웠다. AND는 둘 다 1일 때만 1을 내보내고, OR는 하나라도 1이면 1을 내보내며, NOT은 0과 1을 뒤집는다. 이것만 보면 컴퓨터가 그저 예, 아니오만 판단하는 기계처럼 보인다.

그런데 놀랍게도 이 작은 판단 블록들을 잘 이어 붙이면 덧셈 회로를 만들 수 있다. 덧셈은 컴퓨터 계산의 출발점이다. 숫자를 더할 수 있으면 뺄셈도, 곱셈도, 비교도 만들 수 있다. 마치 레고 블록 몇 종류로 자동차, 집, 로봇을 모두 만드는 것과 같다.

이번 장의 목표는 간단하다. 0과 1을 더하는 회로를 만들고, 그것을 이어 붙여 여러 자리 숫자를 더하는 방법을 보는 것이다.

AI 생성 이미지

이진수 덧셈에서 가장 중요한 순간

사람이 자주 쓰는 십진수에서는 한 자리에서 9보다 커지면 자리올림이 생긴다.

예를 들어 8 + 7은 15다. 일의 자리에는 5를 쓰고, 십의 자리로 1을 올린다.

이진수도 똑같다. 다만 이진수는 한 자리에서 쓸 수 있는 숫자가 0과 1뿐이다. 그래서 1보다 커지는 순간 바로 자리올림이 생긴다.

이진수 한 자리 덧셈은 네 가지뿐이다.

여기서 가장 중요한 줄은 1 + 1 = 10이다.

십진수로 보면 1 더하기 1은 2다. 하지만 이진수에서 2는 10으로 쓴다. 그러므로 한 자리 덧셈 회로는 답을 하나만 내보내면 안 된다.

두 가지를 내보내야 한다.

• 이 자리에 남을 값: 합

• 다음 자리로 넘어갈 값: 자리올림

이제 덧셈 회로의 모양이 조금 보인다. 회로는 두 비트를 입력으로 받고, 합과 자리올림 두 신호를 출력해야 한다.

반가산기: 두 비트를 더하는 첫 번째 회로

두 비트만 더하는 가장 작은 덧셈 회로를 반가산기라고 한다. 가산기는 더하는 장치라는 뜻이고, 반가산기는 아직 완전하지 않은 덧셈 장치라는 뜻이다.

왜 반쪽일까? 두 입력만 더할 수 있고, 이전 자리에서 올라온 자리올림은 아직 받을 수 없기 때문이다.

반가산기의 입력은 두 개다.

• A

• B

출력도 두 개다.

• 합 S

• 자리올림 C

진리표로 보면 이렇게 된다.

이 표를 천천히 보자.

합 S가 1이 되는 때는 언제일까? A와 B가 서로 다를 때다. 0 + 1이면 1이고, 1 + 0이어도 1이다. 하지만 0 + 0이면 0이고, 1 + 1이면 이 자리에는 0이 남는다.

이런 회로를 XOR 게이트라고 부른다. XOR는 두 입력이 서로 다를 때만 1을 내보내는 게이트다. 한국어로는 배타적 OR라고도 하지만, 처음에는 이름보다 규칙이 중요하다.

• 서로 같으면 0

• 서로 다르면 1

그러면 합 S는 XOR 게이트로 만들 수 있다.

자리올림 C는 언제 1이 될까? A와 B가 둘 다 1일 때뿐이다. 이것은 바로 AND 게이트의 규칙이다.

그래서 반가산기는 이렇게 만들 수 있다.

• 합 S = A XOR B

• 자리올림 C = A AND B

덧셈 회로가 갑자기 어려운 마법처럼 보이지 않는다. 사실은 서로 다른지 확인하는 회로 하나와, 둘 다 1인지 확인하는 회로 하나가 나란히 일하는 구조다.

종이 스위치로 따라 해 보기

집에서 실제 반도체 회로를 만들 필요는 없다. 종이 카드만으로도 반가산기의 생각을 흉내 낼 수 있다.

A 카드와 B 카드를 만든다. 각각 0 또는 1을 적는다. 그리고 두 가지 질문을 한다.

첫째, A와 B가 서로 다른가?

• 그렇다: 합은 1

• 아니다: 합은 0

둘째, A와 B가 둘 다 1인가?

• 그렇다: 자리올림은 1

• 아니다: 자리올림은 0

예를 들어 A가 1이고 B가 1이면, 첫 번째 질문의 답은 아니다이다. 그래서 합은 0이다. 두 번째 질문의 답은 그렇다이다. 그래서 자리올림은 1이다.

결과는 10이다. 바로 이진수의 1 + 1 = 10이다.

컴퓨터 안에서는 종이 카드 대신 전압 신호가 움직인다. 0과 1이 전선으로 들어가고, 게이트가 정해진 질문을 한 뒤, 결과 신호를 내보낸다. 생각보다 단순하지만, 이 단순한 일이 엄청나게 빠르게 일어난다.

반가산기만으로는 부족한 이유

반가산기는 두 비트를 더할 수 있다. 그렇다면 여러 자리 숫자도 반가산기만 많이 놓으면 될까?

조금만 계산해 보면 문제가 보인다.

이진수 11과 01을 더해 보자.

  11
+ 01
----
 100

오른쪽 자리부터 보면 1 + 1이다. 결과는 0이고, 다음 자리로 1이 올라간다.

그다음 자리에서는 원래 있던 1 + 0에다가, 오른쪽에서 올라온 자리올림 1도 함께 더해야 한다.

즉 실제로는 세 개를 더해야 한다.

1 + 0 + 자리올림 1

반가산기는 입력이 두 개뿐이다. 오른쪽 자리에서 올라온 자리올림을 받을 자리가 없다. 그래서 여러 자리 덧셈에는 더 완전한 덧셈 회로가 필요하다.

그 회로가 전가산기다.

전가산기: 자리올림까지 받아들이는 회로

전가산기는 세 개의 입력을 더한다.

• A

• B

• 이전 자리에서 올라온 자리올림 Cin

그리고 두 개의 출력을 낸다.

• 합 S

• 다음 자리로 보낼 자리올림 Cout

여기서 Cin은 carry in, 즉 들어오는 자리올림이다. Cout은 carry out, 즉 나가는 자리올림이다.

전가산기의 규칙도 어렵지 않다. 입력 세 개 중 1이 몇 개인지만 세면 된다.

입력에 1이 하나 있으면 합은 1, 자리올림은 0이다.

입력에 1이 두 개 있으면 합은 0, 자리올림은 1이다. 이진수로 2는 10이기 때문이다.

입력에 1이 세 개 있으면 합은 1, 자리올림은 1이다. 십진수 3은 이진수로 11이다.

전가산기를 만드는 방법도 재미있다. 반가산기 두 개와 OR 게이트 하나를 이어 붙이면 된다.

1. 첫 번째 반가산기가 A와 B를 더한다.

2. 그 결과로 임시 합과 첫 번째 자리올림이 나온다.

3. 두 번째 반가산기가 임시 합과 Cin을 더한다.

4. 두 번째 합이 최종 합 S가 된다.

5. 두 반가산기에서 나온 자리올림들을 OR 게이트로 합쳐 Cout을 만든다.

왜 마지막에 OR를 쓸까? 두 곳 중 어느 한 곳에서라도 자리올림이 생기면 다음 자리로 1을 보내야 하기 때문이다.

전가산기는 작은 덧셈 공장 같다. A와 B가 들어오고, 옆 공장에서 넘어온 자리올림도 들어온다. 공장은 이 자리에 남길 결과를 포장해 내보내고, 넘치는 값은 다음 공장으로 보낸다.

여러 자리 덧셈: 전가산기를 줄줄이 잇기

이제 여러 자리 숫자를 더할 수 있다. 방법은 간단하다. 전가산기를 자리 수만큼 나란히 놓는다.

가장 오른쪽, 즉 가장 작은 자리부터 계산한다. 여기에는 이전 자리에서 올라온 값이 없으므로 Cin은 0으로 시작한다. 그 자리의 Cout은 바로 왼쪽 자리의 Cin으로 들어간다.

이렇게 자리올림이 오른쪽에서 왼쪽으로 차례차례 전해진다. 물길이 작은 수문을 지나 다음 수문으로 흘러가는 모습과 비슷하다.

예를 들어 0111과 0101을 더해 보자. 십진수로는 7 + 5다.

  0111
+ 0101
------
  1100

오른쪽부터 따라가면 이렇다.

결과는 1100이다. 이진수 1100은 십진수 12다. 7 + 5 = 12와 맞다.

이런 덧셈 회로를 리플 캐리 가산기라고 부른다. 리플은 물결처럼 퍼진다는 뜻이다. 자리올림이 오른쪽에서 왼쪽으로 물결처럼 전달되기 때문에 붙은 이름이다.

단점도 있다. 앞자리의 결과가 완전히 정해지려면 오른쪽에서 온 자리올림을 기다려야 한다. 자리 수가 많아지면 기다리는 시간이 길어진다. 그래서 실제 CPU에는 더 빠르게 자리올림을 예측하거나 나누어 계산하는 여러 방법이 쓰인다. 하지만 기본 생각은 같다. 한 자리 덧셈 회로를 잘 연결하면 큰 숫자도 더할 수 있다.

덧셈 회로가 계산의 중심이 되는 이유

컴퓨터가 계산한다는 말은 이제 조금 더 구체적으로 보인다. 숫자가 0과 1의 줄로 표현되고, 각 자리가 전기 신호로 회로에 들어간다. 논리 게이트들은 그 신호를 보고 합과 자리올림을 만든다. 자리올림은 다음 자리로 전달된다. 마지막에 남은 0과 1의 줄이 계산 결과다.

그렇다면 컴퓨터는 덧셈만 잘하면 될까? 놀랍게도 많은 계산이 덧셈에서 출발한다.

뺄셈은 덧셈 회로를 살짝 바꾸어 만들 수 있다. 컴퓨터는 보통 빼려는 수의 비트를 뒤집고 1을 더하는 방법을 사용한다. 이를 2의 보수라고 한다. 처음에는 이상해 보이지만, 정해진 자리 수 안에서는 뺄셈을 덧셈 문제로 바꾸어 주는 아주 편리한 약속이다.

곱셈도 덧셈을 반복하고 자리를 옮기는 방식으로 만들 수 있다. 십진수 곱셈에서 한 줄씩 곱한 뒤 아래로 더하는 것과 비슷하다. 이진수에서는 각 자리가 0 또는 1뿐이라 더 단순하다. 1이면 그 수를 더하고, 0이면 더하지 않는다.

비교도 덧셈과 연결된다. 두 수가 같은지 보려면 빼 보았을 때 결과가 0인지 확인하면 된다. 어느 쪽이 큰지 알고 싶을 때도 뺄셈 결과의 부호나 자리올림 상태를 살펴볼 수 있다.

그래서 CPU 안에는 산술 논리 장치, 줄여서 ALU라는 부분이 있다. ALU는 더하기, 빼기, 비교하기, AND 같은 논리 연산을 맡는 계산 작업대다. 그 중심에는 오늘 배운 가산기의 생각이 들어 있다.

아직 부족한 한 가지: 시간을 기억하기

덧셈 회로는 입력이 들어오면 규칙에 따라 출력을 만든다. 하지만 지금까지의 회로는 결과를 오래 붙잡아 두지 않는다. 입력이 바뀌면 출력도 바뀐다.

이런 회로를 조합 논리 회로라고 부른다. 현재 입력만 보고 현재 출력을 정하는 회로라는 뜻이다. 반가산기와 전가산기가 여기에 속한다.

하지만 컴퓨터가 제대로 일하려면 계산 결과를 잠시 기억해야 한다. 다음 명령을 실행할 때 이전 결과를 써야 하기 때문이다. 계산이 끝난 값을 붙잡아 두는 회로가 필요하다.

다음 장에서는 시간이 들어간 회로를 만난다. 0과 1을 단순히 지나가게 하는 것이 아니라, 잠시 붙잡아 두는 방법을 배울 것이다. 계산하는 회로에 기억하는 회로가 더해지면, 컴퓨터는 한 걸음 더 실제 기계에 가까워진다.