backend/computer science

Nand2tetris: 02 boolean arithmetic and the alu

seul chan 2021. 4. 6. 09:06

2.1. Binary numbers

2진법에 대한 간단한 설명. 자세한 내용은 생략

2.2. Binary addition

이진법을 더하는 법. 10진수처럼 더하면 된다.

다만 할당된 비트 (ex. 8bit + 8bit)를 넘어서는 carry는 overflow로 처리된다.

3가지 형태의 adder를 만들어볼 예정

Half adder

두 bit를 더함.

a, b를 더해서 sum(값)과 carry가 나옴

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

Full adder

위의 half adder에서 이전 계산에서 나온 carry도 받는 adder

a, b, c(이전 carry)를 받아서 sum, carry를 리턴한다

총 진리표를 그려보면 8가지가 나옴

| a | b | c | sum | carry |
| 0 | 0 | 0 | 0   | 0     |
...
| 1 | 1 | 1 | 1   | 1     |

Multi-bit Adder

두 full number를 더해서 output을 내보내는 adder.

16-bit adder는 16bit a, b를 받아 16bit output을 반환한다.

2.3. Negative Numbers

4 bits로 나타낼 수 있는 양수는 0~15 이다. (0000, 0001, ... 1111)

4bit로 음수를 나타는 데에는 여러가지 방법이 있다.

가장 간단한 방법은 음수일 경우 가장 첫번째 bit를 1로 바꾸는 방법

ex.)

0001 -> 1
1111 -> -1
0010 -> 2
1010 -> -2
...

하지만 위 방법은 여러가지 이유로 쓰이지 않음. 위 경우라면 1000이 -0이 되어 구현시에 매번 이를 처리해주어야됨.

그래서 쓰이는 법은 2의 보수법

음수 -x를 "2의n승 - x" (2**n - x)로 표현하는 방법

0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 -8 (8)
1001 -7 (9)
1010 -6 (10)
1011 -5 (11)
1100 -4 (12)
1101 -3 (13)
1110 -2 (14)
1111 -1 (15)

위에서 음수 3을 구하려면 2의 4승에서 3을 뺀 13이 음수3이 된다. (2**4 -3)

2의 보수의 장점

더하기 가능

-2 + -3

  -2 -> 14 -> 1110
+ -3 -> 13 -> 1101

1110 + 1101 = 11011이지만, 11011은 4bit를 넘으므로 overflow를 제외한 1011인 11을 값으로 쓴다.

1011 -> 11 -> -5 (-2 + -3)

Computing -x

_ Input: x
_ Output: -x (in 2s complement)

2**n - x = 1 + (2**n -  1) - x

2**n - 1은 111111.. 이므로 x를 빼고 마지막에 1만 더해주면 됨.

ex. 4의 음수인 -4를 구하려면?

4: 0100

    1. 1111에서 4(0100)를 빼줌: 1111 - 0100 = 1011
    1. 위해서 구한 값(1011)에서 1을 더해줌: 1011 + 1 = 1100 -> 우리가 구하려던 값 (12)이 나온걸 알 수 있음

2.4. Arithmetic Logic Unit (ALU)

폰 노이만 다이어그램을 보면 CPU의 핵심이 ALU인 것을 볼 수 있음.

ALU는 두 input을 받아 output을 내보내 주는 function

  • Arithmetic operations: interger addition, multiplication, division...
  • logical operations: And, Or, Xor ...

The Hack ALU

  • Operators on 2 16-bit 2's complement values
  • Outputs: 16-bit 2's complement values
  • Which function to compute: six 1-bit bit
  • Compute one out of a family of 18 functions
  • Also output two 1-bit values (zr, ng) -> 이후에 설명할 에정

ALU가 함수를 실행시키게 하려면 control bit를 정해진 binary combination에 맞게 세팅하면 됨.

image

완전한 진리표는 2의 6승인 64개이지만 위 truth table은 자주 쓰이는 18개만 표시

The Hack ALU operation

pre-setting the x input

  • zx: if zx then x = 0
  • nx: if nx then x = !x

pre-setting the y input

  • zy: if zy then y = 0
  • ny: if ny then y = !y

selecting between computing + or &

  • f: if f then out=x+y else out=x&y

post-setting the output

  • no: if no then out=!out

위의 6가지 operation을 실행시키면 out이 나옴

ex 1) !x

zx = 0
nx = 0
zy = 1
ny = 1
f = 0
no = 1

위 operation은 !x out이 되는데, 이를 직접 해보면 다음과 같음

Input:

  • x: 1 1 0 0
  • y: 1 0 1 1

Following pre-settings:

  • x: zx, nx가 모두 0이기 때문에 x는 그대로 1 1 0 0
  • y: zy, ny가 모두 1이기 때문에 y는 모두 !0인 1 1 1 1

Computing and post-setting:

  • f = 0 이기 때문에 x&y -> 1 1 0 0
  • no = 1 이기 떄문에 위에서 !(x&y)가 되어 -> 0 0 1 1

결과적으로 !x와 같은 값이 나온다

ex2) y-x

zx = 0
nx = 0
zy = 0
ny = 1
f = 1
no = 1

Input:

  • x: 0 0 1 0 (2)
  • y: 0 1 1 1 (7)

Following pre-settings:

  • x: zx, nx가 모두 0이기 때문에 x는 그대로 0 0 1 0
  • y: zy=0, ny=1이기 때문에 y는 !y -> 1 0 0 0

Computing and post-setting:

  • f = 1이기 때문에 x+y -> 0 0 1 0 + 1 0 0 0 = 1 0 1 0
  • no = 1이기 때문에 !(x+y) -> 0 1 0 1(5)
  • 결론적으로 y-x(7-2)인 5(0 1 0 1)가 나온다

ex3) 위 18개 진리표에 나오지 않은 로직의 결과는?

zx = 1
nx = 0
zy = 1
ny = 1
f = 1
no = 1
  • x: 0 0 1 1 (3)
  • y: 0 1 1 0 (6)
  • x: zx=1, nx=0 -> x = 0 0 0 0
  • y: zy=1, ny=1 -> y = !0 = 1 1 1 1
  • f=1 -> x+y -> 1 1 1 1
  • no=1 -> !(x+y) -> 0 0 0 0

-> 위 로직 조합은 0의 결과가 나옴

The Hack ALU output control bits

zr, ng

if out == 0 then zr = 1, else zr = 0
if out < 0 then ng = 1, else ng = 0

왜 위 두 비트가 필요한지?

Perspective

The Hack ALU is

  • simple
  • elegant
  • easy to implement
    • set 16-bit value to 0000000000000000
    • set 16-bit value to 1111111111111111
    • Negate 16-bit value (bit-wise)
    • Compute + or & on two 16-bit values
    • That's all!

Project 2 overview

  • Given: project 1에서 만든 칩들
  • Goal: 다음 칩들을 제작
    • HalfAdder
    • FullAdder
    • Add16
    • Inc16
    • ALU

HalfAdder

  • input: a, b
  • out: sum, carry

Tip: 두개의 기초적인 게이트로 구현 가능

  • sum: xor
  • carry: and

image

FullAdder

  • input: a, b, c
  • out: sum, carry

Tip: 두개의 half-adder로 구현 가능

image

16-bit adder

  • input: a[16], b[16]
  • out: out[16]

Tip

  • 16 full adder의 sequence로 이뤄짐
  • carry bit는 right to left로 "piped"됨
  • overflow는 무시하면 됨

16-bit incrementor

1을 증가시켜주는 칩. overflow는 무시

  • input: a[16]
  • out: out[16]

Tip:

  • single-bit 0, 1도 hdl로 구현 가능? (true, false)

ALU

Tip:

  • Building blocks: Add16과 project 1에서 만든 칩들
  • 20줄 이하의 HDL 코드로 만들 수 있음..!
저작자표시