Boolean Arithmetic

2.1 Background

1) Binary Numbers

Binary Number: 0과 1만을 사용하는 base-2 수 체계.

$n$ 자리 이진수

x_nx_{n-1}\cdots x_1x_0

의 값은 다음과 같이 계산한다.

(x_nx_{n-1}\cdots x_0)_2 = \sum_{i=0}^{n}x_i2^i

예를 들어,

(10011)_2 = 1\cdot2^4 + 0\cdot2^3 + 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = 19

Meaning: 컴퓨터는 수를 bit의 조합으로 표현한다.

2) Bit Significance

Least Significant Bit (LSB): 이진수에서 가장 오른쪽에 있는 bit.

Most Significant Bit (MSB): 이진수에서 가장 왼쪽에 있는 bit.

예를 들어,

10110

에서

LSB는 오른쪽 끝의 0
MSB는 왼쪽 끝의 1

이다.

Meaning: 각 bit의 위치에 따라 수에서 가지는 가중치가 달라진다.

2.2 Binary Addition

1) Basic Binary Addition

이진수 덧셈은 십진수 덧셈과 마찬가지로 오른쪽에서 왼쪽으로 수행한다.

기본 규칙은 다음과 같다.

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

특히,

1+1=10_2

이므로

sum = 0
carry = 1

이 된다.

Meaning: 여러 bit의 덧셈은 각 자리의 덧셈과 carry 전달로 이루어진다.

2) Carry

Carry: 한 자리의 덧셈 결과가 다음 상위 bit로 전달되는 값.

다음 자리에서는

a+b+carry

를 계산한다.

Meaning: n-bit 덧셈은 작은 bit 덧셈기를 연속해서 연결하여 구현할 수 있다.

3) Overflow

Overflow: 정해진 bit 수로 결과를 표현할 수 없는 상태.

예를 들어 4-bit 시스템에서

1111+0011

을 계산하면 실제 결과는 5-bit가 필요할 수 있다.

책에서 구현하는 기본 adder와 ALU는 overflow를 별도로 검출하거나 처리하지 않는다.

Meaning: 고정된 word width에서는 최상위 범위를 벗어난 bit가 손실될 수 있다.

2.3 Signed Binary Numbers

1) Two's Complement

Two's Complement: 음수를 표현하는 표준적인 binary representation.

$n$ -bit 시스템에서 양수 $x$ 의 음수 표현은

2^n-x

로 정의할 수 있다.

예를 들어 5-bit에서 $-2$ 는

2^5-2 = 32-2 = 30

이므로

-2=(11110)_2

이다.

Meaning: 같은 binary adder를 사용하여 양수와 음수를 함께 계산할 수 있게 해준다.

2) Range of Two's Complement

$n$ -bit two's complement가 표현할 수 있는 정수 범위는

-2^{n-1} \le x \le 2^{n-1}-1

이다.

예를 들어 4-bit에서는

-8 \le x \le 7

이다.

Meaning: 음수 쪽이 양수 쪽보다 하나 더 많은 값을 표현한다.

3) Sign Bit

Two's complement에서 MSB는 수의 부호를 판단하는 데 사용할 수 있다.

MSB=0 \Rightarrow \text{non-negative}

MSB=1 \Rightarrow \text{negative}

Meaning: 최상위 bit를 보면 signed integer가 음수인지 빠르게 판단할 수 있다.

4) Negation

Two's complement에서 $-x$ 를 구하는 간단한 방법은

모든 bit를 반전한다.
1을 더한다.

즉,

-x=\operatorname{Not}(x)+1

이다.

예를 들어 4-bit에서

2=0010

이라면 bit를 반전하여

1101

을 얻고 1을 더하면

1110

이 된다.

따라서

-2=1110

이다.

Meaning: 음수 변환을 Not과 addition만으로 구현할 수 있다.

5) Subtraction

뺄셈은 two's complement를 이용하면 덧셈으로 바꿀 수 있다.

x-y=x+(-y)

그리고

-y=\operatorname{Not}(y)+1

이므로 별도의 복잡한 subtraction hardware가 필요하지 않다.

Meaning: 덧셈 회로 하나로 덧셈과 뺄셈을 모두 구현할 수 있다.

2.4 Adders

1) Half-Adder

Half-Adder: 두 개의 bit를 더하는 회로.

입력:

출력:

sum
carry

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

Half-Adder의 출력은 다음 Boolean function과 같다.

sum=\operatorname{Xor}(a,b)

carry=\operatorname{And}(a,b)

Meaning: 두 bit를 더하기 위한 가장 기본적인 arithmetic circuit이다.

2) Full-Adder

Full-Adder: 세 개의 bit를 더하는 회로.

입력:

여기서 c는 이전 자리에서 전달된 carry로 사용할 수 있다.

출력:

sum
carry

a+b+c

의

LSB가 sum
MSB가 carry

가 된다.

Meaning: 여러 자리 이진수를 더할 때 필요한 기본 building block이다.

3) Half-Adder and Full-Adder

두 회로의 차이는 입력 수이다.

\text{Half-Adder} : 2\text{ bits}

\text{Full-Adder} : 3\text{ bits}

Full-Adder는 두 개의 Half-Adder와 추가적인 논리 게이트를 이용하여 구현할 수 있다.

Meaning: carry까지 포함하여 계산해야 하는 실제 multi-bit addition에는 Full-Adder가 필요하다.

2.5 Multi-Bit Adder

1) Add16

Add16: 두 개의 16-bit 값을 더하는 adder.

입력:

a[16]
b[16]

출력:

out[16]

기능:

out=a+b

Two's complement 방식의 integer addition을 사용한다.

Meaning: 16-bit word 단위의 정수 덧셈을 수행한다.

2) Carry Propagation

n-bit adder는 여러 Full-Adder를 연결하여 만들 수 있다.

가장 낮은 자리에서 발생한 carry를 다음 자리의 Full-Adder에 전달한다.

개념적으로

FA_0 \rightarrow FA_1 \rightarrow FA_2 \rightarrow \cdots \rightarrow FA_{n-1}

형태이다.

Meaning: 작은 1-bit adder들을 연결하여 임의 크기의 정수 adder를 만들 수 있다.

3) Ripple-Carry Adder

이처럼 carry가 LSB에서 MSB 방향으로 순차적으로 전달되는 구조를 일반적으로 ripple-carry 방식으로 볼 수 있다.

책의 기본 구현은 단순하지만 carry가 여러 단계를 지나가야 한다.

Meaning: 구현은 쉽지만 word width가 커질수록 carry propagation delay가 증가한다.

2.6 Incrementer

1) Inc16

Incrementer: 입력 값에 1을 더하는 전용 회로.

16-bit incrementer의 기능은

out=in+1

이다.

Meaning: counter나 program counter처럼 값을 하나씩 증가시키는 회로에서 자주 사용된다.

2.7 Arithmetic Logic Unit

1) ALU

Arithmetic Logic Unit (ALU): arithmetic operation과 logical operation을 수행하는 CPU의 핵심 회로.

Hack ALU는 두 개의 16-bit 입력을 받는다.

x[16]
y[16]

그리고 하나의 16-bit 결과를 출력한다.

out[16]

Meaning: CPU가 실제 계산을 수행하는 핵심 연산 장치이다.

2) ALU Control Bits

Hack ALU는 6개의 control bit를 사용한다.

zx
nx
zy
ny
f
no

각 bit는 특정한 입력 또는 출력 변환을 제어한다.

zx

zx: x 입력을 zero로 만들지 결정한다.

zx=1 \Rightarrow x=0

nx

nx: x를 bit-wise negate할지 결정한다.

nx=1 \Rightarrow x=!x

zy

zy: y 입력을 zero로 만들지 결정한다.

zy=1 \Rightarrow y=0

ny

ny: y를 bit-wise negate할지 결정한다.

ny=1 \Rightarrow y=!y

f

f: 핵심 연산을 선택한다.

f=1 \Rightarrow out=x+y

f=0 \Rightarrow out=x\&y

no

no: 최종 output을 negate할지 결정한다.

no=1 \Rightarrow out=!out

Meaning: 소수의 단순한 control bit 조합으로 여러 arithmetic/logical operation을 만들어낸다.

2.8 ALU Operation Flow

Hack ALU의 전체 처리 과정은 다음과 같다.

1) Process x

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

2) Process y

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

3) Compute

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

4) Process Output

if no then out = !out

Meaning: 입력을 먼저 변형하고, 핵심 연산을 수행한 뒤, 출력에 추가 변형을 적용한다.

2.9 ALU Functions

Hack ALU는 6개의 control bit를 조합하여 여러 함수를 계산한다.

반드시 알아둘 대표 연산은 다음과 같다.

Constants

0

1

-1

Direct Values

x

y

Negation

!x

!y

Arithmetic Negation

-x

-y

Increment

x+1

y+1

Decrement

x-1

y-1

Addition

x+y

Subtraction

x-y

y-x

Logical And

x\&y

Logical Or

x|y

Meaning: 단순한 Add, And, Not 구조만으로 CPU가 필요한 여러 연산을 생성할 수 있다.

2.10 ALU Status Outputs

1) zr

zr: ALU 결과가 0인지 나타내는 output bit.

out=0 \Rightarrow zr=1

그 외에는

zr=0

이다.

Meaning: 조건 분기에서 결과가 zero인지 판단하는 데 사용할 수 있다.

2) ng

ng: ALU 결과가 음수인지 나타내는 output bit.

out<0 \Rightarrow ng=1

Two's complement에서는 MSB를 이용해 음수를 판단할 수 있다.

Meaning: CPU가 연산 결과의 부호를 판단하는 데 사용할 수 있다.

2.11 ALU as a Controlled Circuit

ALU의 중요한 특징은 연산별로 완전히 다른 회로를 따로 만드는 것이 아니라, 동일한 내부 회로의 동작을 control bit로 변경한다는 것이다.

즉,

\text{Data Inputs} + \text{Control Bits} \rightarrow \text{Selected Operation}

이다.

Meaning: control signal을 이용하여 하나의 hardware block을 다양한 연산에 재사용한다.

2.12 Hardware and Software Trade-Off

ALU에 모든 연산을 직접 구현할 필요는 없다.

Hack ALU에는 예를 들어 다음 연산이 직접 포함되지 않는다.

multiplication
division
floating-point arithmetic

이러한 연산은 이후 software에서 구현할 수 있다.

Meaning: 연산을 hardware에 넣으면 빠르지만 회로가 복잡해지고, software로 구현하면 hardware는 단순해지지만 실행 비용이 증가한다.

2.13 Carry Look-Ahead

기본 multi-bit adder에서는 carry가 한 자리씩 전달된다.

이 방식은 단순하지만 긴 propagation delay를 만들 수 있다.

책에서는 이를 개선할 수 있는 방법으로 carry look-ahead와 같은 기법을 언급한다.

Meaning: 실제 고성능 processor에서는 addition delay를 줄이기 위한 더 효율적인 adder 구조를 사용한다.

2.14 Construction Hierarchy

Boolean arithmetic hardware는 다음과 같은 계층으로 구성된다.

\text{Logic Gates}

\downarrow

\text{Half-Adder}

\downarrow

\text{Full-Adder}

\downarrow

\text{Multi-Bit Adder}

\downarrow

\text{ALU}

Meaning: Chapter 1에서 만든 Boolean gate가 실제 산술 연산 회로로 확장된다.

Essential Study Checklist

반드시 이해하고 기억해야 하는 내용:

Binary system은 base 2를 사용한다.

(x_n\cdots x_0)_2 = \sum_{i=0}^{n}x_i2^i

LSB는 가장 낮은 자리 bit이고, MSB는 가장 높은 자리 bit이다.
이진 덧셈은 각 자리의 sum과 다음 자리로 전달되는 carry로 이루어진다.
Two's complement는 signed integer를 표현하는 핵심 방식이다.
n-bit two's complement의 범위는

-2^{n-1} \le x \le 2^{n-1}-1

이다.

Two's complement에서 음수는 일반적으로 MSB가 1이다.
$-x$ 는

-x=!x+1

로 만들 수 있다.

뺄셈은

x-y=x+(-y)

로 변환할 수 있다.

Half-Adder는 두 bit를 더한다.

sum=Xor(a,b)

carry=And(a,b)

Full-Adder는 세 bit를 더한다.

a+b+carry_{in}

여러 Full-Adder를 연결하면 multi-bit adder를 만들 수 있다.
Incrementer는

out=in+1

을 계산한다.

ALU는 CPU의 arithmetic 및 logical operation을 수행한다.
Hack ALU의 핵심 입력은

x[16]
y[16]

이다.

Hack ALU에는 6개의 control bit가 있다.

zx
nx
zy
ny
f
no

zx, zy는 입력을 zero로 만든다.
nx, ny, no는 각각 x, y, output을 negate한다.
f는 핵심 연산을 선택한다.

f=1 \Rightarrow x+y

f=0 \Rightarrow x\&y

Hack ALU는 다음과 같은 핵심 연산들을 생성할 수 있다.

0,\ 1,\ -1

x,\ y,\ !x,\ !y

-x,\ -y

x+1,\ y+1,\ x-1,\ y-1

x+y,\ x-y,\ y-x

x\&y,\ x|y

zr은 결과가 0인지 나타낸다.
ng는 결과가 음수인지 나타낸다.
기본 adder는 단순하지만 carry propagation delay가 존재한다.
Chapter 2의 가장 중요한 구성 관계는

\boxed{ \text{Boolean Gates} \rightarrow \text{Adders} \rightarrow \text{ALU} }

이다.

이 장의 핵심 설계 원리는 복잡한 arithmetic operation도 결국 단순한 Boolean operation과 control signal의 조합으로 구현할 수 있다는 것이다.

2.1 Background​

1) Binary Numbers​

2) Bit Significance​

2.2 Binary Addition​

1) Basic Binary Addition​

2) Carry​

3) Overflow​

2.3 Signed Binary Numbers

1) Two's Complement​

2) Range of Two's Complement​

3) Sign Bit​

4) Negation​

5) Subtraction​

2.4 Adders

1) Half-Adder​

2) Full-Adder​

3) Half-Adder and Full-Adder​

2.5 Multi-Bit Adder

1) Add16​

2) Carry Propagation​

3) Ripple-Carry Adder​