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
000110 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
BinaryDecimal
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
100s10s 1s
102101 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
100s10s 1s
102101 100
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary Decimal
1 0 1two
4s2s 1s
2221 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
4s2s 1s
2221 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
bnbn-1bn-2…b1b0
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary Decimal
bnbn-1bn-2…b1b0
=
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary Decimal
bnbn-1bn-2…b1b0
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 10 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 10 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 121
0 1 0 1 1 1 0 092
+
Addition
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 121
0 1 0 1 1 1 0 092
113
+
Addition
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 121
0 1 0 1 1 1 0 092
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 ‹#›
0010110
10010111
01010010
11101001
+
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 ‹#›
0010110
10010111
01010010
11101001
+
Half adder
absumcarry
0000
0110
1010
1101
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
absumcarry
0000
0110
1010
1101
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 ‹#›
0010110
10010111
01010010
11101001
+
Full adder
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0010110
10010111
01010010
11101001
+
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 ‹#›
0010110
10010111
01010010
11101001
+
Multi-bit Adder
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0010110
10010111
01010010
11101001
+
Multi-bit Adder
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0010110
10010111
01010010
11101001
+
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
101010
101111
110012
110113
111014
111115
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
00000
00011
00102
00113
01004
01015
01106
01117
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
zxnxzynyfnoout
1010100
1111111
111010-1
001100x
110000y
001101!x
110001!y
001111-x
110011-y
011111x+1
110111y+1
001110x-1
110010y-1
000010x+y
010011x-y
000111y-x
000000x&y
010101x|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 inputpre-setting
the y inputselecting between computing + or &post-setting the outputResulting
ALU output
zxnxzynyfnoout
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&yif 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 inputpre-setting
the y inputselecting between computing + or &post-setting the outputResulting
ALU output
zxnxzynyfnoout
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&yif no
then
out=!out
out(x,y)=
1010100
1111111
111010-1
001100x
110000y
001101!x
110001!y
001111-x
110011-y
011111x+1
110111y+1
001110x-1
110010y-1
000010x+y
010011x-y
000111y-x
000000x&y
010101x|y
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
pre-setting
the x inputpre-setting
the y inputselecting between computing + or &post-setting the outputResulting
ALU output
zxnxzynyfnoout
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&yif no
then
out=!out
out(x,y)=
1010100
1111111
111010-1
001100x
110000y
001101!x
110001!y
001111-x
110011-y
011111x+1
110111y+1
001110x-1
110010y-1
000010x+y
010011x-y
000111y-x
000000x&y
010101x|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 inputpre-setting
the y inputselecting between computing + or &post-setting the outputResulting
ALU output
zxnxzynyfnoout
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&yif no
then
out=!out
out(x,y)=
1010100
1111111
111010-1
001100x
110000y
001101!x
110001!y
001111-x
110011-y
011111x+1
110111y+1
001110x-1
110010y-1
000010x+y
010011x-y
000111y-x
000000x&y
010101x|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 = 0These 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 ‹#›PerspectiveThe Hack ALU is:SimpleElegantTo implement it this ALU,you only need to know how to:Set a 16-bit value to 0000000000000000Set a 16-bit value to 1111111111111111Negate a 16-bit value (bit-wise)Compute plus or And on two 16-bit valuesThat’s it!“Simplicity is the ultimate sophistication.” ― Leonardo da VinciNand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›Binary numbersBinary additionNegative numbersArithmetic Logic UnitProject 2 overviewChapter 2: Boolean arithmeticNand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›Project 2Given: All the chips built in Project 1HalfAdderFullAdderAdd16Inc16ALUGoal: 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 Adderabsumcarry0000011010101101Implementation tipCan 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.hdlNand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›Full AdderImplementation tipsCan be built using twohalf-adders./** Computes the sum of three bits. */CHIP HalfAdder {IN a, b, c;OUT sum, carry;PARTS:// Put your code here:}FullAdder.hdlabcsumcarry0000000110010100110110010101011100111111Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›16-bit adderImplementation tipsAn n-bit adder can be built from n full-adder chipsThe carry bit is “piped” from right to leftThe 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.hdlNand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›16-bit incrementorImplementation tipThe 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.hdlNand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›ALUImplementation tipsBuilding blocks: Add16, and some gates built in project 1Can 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.hdlNand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›Project 2 Resourceswww.nand2tetris.orgAll the necessary project 2 files are available in:nand2tetris / projects / 02Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›More resourcesHDL Survival GuideHardware Simulator Tutorialnand2tetris Q&A forumAll available in: www.nand2tetris.orgNand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›Best practice adviceTry to implement the chips in the given orderIf 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 chipsYou can invent new, “helper chips”; however, this is not required: you can build any chip using previously-built chips onlyStrive to use as few chip-parts as possibleYou will have to use chips implemented in Project 1For 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 numbersBinary additionNegative numbersArithmetic Logic UnitProject 2 overviewChapter 2: Boolean arithmeticNand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›Chapter 2Boolean ArithmeticFrom Nand to TetrisBuilding a Modern Computer from First PrinciplesThese slides support chapter 2 of the bookThe Elements of Computing Systems By Noam Nisan and Shimon SchockenMIT PressNand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›zxnozrnxzynyfALUng16 bits16 bitsxy16 bitsout/docProps/thumbnail.jpeg
Reviews
There are no reviews yet.