Name: [SOLVED] CS gui PowerPoint Presentation
Brand: Assignment Chef
SKU: 9608057002
Price: 25 USD
Availability: InStock
Rating: 5 (1 reviews)

5/5 - (1 vote)

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.
Well 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

= 7102 + 8101+9100 = 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

= 1102+ 0101 + 1100 = 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-2b1b0

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
Thats one possible representation
Well 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

= ? ? ? ?? ? ? ? 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

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

/* Adds two 16-bit, twos-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 #
Twos 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 #
Twos 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 #
Twos 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 twos complement

-2
-3

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright Noam Nisan and Shimon Schocken Slide #
Addition using twos complement

-2
-3

14
13

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright Noam Nisan and Shimon Schocken Slide #
Addition using twos complement

-2
-3

14
13

1110
1101

Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright Noam Nisan and Shimon Schocken Slide #
Addition using twos 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 twos 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 twos complement

-2
-3
-5
+

14
13
11
+

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

Twos 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 twos complement)
Insight: if we solve this well 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 twos complement)
Idea:2n x = 1 + (2n 1) x
11111111 two
11111111
10101100 (some x example)

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 twos 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 #
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, twos complement values
Outputs a 16-bit, twos 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 ALUs 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 ALUs 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

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 computers 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 valuesThats 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, twos-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 dont 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 consistencys 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.

Only logged in customers who have purchased this product may leave a review.

Whatsapp Us

[SOLVED] CS gui PowerPoint Presentation

Reviews

Related products

[SOLVED] SciCalculator

[SOLVED] Programming Project for TCP Socket Programming

[SOLVED] pakudex

[Solved] Program that reads in the file climate_data_2017_numeric.csv

[Solved] Problem 3: Who are the Winners

[Solved] Python Program 8 solved