NAND to Tetris - 1장: 조합 게이트

우리가 처음으로 만들어 볼 것은 AND, OR, NOT, XOR, MUX, DMUX 등의 불 함수의 결과를 반환하는 게이트웨이이다. 이 게이트를 만들면 다음에는 이 게이트들로 가산기와 ALU를 만들 것이다. 게이트는 트랜지스터로 만들 수 있다. 하지만 트랜지스터는 컴퓨터과학보다는 물리학의 분야이기 때문에 이 과정에서는 트랜지스터 이하 계층은 생략하고, 태초에 누군가가 트랜지스터로 NAND 게이트를 만들어 두었다고 생각하고 진행한다. 이후에 설명하겠지만, NAND 게이트 하나로 모든 게이트를 만들 수 있다.

 

불 함수

불 함수는 m개의 불리언 값을 입력받아 n개의 불리언 값을 반환하는 함수이다. 게이트는 이 불 함수를 물리적으로 만든 것이다. 불 함수를 표현하는 방법은 두 가지가 있다. 하나는 진리표를 이용한 방법, 또 다른 하나는 불 표현식을 이용한 방법이다.

 

x	y	f(x, y)
0	0	1
0	1	0
1	0	1
1	1	0

 

위 표는 입력이 2개이고 반환값이 1개인 한 불 함수의 진리표를 나타낸 것이다. 이 진리표는 같은 의미를 가지는 불 표현식으로도 나타낼 수 있다. 하나의 진리표에는 여러 불 표현식이 있을 수 있다. 예를 들어 위 진리표를 NOT y 로도 표현 가능하지만 (NOT x AND NOT y) OR (x AND NOT y) 로도 표현 가능하다. 따라서 진리표는 게이트의 인터페이스, 불 표현식은 게이트의 구현으로 생각할 수 있다.

 

또 모든 진리표는 그에 대응하는 불 표현식을 하나 이상 가진다. 정준 표현을 사용하여 하나의 불 표현식을 쉽게 찾을 수 있다. 반환 결과가 1인 행들을 표현하고, 행들을 OR로 합치면 된다. 위 진리표에서는 첫째행과 셋째행의 결과가 1인데, 각각 NOT x AND NOT y, x AND NOT y이다. 이들을 OR로 합치면 (NOT x AND NOT y) OR (x AND NOT y)이고, 진리표를 대입해보면 이 표현식이 맞다는 것을 증명할 수 있다.

HDL

게이트를 만드는 개발자들은 자신이 만든 게이트의 실행 결과가 진리표 (인터페이스)와 같은지를 테스트해야하고, 만약 틀렸다면 수정하고, 또 여러 구현 중 어떤 것이 성능과 에너지 효율이 좋은지 비교해봐야 한다. 이 과정을 직접 칩을 만들어야 한다면 무척 어렵고 비용이 많이 들 것이다. 따라서 게이트를 구현할 때는 HDL이라는 언어를 사용하여 하드웨어 시뮬레이터로 테스트하고, 설계가 완료된 이후에 HDL을 기반으로 칩을 만든다. 우리도 또한 하드웨어 시뮬레이터와 HDL을 사용해서 게이트를 구현할 것이다.

 

만들 것들

우리는 NAND 게이트는 이미 만들어져있다고 가정하고 진행한다. NAND 게이트의 진리표는 다음과 같다.

x	y	x NAND y
0	0	1
0	1	1
1	0	1
1	1	0

NAND 게이트로 아래의 여러 조합 게이트들을 만들 것이다. 이번 글에서는 게이트들의 인터페이스만 설명하고 실제 구현은 다음 글에서 설명하겠다. 인터페이스를 보고 HDL 코드로 직접 게이트를 구현해보자. 이 책에서 쓰는 HDL 코드는 실제 HDL과 비슷하지만 매우 간단하게 축약된 언어이다. 자세한 내용은 책의 부록 A를 참고한다.

 

Not

입력이 1이면 0을 반환하고 입력이 0이면 1을 반환한다.

x	NOT x
0	1
1	0

 

And

두 입력이 모두 1이면 1을 반환하고 나머지 경우엔 0을 반환한다.

x	y	x AND y
0	0	0
0	1	0
1	0	0
1	1	1

 

Or

두 입력 중 하나 이상이 1이면 1을 반환하고 나머지 경우엔 0을 반환한다.

x	y	x OR y
0	0	0
0	1	1
1	0	1
1	1	1

 

Xor

두 입력의 값이 다를 경우 1을 반환하고 같으면 0을 반환한다.

x	y	x XOR y
0	0	0
0	1	1
1	0	1
1	1	0

 

멀티플랙서 (Mux)

멀티플랙서는 두 입력 중에서 한 입력을 선택해서 반환한다. sel이 0이면 a의 값을 반환하고 sel이 1이면 b의 값을 반환한다.

sel	a	b	out
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

 

디멀티플랙서 (Dmux)

디멀티플랙서는 in으로 들어온 입력을 두 출력선 a, b 중 하나로 반환한다. sel이 0이면 a 출력선에서 in을 반환하고, sel이 1이면 b 출력선에서 in을 반환한다.

sel	in	a	b
0	0	0	0
0	1	1	0
1	0	0	0
1	1	0	1

 

Not16, And16, Or16, Mux16

각각 Not, And, Or, Mux와 동작은 같고 입력과 출력이 16비트인 점만 다르다.

 

Or8Way

8비트 입력을 받아 8비트 중 한 비트라도 1이면 1을 반환하고 그 외에는 0을 반환한다.

 

Mux4Way16

Mux16에서 입력이 두 개가 아니라 a, b, c, d 4개로 바뀌었고, 그에 따라 sel도 2비트로 바뀐 게이트이다.

sel[1]	sel[0]	out
0	0	a
0	1	b
1	0	c
1	1	d

 

Mux8Way16

이번에는 입력이 a ~ h까지 8개인 Mux이다. sel은 3비트로 바뀌었고, sel의 값이 0 ~ 7일 때 각각 a ~ h를 반환한다.

 

Dmux4Way

Dmux에서 출력선이 4개로 바뀌었고 sel은 2비트이다. 

sel[1]	sel[0]	a	b	c	d
0	0	in	0	0	0
0	1	0	in	0	0
1	0	0	0	in	0
1	1	0	0	0	in

 

Dmux8Way

출력선이 8개, sel은 3비트인 Dmux 게이트이다.