Skip to content
Elvis Chidera

[WIP] The Elements of Computing Systems: Building a Modern Computer from First Principles

notes4 min read

Chapter 1: Boolean logic

Binary variables

Modern computers store and process information stored as two-valued signals — called bits (i.e. binary digits). Two-value signals were chosen because they can readily be represented, stored, and transmitted. For example, as:

  • The presence or absence of a hole in a punched card
  • High or low voltage on a wire
  • A magnetic domain oriented clockwise or counterclockwise.

A binary variable or a bit can represent two possible states: 0 and 1; off and on; false and true; no and yes; etc. nn binary variables can be used to represent 2n2^n states. e.g.

b2b_2b1b_1b0b_0
000
001
010
011
100
101
110
111

Boolean functions

Boolean algebra is used to manipulate binary values. A boolean function (aka boolean operator) is a function that operates on binary inputs and returns binary outputs.

The total number of boolean functions for nn binary variables is 22n2^{2^n}. Explanation:

  • There are 2n2^n input combinations.
  • Each of these input combinations can be mapped to either 0 or 1.
  • The total number of boolean functions is thus: 22n2^{2^n}
  • e.g. There are 16 distinct boolean functions for 2 binary variables.
FunctionExpressionA=0, B=0A=0, B=1A=1, B=0A=1, B=1
F000000
F1NOT A AND NOT B1000
F2NOT A AND B0100
F3NOT A1100
F4A AND NOT B0010
F5NOT B1010
F6XOR(A, B)0110
F7NAND(A, B)1110
F8A AND B0001
F9XNOR(A, B)1001
F10B0101
F11NOT A OR B1101
F12A0011
F13A OR NOT B1011
F14A OR B0111
F1511111

Logic gates

A gate (also called chip in the book) is a physical device that implements a boolean function. Every digital device is based on a set of chips designed to store and process binary information. These chips are all made of elementary logic gates. Elementary logic gates can be physically realized using many different hardware technologies, but their logical behavior, or abstraction, is consistent across implementations.

Since all logic gates have the same input and output data type (i.e. binary), they can be combined, creating composite gates of arbitrary complexity. e.g. Xor = Or( And(a, Not(b)), And(Not(a), b) ).

Any given logic gate can be viewed from two perspective:

  1. External: The interface of the gate, outlining its input pins, output pins, and its behavior.
  2. Internal: The implementation of the gate. There can be multiple implementations of a gate’s interface. The goal is to find an implementation that is correct (functional requirement) and efficient (performance requirement).

Hardware description language (HDL)

Hardware description language is a formalism used by hardware designers to design chip architecture.

The designer specifies the chip logic by writing a HDL program, which is then subjected to a rigorous battery of tests. The tests are carried out virtually, using computer simulation: A special software tool, called a hardware simulator, takes the HDL program as input and creates a software representation of the chip logic. Next, the designer can instruct the simulator to test the virtual chip on various sets of inputs. The simulator computes the chip outputs, which are then compared to the desired outputs.

The hardware simulator can also simulate and quantify the performance characteristics (energy consumption, computational speed, cost) of a chip.

Gates specification

The specifications of the logic gates needed to build the chips of our computer system are given below.

Primitive gates

Nand gate

Shorthand for Not-And because its equivalent to Not(And(a, b)).

Truth table:

abNand(a, b)
001
011
101
110

API:

Chip nameNand
Inputa, b
Outputout
Functionif ((a == 1) and (b==1)) then out = 0, else out = 1

The NAND gate is a primitive gate because it can be used to implement any boolean function. Proof:

  • Various subsets of logical operators can be used for expressing any boolean function, and { And, Or, Not } is one such subset. NAND can be used to implement each member of the subset as demonstrated below.
  • NOT(a) = NAND(a, a)
  • AND(a, b) = NOT(NAND(a, b))
  • OR(a, b) = NOT(NOT(a) AND NOT(b)) (De morgan law)

Classical logical gates

These gates implement classical logical operators.

Not (aka inverter) gate

This gate outputs the opposite value of its input’s value.

Truth table:

aNot(a)
01
10

API:

Chip nameNot
Inputin
Outputout
Functionif (in == 0) then out = 1, else out = 0

HDL:

1CHIP Not {
2 IN in;
3 OUT out;
4
5 PARTS:
6 Nand(a= in, b= in, out= out);
7}
And gate

Returns 11 when both its inputs are 11, and 00 otherwise.

Truth table:

abAnd(a, b)
000
010
100
111

API:

Chip nameAnd
Inputa, b
Outputout
Functionif ((a == 1) and (b==1)) then out = 1, else out = 0

HDL:

1CHIP And {
2 IN a, b;
3 OUT out;
4
5 PARTS:
6 Nand(a= a, b= b, out= nandout);
7 Not(in= nandout, out= out);
8}
Or gate

Returns 11 when at least one of its inputs is 11, and 00 otherwise.

Truth table:

abOr(a, b)
000
011
101
111

API:

Chip nameOr
Inputa, b
Outputout
Functionif ((a == 0) and (b == 0)) then out = 0, else out = 1

HDL:

1CHIP Or {
2 IN a, b;
3 OUT out;
4
5 PARTS:
6 Not(in= a, out= nota);
7 Not(in= b, out= notb);
8 And(a= nota, b= notb, out= notaandnotb);
9 Not(in= notaandnotb, out= out);
10}
Xor (aka exclusive or) gate

Returns 11 when exactly one of its input is 11, and 00 otherwise.

Truth table:

abXor(a, b)
000
011
101
110

API:

Chip nameXor
Inputa, b
Outputout
Functionif (a != b) then out = 1, else out = 0

HDL:

1CHIP Xor {
2 IN a, b;
3 OUT out;
4
5 PARTS:
6 Not(in= a, out= nota);
7 Not(in= b, out= notb);
8 And(a= a, b= notb, out= aandnotb);
9 And(a= b, b= nota, out= bandnota);
10 Or(a= aandnotb, b= bandnota, out= out);
11}

Control flow gates

These gates provide means for controlling flows of information.

Multiplexer

A multiplexer is a three-input gate. Two input bits, named a and b, are interpreted as data bits, and a third bit, named sel, is interpreted as a selection bit. The multiplexer uses sel to select and output the value of either a or b.

Fig1.9

Truth table:

abselout
0000
0010
0100
0111
1001
1010
1101
1111

API:

Chip nameMux
Inputa, b, sel
Outputout
Functionif (sel == 0) then out = a, else out = b

HDL:

1CHIP Mux {
2 IN a, b, sel;
3 OUT out;
4
5 PARTS:
6 Not(in= sel, out= notsel);
7 And(a= a, b= notsel, out= aandnotsel);
8 And(a= b, b= sel, out= bandsel);
9 Or(a= aandnotsel, b= bandsel, out= out);
10}
Demultiplexer

A demultiplexer performs the opposite function of a multiplexer: it takes a single input value and routes it to one of two possible outputs, according a selector bit that selects the destination output.

Fig1.10

inselab
0000
0100
1010
1101

API: | | | |-----------|--------------------------------------------------------------| | Chip name | DMux | | Input | in, sel | | Output | a, b | | Function | if (sel == 0) then {a, b} = {in, 0}, else {a, b} = {0, in} |

HDL:

1CHIP DMux {
2 IN in, sel;
3 OUT a, b;
4
5 PARTS:
6 Not(in= sel, out= notsel);
7 And(a= in, b= notsel, out= a);
8 And(a= in, b= sel, out= b);
9}

Multi-bit versions of basic gates

This section describes several 16-bit logic gates that will be needed for constructing our target computer platform. HDL programs treat multi-bit values like single-bit values, except that the values can be indexed in order to access individual bits. For example, if in and out represent 16-bit values, then out [3] = in[5] sets the 3rd bit of out to the value of the 5th bit of in. The bits are indexed from right to left, the rightmost bit being the 0’th but and the leftmost bit being the 15’th bit (in a 16-bit setting).

16-bit Not gate

Applies the Boolean operation Not to every one of the input bits.

API:

Chip nameNot16
Inputin[16]
Outputout[16]
Functionfor i = 0..15 out[i] = Not(in[i])

HDL:

1CHIP Not16 {
2 IN in[16];
3 OUT out[16];
4
5 PARTS:
6 Not(in= in[0], out= out[0]);
7 Not(in= in[1], out= out[1]);
8 Not(in= in[2], out= out[2]);
9 Not(in= in[3], out= out[3]);
10 Not(in= in[4], out= out[4]);
11 Not(in= in[5], out= out[5]);
12 Not(in= in[6], out= out[6]);
13 Not(in= in[7], out= out[7]);
14 Not(in= in[8], out= out[8]);
15 Not(in= in[9], out= out[9]);
16 Not(in= in[10], out= out[10]);
17 Not(in= in[11], out= out[11]);
18 Not(in= in[12], out= out[12]);
19 Not(in= in[13], out= out[13]);
20 Not(in= in[14], out= out[14]);
21 Not(in= in[15], out= out[15]);
22}
16-bit And gate

Applies the Boolean operation And to every one of the input bits.

API:

Chip nameAnd16
Inputa[16], b[16]
Outputout[16]
Functionfor i = 0..15 out[i] = And(a[i], b[i])

HDL:

1CHIP And16 {
2 IN a[16], b[16];
3 OUT out[16];
4
5 PARTS:
6 And(a= a[0], b= b[0], out= out[0]);
7 And(a= a[1], b= b[1], out= out[1]);
8 And(a= a[2], b= b[2], out= out[2]);
9 And(a= a[3], b= b[3], out= out[3]);
10 And(a= a[4], b= b[4], out= out[4]);
11 And(a= a[5], b= b[5], out= out[5]);
12 And(a= a[6], b= b[6], out= out[6]);
13 And(a= a[7], b= b[7], out= out[7]);
14 And(a= a[8], b= b[8], out= out[8]);
15 And(a= a[9], b= b[9], out= out[9]);
16 And(a= a[10], b= b[10], out= out[10]);
17 And(a= a[11], b= b[11], out= out[11]);
18 And(a= a[12], b= b[12], out= out[12]);
19 And(a= a[13], b= b[13], out= out[13]);
20 And(a= a[14], b= b[14], out= out[14]);
21 And(a= a[15], b= b[15], out= out[15]);
22}
16-bit Or gate

Applies the Boolean operation Or to every one of the input bits.

API:

Chip nameOr16
Inputa[16], b[16]
Outputout[16]
Functionfor i = 0..15 out[i] = Or(a[i], b[i])

HDL:

1CHIP Or16 {
2 IN a[16], b[16];
3 OUT out[16];
4
5 PARTS:
6 Or(a= a[0], b= b[0], out= out[0]);
7 Or(a= a[1], b= b[1], out= out[1]);
8 Or(a= a[2], b= b[2], out= out[2]);
9 Or(a= a[3], b= b[3], out= out[3]);
10 Or(a= a[4], b= b[4], out= out[4]);
11 Or(a= a[5], b= b[5], out= out[5]);
12 Or(a= a[6], b= b[6], out= out[6]);
13 Or(a= a[7], b= b[7], out= out[7]);
14 Or(a= a[8], b= b[8], out= out[8]);
15 Or(a= a[9], b= b[9], out= out[9]);
16 Or(a= a[10], b= b[10], out= out[10]);
17 Or(a= a[11], b= b[11], out= out[11]);
18 Or(a= a[12], b= b[12], out= out[12]);
19 Or(a= a[13], b= b[13], out= out[13]);
20 Or(a= a[14], b= b[14], out= out[14]);
21 Or(a= a[15], b= b[15], out= out[15]);
22}
16-bit Multiplexer gate

Operates exactly as the basic multiplexer, except that its input and output are 16-bits wide.

API:

Chip nameMux16
Inputa[16], b[16], sel
Outputout[16]
Functionif (sel == 0) then for i = 0..15 out[i] = a[i], else for i = 0..15 out[i] = b[i]

HDL:

1CHIP Mux16 {
2 IN a[16], b[16], sel;
3 OUT out[16];
4
5 PARTS:
6 Mux(a= a[0], b= b[0], sel= sel, out= out[0]);
7 Mux(a= a[1], b= b[1], sel= sel, out= out[1]);
8 Mux(a= a[2], b= b[2], sel= sel, out= out[2]);
9 Mux(a= a[3], b= b[3], sel= sel, out= out[3]);
10 Mux(a= a[4], b= b[4], sel= sel, out= out[4]);
11 Mux(a= a[5], b= b[5], sel= sel, out= out[5]);
12 Mux(a= a[6], b= b[6], sel= sel, out= out[6]);
13 Mux(a= a[7], b= b[7], sel= sel, out= out[7]);
14 Mux(a= a[8], b= b[8], sel= sel, out= out[8]);
15 Mux(a= a[9], b= b[9], sel= sel, out= out[9]);
16 Mux(a= a[10], b= b[10], sel= sel, out= out[10]);
17 Mux(a= a[11], b= b[11], sel= sel, out= out[11]);
18 Mux(a= a[12], b= b[12], sel= sel, out= out[12]);
19 Mux(a= a[13], b= b[13], sel= sel, out= out[13]);
20 Mux(a= a[14], b= b[14], sel= sel, out= out[14]);
21 Mux(a= a[15], b= b[15], sel= sel, out= out[15]);
22}

Multi-way versions of basic gates

Logic gates that operate on one or two inputs have natural generalization to multi-way variants that operate on more than two inputs.

Multi-way 16-bit demultiplexer gate

An m-way n-bit demultiplexer routes its single n-bit input to one of its m n-bit outputs. The other outputs are set to 0. The selection is specified by a set of k selection bits, where k=log2mk = log_2{m}.

Our target computer platform requires two variants of this chip: a 4-way 1-bit demultiplexer and an 8-way 1-bit demultiplexer.

API: | | | |-----------|--------------------------------------------------------------| | Chip name | DMux4Way | | Input | in, sel[2] | | Output | a, b, c, d | | Function | if (sel == 00) then {a, b, c, d} = {1, 0, 0, 0},<br><br>else if (sel == 01) then {a, b, c, d} = {0, 1, 0, 0},<br><br>else if (sel == 01) then {a, b, c, d} = {0, 0, 1, 0},<br><br>else if (sel == 11) then {a, b, c, d} = {0, 0, 0, 1}<br> |

HDL:

1
Chip nameDMux8Way
Inputin, sel[3]
Outputa, b, c, d, e, f, g, h
Functionif (sel == 000) then {a, b, c, …, h} = {1, 0, 0, 0, 0, 0, 0, 0},<br><br>else if (sel == 001) then {a, b, c, …, h} = {0, 1, 0, 0, 0, 0, 0, 0},<br><br>if (sel == 010) then {a, b, c, …, h} = {0, 0, 1, 0, 0, 0, 0, 0},<br><br>…<br><br>if (sel == 111) then {a, b, c, …, h} = {0, 0, 0, 0, 0, 0, 0, 1}<br>

HDL:

1
© 2024 by Elvis Chidera. All rights reserved.