Tue 24th Dec 2019
Table of Contents
- Truth Tabels and Canonical Representations
- Gates
- Multiplexors and Demulitplexors
- Variants
- DeMorgan’s Laws
- Exercises
Truth Tabels and Canonical Representations
A Truth Table is a way of specifying a boolean function, for example $f(x, y, z)$ depends on three boolean inputs, $x$, $y$ and $z$ as so:
x y z f(x, y, z) x y z f(x, y, z)
================ ================
0 0 0 0 1 0 0 1
0 0 1 0 1 0 1 0
0 1 0 1 1 1 0 1
0 1 1 0 1 1 1 0
From here, we can create the Canonical Representation, to do that you:
- Take every row where the output is
1
. and
together each literal in that row.- Apply
not
to each literal that is0
. or
together each of these terms.
For example, we care about rows 3, 5 and 7:
Row 3: (not x) and y and (not z)
Row 5: x and (not y) and (not z)
Row 7: x and y and (not z)
Function:
(not x) and y and (not z)
or x and (not y) and (not z)
or x and y and (not z)
Or $\bar{x}y\bar{z} + x\bar{y}\bar{z} + xy\bar{z}$.
This also shows that all boolean functions can be expressed with and
and or
.
Gates
A gate is a physical device that implements a boolean function.
The NAND gate is complete, any boolean function can be implemented using just that gate. (The NOR gate is also complete.)
Multiplexors and Demulitplexors
A multiplexor (multiplexer? spelling?) has 3 inputs - one is the selection bit that determines which of other inputs the output copies. A demultiplexor does the opposite, taking 2 inputs and providing two outputs. The selection input determines which of outputs the other input is sent to.
Variants
The gates can have multi-bit versions that take inputs of say 32 bits. For basic gates these can be constructed by duplicating the gate.
Some gates can also be multi-way, taking more inputs and working in the way you’d expect.
DeMorgan’s Laws
DeMorgan’s Laws are a pair of transformations on boolean logic.
\[\overline{A \cup B} = \overline{A} \cap \overline{B}\] \[\overline{A \cap B} = \overline{A} \cup \overline{B}\]Exercises
You start with Nand
.
Instructions for HDL.
Basic Gates
Not(a) = Nand(a, a)
And(a, b) = Not(Nand(a, b))
Or(a, b) = Nand(Not(a), Not(b))
Xor(a, b) = Or(And(a, Not(b)),
And(Not(a), b))
Mux(a, b, sel) = Or(And(Not(sel), a),
And(sel, b)))
DMux(in, sel) = {
And(Not(sel), in),
And(sel, in)
}
Example HDL:
CHIP Xor {
IN a, b;
OUT out;
PARTS:
Not(in=a, out=nota);
Not(in=b, out=notb);
And(a=a, b=notb, out=c);
And(a=nota, b=b, out=d);
Or(a=c, b=d, out=out);
}
Buses of bits are indexed from the right, eg:
/**
* 8-way 16-bit multiplexor:
* out = a if sel == 000
* b if sel == 001
* etc.
* h if sel == 111
*/
CHIP Mux8Way16 {
IN a[16], b[16], c[16], d[16],
e[16], f[16], g[16], h[16],
sel[3];
OUT out[16];
PARTS:
Mux16(a=a, b=b, sel=sel[0], out=i);
Mux16(a=c, b=d, sel=sel[0], out=j);
Mux16(a=e, b=f, sel=sel[0], out=k);
Mux16(a=g, b=h, sel=sel[0], out=l);
Mux16(a=i, b=j, sel=sel[1], out=m);
Mux16(a=k, b=l, sel=sel[1], out=n);
Mux16(a=m, b=n, sel=sel[2], out=out);
}