NAND to Tetris - 2장: Adder, Inc, ALU

이번 장에서는 지난 장에서 만든 게이트들을 사용하여 두 이진 수를 더하는 Adder 게이트, 입력에 1을 더한 수를 반환하는 Inc 게이트, 그리고 CPU의 모든 연산을 담당하는 아주 중요한 ALU 게이트를 만들어 볼 것이다. 불 연산으로 덧셈을 구현한다는 것은 개인적으로 신기했는데, 어떻게 했는지 같이 살펴보자. 

 

2진수의 음수 표현

덧셈을 구현하려면 우선 2진수에서 음수를 어떻게 표현할지를 생각해봐야 한다. 왜냐하면 컴퓨터는 식 3 - 2를 사실 3 + (-2)로 계산하는데, 음수를 어떻게 표현했는지에 따라 이 계산이 조금 더 쉬워질 수도 있고 어려워질 수도 있기 때문이다. 2진수로 음수를 표현하는 방법은 3가지가 있다.

 

1) 부호와 크기를 표현

가장 쉬운 방법은 가장 왼쪽 비트로 양수 또는 음수인지를 표현하고 나머지 비트로 크기를 표현하는 방법이다. 예를 들어 -5를 8비트로 표현하는 경우 10000101 가 된다. 이 방법은 간단하지만 두 가지 문제가 있다. 첫째로, 0을 나타내는 방법이 2가지가 되어 모호함이 생긴다. 00000000과 10000000 모두 0으로 해석된다. 둘째로, 음수를 더할 때 단순 이진 덧셈을 한다면 잘못된 결과가 나온다.

예를 들어 5 + (-5)를 해보자. 

  00000101 // 5
+ 10000101 // -5
 -----------
  10001010 // -10

 

올바른 정답은 0이어야 하지만 -10이 나왔다. 이렇게 부호와 크기를 표현하는 방식에서는 양수를 더할 때와 음수를 더할 때 덧셈의 구현을 다르게 해야 한다는 불편함이 있다. 그 말은 덧셈 게이트 구현을 위해 더 많은 하드웨어가 필요하다는 뜻이고, 이는 제작 비용과 성능 모두에 안 좋으므로 다른 방법을 찾아봐야 한다.

 

2) 1의 보수

2진수로 음수를 표현하는 또 다른 방법으로는 1의 보수가 있다. 어떤 수의 1의 보수를 구할 때는 111... 1과 자기 자신을 XOR 하면 된다 (쉽게 말해 각 비트를 뒤집는다). 예를 들어 8비트에서 5의 1의 보수는 11111010이다. 

 

    00000101 // 5
XOR 11111111
------------
    11111010 // -5

 

이 표현법도 부호와 크기 표현법처럼 두가지 문제점이 있다. 첫 번째 문제점은 이 표현법에서도 0은 두 가지로 표현될 수 있다. 000... 0도 0이지만, 111... 1도 0이다. 두 번째 문제점은 두 수를 더했을 때 가장 왼쪽 비트에서 올림 (순환 올림)이 발생했을 때는 이 올림을 가장 오른쪽 비트로 보내 다시 더해줘야 하는 불편함이 있다.

 

  00000101 // 5
+ 11111100 // -3
-----------
 100000001 (순환 올림 발생)

  00000001
+        1 (순환 올림 비트를 가장 오른쪽 비트에 더해주기)
-----------
  00000010 // 2

 

부호와 크기 표현법과 1의 보수는 언급된 문제들 때문에 현대 컴퓨터 시스템에서는 잘 사용되지 않는다. 위 문제점들을 해결한 2의 보수를 알아보자.

 

3) 2의 보수

2의 보수는 1의 보수에 1을 더하고, 가장 왼쪽 비트에서의 올림은 무시함으로써 얻을 수 있다. 예를 들어 8비트에서 5의 2의 보수는 11111011이다. 2의 보수법에서는 0의 표현이 단 하나이다. 00000000의 2의 보수는 그대로 00000000이기 때문이다.

 

또 2의 보수 덧셈은 앞의 표현법들보다 훨씬 간단하다. 두 수를 더하고, 가장 왼쪽 비트에서의 올림은 무시한다.

 

  00000101 // 5
+ 11111101 // -3
-----------
 100000010 
-----------
  00000010 // 2 (가장 왼쪽 비트에서의 올림은 무시)

 

2의 보수로 음수를 표현하면 이렇게 덧셈이 단순해지므로 현대 컴퓨터는 대부분 2의 보수를 사용하고 있으며, 우리도 2의 보수를 사용할 것이다.

 

만들 것들

반가산기

반가산기, 또는 half adder는 2진수 덧셈을 구현하기 위한 첫 번째 단계이다. 반가산기는 두 비트를 입력으로 받고 sum과 carry를 반환한다. 반가산기의 진리표는 다음과 같다.

 

a	b	sum	carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

 

진리표를 잘 보면 sum과 carry는 x와 y의 간단한 불 연산만으로 표현할 수 있을 것 같다. 자세한 구현은 다음 글에서 설명하겠다.

 

전가산기

전가산기, 또는 full adder는 3개의 비트를 입력으로 받아 sum과 carry를 반환한다.

 

a	b	c	sum	carry
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

 

16비트 가산기

두 16비트 수를 입력받아 두 수의 합을 반환한다. 오버플로우는 무시한다. 전가산기를 활용하여 구현하면 된다.

 

16비트 증분기

16비트 수 하나를 입력받아 그 수에 1을 더한 값을 반환한다. 오버플로우는 무시한다.

 

ALU

이번 장에서 만드는 부품들 중 가장 핵심적인 역할을 하는 부품이다. 두 수의 덧셈, 뺄셈, 불 연산, 입력을 0 또는 1 또는 -1로 만들기, 1 더하기, 1 빼기 등등 다양한 연산을 할 수 있는 하나의 칩을 만들 것이다. 우리가 만들 CPU에는 곱셈 연산이 없다. 우리는 곱셈 연산을 하드웨어에서 하지 않고 나중에 소프트웨어(운영체제)에서 처리하도록 만들 것이다. 

 

ALU의 입력은 16비트 두 수 x, y 그리고 6개의 제어 비트 zx, nx, zy, ny, f, no가 있다.

zx가 1이면 x를 0으로 만들고, nx가 1이면 x를 반전시킨다. zy, ny는 y에 대해서 똑같이 행한다. f가 1이면 변환된 x와 y를 더하고, 0이면 AND 연산을 한다. no가 1이면 반환 값을 반전시킨다. 

ALU는 최종적으로 계산된 값을 반환하고 그 외에도 zr, ng를 반환한다. zr은 계산 결과가 0이면 True, ng는 계산 결과가 음수이면 True이다.

 

제어 비트에 따른 ALU의 결과 진리표는 다음과 같다. 전체 열의 수는 64개이지만 중요한 18개만 나열해보았다.

 

zx	nx	zy	ny	f	no	out
1	0	1	0	1	0	0
1	1	1	1	1	1	1
1	1	1	0	1	0	-1
0	0	1	1	0	0	x
1	1	0	0	0	0	y
0	0	1	1	0	1	!x
1	1	0	0	0	1	!y
0	0	1	1	1	1	-x
1	1	0	0	1	1	-y
0	1	1	1	1	1	x+1
1	1	0	1	1	1	y+1
0	0	1	1	1	0	x-1
1	1	0	0	1	0	y-1
0	0	0	0	1	0	x+y
0	1	0	0	1	1	x-y
0	0	0	1	1	1	y-x
0	0	0	0	0	0	x&y
0	1	0	1	0	1	x|y

 

위 표에서 몇몇 결과는 재미있다. 예를 들어 세 번째 행은 zx가 1이므로 x을 우선 0으로 만든다. 그리고 nx가 1이므로 x를 뒤집는다. 2의 보수 표현법에서는 !x 는 -x - 1이다. (2의 보수 표현법에서 -x 는 !x + 1이므로) 따라서 x는 -1이 된다. y는 zy가 1이므로 0이 된다. f가 1이므로 결과는 -1 + 0 = -1이 된다.

 

밑에서 네 번째 행(x-y)도 봐보자. nx가 1이므로 x를 -x - 1로 바꾼다. y는 바꾸지 않고 그대로 둔다. f가 1이므로 두 수를 더해 (-x - 1 + y) 이 되고, no가 1이므로 이 결과를 다시 뒤집는다. 그럼 최종 결과는 -(-x -1 + y)-1 = x + 1 - y - 1 = x - y 가 된다.

 

6개의 제어 비트를 사용해 하나의 게이트로 여러 실용적인 연산을 할 수 있게 만들었다. 하지만 지금까지 만든 게이트들은 단순히 입력에 대한 계산 결과만 구할 수 있다. 우리가 프로그래밍을 할 때 어떤 값을 변수에 담아놓고 여러 번 불러와 쓸 수 있으려면 값을 저장할 수 있는 무언가가 필요하다. 이에 대해선 3장에서 다룬다.