## Beginning Logic Design – Part 2

Hello and welcome to Part 2 of my Beginning Logic Design series!

In this lesson we are going to build a 4-bit adding machine!

# Binary Numbers

In the digital world all we have is 0 and 1, so we need to come up with some clever ways to represent numbers. For now we’ll only worry about 4-bit unsigned integers.

Here’s a chart of the decimal numbers we’ll be able to represent, along with those same numbers in Binary and Hexadecimal

The digit displays in Logicly have 4 inputs, each represents a binary bit. The order for this display in Logicly goes from the least significant bit at the top to the most significant bit at the bottom.

I suggest building this design in Logicly yourself and playing with the switches if this is unfamiliar to you.

# The Classic 1-Bit Adder Circuits

Probably the most famous of combinational circuits is the Adder. Take two numbers in, and output the sum. Typically we start this design by creating what is known as a half adder, it takes two 1-bit inputs and adds them together.

Let’s look at a truth table for 1 bit addition (in binary!)

As you can see, to handle all 4 possible cases, we need to output 2 binary digits due to the `1+1` case. To support addition with any set number of digits, you need one more output digit to support the carry over value that changes a higher digit. This is similar to when you do `9+9` with decimal numbers, you carry a `1` to the 10’s place so you can represent the sum as `18` instead of just `8`, which would be wrong! We’ll separate out the sum and carry out in our table so that they are easy to reference.

Looking at this table, think of what gate could take `a` and `b` as inputs and output `carry`, as well as what could take `a` and `b` as inputs and output `sum`.

The answer is that we can use an `AND` gate to determine what the `carry` should be, and an `XOR` gate to determine the `sum`.

This is called a half adder, named so because it provides roughly half of a more useful design called a full adder. The full adder also lets us add two 1-bit numbers together, but can also handle chaining carry values together to add numbers of any width of bits!

The full adder shares the same two outputs, but adds a `carry in` input to consider the `carry out` value of a lower digit. Think about how we handle long addition in decimal, with the example of adding 123 and 99.

For the middle digit of the answer here, you will add three numbers, 2 + 9 + 1(the `carry in`) to land at 2 (`carry out` the 1).

We follow this same principle for the full adder, the truth table for which is a wee bit more complicated, due to the additional input.

The design for the full adder will take a bit more effort to work out, but let’s look at this table and make a few observations.

• When the `carry in` input is 0, the `carry out` and `sum` are the same as for the half adder, so we can use that design as a base for half of the input possibilities
• When `carry in` is 1, the `sum` is the opposite of what it otherwise would be
• When `carry in` is 1, the `carry out` is 1 if any other input is also 1

Hopefully you found some success in building your own full adder, but if not, don’t fret! Build this design on your end and tinker with it a bit.

It takes some practice to analyze these circuits. This one only has 3 inputs and two outputs, but it’s the arrangement of the 5 logic gates inside that makes you scratch your head. To understand a circuit like this I will look at the outputs, and follow the lines back to the inputs.

In this design, the `XOR` gates that lead to `sum` creates a situation where `sum` will be 1 if an odd number of the inputs are 1. For `carry out` there are two `AND` gates that result in the final `OR` gate outputting 1 if either `a` AND `b`, or if ((`a` XOR `b`) AND `carry in`).

With this design validated, we can save this as a custom component in logicly so we hide this complexity within a black box and get back to focusing on our goal, the adding machine!

We’ll first need to name the inputs and outputs. You can name them by clicking on the switches and light bulbs and entering the name into prompt that pops up. Next, highlight the whole design and go to `Edit->Create Integrated Circuit `or right click and select `Create Integrated Circuit` from the menu.

On my end, before hitting save, I moved the outputs so that sum was on top and `carry_out` was below it. We now have a reusable Full Adder circuit!

# Putting It All Together

Before I go too far, and make a huge mess of our schematic, I’ll make a 2-bit adder. I’ll start by adding some switches I can use to setup my inputs, along with displays to see what number it represents.

Next, I’ll add two full adders, and wire the upper switch (least significant bits) to the first adder.

Next I’ll hook up the output display by routing the sum to it.

The full adder isn’t outputting a valid state because some of its own inputs are invalid, in this case the lack of a `carry in` signal. I’ll use a constant to keep it low for the lowest bit.

At this point it can handle 1 bit input, but only 1 bit output. I could hook up the carry in for the 2nd bit.

To handle 2 bit input, I’ll route the 2nd bit switches to the next adder and route the `carry out` of the first adder to the `carry in` of the next. To display the output here, I’ll route the `sum` of the first adder to the 1st bit of display input, route the 2nd adder’s `sum` to the 2nd bit input, and the final `carry out` to the 3rd bit.

This same pattern can be extended to handle another 2 bits.

There’s the 4-bit adding machine! It could be made to any bit width, but 4 fits a single display. It is possible for there to be a 5th bit of output, but we’ll just drop that for now. In many adders that final carry is interpreted as an carry flag to let you know the sum digit width was larger than the input digit width.

For a messier example of how this can scale, here’s a 16-bit adder in logicly.

Save

Save

Save

Save

Save

## Beginning Logic Design – Part 1

I have a passion for learning about technology. My desire to understand more about how things work has driven me to dive into lower and lower levels of computing systems. For the last couple years I’ve been trying to go all the way down to working with the basic digital components. I did not find many resources to help learning these low level basics, so today I am kicking off a series to teach others how easy it can be to get started with digital logic design.

# How We’ll Be Learning

There are not a lot of tools I’ve found that are modern, useful or stable enough to use to get started with learning basic digital design. Most legit hardware design tools are based on using a Hardware Description Language such as VHDL or SystemVerilog. I think the early digital knowledge you need is best solidified with schematic design and simulation; by working with the most basic logic gates to understand how larger and more complex designs can be made from very simple components.

The best tool I’ve found so far for digital logic design and simulation is logic.ly, an educational piece of software that has a clean and usable interface along with a good set of features around managing subcomponents. It is not free software, a full license runs around \$60, but there is a free trial that you can use for up to 30 days. It is also only supported for Windows and OSX, though I have had good luck running it via Wine on my Ubuntu box.

The best free (and open source!) alternative to this I found was BOOLR, which is a fairly impressive simulator but as of this writing is not stable enough to recommend. I’ll be keeping an eye on that project to see where it goes.

As far as prerequisite knowledge requirements, I recommend some familiarity with binary and hexadecimal numbers. Outside of that, some determination is all you need!

# Getting Started

To get started, download Logicly and get it installed. Activate your 30-day trial and fire it up!

To get the lay of the land, let’s look at some of the most basic components Logicly has to offer.

I have Logicly’s 5 input devices on the left and its 2 output devices on the right.

Starting from the top of the inputs, Logicly has a toggle switch that operates very similar to a light switch, it outputs 0 when the switch is off and 1 when the switch is on. Below that is a button, or momentary switch, that normally outputs 0, but while it is held down will output 1. The next input devices is a clock signal, it automatically flips its output after a configurable time, one second by default. The last two inputs are constants, always 1 or always 0.

On the right side we have the outputs. The light bulb is lit or unlit depending on the signal being driven to it. The second output device is a digit display, which will show a 0-F hexadecimal value based on its 4 input bits. We’ll only be using the light bulb for this lesson.

Feel free to dabble with these components if you’d like, we’ll use them to explore the logic gates in the next section.

# Basic Logic Gates

Logicly has 9 components in it’s Logic Gates category, we’ll explore them each here.

The first row has the `Buffer` and the `NOT` gate. These are the simplest gates. The `Buffer` simply outputs an identical signal to its input, in Logicly this is generally only useful for adding a bit of delay to signal propagation. We won’t be using the `Buffer` component very much, if at all. The `NOT` gate will output the opposite of its input.

As you can see above, when the switch is on, the light behind the buffer is also on, while the `NOT` gate inverts the signal and the light behind it stays off. Notice the similarity of the component symbols, in digital design you’ll often see a small circle that indicates the inversion of a signal from low to high or high to low.

The next row of components is the `AND` gate and the `NAND` (NOT-AND) gate. The `AND` gate will output 1 only if all inputs provided to it are 1.

The `NAND` gate has the opposite output of the `AND` gate, similar to what you’d see if you used a `NOT` gate to invert the output of an `AND` gate.

The next two gates are `OR` and `NOR`. The `OR` gate will output 1 if any input is 1, and 0 if all inputs are 0.

As you may expect, the `NOR` gate is very similar to the `OR` gate, but with inverted outputs.

The next couple gates are `XOR` and `XNOR`. The `XOR` gate, short for exclusive-or, is a little bit trickier. In a 2-input configuration it will output 1 if the two inputs differ, and 0 if the two inputs are the same.

This symbol for `XOR` is very similar to `OR`, but has an extra curved line on its input side to stand apart. Just like with the other N* gates the `XNOR` has the opposite outputs of `XOR`.

The last basic logic gate Logicly gives us is a `Tri-State` Gate. It is very similar to the `Buffer` with the addition of a signal to control if the output of the buffer is enabled. If the `Tri-State` is enabled, the output will match the input, if disabled it will not emit an output which leaves the connection unset, or floating, allowing something else to control the output line its connected to. Don’t worry about this gate for now, we won’t use it for a bit.

It can take a while to get used to these symbols and their outputs, here’s a diagram that shows the truth tables, and boolean algebraic expressions for these gates.

These gates are each fairly simple but all digital electronics are composed of just these gates in various arrangements! It may take a while to understand how things like RAM, CPUs and entire computers can be built from such simple components, but as you practice building incrementally more complex circuits it will begin to make sense.

# Functionally Complete Gates

Two of these logic gates (`NAND` and `NOR`) have a very special feature, they are functionally complete. This means that any other gate, and therefore any digital machine, can be made of just `NAND` gates or just `NOR` gates. This has some significant benefits for manufacturing electronics, but since we’re not fabs we’ll just explore this property to get a bit of practice building some simple circuits. NAND logic is a bit more popular for various reasons, so let’s explore how we can make some of other other basic gates by using just `NAND` gates.

To start off with, here’s a `NAND` gate setup to work just like a `NOT` gate, I have these gates in parallel so they share the same input to allow for easy comparison.

By simply wiring the switch to both `NAND` inputs, we get the exact same behavior as a `NOT` gate.

We can use this same concept to implement an `AND` gate. Since `NAND` has the opposite output of `AND`, we can use the previous `NOT`-like configuration to flip the output of `NAND` to match `AND`. `NNAND`?

For some solo practice, try your hand at replicating the function of `OR` and `XOR` gates using only `NAND` gates. If you get stuck (I did), reference Wikipedia’s page on NAND Logic for the solution and look at the wire states in Logicly as you toggle the inputs and think about why it works.

This is a whopper of a first lesson, but I hope it’s useful for folks just starting out. If you have any questions or feedback please leave a note in the comments and I’d be glad to help you out. In the next post we’ll be exploring some of the interesting things you can do by combining these basic logic gates. Keep tinkering!

Save

Save

Save