Logic Gates & Memory: Building an 8-Bit Adder from Scratch

In this chapter, we’ll see how simple switches can be combined into logic gates, the fundamental building blocks of digital circuits. Step by step, we’ll explore the basic gates: NOT, AND, OR, and a few useful variations. Then we move on to how they can be wired together into larger circuits, known as combinational logic. Along the way, we’ll build our first arithmetic circuits: starting with the Half-Adder, then extending it into a Full-Adder, and finally chaining them together to create an 8-bit adder, capable of adding entire binary numbers. Finally, we’ll wrap up with an introduction to sequential logic, where circuits gain memory and can remember past states.

From switches to logic gates

As we saw in the previous chapter, a transistor at its core acts like an electronic switch: it either allows current to flow (on) or prevents it from flowing (off). In the simple circuit shown below, an AA battery provides the power, the LED indicates the on/off states, a transistor controls the electric flow, and the resistors limit the current to protect the transistor and LED from damaging or even exploding (which can happen to the best of us).

By looking at the circuit, you will notice that it is just an LED that turns on and off depending on the transistor’s state. It may not look impressive, but here is the idea: by cleverly wiring transistors, we can make them do more than switch a light on/off. We can make them process information. This is where logic gates come in. The very first one we’ll explore is the NOT gate, followed by the AND and OR gates.

NOT Gate

You may wonder: What happens if we change how the LED is connected? Instead of wiring it directly to the transistor’s output path, we place it on the transistor’s collector side (the path to ground). Now something interesting happens: the circuit flips the signal. The output becomes the opposite of the input. This is called an inverter, or more commonly, a NOT gate.

When the transistor is on, current flows from the battery’s positive side through the resistor and straight to its negative (ground) via the transistor. In this state, the transistor acts almost like a short circuit, providing a low-resistance path for the current to follow. A transistor isn’t a perfect wire, and even when fully on, there is still a tiny “resistance” inside it. This tiny resistance causes a small voltage drop across the transistor. Most of the battery’s voltage now falls across the first resistor and the transistor. Very little voltage is left for the LED, so it stays off. In digital circuits, this small leftover voltage is still seen as a logical 0 (low). When the transistor switches off, the path to ground vanishes. Current can now flow through the LED instead. The LED lights up, which we read as a logical 1 (high).

In logic and computer science, outputs for every possible input are often shown in a truth table. A truth table lists all input values (true or false) and the corresponding outputs. Below is the truth table for a NOT gate. In math, the output is often labelled as Y.

AND Gate

Of course, we are not limited to using just one transistor. By combining multiple, we can build circuits that only give an output under specific conditions. One of them is the AND gate. In the example below, we connect two transistors in series (one after the other) to create an AND gate. Current from the source must pass through both transistors before it can reach the output. In other words, the output will be high if and only if both inputs (A and B) are high. If either transistor is off, the path is broken, and no current reaches the output.

Here follows the truth table for the AND gate:

OR Gate

Now let’s try wiring the transistors in parallel instead of in series. This gives us the OR gate. In this case, the current only needs one path or the other to reach the output to make it high, hence the name OR.

Here is the truth table for the OR gate:

XOR Gate

There is one more gate that deserves special attention, and because we will need it later: the XOR gate, short for exclusive OR. This gate is like the regular OR gate, but with a twist. As we know from the previous section, with an OR, the output is high if one or both inputs are high. With the XOR, the output is only high if exactly one input is high. This behaviour makes XOR extremely useful, because it can act as a simple difference detector: output is 1 if the inputs are different, and 0 if they’re the same. You’ll see XOR pop up again in circuits that perform arithmetic, like adders.

Here’s the truth table for XOR:

NAND and NOR Gate

By combining the previous gates, we can create even more variations. For example, if we take the output of an AND gate and run it through a NOT gate, we get a NAND gate (short for NOT AND). Likewise, combining an OR with a NOT gives a NOR gate (NOT OR). NAND and NOR are called universal gates because you can combine them to perform any Boolean function and thus create any other type of logic gate (AND, OR, NOT, XOR, XNOR).

Combinational Logic

So far, we’ve looked at the basic gates: NOT, AND, OR, and a few variations like XOR, NAND, and NOR. Each one flips, combines, or filters signals simply. The real magic begins when we connect them. By combining gates, we can create circuits that solve more interesting problems. These are called combinational logic circuits. The key feature of combinational logic is that the output depends only on the current inputs. These circuits are stateless. They don’t remember what happened before, meaning that if you give the same inputs, you’ll always get the same outputs. With enough combinational logic, we can create circuits that add, subtract, increment, and do much more. In fact, arithmetic operations in a computer all come down to cleverly arranging these simple logic gates.

To see combinational logic in action, let’s build something practical: a circuit that can add two numbers together, the Half-Adder, a simple circuit that can add two binary bits together. Before we dive in, here’s a quick overview of the most common gate symbols:

Okay, let’s start small. Suppose we add two 1-bit numbers, A and B. The result of this addition has two parts: the sum and the carry. The sum is the result of the addition, and the carry is like the overflowing bit, indicating that the result is greater than we can hold in the sum. For example:

Here’s the fun part: we can build this exact behaviour using only the gates we’ve already learned! When we look at the table above, we can see that the sum is only 1 when either A or B is 1. This exactly matches the behaviour of an XOR. Now for the carry, it is only 1 when both A and B are 1. This is the behaviour of the AND gate. If we put that together, it will look something like this:

This little circuit is our first glimpse at how computers perform arithmetic operations. It’s neat, but it has a limitation: it doesn’t handle a carry input. In real arithmetic, numbers don’t exist in isolation. When adding multi-bit numbers, each column might produce a carry that needs to be added to the next. This is where the bigger brother of the Half-Adders comes into play, the Full-Adder. A Full-Adder extends the Half-Adder by including a carry-in bit (C-in). Its outputs are the sum and a carry-out bit (C-out). How do we build one? Well, it’s surprisingly easy! Here is how it works:

1. Take two Half-Adders.
2. Feed the sum from the first into one input of the second (together with C-in).
3. Use an extra OR gate to combine the carry outputs from both Half-Adders.

The result is a Full-Adder!

Now, here’s where it gets exciting: if we chain multiple Full-Adders together by feeding each carry-out into the next carry-in, we can add multi-bit numbers. For example, connecting 8 Full-Adders creates an 8-bit adder, capable of adding two 8-bit numbers. The final carry-out then serves as an overflow signal if the result doesn’t fit into 8 bits.

Sequential Logic

So far, we’ve only looked at combinational logic circuits, circuits whose output only depends on the current inputs. Change an input, and the output changes immediately. A computer needs more than just that. If you write a sentence and your computer instantly forgets the previous letter every time you press a new key, it would not be useful. It also needs memory. This is where sequential logic comes in. Sequential circuits combine logic gates with feedback loops so that the output doesn’t just depend on the current inputs, but also on the circuit’s previous state. In other words, they have memory.

A simple example of sequential logic in action is a flip-flop, a tiny circuit that can store a single bit of information. The information is stored until a new input changes it. One of the simplest types is the SR flip-flop (Set-Reset flip-flop). It has two inputs:

• S (Set): tells the circuit to remember a 1
• R (Reset): tells the circuit to remember a 0

And it has the outputs Q and Q′, which hold the stored value and its inverse.

The truth table looks like this:

Notice something new here: when S = 0 and R = 0, the output doesn’t change. The flip-flop remembers whatever it was holding before. That’s memory in action. As you can see, this simple flip-flop has a flaw: the state where both S and R are 1 is undefined. Luckily, engineers have designed improved versions like the JK and D flip-flops that avoid the undefined state, making them more reliable building blocks for memory.