CS代考计算机代写 gui PowerPoint Presentation

PowerPoint Presentation

Chapter 2
Boolean Arithmetic

From Nand to Tetris
Building a Modern Computer from First Principles
These slides support chapter 2 of the book
The Elements of Computing Systems
By Noam Nisan and Shimon Schocken
MIT Press

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
You are welcome to use this presentation, or any part of it,
in Nand to Tetris courses, or in other courses, as you see fit.
Usage is free provided that it supports instruction in an educational,
non-profit setting.
Feel free to use the slides as-is, or modify them as needed.
We’ll appreciate it if you will give credit somewhere to Nand to Tetris,
and put a reference to www.nand2tetris.org
You are welcome to remove this slide from the presentation. If you make extensive changes to the slides, you can remove the copyright notice also.
Happy teaching!
Noam Nisam / Shimon Schocken
Usage Notice

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview
Chapter 2: Boolean arithmetic

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 1

00 01 10 11

3 bits – 8 possibilities

N bits – 2N possibilities

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers
Binary Decimal
0 0
1 1
10 2
11 3
100 4
101 5

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers

7 8 9 ten

100s 10s 1s
102 101 100

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers

7 8 9 ten

= 7・102 + 8・101 + 9・100 = 789 ten

100s 10s 1s
102 101 100

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary  Decimal

1 0 1two

4s 2s 1s
22 21 20

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary  Decimal

1 0 1two

= 1・102 + 0・101 + 1・100 = 5 ten

4s 2s 1s
22 21 20

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary  Decimal

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary  Decimal
bn bn-1 bn-2 … b1 b0

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary  Decimal
bn bn-1 bn-2 … b1 b0

=

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary  Decimal
bn bn-1 bn-2 … b1 b0

Maximum value represented by k bits:
1 + 2 + 4 + … + 2k-1 = 2k-1

=

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Fixed word size

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Fixed word size
We will use a fixed number of bits.
Say 8 bits.

0000 0000
0000 0001
0000 0010
0000 0011

0111 1111
1000 0000
1000 0001

1111 1110
1111 1111

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Fixed word size
We will use a fixed number of bits.
Say 8 bits.

0000 0000
0000 0001
0000 0010
0000 0011

0111 1111
1000 0000
1000 0001

1111 1110
1111 1111
28 = 256 values

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing signed numbers
positive values

negative values
We will use a fixed number of bits.
Say 8 bits.

0000 0000
0000 0001
0000 0010
0000 0011

0111 1111
1000 0000
1000 0001

1111 1110
1111 1111

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing signed numbers
positive values

negative values
We will use a fixed number of bits.
Say 8 bits.

0000 0000
0000 0001
0000 0010
0000 0011

0111 1111
1000 0000
1000 0001

1111 1110
1111 1111
That’s one possible representation
We’ll use a better one, later

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten = ? ? ? ? ? ? ? ? two

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten = 64

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten = 64 + 16

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten = 64 + 16 + 4

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten = 64 + 16 + 4 + 2

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten = 64 + 16 + 4 + 2 + 1

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten = 64 + 16 + 4 + 2 + 1

= ? ? ? ? ? ? ? ? two

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten = 64 + 16 + 4 + 2 + 1

= 0 1 0 1 0 1 1 1 two

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal  Binary
87ten = 64 + 16 + 4 + 2 + 1

= 0 1 0 1 0 1 1 1 two

32 8

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview

Chapter 2: Boolean arithmetic

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Boolean arithmetic
Addition
Subtraction
Comparison (<,>,=)
Multiplication
Division
implement
get for free
postpone
to software
postpone
to software
get for free

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
? ? ? ? ? ? ? ?
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

0 0 0 1 0 1 0 1 21
0 1 0 1 1 1 0 0 92

+
Addition
+

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

0 0 0 1 0 1 0 1 21
0 1 0 1 1 1 0 0 92
113
+
Addition
+

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

0 0 0 1 0 1 0 1 21
0 1 0 1 1 1 0 0 92
0 1 1 1 0 0 0 1 113
+
Addition
+

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

5 7 8 3
2 4 5 6
? ? ? ?
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

5 7 8 3
2 4 5 6

+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

5 7 8 3
2 4 5 6
9
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1
5 7 8 3
2 4 5 6
3 9
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1
5 7 8 3
2 4 5 6
2 3 9
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1
5 7 8 3
2 4 5 6
8 2 3 9
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
? ? ? ? ? ? ? ?
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0

+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
1
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
0 1
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
0 0 1
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
0 0 0 1
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
1 0 0 0 1
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
1 1 0 0 0 1
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
1 1 1 0 0 0 1
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
0 1 1 1 0 0 0 1
+
Addition

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Overflow

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

1 0 0 1 0 1 0 1
1 1 0 1 1 1 0 0
? ? ? ? ? ? ? ?
+
Overflow

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 0 0 0 1 1 1 0 0
1 0 0 1 0 1 0 1
1 1 0 1 1 1 0 0
1 0 1 1 1 0 0 0 1
+
Overflow

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Building an Adder

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Building an Adder
Half adder: adds two bits
Full adder: adds three bits
Adder: adds two integers

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Half adder

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

sum bit
carry bit

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Half adder

/** Computes the sum of two bits. */

CHIP HalfAdder {
IN a, b;
OUT sum, carry;

PARTS:
// Put your code here:
}
HalfAdder.hdl
a b sum carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Full adder

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Full adder

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Full adder

sum bit
carry bit

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Full adder
/** Computes the sum of three bits. */

CHIP HalfAdder {
IN a, b, c;
OUT sum, carry;

PARTS:
// Put your code here:
}
FullAdder.hdl

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Multi-bit Adder

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Multi-bit Adder

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Multi-bit Adder

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Multi-bit Adder

/* Adds two 16-bit, two’s-complement values.
* The most-significant carry bit is ignored. */

CHIP Add16 {
IN a[16], b[16];
OUT out[16];

PARTS:
// Put you code here:
}
Add16.hdl

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview

Chapter 2: Boolean arithmetic

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers (using 4 bits)
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers (using 4 bits)
Using n bits, we can represent
the positive integers in the range
0 … 2n-1
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 10
1011 11
1100 12
1101 13
1110 14
1111 15

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing negative numbers
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Possible solution: use a sign bit
Use the left-most bit to represent the sign, -/+
Use the remaining bits to represent a positive number
Complications:
-0?
x + (-x) is not 0
more complications
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 -0
1001 -1
1010 -2
1011 -3
1100 -4
1101 -5
1110 -6
1111 -7

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Two’s Complement
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Represent the negative number -x using the positive number 2n – x

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Two’s Complement

Represent the negative number -x using the positive number 2n – x
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 -8 (16 – 8)
1001 -7 (16 – 9)
1010 -6 (16 – 10)
1011 -5 (16 – 11)
1100 -4 (16 – 12)
1101 -3 (16 – 13)
1110 -2 (16 – 14)
1111 -1 (16 – 15)

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Two’s Complement
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 -8 (16 – 8)
1001 -7 (16 – 9)
1010 -6 (16 – 10)
1011 -5 (16 – 11)
1100 -4 (16 – 12)
1101 -3 (16 – 13)
1110 -2 (16 – 14)
1111 -1 (16 – 15)
positive numbers range:
0 … 2n-1 – 1

negative numbers range:
-1 … -2n – 1

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement

-2
-3

+

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement

-2
-3

+

14
13

+

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement

-2
-3

+

14
13

+

1110
1101

+

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement

-2
-3

+

14
13

+

1110
1101
11011
+
11011 = 27 ten
1011 = 11 ten

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement

-2
-3

+

14
13
11
+

1110
1101
11011
+
11011 = 27 ten
1011 = 27 ten

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement

-2
-3
-5
+

14
13
11
+

1110
1101
11011
+
11011 = 27 ten
1011 = 27 ten

Two’s complement rationale:
representation is modulu 2n
addition is modulu 2n

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x
Input: x
Output: -x (in two’s complement)
Insight: if we solve this we’ll know how to subtract:
y – x = y + (-x)

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x
Input: x
Output: -x (in two’s complement)
Idea: 2n – x = 1 + (2n – 1) – x
11111111 two
11111111
10101100 (some x example)

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x
Input: x
Output: -x (in two’s complement)
Idea: 2n – x = 1 + (2n – 1) – x
11111111 two
11111111
10101100 (some x example)
01010011

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x
Input: x
Output: -x (in two’s complement)
Idea: 2n – x = 1 + (2n – 1) – x
11111111 two
11111111
10101100 (some x example)
01010011 (flip all the bits)


Now add 1 to the result

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x (example)
Input: 4
Output: should be 12 (representing -4 in two’s compelemt)
Input: 0100
Flip the bits: 1011

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x (example)
Input: 4
Output: should be 12 (representing -4 in two’s compelemt)
Input: 0100
Flip the bits: 1011
Add one: 1
+

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x (example)
Input: 4
Output: should be 12 (representing -4 in two’s compelemt)
Input: 0100
Flip the bits: 1011
Add one: 1
Output: 1100

+

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x (example)
Input: 4
Output: should be 12 (representing -4 in two’s compelemt)
Input: 0100
Flip the bits: 1011
Add one: 1
Output: 1100
= 12 ten
+
To add 1:
Flip all the bits from right to left, stop when the first 0 flips to 1

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview

Chapter 2: Boolean arithmetic

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Input

Von Neumann Architecture
Memory

Output
CPU
Control

ALU

Computer System

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Input

The Arithmetic Logical Unit
Memory

Output
CPU
Control

ALU

Computer System

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Arithmetic Logical Unit

ALU

f
(input1, input2)
input1
input2
f
f
: one out of a family of pre-defined arithmetic and logical functions
The ALU computes a function on the two inputs, and outputs the result
Arithmetic functions: integer addition, multiplication, division, …
logical functions: And, Or, Xor, …
Which functions should the ALU perform?
A hardware / software tradeoff.

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU

Operates on two 16-bit, two’s complement values
Outputs a 16-bit, two’s complement value
Which function to compute is set by six 1-bit inputs
Computes one out of a family of 18 functions
Also outputs two 1-bit values (to be discussed later).

out
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

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU

out
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

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU

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

To cause the ALU to compute a function, set the control bits to one of the binary combinations listed in the table.

control bits

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU in action: compute y-x

Load
tools/builtInChips/ALU.hdl

2. Evaluate
the chip logic

3. Inspect the
ALU outputs

Set the ALU’s inputs and control bits to some test values
(000111 codes “output y-x”)
The built-in ALU implementation has some GUI side-effects
Built-in ALU implementation

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›

The Hack ALU in action: compute x & y

Set the ALU’s inputs and control bits to some test values
(000000 codes “compute x&y”)

Inspect the
ALU outputs
Set to binary I/O format

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Opening up the Hack ALU black box

x
y
out = f(control bits, x, y)

Hack ALU
control bits

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU operation
pre-setting
the x input pre-setting
the y input selecting between computing + or & post-setting the output Resulting
ALU output
zx nx zy ny f no out
if zx
then
x=0 if nx
then
x=!x if zy
then
y=0 if ny
then
y=!y if f
then out=x+y
else out=x&y if no
then
out=!out

out(x,y)=

ALU

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU operation
pre-setting
the x input pre-setting
the y input selecting between computing + or & post-setting the output Resulting
ALU output
zx nx zy ny f no out
if zx
then
x=0 if nx
then
x=!x if zy
then
y=0 if ny
then
y=!y if f
then out=x+y
else out=x&y if no
then
out=!out

out(x,y)=
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

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
pre-setting
the x input pre-setting
the y input selecting between computing + or & post-setting the output Resulting
ALU output
zx nx zy ny f no out
if zx
then
x=0 if nx
then
x=!x if zy
then
y=0 if ny
then
y=!y if f
then out=x+y
else out=x&y if no
then
out=!out

out(x,y)=
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

ALU operation example: compute !x
Example: compute !x
x: 1 1 0 0
y: 1 0 1 1

Following pre-setting:
x: 1 1 0 0
y: 1 1 1 1

Computation and post-setting:
x&y: 1 1 0 0
!(x&y): 0 0 1 1 (!x)

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
ALU operation example: compute y-x
pre-setting
the x input pre-setting
the y input selecting between computing + or & post-setting the output Resulting
ALU output
zx nx zy ny f no out
if zx
then
x=0 if nx
then
x=!x if zy
then
y=0 if ny
then
y=!y if f
then out=x+y
else out=x&y if no
then
out=!out

out(x,y)=
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

Example: compute y-x
x: 0 0 1 0 (2)
y: 0 1 1 1 (7)

Following pre-setting:
x: 0 0 1 0
y: 1 0 0 0

Computation and post-setting:
x+y: 1 0 1 0
!(x+y): 0 1 0 1 (5)

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU output control bits

if (out == 0) then zr = 1, else zr = 0
if (out < 0) then ng = 1, else ng = 0 These two control bits will come into play when we build the complete computer’s architecture. Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› Perspective The Hack ALU is: Simple Elegant To implement it this ALU, you only need to know how to: Set a 16-bit value to 0000000000000000 Set a 16-bit value to 1111111111111111 Negate a 16-bit value (bit-wise) Compute plus or And on two 16-bit values That’s it! “Simplicity is the ultimate sophistication.” ― Leonardo da Vinci Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› Binary numbers Binary addition Negative numbers Arithmetic Logic Unit Project 2 overview Chapter 2: Boolean arithmetic Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› Project 2 Given: All the chips built in Project 1 HalfAdder FullAdder Add16 Inc16 ALU Goal: Build the following chips: A family of combinational chips, from simple adders to an Arithmetic Logic Unit. Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› Half Adder a b sum carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Implementation tip Can be built using two very elementary gates. /** Computes the sum of two bits. */ CHIP HalfAdder { IN a, b; OUT sum, carry; PARTS: // Put your code here: } HalfAdder.hdl Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› Full Adder Implementation tips Can be built using two half-adders. /** Computes the sum of three bits. */ CHIP HalfAdder { IN a, b, c; OUT sum, carry; PARTS: // Put your code here: } FullAdder.hdl 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 Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› 16-bit adder Implementation tips An n-bit adder can be built from n full-adder chips The carry bit is “piped” from right to left The MSB carry bit is ignored. /* * Adds two 16-bit, two’s-complement values. * The most-significant carry bit is ignored. */ CHIP Add16 { IN a[16], b[16]; OUT out[16]; PARTS: // Put you code here: } Add16.hdl Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› 16-bit incrementor Implementation tip The single-bit 0 and 1 values are represented in HDL as false and true. /* * Outputs in + 1. * The most-significant carry bit is ignored. */ CHIP Inc16 { IN in[16]; OUT out[16]; PARTS: // Put you code here: } Inc16.hdl Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› ALU Implementation tips Building blocks: Add16, and some gates built in project 1 Can be built with ~20 lines of HDL code /** The ALU. */ // Manipulates the x and y inputs as follows: // if (zx == 1) sets x = 0 // 16-bit true constant // if (nx == 1) sets x = !x // bitwise Not // if (zy == 1) sets y = 0 // 16-bit true constant // if (ny == 1) sets y = !y // bitwise Not // if (f == 1) sets out = x + y // int. 2's-complement addition // if (f == 0) sets out = x & y // bitwise And // if (no == 1) sets out = !out // bitwise Not // if (out == 0) sets zr = 1 // 1-bit true constant // if (out < 0) sets ng = 1 // 1-bit true constant ... ALU.hdl Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› Project 2 Resources www.nand2tetris.org All the necessary project 2 files are available in: nand2tetris / projects / 02 Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› More resources HDL Survival Guide Hardware Simulator Tutorial nand2tetris Q&A forum All available in: www.nand2tetris.org Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› Best practice advice Try to implement the chips in the given order If you don’t implement some of the chips required in project 2, you can still use them as chip-parts in other chips. Just rename the given stub-files; this will cause the simulator to use the built-in versions of these chips You can invent new, “helper chips”; however, this is not required: you can build any chip using previously-built chips only Strive to use as few chip-parts as possible You will have to use chips implemented in Project 1 For efficiency and consistency’s sake, use their built-in versions rather than your own implementation. Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› Binary numbers Binary addition Negative numbers Arithmetic Logic Unit Project 2 overview Chapter 2: Boolean arithmetic Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› Chapter 2 Boolean Arithmetic From Nand to Tetris Building a Modern Computer from First Principles These slides support chapter 2 of the book The Elements of Computing Systems By Noam Nisan and Shimon Schocken MIT Press Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#› zx no zr nx zy ny f ALU ng 16 bits 16 bits x y 16 bits out /docProps/thumbnail.jpeg