WORK IN PROGRESS

Building a Computer using Boolean Logic and Math

With the knowledge of Boolean Arithmetic and Boolean Algebra we can put together our basic circuit elements and make a computer from scratch.

In this paper I will demonstrate how one could conceptualize a simple computer using the idea of first principles using simple boolean logic. This knowledge can then be extended to write higher level components of a computer from the virtual machine, operating system, and applications which I will write about in future articles.

Level-0 Ingredients

Based on our knowledge of Boolean Logic we already know that we will need one master ingredient from which we can create other ingredients. This master ingredient is the NAND gate.

A gate is a basic building block of digital circuits. It is described as a device that takes one or more inputs and can have one or more outputs. This is the most basic element of any digital circuit and thus the basic element of a modern computer. We will see from our journey that starts from here all the way to the operating system and applications that computers deal with inputs and outputs. Computers use transistors of different configurations to realize the functionality of the logic gates and the NAND gate is a type of transistor. Because of it’s algebraic function and electrical properties it is considered a universal gate from which we can build other gates in an efficient manner.

NAND

By examining the NAND truth table we can compare this with the truth tables of other operators and we can deduce algebraically how to build the others.

NOT

Looking at the NAND truth table. We can see the top and bottom columns are as follows:

So we can see that NAND on a single bit can then be used to implement our NOT circuit

Wiring

NAND a=input b=input out=out

Which we can wire as such

AND

Let’s evaluate each line of this truth table and see how we can algebracially deduce what we will need. Looking back at our NAND gate we can see that we can chain 2 NAND gates with the second arranged as a NOT gate to produce the equivalent truth table.
\(\displaylines{ x \land y = \lnot(\overline{x \land y}) }\)

Wiring

NAND a=a b=b, out=nand
NOT in=nand, out=out

Which can be wired as such

OR

The logical OR operator will return \(1\) if at least one of the inputs is \(1\) or otherwise returns \(0\)

We can get the OR gate by taking two NOT gates and connecting them to a NAND gate.

Wiring

NAND a=a, b=a, out=nand_a
NAND a=b, b=b, out=nand_b
NAND a=nand_a, b=nand_b, out=out

XOR

This will be true when both \(x\) and \(y\) are the same. So we are combininig two statements: \(x\) and \(\overline{y}\) or \(\overline{x}\) and \(y\) \(\displaylines{ x \oplus y = (x \land \overline{y}) \lor (\overline{x} \land y) }\)

Looking at our NAND truth table, we can take an OR, NAND, and AND gates to change the output of the first row where \(x = y = 0\)

Wiring

OR a=a, b=b, out=a_or_b
NAND a=a, b=b, out=a_nand_b
AND a=a_or_b, b=a_nand_b, out=out

MUX

A multiplexer or MUX is a three input gate which takes \(a\), \(b\), and a selection (sel) bit which will output the value of either \(a\) or \(b\) depending on the value of the selection bit.

Wiring

NOT in=sel out=notselect
NAND a=notselect, b=a, out=sela
NAND a=sel, b=b, out=selb
NAND a=sela, b=selb, out=out

DEMUX

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

Wiring

NOT in=sel, out=notselect
AND a=notselect, b=in, out=a
AND a=sel, b=in, out=b

Multi-Bit Gates

We will be implementing a 16-bit computer by creating 16-bit versions of our logic gates. Every n-bit version will work the same way as the single bit version but we will have the ability to index each value so that we can access individual bits. We will be indexing the values right to left with the right-most value being \(0\) and the left-most value being the \(n\)th bit.

Multi-bit NOT

Wiring

  NOT in=in[0], out=out[0]
  NOT in=in[1], out=out[1]
  NOT in=in[2], out=out[2]
  NOT in=in[3], out=out[3]
  NOT in=in[4], out=out[4]
  NOT in=in[5], out=out[5]
  NOT in=in[6], out=out[6]
  NOT in=in[7], out=out[7]
  NOT in=in[8], out=out[8]
  NOT in=in[9], out=out[9]
  NOT in=in[10], out=out[10]
  NOT in=in[11], out=out[11]
  NOT in=in[12], out=out[12]
  NOT in=in[13], out=out[13]
  NOT in=in[14], out=out[14]
  NOT in=in[15], out=out[15]

Multi-bit AND

Wiring

AND a=a[0], b=b[0], out=out[0]
AND a=a[1], b=b[1], out=out[1]
AND a=a[2], b=b[2], out=out[2]
AND a=a[3], b=b[3], out=out[3]
AND a=a[4], b=b[4], out=out[4]
AND a=a[5], b=b[5], out=out[5]
AND a=a[6], b=b[6], out=out[6]
AND a=a[7], b=b[7], out=out[7]
AND a=a[8], b=b[8], out=out[8]
AND a=a[9], b=b[9], out=out[9]
AND a=a[10], b=b[10], out=out[10]
AND a=a[11], b=b[11], out=out[11]
AND a=a[12], b=b[12], out=out[12]
AND a=a[13], b=b[13], out=out[13]
AND a=a[14], b=b[14], out=out[14]
AND a=a[15], b=b[15], out=out[15]

Multi-bit OR

Wiring

 OR a=a[0], b=b[0], out=out[0]
 OR a=a[1], b=b[1], out=out[1]
 OR a=a[2], b=b[2], out=out[2]
 OR a=a[3], b=b[3], out=out[3]
 OR a=a[4], b=b[4], out=out[4]
 OR a=a[5], b=b[5], out=out[5]
 OR a=a[6], b=b[6], out=out[6]
 OR a=a[7], b=b[7], out=out[7]
 OR a=a[8], b=b[8], out=out[8]
 OR a=a[9], b=b[9], out=out[9]
 OR a=a[10], b=b[10], out=out[10]
 OR a=a[11], b=b[11], out=out[11]
 OR a=a[12], b=b[12], out=out[12]
 OR a=a[13], b=b[13], out=out[13]
 OR a=a[14], b=b[14], out=out[14]
 OR a=a[15], b=b[15], out=out[15]

Multi-bit MUX

Wiring

  MUX a=a[0], b=b[0], sel=sel, out=out[0]
  MUX a=a[1], b=b[1], sel=sel, out=out[1]
  MUX a=a[2], b=b[2], sel=sel, out=out[2]
  MUX a=a[3], b=b[3], sel=sel, out=out[3]
  MUX a=a[4], b=b[4], sel=sel, out=out[4]
  MUX a=a[5], b=b[5], sel=sel, out=out[5]
  MUX a=a[6], b=b[6], sel=sel, out=out[6]
  MUX a=a[7], b=b[7], sel=sel, out=out[7]
  MUX a=a[8], b=b[8], sel=sel, out=out[8]
  MUX a=a[9], b=b[9], sel=sel, out=out[9]
  MUX a=a[10], b=b[10], sel=sel, out=out[10]
  MUX a=a[11], b=b[11], sel=sel, out=out[11]
  MUX a=a[12], b=b[12], sel=sel, out=out[12]
  MUX a=a[13], b=b[13], sel=sel, out=out[13]
  MUX a=a[14], b=b[14], sel=sel, out=out[14]
  MUX a=a[15], b=b[15], sel=sel, out=out[15]

Multi-way Gates

Multi-way variants of the logic gates can operate on multiple inputs at the same time.

8-way OR

An 8-way OR gate will output \(1\) when one of its input bits is \(1\) and \(00\) when none of the input bits are \(1\)

Wiring

  OR a=in[0], b=in[1], out=outab
  OR a=in[2], b=in[3], out=outcd
  OR a=in[4], b=in[5], out=outef
  OR a=in[6], b=in[7], out=outgh
  OR a=outab, b=outcd, out=outabcd
  OR a=outef, b=outgh, out=outefgh
  OR a=outabcd, b=outefgh, out=out

4-way 16-bit MUX

An 4-way 16-bit multiplexer selects one of its m n-bit inputs, and outputs it to its n-bit output. The selection is specified by a set of k selection bits, where \(k = \log_{2} m\). We will use our 16-bit MUX as the basis.

Wiring

  MUX16 a=a, b=b, sel=sel[0], out=outab
  MUX16 a=c, b=d, sel=sel[0], out=outcd
  MUX16 a=outab, b=outcd, sel=sel[1], out=out

8-way 16-bit MUX

Similarly, we need an 8-way 16-bit multiplexer.

  MUX4W16 a=a, b=b, c=c, d=d, sel=sel[0..1], out=outabcd
  MUX4W16 a=e, b=f, c=g, d=h, sel=sel[0..1], out=outdefg
  MUX16 a=outabcd, b=outdefg, sel=sel[2], out=out

Level-1 Ingredients

HADDER

FADDER

ADDER

DFF / Clock

Building the ALU

Binary Addition

Understanding binary addition is key to understanding how computers work. Every function that a computer can perform can be reduced down to the addition of binary numbers.

I’ve worked out a few examples on how to turn a decimal integer into its binary form. This is very simple but learning to think this way will make it easier for us to reason about how we will implement all the mathematical operations we need for the ALU.

First example is the number \(31337_{10}\).

Using this convention we can easily apply the same principle to any base number we want to convert from.

\(\displaylines{ \begin{align*} 11001010_2 &= (1 \cdot 2^{7}) + (1 \cdot 2^{6}) + (0 \cdot 2^{5}) + (0 \cdot 2^{4}) + (1 \cdot 2^{3}) + (0 \cdot 2^{2}) + (1 \cdot 2^{1}) + + (0 \cdot 2^{0}) \\ &= 128 + 64 + 0 + 0 + 8 + 0 + 2 + 0\\ &= 202\\ \\ \end{align*} }\) Integer numbers are unbounded. For any given number \(x\) there are integers that are less than \(x\) and integers that are greater than \(x\) but computers are finite and use a fix word size for representing numbers. A word is a hardware term used to specify the number of bits that computers use to represent a piece of information. Integers are typically stored in 8, 16, 32, or 64 bit registers. This implies that there is a limit of values that can be represented. An 8-bit computer can represent \(2^{8} = 256\) different things. This means that an integer can be from \(0\) to \(255\).

Binary numbers can be added bitwise from right to left. We first have to add the least significant bits (LSB) which are the two rightmost bits following the rules of addition.

Signed Binary Numbers

An n-bit binary system can code \(2^{n}\) values. If we have to represent signed numbers in binary we will have to split the space into 2 to represent negative and positive numbers. Modern computers do this using radix complement or commonly referred to as two’s complement method.

This means the radix complement of an \(n\) digit number \(y\) in radix \(b\) is defined as \(b^{n} - y\)

Using this formula we can look at how a 4-bit binary system would represent both negative and positive integers.

This system codes \(2^{n}\) signed numbers ranging from \(-(2^{n-1})\) to \(2^{n-1} -1\)

Notice that any non-negative number begins with a \(0\) To obtain the binary code of \(-x\) leave all the least significant \(0\)-bits and the first least significant \(1\)-bit of \(x\) intact and flip the remaining bits or flip all the bits and add \(1\) to the result.

So we can also see that there is an added benefit to the twos complement representation since we can see that subtraction is just addition (see Additive Inverse). We can look at \(6 - 7\) seeing that this is basically just \(6_{10} + (-7_{10})\) which would be \(0110_{2} + 1001_{2} = 1111_{2}\) which is just \(-1_{10}\)

Since we now have both addition and subtraction we can also implement multiplication and division all with just binary addition. Remember from group theory about the inverses of multiplication and addition as such we can use addition to to subtract and multiply and use multiplication to divide.

Addition

Sign Conversion

Subtraction

Comparison

Multiplication

Division

Performance

Real computer hardware implements adders differently in order to avoid the performance penalty of having to wait for the carry bits to propagate through the n-bit addends. You can read more about this here.