Imprint | Privacy Policy

Combinational Circuits I

(Usage hints for this presentation)

IT Systems, Summer Term 2024
Dr. Jens Lechtenbörger (License Information)

1. Introduction

1.1. Today’s Core Question

  • How can we perform arithmetic and logic operations on integer numbers, starting from Boolean logic?

1.2. Learning Objectives

  • 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
  • Determine ALU operation based on control bits

1.3. Retrieval Practice

  • Prior knowledge

    • How do you add two numbers with pen and paper, say 4242 + 6789?
    • What is 101010 in decimal?

Agenda

2. Addition

2.1. Pen-and-paper method

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
    • 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

2.2. Adding with fixed bits

  • 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)
  • Insight (recall Fail task)
    • Restricting to \(n\) bits corresponds to Modulo operation
      • \(\mod 2^n\)
    • \(n=8\): 10110111 + 11000101 = 1111100 mod 256

3. 2’s Complement

3.1. Definitions

  • 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\)

3.2. Example and Conversion

  • \(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

3.3. Addition with 2’s Complement

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

        2-5 = 2 + (-5):  0010
        	       + 1011
        		 ----
        		 1101 = -3
        
    • In Hack, overflows will be ignored
      • Programming bug

4. Building an Adder Chip

  • Sequence of chips
    • Increasing complexity
      1. HalfAdder: Adds two bits, produces two output bits
      2. FullAdder: Adds three bits, produces two output bits
      3. Add16: Adds two 16-bit numbers, produces 16-bit output

4.1. Half Adder

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)

4.2. Full Adder Specification

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

4.3. Full Adder Implementation

Full Adder based on Half Adders

Full Adder based on Half Adders

Figure under CC0 1.0

  • 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

4.4. Ripple-Carry 4-bit Adder

  • 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\)

5. Self-Study Tasks

5.1. Negative Numbers

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

5.2. Recall Adders

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

Bibliography

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

License Information

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.