(Usage hints for this presentation)

IT Systems, Summer Term 2024

Dr. Jens Lechtenbörger (License Information)

- How can we perform arithmetic and logic operations on integer
numbers, starting from Boolean logic?
- Based on Chapter 2 of (Nisan and Schocken 2005)

- Compute 2’s complement of a binary number and use it for addition and subtraction
- Build, test, and analyze combinational circuits
leading to the Hack ALU (Project 2)
- Half and full adder, Ripple-Carry Adder (
`Add16`

) - Incrementer (
`Inc16`

) `ALU`

- Half and full adder, Ripple-Carry Adder (
- Determine ALU operation based on control bits

Prior knowledge

- How do you add two numbers with pen and paper, say 4242 + 6789?

- What is 101010 in decimal?

- What is a multi-bit chip?

- Part 1
- Break for self-study
- Part 2

We add digits from **right to left**, possibly with **“carry”**

In decimal

`4242 + 6789 Carry: 11110 ----- 11031`

In binary

`10110111 + 11000101 Carry: 100000110 --------- 101111100`

Note

- Rightmost (lowest) position with carry 0
- Only need to add
**2 bits**

- Only need to add
- Other positions need to add
**3 bits**

Both sample results are 1 digit

**larger**than the inputs**Overflow**in case of fixed digits/bits; incorrect result if discarded

- Rightmost (lowest) position with carry 0

- Binary addition of previous slide
- 10110111 + 11000101 = 101111100 (= 380)
- Suppose restriction to 8 bits
- Largest number is \(2^{8} - 1 = 255\)
- 8-bit-result (drop leading 1 and 0): 1111100 (= 124)
- Incorrect,
**overflow**,**bug** - Examples at Wikipedia

- Incorrect,

- Insight (recall Fail task)
- Restricting to \(n\) bits corresponds to
**Modulo operation**- \(\mod 2^n\)

- \(n=8\): 10110111 + 11000101 = 1111100 mod 256

- Restricting to \(n\) bits corresponds to

Consider \(n\)-bit number \(k\)

\(k_c = 2^n - k\) is

**2’s complement**of \(k\) (and vice versa)- Note: \(k + k_c = 2^n = 0 \mod 2^n\), i.e., complementary numbers add up to zero
- E.g., \(n=4\), \(2^4 = 16\): \(1\) and \(15\) are complements of each other; \(8\) is complement of itself

- If most significant bit of \(k\) is 0, interpret as (usual)
**positive**number If most significant bit is 1, interpret bit pattern as

**negative**number: \(k = -k_c\)- E.g., \(15 = (1111)_2\) and \(8 = (1000)_2\) are interpreted as negative numbers under 2’s complement: \((1111)_2 = -1\) and \((1000)_2 = -8\)

\(2^n\) signed numbers between \(-2^{n-1}\) and \(2^{n-1} - 1\)

- E.g., \(n=4\)

`0 0000 1 0001 1111 -1 2 0010 1110 -2 3 0011 1101 -3 4 0100 1100 -4 5 0101 1011 -5 6 0110 1010 -6 7 0111 1001 -7 1000 -8`

- Note
- Positive numbers start with 0
- Usual binary number

- Negative numbers start with 1
- To convert a number
- Leave all trailing 0’s and first 1 intact, flip all remaining bits or
- Flip all bits and add 1

- Positive numbers start with 0

- We just add bit patterns, mod \(2^n\)
- No need to treat negative numbers specially
**Subtraction**as addition with 2’s complementExample

`2-5 = 2 + (-5): 0010 + 1011 ---- 1101 = -3`

- In Hack, overflows will be ignored
- Programming
**bug**

- Programming

- Sequence of chips
- Increasing complexity
`HalfAdder`

: Adds two bits, produces two output bits`FullAdder`

: Adds three bits, produces two output bits`Add16`

: Adds two 16-bit numbers, produces 16-bit output

- Increasing complexity

a | b | carry | sum |
---|---|---|---|

0 | 0 | 0 | 0 |

0 | 1 | 0 | 1 |

1 | 0 | 0 | 1 |

1 | 1 | 1 | 0 |

- Several implementations possible
- DNF with Not, And, Or
- Alternative based on two gates
`sum = Xor(a, b)`

`carry = And(a, b)`

a | b | c | carry | sum |
---|---|---|---|---|

0 | 0 | 0 | 0 | 0 |

0 | 0 | 1 | 0 | 1 |

0 | 1 | 0 | 0 | 1 |

0 | 1 | 1 | 1 | 0 |

1 | 0 | 0 | 0 | 1 |

1 | 0 | 1 | 1 | 0 |

1 | 1 | 0 | 1 | 0 |

1 | 1 | 1 | 1 | 1 |

- Several implementations possible
- DNF with Not, And, Or
- Based on two Half Adders, see next slide

- Internal names
- C1 = And(a, b)
- S1 = Xor(a, b)
- C2 = And(S1, c) = And(Xor(a, b), c)
- S2 = Xor(S1, c) = Xor(Xor(a, b), c)

- Outputs: carry = Or(C1, C2); sum = S2

- Add 4-bit numbers \(x=x_3 x_2 x_1 x_0\) and \(y=y_3 y_2 y_1 y_0\)
- Produce 5-bit number \(S=x+y = S_4 S_3 S_2 S_1 S_0\)

- What is -42 as 7-bit number in 2’s complement?

- What parts make up a half adder? A full adder? A ripple-carry adder?

Nisan, Noam, and Shimon Schocken. 2005. *The Elements of Computing Systems: Building a Modern Computer from First Principles*. The MIT Press. https://www.nand2tetris.org/.

Source files are available on GitLab (check out embedded submodules) under free licenses. Icons of custom controls are by @fontawesome, released under CC BY 4.0.

Except where otherwise noted, the work “Combinational Circuits I”, © 2024 Jens Lechtenbörger, is published under the Creative Commons license CC BY-SA 4.0.