Digital Circuits and Systems
Section 4 Sequential Circuits 4.1 Overview of Sequential Circuits: Definition
The circuit whose outputs and next state depend on both the input signals and the present state of the circuit
Principle [spot the error!]
Memory Elements
Present State Clock Next State
Combinational Logic
Input Signals Output Signals
4.2 Flip-Flops SR Flip-Flop
S
SET
CLR
S 0 0 1 1
R Q 0 Q 1 0 0 1 1 X K Q 0 Q 1 0 0 1 1 !Q
Q Q 0 0 0 1 1 0 1 1 Q Q 0 0 0 1 1 0 1 1
S 0 1 0 X
R X 0 1 0
JK Flip-Flop
SET
CLR
J 0 0 1 1
J 0 1 X X
K X X 1 0
D Flip-Flop
SET
D Q 0 0 1 1
Q Q D X 0 0 X 1 1
CLR
T Flip-Flop
D T
SET
T 0 1
Q Q !Q
CLR
Q Q 0 0 0 1 1 0 1 1
T 0 1 1 0
4.3 Design of Sequential Circuits
Algorithm:
Obtain the description of circuit and create the
State Diagram
Determine the State Table Minimize the number of states Assign binary codes to each state Determine the number of flip-flops needed and
give a letter symbol to each of them
Choose the type of flip-flops Starting from State Table, derive the Excitation
Table and the Output Table
Derive the minimized circuit output functions
and flip-flop input functions
Draw the Logic Diagram
4.4 Example of Design
Design a sequential logic circuit whose output Z is 1 except when the input X = 1 for at least four clock periods. Then the output Z is 0. Use J-K flip-flops.
State Diagram [X/Z]
1/1 A 0/1 0/1 0/1 B
1/1 C
1/1 D 1/0
0/1
State Coding
Present State A B C D Code 0 0 1 1 0 1 0 1
Flip Flops
We require two JK flip-flops. Lets name them JKA and JKB
State Table
Present State A B C D Next State X=0 X=1 A B A C A D A D Output Z X=0 X=1 1 1 1 1 1 1 1 0
Excitation Table
QA 0 0 0 0 1 1 1 1 QB 0 0 1 1 0 0 1 1 X 0 1 0 1 0 1 0 1 QA 0 0 0 1 0 1 0 1 QB 0 1 0 0 0 1 0 1 JA 0 0 0 1 x x x x KA x x x x 1 0 1 0 JB 0 1 x x 0 1 x x KB x x 1 1 x x 1 0 Z 1 1 1 1 1 1 1 0
Minimisations and Equations JA
X\ QA QB 0 1 00 0 0 01 0 1 11 x x 10 X X
J A XQ B
KA
X\ QA QB 0 1 00 X X 01 x x 11 1 0 10 1 0
KA X
JB
X\ QA QB 0 1 00 0 1 01 x x 11 x x 10 0 1
JB X
KB
X\ QA QB 0 1 00 x x 01 1 1 11 1 0 10 X X
K B X Q A XQ A
Z
X\ QA QB 0 1 00 0 0 01 0 0 11 0 1 10 0 0
Z XQAQB
4.5 State Reduction
Definition of Equivalent States
Two or more states of a sequential circuit are equivalent if for the same values for the inputs, have exactly the same output and determine the sequential circuit transition to the same next state or to equivalent states.
Algorithm for State Reduction
If more 2 or more states are equivalent, one of them can be substituted with the other one The other states that have transitions to one of the removed states have to have their next states changed into the remaining equivalent state
Advantages of State Reduction
By reducing the number of states, it is possible that the number of flip-flops and/or amount of combinational circuitry needed to implement the sequential circuit will decrease, reducing the cost of the circuit
Example of State Reduction
Lets assume that there is the following state table:
Present State A B C D E F G
Next State X=0 A C A E A G A X=1 B D D F F F F X=0 0 0 0 0 0 0 0
Output X=1 0 0 0 1 1 1 1
States G and E are equivalent (same next states for the
same inputs and same outputs for the same inputs)
State reduction => state G will be replaced by E
Present State A B C D E F
Next State X=0 A C A E A E X=1 B D D F F F X=0 0 0 0 0 0 0
Output X=1 0 0 0 1 1 1
States D and F are equivalent State reduction => state F will be replaced by D
Present State A B C D E
Next State X=0 A C A E A X=1 B D D D D X=0 0 0 0 0 0
Output X=1 0 0 0 1 1
By reducing the number of states, the number of flip-flops and amount of combinational circuitry needed to implement this sequential circuit could have decreased, reducing the cost of the circuit. However in this example the number of flip-flops remains the same.
4.6 State Assignment
Definition of State Assignment
The process of assigning a binary code to each state
Possibilities for State Assignment
There are many possibilities to assign binary codes to states The number of possible options increases exponentially with the number of states The cost of the combinational circuit strongly depends on the state assignment chosen Although various State Assignment methods have been proposed, there is no assignment procedure that guarantees a minimal cost for the resulting combinational circuit
Examples of State Assignment
States A B C D E
Assign. 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1
Assign. 2 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1
Assign. 3 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1
4.7 Homework
Having the following state table, design the sequential circuit following state assignment 1, 2 and 3, respectively. Present State A B C D E Next State X=0 A C A E A X=1 B D D D D X=0 0 0 0 0 0 Output X=1 0 0 0 1 1
