Sequential Circuit Design

Vivek Kumar
NIT Uttarakhand
 Presentation Outline
❖ The Design Procedure

❖ Moore Sequence Detector

❖ Mealy Sequence Detector

❖ Tracing State Diagrams and Verifying Correctness

❖ Sequential Comparator

❖ Binary Counter

❖ Up/Down Counter with Enable

 The Design Procedure
Given a Description (or Specification) of the Problem

1. Obtain a state diagram for the sequential circuit

2. Assign binary codes to the states and fill the state table

3. Select the type of Flip-Flops and derive the FF input equations

4. Derive the output equations

5. Draw the circuit diagram

6. Verify the correctness of the final design (verification)

 The State Diagram
❖ A state is an abstraction of memory

❖ A state remembers a history of inputs applied to the circuit

❖ Examples:

 State S0 represents the fact that the last input is a 0

 State S1 represents the fact that the last input is a 1

 State S2 represents the fact that the last two-input sequence is "11"

❖ Obtaining the state diagram is the most important step

❖ Requires experience and good understanding of the problem

 Example: Sequence Detector
❖ A sequence detector is a sequential circuit

❖ Detects a specific sequence of bits in the input

❖ The input is a serial bit stream:

One input bit 𝒙 is fed to the sequence detector each cycle

❖ The output is also a bit stream: One output bit 𝒛 each cycle

Indicates whether a given sequence is detected or not

𝒙
Sequence 𝒛
𝑐𝑙𝑘 Detector
 State Diagram for a Sequence Detector
❖ Example: Design a circuit that detects the input sequence "111"
❖ Begin in an initial state: call it S0
S0 indicates that a 1 is NOT detected yet
As long as the input 𝑥 is 0, remain in the initial state S0
❖ Add a state (call it S1) that detects the first 1 in the input
❖ Add a state (call it S2) that detects the input sequence "11"
❖ Add a state (call it S3) that detects the input sequence "111"

0
1 1 1
S0 S1 S2 S3
 Complete the State Diagram
Moore Design: Assign Output to States
The output in S0, S1, and S2 should be 0 0
0
The output in S3 should be 1
S0 1 S1
0 0
Now complete the state diagram:
Add transitions from S1, S2, S3 0 0 1
back to S0 if the input is 0
Add transition from S3 to itself if S3 S2
1 1 0
the input is 1 to detect sequences
longer than three 1's
1
 State Assignment
❖ Each state must be assigned a unique binary code

❖ If there are 𝑚 states then

The minimum number of state bits: 𝑛 = 𝑙𝑜𝑔2 𝑚

𝑥 is the smallest integer ≥ 𝑥 (ceiling function)

❖ In our example, there are four states: S0, S1, S2, and S3

Therefore, the minimum number of state bits (Flip-Flops) = 2

❖ State assignment: S0 = 00, S1 = 01, S2 = 10 and S3 = 11

❖ If 𝑛 bits are used, the number of unused states = 2𝑛 − 𝑚

❖ In our example, there are NO unused states

 From State Diagram to State Table
0
Present Next State Output
0 State 𝒙 = 0 𝒙 = 1 𝒛
S0 1 S1
S0 S0 S1 0
0 0 S1 S0 S2 0
S2 S0 S3 0
0 0 1
S3 S0 S3 1

S3 S2 Present Next State Output

State 𝒙 = 0 𝒙 = 1 𝒛
1 1 0
00 00 01 0
1
State Assignment 01 00 10 0
S0 = 00, S1 = 01 10 00 11 0
S2 = 10, S3 = 11 11 00 11 1
Structure of a Moore Sequence Detector
Next Current
𝒙 Next State State D Flip State Output 𝒛
Logic Flops Logic

clock

❖ In our design examples, only D-type Flip-Flops will be used

❖ They are the simplest to analyze and implement

❖ Next, we need minimal expressions for

1. Next State Logic

2. Output Logic
 Derive Next State an Output Equations
𝑥 𝐷1 𝑥 𝐷0
Present Next State Output 𝑄1 𝑄0 0 1 𝑄1 𝑄0 0 1
State 𝒙 = 0 𝒙 = 1 𝒛 00 0 0 00 0 1
00 00 01 0 01 0 1 01 0 0
01 00 10 0 0 1 11 0 1
11
10 00 11 0
10 0 1 10 0 1
11 00 11 1
𝑄1 𝑥 + 𝑄0 𝑥 𝑄1 𝑥 + 𝑄0′ 𝑥
Two D-type Flips-Flops
Present State = Flip-Flop Outputs 𝑄1 and 𝑄0
Next State = Flip-Flop Inputs 𝐷1 and 𝐷0
Next State equations: 𝐷1 = 𝑄1 𝑥 + 𝑄0 𝑥 and 𝐷0 = 𝑄1 𝑥 + 𝑄0′ 𝑥
Output equation: 𝑧 = 𝑄1 𝑄0 (from the state diagram)
Draw the Moore Sequence Detector Circuit
𝐷1 = 𝑄1 𝑥 + 𝑄0 𝑥 , 𝐷0 = 𝑄1 𝑥 + 𝑄0′ 𝑥 𝑧 = 𝑄1 𝑄0

Next State Logic

Output
Logic

𝐷1 𝑄1

𝑄1′

𝐷0 𝑄0

𝑄0′
 Mealy Type Sequence Detector
❖ Let us redesign a Mealy type "111" sequence detector
❖ The initial state S0 indicates that a 1 is NOT detected yet
As long as the input 𝒙 is 0, remain in the initial state S0
Notice that input / output is written on the arc (Mealy type)
❖ Add a state (call it S1) that detects the first 1 in the input
❖ Add a state (call it S2) that detects the input sequence "11"

0/0

S0 1/0 S1 1/0 S2
 Complete the Mealy State Diagram
❖ State S2 is reached after detecting the input sequence "11"
❖ At S2, if the next input is 1 then the output should be 1
Make a transition from S2 back to itself labeled 1 / 1
No need for state S3, because output is on the arc
❖ Now complete the state diagram
Add transitions from S1 and S2 back to S0 when input is 0

0/0
0/0 1/1 Mealy Machines
0/0 typically use
1/0 1/0 less states than
S0 S1 S2
Moore Machines
 State Assignment and State Table
Three States ➔ Minimum number of state bits (Flip-Flops) = 2
Assign: S0 = 00, S1 = 01, and S2 = 10 (State 11 is Unused)
0/0
0/0 1/1
0/0

S0 1/0 S1 1/0 S2

Present Next State Output 𝒛 Present Next State Output 𝒛

State 𝒙 = 0 𝒙 = 1 𝒙 = 0 𝒙 = 1 State 𝒙 = 0 𝒙 = 1 𝒙 = 0 𝒙 = 1
S0 S0 S1 0 0 00 00 01 0 0
S1 S0 S2 0 0 01 00 10 0 0
S2 S0 S2 0 1 10 00 10 0 1
 Derive Next State and Output Equations
𝐷1 𝐷0 𝑧
𝑥 𝑥 𝑥
Present Next State Output 𝒛 𝑄1 𝑄0 0 1 𝑄1 𝑄0 0 1 𝑄1 𝑄0 0 1
State 𝒙 = 0 𝒙 = 1 𝒙 = 0 𝒙 = 1 00 0 0 00 0 1 00 0 0
00 00 01 0 0 01 0 1 01 0 0 01 0 0
01 00 10 0 0 11 X X 11 X X 11 X X
10 00 10 0 1
10 0 1 10 0 0 10 0 1
11 XX XX X X
𝑄1 𝑥 + 𝑄0 𝑥 𝑄1′ 𝑄0′ 𝑥 𝑄1 𝑥

Present State = Flip-Flop Outputs 𝑄1 and 𝑄0 (state 11 is unused)

Next State = Flip-Flop Inputs 𝐷1 and 𝐷0
Flip-Flop Input equations: 𝐷1 = 𝑄1 𝑥 + 𝑄0 𝑥 and 𝐷0 = 𝑄1′ 𝑄0′ 𝑥
Output equation: 𝑧 = 𝑄1 𝑥
 Draw the Mealy Sequence Detector Circuit

𝐷1 = 𝑄1 𝑥 + 𝑄0 𝑥 𝐷0 = 𝑄1′ 𝑄0′ 𝑥 𝑧 = 𝑄1 𝑥
Output Logic

Next State
Next State
Logic
Logic
𝑄1 𝑄0
𝐷1 𝐷0

𝑄1′ 𝑄0′

Reset
Mealy versus Moore Sequence Detector
Mealy Sequence Detector Moore
Sequence
0/0 0
0/0 1/1 Detector
0/0 0

1/0 1/0
S0 1 S1
S0 S1 S2
0 0

In general, Moore state diagrams have 0 0 1

more states than corresponding Mealy.

The drawback of Mealy is that glitches S3 S2

1 1 0
can appear in the output if the input is
not synchronized with the clock.
1
 Verification
❖ Sequential circuits should be verified by showing that the
circuit produces the original state diagram
❖ Verification can be done manually, or with the help of a
simulation program
❖ All possible input combinations are applied at each state and
the state variables and outputs are observed
❖ A reset input is used to reset the circuit to its initial state
❖ Apply a sequence of inputs to test all the state-input
combinations, i.e., all transitions in the state diagram
❖ Observe the output and the next state that appears after each
clock edge in the timing diagram
 Input Test Sequence
❖ Required to verify the correct operation of a sequential circuit

❖ It should test each state transition of the state diagram

❖ Test sequences can be produced from the state diagram

❖ Consider the Mealy sequence detector, starting at S0 (reset),

we can use an input test sequence to verify all state transitions:
Input test sequence: reset then x = 0, 1, 0, 1, 1, 0, 1, 1, 1, 1

0/0
0/0 1/1
Reset input
0/0
forces initial
reset S0 1/0 S1 1/0 S2
state to be S0
 Verifying the Mealy Sequence Detector
0/0
0/0 1/1
0/0

reset S0 1/0 S1 1/0 S2

Input test sequence: reset then x = 0, 1, 0, 1, 1, 0, 1, 1, 1, 1

cc0 cc1 cc2 cc3 cc4 cc5 cc6 cc7 cc8 cc9 cc10
clock
reset
x 0 1 0 1 1 0 1 1 1 1
Q1 S0 S0 S1 S0 S1 S2 S0 S1 S2 S2
Q0 glitch

z 0 0 0 0 0 0 0 0 1 1
 Sequential Comparator
Problem Description:
❖ Design a sequential circuit that compares two numbers A and B
❖ Two Inputs: A and B
𝐴 Sequential 𝐺𝑇
A consists of n bits
𝐵 Comparator 𝐿𝑇
B consists of n bits
Bit streaming starting at bit 0 𝐶𝑙𝑜𝑐𝑘 𝑅𝑒𝑠𝑒𝑡

Compare A0 with B0, A1 with B1, etc. (Bit 0 is least significant bit)
❖ A reset signal resets the comparator to its initial state
Reset is required before starting a new comparison
❖ Two outputs: GT (Greater Than) and LT (Less Than)
 Designing the State Diagram
❖ Reset: start initially in state EQ Moore State Diagram
EQ indicates Equality (output is 00) 00, 11

Stay in EQ as long as AiBi = 00 or 11

EQ
❖ Go to LT if Ai < Bi (AiBi = 01) Reset
00
LT indicates Less Than (output is 01)
01 10
❖ Go to GT if Ai > Bi (AiBi = 10)
GT is Greater Than (output is 10) 01
LT GT
❖ Complete the state diagram
01 10
LT → GT and GT → LT 10

LT → LT and GT → GT 00, 11, 01 00, 11, 10

 State Assignment and State Table
Three States ➔ Two Flip-Flops
00, 11
D-type Flip-Flops will be used
State Assignment: EQ = 00, LT = 01, GT = 10 EQ
Reset
Output = Present State (Q1 and Q0) 00

Present Next State (D1 D0) 01 10

State AB AB AB AB
Q1 Q0 00 01 10 11 01
LT GT
0 0 0 0 0 1 1 0 0 0
01 10
0 1 0 1 0 1 1 0 0 1 10
1 0 1 0 0 1 1 0 1 0
00, 11, 01 00, 11, 10
1 1 X X X X X X X X
 Deriving the Next State Equations
Present Next State (D1 D0) State 11 is unused
State AB AB AB AB
Q1 Q0 00 01 10 11 When present state is 11,
0 0 0 0 0 1 1 0 0 0 don't cares are used to
0 1 0 1 0 1 1 0 0 1 fill the next state.
1 0 1 0 0 1 1 0 1 0
Output = Present state
1 1 X X X X X X X X
𝐴𝐵
𝐷1 𝐴𝐵
𝐷0
𝑄1 𝑄0 00 01 11 10 𝑄1 𝑄0 00 01 11 10
00 0 0 0 1 00 0 1 0 0
𝐷1 = 𝑄1 𝐴 + 𝑄1 𝐵′ + 𝐴𝐵′

01 0 0 0 1 01 1 1 1 0 𝐷1 = 𝑄1 (𝐴 + 𝐵′ ) + 𝐴𝐵′
11 X X X X 11 X X X X 𝐷0 = 𝑄0 𝐴′ + 𝑄0 𝐵 + 𝐴′ 𝐵
10 1 0 1 1 10 0 1 0 0 𝐷0 = 𝑄0 (𝐴′ + 𝐵) + 𝐴′ 𝐵
Sequential Comparator Circuit Diagram
𝐷1 = 𝑄1 (𝐴 + 𝐵′ ) + 𝐴𝐵′ 𝐷0 = 𝑄0 (𝐴′ + 𝐵) + 𝐴′ 𝐵

𝐴
𝐷1 𝑄1 𝐺𝑇

𝑄1′

𝐵 𝐷0 𝑄0 𝐿𝑇

𝐶𝑙𝑜𝑐𝑘 𝑄0′

𝑅𝑒𝑠𝑒𝑡
 Designing with Unused States
❖ A circuit with n flip-flops has 2n binary states
❖ However, the state diagram may have m states
❖ Therefore, the number of unused states = 2n – m
❖ Unused states do not appear in the state diagram
 Sometimes treated as don't cares when simplifying expressions in K-maps
❖ However, it is possible to enter an unused state!
 Caused by outside interference or a circuit malfunction
❖ Must specify the output and next state values for unused states
❖ A special (invalid) output can be used to indicate an unused state
❖ A return to a valid state must be possible without reset
 Next state for unused states should be specified (NOT don't cares!)
 Design of a Binary Counter
Problem Specification:

❖ Design a circuit that counts up from 0 to 7 then back to 0

000 → 001 → 010 → 011 → 100 → 101 → 110 → 111 → 000

When reaching 7, the counter goes back to 0 then goes up again

❖ There is no input to the circuit

❖ The counter is incremented each cycle

❖ The output of the circuit is the present state (count value)

❖ The circuit should be designed using D-type Flip-Flops

 Designing the State Diagram
❖ Eight states are needed to store the count values 0 to 7
❖ No input, state transition happens at the edge of each cycle

S0
S7 S1 Three Flip-Flops
are required for
the eight states
S6 S2
Each state is
assigned a unique
S5 S3
binary count value
S4
 State Table
Only two columns: Present State and Next State
State changes each cycle
Present State Next State
000 Q2 Q1 Q0 D2 D1 D0

111 001 0 0 0 0 0 1
0 0 1 0 1 0
0 1 0 0 1 1
110 010 0 1 1 1 0 0
1 0 0 1 0 1
1 0 1 1 1 0
101 011
1 1 0 1 1 1
100 1 1 1 0 0 0
 Deriving the Next State Equations
𝑄0 𝐷2 𝑄0 𝐷1 𝑄0 𝐷0
Present State Next State 𝑄2 𝑄1 0 1 𝑄2 𝑄1 0 1 𝑄2 𝑄1 0 1
Q2 Q1 Q0 D2 D1 D0 00 0 0 00 0 1 00 1 0

0 0 0 0 0 1 01 0 1 01 1 0 01 1 0

0 0 1 0 1 0 11 1 0 11 1 0 11 1 0

0 1 0 0 1 1 10 1 1 10 0 1 10 1 0
0 1 1 1 0 0 𝐷2 = 𝑄2 𝑄1′ + 𝑄2 𝑄0′ + 𝑄2′ 𝑄1 𝑄0
1 0 0 1 0 1 𝐷2 = 𝑄2 (𝑄1′ + 𝑄0′ ) + 𝑄2′ 𝑄1 𝑄0
1 0 1 1 1 0
𝐷2 = 𝑄2 𝑄1 𝑄0 ′ + 𝑄2′ 𝑄1 𝑄0 = 𝑄2 ⨁ (𝑄1 𝑄0 )
1 1 0 1 1 1
𝐷1 = 𝑄1 𝑄0′ + 𝑄1′ 𝑄0 = 𝑄1 ⨁ 𝑄0
1 1 1 0 0 0
𝐷0 = 𝑄0′
 3-Bit Counter Circuit Diagram

𝐷2 = 𝑄2 ⨁ (𝑄1 𝑄0 ) 𝐷2 𝑄2 𝑄2

Output = 3-bit Count Value

𝑄2′

𝐷1 = 𝑄1 ⨁ 𝑄0 𝐷1 𝑄1 𝑄1

𝑄1′

𝐷0 = 𝑄0′ 𝐷0 𝑄0 𝑄0

𝐶𝑙𝑜𝑐𝑘 𝑄0′
 Up/Down Counter with Enable
Problem Specification:

❖ Design a 2-bit Up / Down counter

❖ Two inputs: E (Enable) and U (Up)

If E = 0 then counter remains in the same state (regardless of U)

If EU = 11 then count up from 0 to 3, then back to 0

If EU = 10 then count down from 3 down to 0, then back to 3

❖ The output of the counter is the present state (count value)

❖ The circuit should be designed using T Flip-Flops

❖ A reset signal resets the counter to its initial state

 Designing the State Diagram
❖ Four states are required E=0 E=0
EU = 10
to store the count 0 to 3

❖ Count up if EU = 11 Reset
S0 EU = 11
S1

❖ Count down if EU = 10

EU = 11

EU = 11
EU = 10

EU = 10
❖ Disable counter if E = 0

Transition to same state if

EU = 00 or 01 EU = 11
S3 S2
❖ Asynchronous reset to
EU = 10
start initially at state S0 E=0 E=0
 State Assignment and State Table
❖ Four States ➔ Two State variables (2 Flip-Flops)

❖ State Assignment: S0 = 00, S1 = 01, S2 = 10, and S3 = 11

E=0 E=0
EU = 10

Reset 00 EU = 11
01 Present Next State
State EU EU EU EU
Q1 Q0
EU = 11

EU = 11

00 01 10 11
EU = 10

EU = 10

0 0 0 0 0 0 1 1 0 1
0 1 0 1 0 1 0 0 1 0
EU = 11
11 10 1 0 1 0 1 0 0 1 1 1
EU = 10 1 1 1 1 1 1 1 0 0 0
E=0 E=0
 Excitation Table for Flip-Flops
❖ Excitation Table:

Lists the required input for next state transition

❖ For D Flip-Flop: Input 𝐷 = Next State 𝑄(𝑡 + 1)

❖ For T Flip-Flop: Input 𝑇 = 𝑄 𝑡 ⊕ 𝑄 𝑡 + 1

❖ Excitation tables are used to find the Flip-Flop input equations

Excitation Tables for the D and T Flip-Flops

𝑸(𝒕) 𝑸(𝒕 + 𝟏) 𝑫 𝑸(𝒕) 𝑸(𝒕 + 𝟏) 𝑻
0 0 0 0 0 0
0 1 1 0 1 1
1 0 0 1 0 1
1 1 1 1 1 0
 Deriving the T-Flip-Flop Input Equations
Present Next State at (t+1) Present Flip-Flop Inputs T1 T0
State EU EU EU EU State EU EU EU EU
Q1 Q0 00 01 10 11 Q1 Q0 00 01 10 11
0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1
0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 1
1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 0 1
1 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1

𝐸𝑈 1𝑇 𝐸𝑈
𝑇
0
𝑄1 𝑄0 00 01 11 10 𝑄1 𝑄0 00 01 11 10
00 0 0 0 1 00 0 0 1 1 𝑇1 = 𝑄0 𝐸𝑈 + 𝑄0′ 𝐸𝑈 ′
01 0 0 1 0 01 0 0 1 1
𝑇1 = 𝐸(𝑄0 ⨁ 𝑈)′
11 0 0 1 0 11 0 0 1 1
𝑇0 = 𝐸
10 0 0 0 1 10 0 0 1 1
2-bit Up/Down Counter Circuit Diagram

𝑈
𝑇1 𝑄1 𝑄1

2-bit Count Value

𝑇1 = 𝐸(𝑄0 ⨁ 𝑈)′ 𝑄1′

𝑇0 = 𝐸

𝐸 𝑇0 𝑄0 𝑄0

𝐶𝑙𝑜𝑐𝑘 𝑄0′

𝑅𝑒𝑠𝑒𝑡
❖ Slides are taken from:
Digital Logic Design

Dr. Muhamed Mudawar

King Fahd University of Petroleum and Minerals