(Usage hints for this presentation)

IT Systems, Summer Term 2024

Dr. Jens Lechtenbörger (License Information)

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

Gate’s interface defines number of inputs

- Gates and chips have
**pins**for inputs and outputs Number of inputs called

**fan-in**

Fan-in is 2 for

`Nand`

,`And`

,`Or`

in case of Nand to TetrisWith associative and commutative operations, gates of any fan-in work in any order of computation

Consider

\begin{eqnarray} &&f_2(x_1, x_2, x_3) = \\ && \bar{x_1}\bar{x_2}x_3 + x_1\bar{x_2}\bar{x_3} + x_1\bar{x_2}x_3 + x_1 x_2 \bar{x_3} \end{eqnarray}\(x_1\) \(x_2\) \(x_3\) \(f_2(x_1, x_2, x_3)\) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0

- Gates and chips have

**Multi-bit**gates/chips: Inputs are n-bit operands each- E.g.,
`And16`

: And for 16-bit numbers is applied bit-by-bit`And16(1100110011001100, 00001111000011110000) = 0000110000001100`

- Use 16
`And`

gates in implementation

- E.g.,

**Multi-way**gates/chips: More than 2 inputs, i.e., fan-in larger than 2- E.g.,
`Or8Way`

: 8 inputs;`out = 1`

if at least one of them is 1- Use suitable number of
`Or`

gates in implementation

- Use suitable number of

- E.g.,

Simplify \(f_2(x_1, x_2, x_3)\)

\begin{eqnarray} &&= \color{darkred}{\bar{x_1}\bar{x_2}x_3} + \color{darkblue}{x_1\bar{x_2}\bar{x_3}} + \color{darkred}{x_1\bar{x_2}x_3} + \color{darkblue}{x_1 x_2 \bar{x_3}}\\ &&= \color{darkred}{(\bar{x_1} + x_1)\bar{x_2}x_3} + \color{darkblue}{(\bar{x_2} + x_2)x_1\bar{x_3}}\\ &&= \color{darkred}{\bar{x_2}x_3} + \color{darkblue}{x_1\bar{x_3}} \end{eqnarray}

Simplify \(\bar{x_1}\bar{x_2}x_3 + x_1\bar{x_2}x_3 + x_1 x_2 x_3\)

- \(\color{darkred}{\bar{x_1}\bar{x_2}x_3} + \color{darkred}{x_1\bar{x_2}x_3} + \color{darkblue}{x_1\bar{x_2}x_3} + \color{darkblue}{x_1 x_2 x_3}\)
\(\color{darkred}{(\bar{x_1} + x_1)\bar{x_2}x_3} + \color{darkblue}{(\bar{x_2} + x_2)x_1x_3}\)

Truth table

a b sel out 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1

Specification (from

`Mux.hdl`

)`If sel==1 then out=b else out=a.`

Alternative view on truth table

sel out 0 a 1 b

- Self-study
- Implement
`Mux`

- Start from truth table, simplify (task in Learnweb)
- Use Not, And, Or gates

- Implement
- In class
- Implement
`Mux8Way16`

- Implement

Truth table

in sel a b 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1

- Self-study
- Implement
`DMux`

- Read from truth table
- Use one Not, two And gates

- Implement
- In class
- Implement
`DMux8Way`

- Implement

Given:

`Nand(a,b)`

,`false`

a b Nand(a, b) 0 0 1 0 1 1 1 0 1 1 1 0 - Build:
- Not(a) = …
- true = …
- And(a,b) = …
- Or(a,b) = …
- Mux(a,b,sel) = …
- Etc. - 12 gates altogether

- See Chapter 1 of (Nisan and Schocken 2005)

- Boolean logic is formal foundation for functionalities of gates and chips
- DNF provides canonical representation for Boolean functions
- Can be read off truth table
- Simplification with laws

- Project 1 builds on Boolean logic to construct gates and circuits
- Starting from {Nand}, which is functionally complete

- Please ask questions and provide feedback on a regular basis

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 “Boolean Logic II”, © 2024 Jens Lechtenbörger, is published under the Creative Commons license CC BY-SA 4.0.