Beginning Logic Design – Part 3

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

In the last post we explored a common combinational circuit, the adder. In this post I’ll explore some of the basic sequential logic elements: latches and flip-flops.

Sequential Circuits

So far, the circuits I’ve shared are pretty linear. The schematic diagrams have had inputs on the left and all signals move toward the outputs on the right. For sequential circuits, there is an element of feedback where some outputs are routed back into an earlier gate.

Let’s look at the concept of feedback using the NOR gate as our base. I’ll provide one switch as input, and I’ll use it’s own output as the second input.

NOR gate with feedback

In this configuration, the NOR cannot yet determine what it’s output should be, let’s look at the truth table for NOR to understand why.

NOR truth table

Looking at the truth table, if we only know one of the inputs and we know that it’s 0, we can’t determine the output. On the other hand if we know one of the inputs is 1 we can safely say the output is 0.

Now the second input is also known, but something interesting happens if we turn the switch off now.

A confused NOR gate

When the switch is off, the NOR gate will flip its output back and forth due to the feedback loop. When the gate sees the 1 on its 2nd input it changes its output to 0, when it then sees both inputs as 0 it again starts to output 1. If we turn the switch back on, it again doesn’t matter what the second input is set to, the output will be locked to 0.



The Set-Reset Latch

The sequential circuit with the single NOR doesn’t give us a very useful function. It initially has an undefined output state after which it can either have an off state when we give it an input of 1 or a crazy flipping back and forth state when we input 0. A design called the SR (Set-Reset) latch can provide a more useful operation. It is like the previous design but with two sides and the NOR gates providing feedback to each other.

The Set-Reset latch

Just like before, the initial output cannot be determined. This time, by turning the top switch on, the top NOR will now have a known output of 0. This will also cause the bottom NOR to have a known output  of 1 because both of its inputs are now 0. Since the bottom output is now 1, the top NOR will stay 0 as the top switch goes back off.

Setting the SR latch

When both inputs are 1, both outputs are 0 since neither NOR gate has the two 0 inputs needed to output 1.

SR latch with both inputs high

The first switch to toggle to 1 will have its NOR gate toggle output to 1 which will lock the opposite NOR gate to 0.

Looking at the overall behavior of the SR latch

By convention, we refer to one of these inputs as set and the other as reset.The output state of a latch is usually labeled as Q and sometimes the latch will also output the opposite of Q. In this design Q is the output from the NOR gate on the reset side of the design. Since the design is symmetrical, it doesn’t matter which side you choose to be set or reset.

SR latch with labels

Here’s a table that describes the various interactions we see for this design.

SR latch operations table

Since !Q is expected to be the opposite of Q, the outputs are not considered valid with both inputs are 1 as that results in both outputs being 0.  There is another model for the SR latch that is built using an AND, OR and NOT gate to prioritize reset over set.

SR and-or implementation

In this design there is no !Q output and if reset is 1, the value of set is effectively ignored since the AND gate here will never output 0 when reset is 1.

There is also a way to make a similar SR latch with NAND gates, though it has inverted operations where the output is stable when both inputs are 1 and you drop an input to 0 to set or reset the output.

NAND based SR latch in reset state

The last variation of the SR latch I want to share is the gated SR latch, which adds an enable input that assist in controlling the latch operation.

SR latch with enable input

The addition of the AND gates with enable input give you a bit extra control of when state changes are allowed. When the enable input is 0, it will preserve the latches state. This allows you to setup set and reset as you’d like, when you’re ready for the latch to operate you can toggle enable on and off to perform the operation.

Using enable to control when the SR latch changes state

The SR latch is quite common and useful, and can be used as a basis for other common latches.

The Gated D Latch

I am a fan of the gated D latch, it is a slight variation to the SR latch that gives you a simple way of storing a single bit of information. By renaming set to data, and replacing reset with the inverse value of data, we provide our bit to store via the data input and use enable to control when that data is latched.

A D latch design

This design removes the possibility of an input state that would set both Q and !Q to 0, and lets use use a single input to choose if Q will be 1 or 0.

D latch in action

When Latches Become Flip-Flops

In the components section of Logicly there are a few objects under the category Flip-Flops. There are SR, D, JK and T flip-flops. Latches and flip-flops are commonly confused. The first few designs we looked at have no inputs intended for synchronization, these are just called latches. We then looked at gated latches, which add an enable input so that we can control when the data on the other input lines should be treated as valid. With a gated latch, the entire time the enable signal is active, changes to the other inputs will affect the state of the latch. The special bit about a flip-flop is that the state of the latch is limited to the transition of enable from low-to-high (rising or positive edge) or high-to-low (falling or negative edge).

Diagram showing some features of a clock signal

A gated latch can be affected by it’s input during one half of the clock period, while a flip-flop is at a point in time. This is very helpful for digital designs that need more precise timings, such as a CPU.

The easiest way to build my own D flip-flop would be to first save my gated D latch as a component.

Creating a D latch IC

Now, I’ll place two D latches in my design and route the q output of the first to the data input of the second. By connecting a clock to the enable input of the first, and providing the inverted clock signal to the second, it creates a circuit that will only change the output on the falling edge of the clock signal.

Falling edge triggered D flip-flop

Now that’s a functional flip-flop! I encourage you to build this design yourself and play with the input as the clock changes to watch how it will only change as the clock transitions from 1 to 0.

To make a flip flop that triggers on the rising clock edge, route the inverse clock to the first latch, and the normal clock to the second latch.

Rising edge triggered Flip Flop

With that we now know how we can build our very own flip flops to store individual bits of data! For continued exploration on latches and flip flops, I encourage you to dive into the web and build your own JK and T type flip flops. You may also notice that the D flip-flops in logicly have some extra inputs for clear and preset; you can explore what those asynchronous inputs provide and see if you can add that functionality to your own flip flop implementation! It will all sink in with practice!

That wraps it up for this post. If you have any questions or feedback I would love to see your submission in the comments. Keep tinkering!

Save

Save

Save

Save

Save

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 numbers we’ll be able to represent with 4 bits

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.

Logicly digit display showing the hexadecimal value for 0101

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.

Half adder truth table

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.

A half adder circuit

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.

Very Math

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.

Truth table for a full adder

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

Try on your own to make a full adder!

The Full Adder

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.

A common full adder implementation, other designs are possible

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.

Create integrated circuit prompt

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.

My two bit operands

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

Starting to wire it up

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

The display is angry!

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.

Setting the carry input to 0

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.

Reading both output bits

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.

A working 2 bit adder

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

A 4 bit adder!

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.

This is the largest I’m willing to fuss with in Logicly

That covers this post on building some digital adders. If you have any feedback or questions please leave a comment! Keep tinkering!

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!

Logicly running via Wine on Ubuntu 16.04

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

Input and Output devices in Logicly

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.

A buffer and a NOT gate in parallel

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.

AND gate in various input configurations

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.

NAND gate in various input configurations

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.

OR gate in various input configurations

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.

XOR gate in various input configurations

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.

NOT gate next to NOT implemented with a NAND gate

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?

AND gate next to AND implemented with NAND gates

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