Ground Up: Gates

Welcome to a series of posts cleverly titled Ground Up, where I explain computing concepts from the ground up! We’ll explore how computers work starting with transistors and going from there. This post specifically covers gates, binary math, and adders.

• [Part 1: Bits]({% post_url 2021-06-18-ground-up-bits %})
• Part 2: Gates
• [Part 3: Memory]({% post_url 2021-07-18-ground-up-memory %})
• [Part 4: State Machines]({% post_url 2021-09-18-ground-up-state-machines %})

Gates

In the [previous section]({% post_url 2021-06-18-ground-up-bits %}) we learned about transistors and how we can use them to make circuits that perform binary logic. Let’s catalog these gates as additions to our building blocks.

Gate	Transition Table	Gate Symbol
NOT	A Output 0 1 1 0
AND	A B Output 0 0 0 0 1 0 1 0 0 1 1 1
NAND	A B Output 0 0 1 0 1 1 1 0 1 1 1 0
OR	A B Output 0 0 0 0 1 1 1 0 1 1 1 1
NOR	A B Output 0 0 1 0 1 0 1 0 0 1 1 0
XOR	A B Output 0 0 0 0 1 1 1 0 1 1 1 0
XNOR	A B Output 0 0 1 0 1 0 1 0 0 1 1 1

Binary

Gates operate on binary data; “on” or “off,” 1 or 0. This data doesn’t really mean anything unless we give it meaning, and I think a useful thing we could do is have it represent numbers. Binary numbers are exactly like normal numbers, except we only have two symbols to work with (represented by “off” and “on”).

If we were to count up in binary, we would start with 0, then 1, then.. well that’s all the symbols we have! To get around this, let’s add a more significant digit 10. Do you see any similarities with using ten symbols to count? I hope so, because this way of thinking can be extended to any basis, including base 16 which uses 16 symbols! But we’ll get to that later. For now, it’s enough to know how to represent larger numbers using binary digits (bits).

Converting Between Binary and Decimal Numbers

We have established that we can represent numbers in binary, and if we stick to this representation, we can express the relationship between binary and decimal numbers using math. Given a binary number $$B$$ with $$n$$ bits, it’s decimal value can be calculated as:

{% raw %} $$ \sum_{k=0}^{n-1} B_{k}\cdot 2^{k} $$ {% endraw %}

where $$B_{k}$$ is the $$k$$th significant bit of $$B$$.

I find it’s best to comprehend this with an example. A three-bit binary number 101 would be:

{% raw %} $$ \begin{align} 101_2 &= (1)\cdot 2^{2} + (0)\cdot 2^{1} + (1)\cdot 2^{0} \ &= 2^{2} + 2^{0} \ &= 4 + 1 \ &= 5 \end{align} $$ {% endraw %}

Going from decimal to binary is a similar operation. The way I think of it, is finding all of the powers of two that sum to the decimal value. An algorithm to do this for a decimal number $$D$$ is to repeatedly divide $$D$$ by $$2$$ and noting the remainder until $$D$$ is $$0$$. The binary number is the remainders in reverse order. Here is an example for converting $$6$$ to binary.

Alternatively, $$6$$ is $$4 + 2$$ = $$2^{2} + 2^{1}$$ which means bit $$2$$ and $$1$$ are set: 110.

Binary Math

We can even perform math in binary the same way we normally do. 1 + 1 = 10. Here’s another example of using larger numbers: 0110 + 1100. On the left is the binary representation, and the right is the decimal.

Hopefully this example makes it clear, but the same rules of adding decimal numbers applies to adding binary numbers. When you overflow, you need to carry the 1 to the next significant digit.

Adder

Now that we know how to represent numbers using binary, let’s make a circuit that will add two bits for us. We’ll begin with the state transition table. We have two bits as input, and two bits as output.

This table describes adding two single bits together, with the output being a single two-bit number. Out1 is the most signifcant bit, and Out0 is the least significant bit.

So far so good, but there’s one problem. Sometimes we need to add 3 bits together when there is a carry-over like in the previous example.

Let’s modify the circuit to sum three bits: two inputs and a carry.

| A | B | C | Out₁ | Out₀ | |:—:|:—:|:—:|:—::|:—:| | 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 | {: style=“width: 30%;”}

Now let’s create this circuit using our building blocks. The first step is to create a minimal boolean expression that models our transition table. We want to express each output bit as a function of input bits. One way to figure this out is with Karnaugh Maps, but we’ll cover that later. For now, we will use the following.

{% raw %} $$ \begin{align} Out_1 &= AB | BC | AC \ Out_0 &= A \oplus B \oplus C \ \end{align} $$ {% endraw %} Note: sometimes AND is represented as multiplication and OR as addition. Similarly you may see XOR represented with ^.

Instructions: toggle the inputs to see how the circuit reacts.

Let’s try stacking two together to add 2-bit numbers. For simplicity, we will package the above gates together into a single unit. You’ll notice we connect Out₁, the overflow bit, directly to C, and this can be chained indefinitely.

Conclusion

Excellent! Hopefully you are starting to see the usefulness of all of these low level components as we start to build up what we can do with them. Here’s a bonus challenge: see if you can modify our adder to do subtraction! Hint: you do not have to change any internal gates.

As always if any parts were unclear, please feel free to contact me.

[Take me to the next part!]({% post_url 2021-07-18-ground-up-memory %})