Figure 1

http://www.pling.org.uk/cs/dad.html

Up til now, you have probably only dealt with combinatorial circuits, where the circuit outputs depend only on the current inputs. With sequential circuits, we can now store a previous input in memory states (using memory elements such as flip-flops), so that the circuit’s output is a function of both current and past inputs. Making the outputs to be dependent on a series of inputs allows us to tackle more complex computational problems with simpler circuitry.

Once the necessary states for a sequential circuit have been established and encoded, the next step is implementing the transitions between states using combinatorial logic. At every clock pulse, the flip-flops that are encoding the current state are updated to represent the next state depending on the current state and inputs. Using the state diagram, we can create a transition table which will dictate the combinatorial part of the sequential circuit.

Depending on the type of memory element used (e.g. JK flip-flops, D flip-flops), the combinatorial logic that feeds into the memory must be implemented differently. You can optimize sequential circuits by choosing the optimal memory element. But there are always trade-offs, and the best option will depend on individual circumstances.

In the next section, we have an example of implementing a state diagram as a circuit by creating a next state/excitation table.

State diagrams describe different states in a sequential circuit. Each circle is a state and the arrows between the circles shows how to transition to the next state. Each arrow has 2 numbers next to it. The first number is the input value received and the next number is what the output value would be based on the most recent input and the previous inputs.

An example of a sequential circuit is a sequence recognizer. A sequence recognizer takes a string of numbers and test to see if there is a certain set of numbers in that string. For this example, our sequence recognizer will test for two sets of numbers: 1111 and 101. To do this, we will start by building a state diagram. The first step is to define what states are needed. One state that is necessary is A. State A means nothing in our sequences has been detected. The next state needed is B. State B means 1 has been detected. The next state is state C which says that 11 has been detected. The final state is D which says that 111 has been detected. This is the final state needed because the next input will decide if the sequence has been detected our not. If it has been detected then the output is 1 and we cycle back to state C. If the sequence has not been detected, then the output is 0 and we cycle back to state A. Our other sequence is 101. The states for this sequence are A (nothing detected), B(1 detected) and E which says that 10 has been detected. This gives a total of 5 states.

Next is to decide the state transitions, i.e. how we move from one state to the next. Depending on your preference, you can draw a state diagram first and then a state table or the other way around. We are going to draw a diagram first. To start, draw circles (or any shape of your choosing) and label each circle with a state name. Then draw arrows between each state making sure to label the input needed to get to that state and the output that would be produced at that time. Be sure to draw an arrow to denote what the first state is.

Figure 2

Turning this into a table, and then into circuitry takes some time. Start by asking what kind of storage you want to use. For the purpose of this example, we’ll use D latches.

Since there are 5 states in this diagram, we have to use 3 flip-flops to represent them in binary.

A= 000 B= 001 C=010 D= 011 E=111

Now, we’ll build a table that shows input, states, next states, outputs of the D, and outputs

After this, you need to draw out K-maps to find the minimal SOP expressions for the D’s and z.

D₃ = Q₃’Q₂x’ + Q₂Q₁x + Q₃’Q₁x’

D₂ = Q₃’Q₂ + Q₃’Q₁ + Q₁x

D₁ = Q₂Q₁’ + Q₁’x + Q₂x

z = Q₃x