De Unit4 Notes

DIGITAL ELECTRONICS
GAYATHRI DEVI B
Department of Electrical & Electronics Engineering

DIGITAL ELECTRONICS
Synchronous Sequential Networks
GAYATHRI DEVI B
DIGITAL ELECTRONICS
Basic structure of Synchronous Sequential Networks
❖ Sequential Circuits are those which have the notion of

an internal state.
❖ This notion of Internal State is necessary because in

sequential circuits, the output of the circuit is function of
both the present input as well as the past inputs.
❖ The Internal State of a sequential circuit is nothing but the

reflection of the past inputs to the circuit.
❖ Now the Internal State of a Sequential Circuit is represented

by a number of State Variables.
DIGITAL ELECTRONICS
o/p is a function of
Mealy the present state as
well as the i/p
Analysis of synchronous
sequential network
Moore only the present
state
DIGITAL ELECTRONICS
❖ Each state variable can be in 1 of 2 possible states.
❖ This is because State Variables are physically implemented

with the help of Flip-Flops, and each Flip-Flop can only
represent 2 possible states.
❖ Therefore, if we have ‘N’ Flip-Flops, we can represent a

maximum of 2N states.
DIGITAL ELECTRONICS
❖ A general sequential circuit network has memory section and

combination circuits at the memory inputs and outputs.
❖ Assume the followings structure of a general sequential circuit.
❖ The circuit memory section consists of the m of flip flops.

These have a set Q with the m present state outputs Q0 , Q1 ...
and Qm − 1 .
❖ There is a set X of i inputs X0 , X1 , ... Xi . These are applied to a

combinational circuit, the j outputs of which are the inputs to
the memory section.
DIGITAL ELECTRONICS
❖ The present state of Q changes on the clock transition(s) to

next state Q′.
❖ The transition is by clock 1 or 0 or ↑ or ↓
❖ Further, a set Y with outputs Y0 , Y1 , Yj is obtained from the

network as per Q (or Q and X) using a combinational circuit at
the output stages.
DIGITAL ELECTRONICS
DIGITAL ELECTRONICS
Classification of sequential circuit as moore and mealy state

machine circuits:
❖ Classification of a Sequential Circuit as Moore Model Circuit:
➢ A general clocked sequential circuit in which Y final stage

combinational circuit output is as per Q only is called a circuit
implementing a Moore machine and is Moore model of the
sequential circuit.
DIGITAL ELECTRONICS
❖ Classification of a Sequential Circuit as Mealy Model Circuit:
➢ A general sequential circuit in which the final stage outputs Y as

per Q and X is called a circuit implementing a Mealy machine
and is Mealy model of the sequential circuit.
➢ Mealy Model Q′ = FQ (X, Q) (Next state outputs Q′ are the

function of past state Q and present inputs X at the clocking
instance) and Y = FY (Q, X) (Y is a function of present state
outputs Q before the clocking instance).
THANK YOU
Gayathri Devi B
gayathridb@pes.edu
+91 80 6666 3333 Extn 273
DIGITAL ELECTRONICS
GAYATHRI DEVI B

DIGITAL ELECTRONICS
GAYATHRI DEVI B
DIGITAL ELECTRONICS
Next State Tables/Characteristic Equations of F/Fs
❖Characteristic equation gives the next state equation of a given

flip-flop with the given inputs and present state.
❖To derive the characteristic equation of a FF, write the function

table of the given FF and construct K-Map with the given inputs
and present state determine the equation of the next state.
DIGITAL ELECTRONICS
1. SR Flip Flop Characteristic Equation:

The Next State table is given by;
CLK S R Qn (present Q n+1 (next

state) state)
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 FORBIDDEN
1 1 1 0 FORBIDDEN
DIGITAL ELECTRONICS
K-Map to determine Q n+1
The Next State Equation is Q n+1 = S+R’Q

DIGITAL ELECTRONICS
2. JK Flip-Flop Characteristic Equation:

CLK J K Qn Q n+1
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
DIGITAL ELECTRONICS
The Next State Equation is Q n+1 = JQ’+K’Q

DIGITAL ELECTRONICS
3. Data Flip-Flop Characteristic Equation:

CLK D Qn Q n+1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
DIGITAL ELECTRONICS

D Q Q’ Q
D’ 0 0
D 1 1
D
The Next State Equation is Q n+1 = D
DIGITAL ELECTRONICS
4. Toggle Flip-Flop Characteristic Equation:
CLK T Qn Q n+1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
DIGITAL ELECTRONICS
The Next State Equation is Q n+1 = TQ’+T’Q= T EXOR Q

THANK YOU
Gayathri Devi B
gayathridb@pes.edu
+91 80 6666 3333 Extn 273
DIGITAL ELECTRONICS
GAYATHRI DEVI B

DIGITAL ELECTRONICS
GAYATHRI DEVI B
DIGITAL ELECTRONICS
Excitation Table, Transition Table, State Table, State Diagram
Excitation Table:
❖ An excitation table is a tabular representation of X and Q at
the FFs and of Y as per Fo for the combination circuit at the
output stages.
❖ It gives present states and the inputs given at the memory

section. It also gives the outputs that follow the excitations at
the memory section.
❖ Number of rows in each column equals 2m where m is the

number of flip flops because each flip flop has one Q output
and m flip-flops can have 2m different combinations of the
states at the Qs.
DIGITAL ELECTRONICS
❖ For example, if (Q1, Q2) are the Qs of two FFs, then (Q1, Q2)
= (0, 0), (0, 1), (1, 0) and (1, 1) are the four combinations
possible for the four different states of the memory-section
present outputs.
❖ First column of excitation table gives a present state (Q1, Q2)

in its each row.
❖ The number of columns for the excitation inputs Q equals the

number of possible combinations of external inputs in the set
X.
❖ It equals 2i if there are i distinct literal to represent the inputs
when there are i inputs X1, X2, ... Xi.
DIGITAL ELECTRONICS
❖ For example, if (X1, X2) are the external input to the memory
section then (X1, X2) = (0, 0), (0, 1), (1, 0) and (1, 1) are the
four combinations possible for the four different states of the
memory section present outputs.
❖ For each set of inputs, there is a set of excitation inputs to the

memory section, for example, corresponding to each set of
external inputs, there will be four sets of inputs to (D1, D2) in
case of two D FFs at the memory section.
DIGITAL ELECTRONICS
❖ Mealy Model :The number of columns for the output Y also

equals the number of possible 2i combinations of external
inputs in the set X. Suppose output stage has two outputs, Y1
and Y2. Then there will be four columns for the case of four
sets of external inputs and each column having entries for
pair of outputs of (Y1, Y2).
❖ Moore Model :The number of column = 1 for the output Y as

in Moore model Y depends on Qs only. The column entries
for values of (Y1, Y2) as per the combinational circuit
between the memory section output Qs and Ys.
DIGITAL ELECTRONICS
Excitation Table,Transition Table,State Table,State Diagram
Transition Table:
❖ A transition table is a tabular representation of FQ and FO. It

shows how the sequential circuit FFs will respond to all the
present inputs Xs and Qs and will generate Ys from the Qs.
❖ Number of rows in each column equals 2m for the m-FFs. First

column of transition table gives a present state (Q1, Q2) in its
each row for the case of m = 2.
❖ This is because there are four combinations possible for the

four different states (of Qs) of the memory section present
outputs.
DIGITAL ELECTRONICS
❖ The number of columns for the next state Q′ equals the

X. It equals 2i.
❖ For each set of inputs, there is a set of memory section

outputs after the transition at the memory section, for
example, corresponding to each set of external inputs, there
will be a set of next state outputs (Q1′, Q2′) in case of two FFs
at the memory section.
DIGITAL ELECTRONICS
❖ Mealy Model The number of columns for the output Y also
inputs in the set X.
❖ Moore Model The number of column = 1 for the output Y as in

Moore model Y depends on Qs only.
DIGITAL ELECTRONICS
State Table
❖ A state table is a tabular representation of the present state

in column 1 and next state after the transition in a set of
succeeding columns.
❖ The outputs are shown in next set of columns. Number of

rows in each column equals 2m for a memory section of m
flip-flops.
DIGITAL ELECTRONICS
❖ For example, if (Q1, Q2) are the Qs of two FFs, then let us
assume the followings: S(Q1, Q2)= S (0, 0) = S0 for (0, 0)
values of (Q1, Q2), S(Q1, Q2)= S (0, 1) = S1 for (0, 1) values of
(Q1, Q2), S(Q1, Q2)= S (1, 0) = S2 for (1, 0) values of (Q1, Q2),
and S(Q1, Q2)= S (1, 1) = S3 for (1, 1) values of (Q1, Q2).
❖ A state in a row on first column is written as either S0, S1, S2

or S3 for the row 1, row 2, row 3 or row 4, respectively.
❖ These are as per four possible values of (Q1, Q2) in case of

two FFs used at the memory section.
DIGITAL ELECTRONICS
❖ The number of columns for the next state S equals the

X.
❖ It equals 2i. For each set of inputs, there is a set of memory

section states resulting after the transition at the memory
section, for example, corresponding to each set of external
inputs, there will be four sets of next states.
❖ A state in a row is either S0 or S1, S2 or S3 as per the post

transition values of next state (Q1′, Q2′) in case of two FFs
used at the memory section.
DIGITAL ELECTRONICS
❖ Moore Model The number of columns for the output Y also

inputs in the set X.
❖ Moore Model The number of column = 1 for the output Y as

in Moore model Y depends on Qs only.
DIGITAL ELECTRONICS
State Diagram:
❖ A state diagram is diagrammatic representation of the state

table. A set of present Q0, Q1, ... is denoted by a state.
❖ There are z (= 2m) maximum possible states S0, S1, ..., Sz−1
in a sequential circuit with m-FFs.
1. The number of nodes = number of rows in the state table.

2. 2. For two flip-flops, there are four states S0, S1, S2 and S3.
So four circles are drawn for the four nodes of a graph.
3. 3. A directed arc from the present state node to the next
state node shows a transition.
DIGITAL ELECTRONICS
4. A small diameter circular directed arc marks a transition in

which the state remains unchanged.
5. The number of directed arcs equals the number of transitions

in which the state changes.
6. The number of directed circular arcs equals the number of

transitions in which the state does not change.
THANK YOU
Gayathri Devi B
gayathridb@pes.edu
+91 80 6666 3333 Extn 273
DIGITAL ELECTRONICS
GAYATHRI DEVI B

DIGITAL ELECTRONICS
GAYATHRI DEVI B
DIGITAL ELECTRONICS
Analysis of Synchronous Sequential Networks
ANALYSIS PROCEDURE :
An analysis is important for implementing a sequential circuit.

Analysis also provides a tabular description of the circuit. The
methods for analysis are as follows:
1. Draw a logic circuit diagram.
2. 2. Perform state variables assignments and excitation

(means FF inputs) variables assignments.
3. Find the expressions for the excitations from the flip flop
characteristics equations as per the excitations and make an
excitation table. In other words, find Q′ = FQ (X, Q) and Y
DIGITAL ELECTRONICS
4. Make a transition table from the expressions for Y = FO (X, Q)

in case of Mealy model and Y = FO (Q) in case of Moore model.
5. Perform state minimization and make minimal state table.
6. Draw the state diagram.

DIGITAL ELECTRONICS
Example 1:Analyse the sequential circuit shown. Identify the type

and Justify.
DIGITAL ELECTRONICS
Step 1: Logic circuit drawing: Logic circuit drawing is as per

designed circuit.
Step 2: Performing state variables assignments and excitation (FF

triggering) variables assignments: State variables in the circuit are
Q2, Q2, Q1 and Q1 at the lower and upper FFs, respectively.
Excitation variables are D1 and D2.
Step 3: Finding the expressions for the excitations from the flip
flop characteristics equations as per the excitations and make an
excitation table: Therefore, the excitation expressions for next
state Qs are as follows:
DIGITAL ELECTRONICS
❖ Now, the steps for finding the transition equation are the
followings using the input variables for the excitations of the
FFs.
❖ Two expressions for the excitation inputs for the

combinational circuit are as follows:
DIGITAL ELECTRONICS
❖ The output equation for the Y is as follows:
❖ Table below gives the excitation table for present states,

excitation inputs and the present output Y
DIGITAL ELECTRONICS
The below Table gives the transition table made by using the next
state Equations. It is same as Excitation Table because a D FFs
reflects the D at Q.
DIGITAL ELECTRONICS
Step 5: Perform state minimization and make minimal state table

as shown below
DIGITAL ELECTRONICS
Step 6: Draw the state diagram

From the state table the state diagram is drawn. The directed
arc represents a transition. It is labelled with present input and
the output after the transition. This is clarified in the followings
for each state at the rows of the table.
THANK YOU
Gayathri Devi B
gayathridb@pes.edu
+91 80 6666 3333 Extn 273
DIGITAL ELECTRONICS
GAYATHRI DEVI B

DIGITAL ELECTRONICS
GAYATHRI DEVI B
DIGITAL ELECTRONICS

and Justify.
DIGITAL ELECTRONICS
Step 1: Logic circuit drawing
Step 2: Performing state variables assignments and excitation

(FF triggering) variables assignments: State variables in the
circuit are Q2, Q2, Q1 and Q1 at the lower and upper FFs,
respectively. Excitation variables are D, J and K.
excitation table: Therefore the excitation expressions are as
follows:
Q1′ = D
DIGITAL ELECTRONICS
❖ Now, the steps for finding the transition equations are the
FFs.
❖ Two expressions for the combinational circuit for the excitation

inputs are as follows:
DIGITAL ELECTRONICS
Therefore, the next state after the state transition equations are as
per the excitation expression and are given by ,
The output equation for the Y is as follows:
Since combinational circuit inputs at the memory section outputs

Y is such that the Y depend on X, we have a circuit, which is a
Mealy model sequential circuit.
DIGITAL ELECTRONICS
Excitation table for the for the sequential circuit is as follows:

DIGITAL ELECTRONICS
Transition table for the sequential circuit is as follows:

DIGITAL ELECTRONICS
State table for the sequential circuit is as follows:

DIGITAL ELECTRONICS
Step 6: Draw the state diagram.
From the state table the state diagram is drawn. Since the
circuit is a Mealy model sequential circuit, the nodes S0, S1, S 2
and S 3 are labeled at the center of a circle. The directed arc
represents a transition. It is labeled with present input and the
output after the transition. It is clarified in the following for a
state present at each row.
Consider row 1 of state table in Table
1. Transition is from S0 to S0 itself when input X = 0 and output
is Y = 0. Hence a directed circular arc is shown for the node S0 .
It is labeled 0/0. 2. Transition is from S0 to S2 when input X = 1
and output is Y = 0. Hence the directed arc is from S0 to S2 and
is also labeled 1/0.
DIGITAL ELECTRONICS
Consider row 2 of state table
3. Transition is from S1to S1 itself when input X = 0 and output is

Y = 1. Hence the directed circular arc is shown at the node S1 and
is labeled 0/1. 4. Transition is from S1 to S2 when input X = 1 and
output is Y = 0. Hence the directed arc is from S1 to S2 and is also
labeled 1/0.

5. Transition is from S2 to S1 when input X = 0 and output is Y =
1. Hence a directed arc i+s shown from the node S2 to S1. It is
labeled 0/0. 6. Transition is from S2 to S3 when input X = 1 and
labeled 1/1.
DIGITAL ELECTRONICS- UE19EE203

is Y = 1. Hence a directed arc is shown from the node S3 to node
S0. It is labeled 0/1. 8. Transition is from S3 to S0 when input X =
1 and output is Y = 1. Hence the directed arc is from S3 to S0
and is also labeled 1/1.
THANK YOU
Gayathri Devi B
gayathridb@pes.edu
+91 80 6666 3333 Extn 273
DIGITAL ELECTRONICS
GAYATHRI DEVI B

DIGITAL ELECTRONICS
GAYATHRI DEVI B
DIGITAL ELECTRONICS

and Justify.
DIGITAL ELECTRONICS
Step 1: Logic circuit drawing
Step 2: Performing state variables assignments and excitation

(FF triggering) variables assignments: State variables in the
circuit are Q2, Q2, Q1 and Q1 at the lower and upper FFs,
respectively. Excitation variables are D, J and K.
excitation table: Therefore the excitation expressions are as
follows:
Q1′ = D
DIGITAL ELECTRONICS
❖ Now, the steps for finding the transition equations are the
FFs.
❖ Two expressions for the combinational circuit for the excitation

inputs are as follows:
DIGITAL ELECTRONICS
Therefore, the next state after the state transition equations are as
per the excitation expression and are given by ,
The output equation for the Y is as follows:
Since combinational circuit inputs at the memory section outputs

Y is such that the Y depend on X, we have a circuit, which is a
Mealy model sequential circuit.
DIGITAL ELECTRONICS
Excitation table for the for the sequential circuit is as follows:

DIGITAL ELECTRONICS
Transition table for the sequential circuit is as follows:

DIGITAL ELECTRONICS
State table for the sequential circuit is as follows:

DIGITAL ELECTRONICS
Step 6: Draw the state diagram.
From the state table the state diagram is drawn. Since the
circuit is a Mealy model sequential circuit, the nodes S0, S1, S 2
and S 3 are labeled at the center of a circle. The directed arc
represents a transition. It is labeled with present input and the
output after the transition. It is clarified in the following for a
state present at each row.
Consider row 1 of state table in Table
is Y = 0. Hence a directed circular arc is shown for the node S0 .
It is labeled 0/0. 2. Transition is from S0 to S2 when input X = 1
and output is Y = 0. Hence the directed arc is from S0 to S2 and
is also labeled 1/0.
DIGITAL ELECTRONICS
3. Transition is from S1to S1 itself when input X = 0 and output is

Y = 1. Hence the directed circular arc is shown at the node S1 and
is labeled 0/1. 4. Transition is from S1 to S2 when input X = 1 and
labeled 1/0.

5. Transition is from S2 to S1 when input X = 0 and output is Y =
1. Hence a directed arc i+s shown from the node S2 to S1. It is
labeled 0/0. 6. Transition is from S2 to S3 when input X = 1 and
labeled 1/1.

is Y = 1. Hence a directed arc is shown from the node S3 to node
S0. It is labeled 0/1. 8. Transition is from S3 to S0 when input X =
1 and output is Y = 1. Hence the directed arc is from S3 to S0
and is also labeled 1/1.
THANK YOU
Gayathri Devi B
gayathridb@pes.edu
+91 80 6666 3333 Extn 273
DIGITAL ELECTRONICS
GAYATHRI DEVI B

DIGITAL ELECTRONICS
GAYATHRI DEVI B
DIGITAL ELECTRONICS
Modeling of Synchronous Sequential Networks-Mealy as
Serial Adder
❖ In the serial adders we know that only one bit addition takes
place at a time and hence it takes processing time.
❖ For a mealy machine, the output should be during the

transition between the state.
❖ The output is the sum and the carry is in the memory. Carry
can only be of two forms, either 1 or 0 so accordingly we
have two states, S0 where carry is 0 and S1 where carry is 1.
DIGITAL ELECTRONICS
Mealy as Serial Adder
❖Since, we perform only 1 bit addition at a time and have two

inputs so we get 4 possible combinations 00, 01, 10 and 11.
Step 1: Draw the state diagram,

inputs- x= 0 0 1 1
y= 0 1 0 1
DIGITAL ELECTRONICS
Step 2: Write the state table.

Since we have two states, one flip flop is enough to
implement the sequential circuit. Let us take the D-flip flop
because we just want to store the previous carry to give as input
for the next stages. X Y P.S N.S Output D f/f
A A+ Sum
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 0 1 0
0 1 1 1 0 1
1 0 0 0 1 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 1
DIGITAL ELECTRONICS
Step 3: Write equation for sum and equation for input of D-f/f.
We can obtain this using the 8 cells k-map.
K-map for sum:
We know that, this is a combination of XOR gate, hence sum=

x⊕y⊕A
DIGITAL ELECTRONICS
K-map for D-f/f:
From the k-map, we get DA = xA+yA+xy

DIGITAL ELECTRONICS
Step 4: Draw the circuit diagram.

Now, that we have got the two equations,
sum= x ⊕ y ⊕ A
DA = xA+yA+xy
We can draw the circuit diagram:
THANK YOU
Gayathri Devi B
gayathridb@pes.edu
+91 80 6666 3333 Extn 273
DIGITAL ELECTRONICS
GAYATHRI DEVI B

DIGITAL ELECTRONICS
GAYATHRI DEVI B
DIGITAL ELECTRONICS
MOORE as serial adder
Mealy the present state as
well as the i/p
Analysis of synchronous
sequential network
Moore only the present
state
1 f/f to generate sum, during shift of

Serial every carry there is a unit
delay(approx. 10 ns)
Adder 4 f/fs to generate 4-bit addition
simultaneously, carry look ahead
Parallel generator generates o/p and
intermediate carries. Hence, there is
no delay
DIGITAL ELECTRONICS
Unit delay : Since the output doesn’t depend upon the input, the
correct sum bit from the adder is not established until the next
clock period, i.e., until the next state is reached. This in effect
imposes unit delay on the output
• In a Moore sequential network, the first output is ignored and
subsequent outputs are taken as the output sequence.
• Each state is associated with both output as well as information
regarding how the past history of inputs was responsible for that
output. Hence we need 4 states as the sum bit 0 or 1 can be
generated with or without carry from the previous order
addition.
• There are 4 possible combinations of inputs x and y in every
state, hence there are 16 transitions overall.
DIGITAL ELECTRONICS
1
sum
0
x y Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 1 1
DIGITAL ELECTRONICS
For state S0, previous carry pc =0, if sum
00
x+y+pc is 0, it stays in S0, else moves to
S0 01 S1 other states.
00 10 01
1. x=y=0, sum=carry=0, stays in the same
11 state.
2. x=0, y=1, sum=1, carry=0, goes to S1
S2 S3
10 11 3. x=1, y=0, sum=1, carry=0, goes to S1
4. x=y=1, sum=0, carry=1, goes to S
DIGITAL ELECTRONICS
For state S1, previous carry pc =0, if sum x+y+pc of is 1, it stays in

S1, else moves to other states.
1. x=y=0, sum=0, carry=0, goes to S0

2. x=0, y=1, sum=1, carry=0, stays in S1
3. x=1, y=0, sum=1, carry=0, stays in S1
4. x=y=1, sum=0, carry=1, goes to S2
DIGITAL ELECTRONICS
DIGITAL ELECTRONICS
DIGITAL ELECTRONICS
MEALY & MOORE as serial adders
• There are 4 states, these are

implemented by 2 D-flipflops DA
and DB
• Sum/output depends on present

state. For 00 and 10,i.e., S0 and S2,
output is 0 and for 01 and 11,i.e.,
S1 and S3 sum is 1.
DIGITAL ELECTRONICS
DIGITAL ELECTRONICS
Summary
• Every Mealy network has a corresponding Moore network

under the assumption that the output of initial state of
Moore network is ignored.
• Moore network requires 4 states as opposed to 2 of Mealy
since the outputs are associated with the present states and
not the input.
• Since output is not a function of input, there is a unit delay.
DIGITAL ELECTRONICS
DIGITAL ELECTRONICS
THANK YOU
Gayathri Devi B
gayathridb@pes.edu
+91 80 6666 3333 Extn 273
Synchronous Sequential Circuit Review
1
Steps
2
Derivation of JK Excitation Table
JK Excitation
JK Characteristic Table
Table
J K Q Q+
Q Q+ J K
0 0 0 0
0 0 1 1 0 0 0 X
0 1 0 0 0 1 1 X
0 1 1 0 1 0 X 1
1 0 0 1 1 1 X 0
1 0 1 1
1 1 0 1
1 1 1 0
4/3/2009 Page 3
Flip-Flop Excitation Tables
Q Q+ J K S R T D
0 0 0 X 0 X 0 0
0 1 1 X 1 0 1 1
1 0 X 1 0 1 1 0
1 1 X 0 X 0 0 1
You can use any FF type for your implementation
FF types can be mixed;

you could use a JK FF for Q1 and a T FF for Q0
4/3/2009 Page 4
Sequence recognizer (Mealy)
• A sequence recognizer is a circuit that processes an input sequence of bits
• The recognizer circuit has only one input, X

– One bit of input is supplied on every clock cycle
• There is one output, Z, which is 1 when the desired pattern is found
• Our example will detect the bit pattern ―1001‖:
Inputs: 1 1 1 0 01 1 0 1 00 1 00 1 1 0 …
Outputs: 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 …
• A sequential circuit is able to ―remember‖ the inputs from previous clock

cycles, in order to determine whether the specific sequence appeared
5
Step 1: Making a state table
• The first we derive a state table based on the problem statement. The
table should show the present states, inputs, next states and outputs
– Sometimes it is easier to first find a state diagram and then
convert that to a table
This is often the most challenging step.
• Once you have the state table,
the rest of the design procedure is the same for all sequential circuits
6
A basic Mealy state diagram
• What state do we need for the sequence recognizer?
– The circuit must ―remember‖ inputs from previous clock cycles

– For example, if the previous three inputs were 100 and the current
input is 1, then the output should be 1
– The circuit must remember occurrences of parts of the desired
pattern—in this case, 1, 10, and 100
• Starting state diagram:
1/0 0/0 0/0

A B C D
State Meaning
A Arbitrary starting state; Circuit sees a ―1‖, it progresses towards B.
Output is ―0‖
B Circuit sees a ―0‖, it progresses towards C. Output is ―0‖
C Circuit sees a ―0‖, it progresses towards D. Output is ―0‖
D See next page
7
Overlapping occurrences of the pattern
• What happens if we’re in state D (the last three inputs were 100), and
the current input is 1?
– The output should be a 1, because we’ve found the desired pattern

– This last 1 could also be the start of another occurrence of the pattern!
For example, 1001001 contains two occurrences of 1001
– To detect overlapping occurrences of the pattern, the next state
should be B.
1/0 0/0 0/0
A B C D
1/1
State Meaning
A None of the desired pattern (1001) has been input yet.
B We’ve already seen the first bit (1) of the desired pattern.
C We’ve already seen the first two bits (10) of the desired pattern.
D We’ve already seen the first three bits (100) of the desired pattern.
8
Filling in the other arrows
• Two outgoing arrows for each node, to account for the possibilities of
X=0 and X=1
• The remaining arrows we need are shown in blue. They also allow for
the correct detection of overlapping occurrences of 1001.
0/0
1/0
1/0 0/0 0/0

A B C D
1/0
0/0 1/1
State Meaning
A None of the desired pattern (1001) has been input yet.
B We’ve already seen the first bit (1) of the desired pattern.
C We’ve already seen the first two bits (10) of the desired pattern.
D We’ve already seen the first three bits (100) of the desired pattern.
9
Mealy state diagram & table
0/0
1/0
1/0 0/0 0/0

A B C D
1/0
0/0 1/1
Present Next
State Input State Output
A 0 A 0
A 1 B 0
B 0 C 0
B 1 B 0
C 0 D 0
C 1 B 0
D 0 A 0
D 1 B 1
10
Step 2: Assigning binary codes to states
• We have four states ABCD, so we need at least two flip-flops Q1Q0
• The easiest thing to do is represent state A with Q1Q0 = 00, B with 01, C
with 10, and D with 11
• The state assignment can have a big impact on circuit complexity, but we
won’t worry about that too much in this class
Present Next
Present Next State Input State Output
State Input State Output Q1 Q0 X Q 1 Q0 Z
A 0 A 0 0 0 0 0 0 0
A 1 B 0 0 0 1 0 1 0
B 0 C 0 0 1 0 1 0 0
B 1 B 0 0 1 1 0 1 0
C 0 D 0 1 0 0 1 1 0
C 1 B 0 1 0 1 0 1 0
D 0 A 0 1 1 0 0 0 0
D 1 B 1 1 1 1 0 1 1
11
Step 3: Finding flip-flop input values
• Next we have to figure out how to actually make the flip-flops change
from their present state into the desired next state
• This depends on what kind of flip-flops you use!
• We’ll use two JKs. For each flip-flip Qi, look at its present and next states,
and determine what the inputs Ji and Ki should be in order to make that
state change.
Present Next
State Input State Flip flop inputs Output
Q1 Q0 X Q1 Q0 J1 K1 J0 K0 Z
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 1 0 0
0 1 1 0 1 0
1 0 0 1 1 0
1 0 1 0 1 0
1 1 0 0 0 0
1 1 1 0 1 1
12
Back to the example
Q(t) Q(t+1) J K
• Use the JK excitation table on the right to
0 0 0 x
find the correct values for each flip-flop’s
0 1 1 x
inputs, based on its present and next states 1 0 x 1
1 1 x 0
Present Next
Q1 Q0 X Q1 Q0 J1 K1 J0 K0 Z
0 0 0 0 0 0 x 0 x 0
0 0 1 0 1 0 x 1 x 0
0 1 0 1 0 1 x x 1 0
0 1 1 0 1 0 x x 0 0
1 0 0 1 1 x 0 1 x 0
1 0 1 0 1 x 1 1 x 0
1 1 0 0 0 x 1 x 1 0
1 1 1 0 1 x 1 x 0 1
13
Step 4: Find equations for the FF inputs and output
• Now you can make K-maps and find equations for each of the four flip-
flop inputs, as well as for the output Z
• These equations are in terms of the present state and the inputs
• The advantage of using JK flip-flops is that there are many don’t care
conditions, which can result in simpler MSP equations
Present Next
Q1 Q0 X Q1 Q0 J1 K1 J0 K0 Z
0 0 0 0 0 0 x 0 x 0
0 0 1 0 1 0 x 1 x 0
0 1 0 1 0 1 x x 1 0
0 1 1 0 1 0 x x 0 0
1 0 0 1 1 x 0 1 x 0
1 0 1 0 1 x 1 1 x 0
1 1 0 0 0 x 1 x 1 0
1 1 1 0 1 x 1 x 0 1
14
FF input equations
Present Next
Q1 Q0 X Q1 Q0 J1 K1 J0 K0 Z
0 0 0 0 0 0 x 0 x 0
0 0 1 0 1 0 x 1 x 0
0 1 0 1 0 1 x x 1 0
0 1 1 0 1 0 x x 0 0
1 0 0 1 1 x 0 1 x 0
1 0 1 0 1 x 1 1 x 0
1 1 0 0 0 x 1 x 1 0
1 1 1 0 1 x 1 x 0 1
J1 Q1 Q0 K1 Q1 Q0
00 01 11 10 00 01 11 10
0 0 1 x x 0 x x 1 0
X X
1 0 0 x x 1 x x 1 1
J1 = X’ Q0 K1 = X + Q0
15
FF input equations
Present Next
Q1 Q0 X Q1 Q0 J1 K1 J0 K0 Z
0 0 0 0 0 0 x 0 x 0
0 0 1 0 1 0 x 1 x 0
0 1 0 1 0 1 x x 1 0
0 1 1 0 1 0 x x 0 0
1 0 0 1 1 x 0 1 x 0
1 0 1 0 1 x 1 1 x 0
1 1 0 0 0 x 1 x 1 0
1 1 1 0 1 x 1 x 0 1
J0 Q1 Q0 K0 Q1 Q0
00 01 11 10 00 01 11 10
0 0 x x 1 0 x 1 1 x
X X
1 1 x x 1 1 x 0 0 x
J0 = X + Q1 K0 = X’
16
Output equation
Present Next
Q1 Q0 X Q1 Q0 J1 K1 J0 K0 Z
0 0 0 0 0 0 x 0 x 0
0 0 1 0 1 0 x 1 x 0
0 1 0 1 0 1 x x 1 0
0 1 1 0 1 0 x x 0 0
1 0 0 1 1 x 0 1 x 0
1 0 1 0 1 x 1 1 x 0
1 1 0 0 0 x 1 x 1 0
1 1 1 0 1 x 1 x 0 1
Z Q1 Q0
00 01 11 10
0
X
1 1
Z = X Q1 Q0
17
Step 5: The circuit
• Lastly, we use these simplified equations to build the completed circuit
J1 = X’ Q0
K1 = X + Q0
J0 = X + Q1
K0 = X’
Z = Q1Q0X
18
Building the same circuit with D flip-flops
• What if you want to build the circuit using D flip-flops instead?
• We already have the state table and state assignments, so we can just
start from Step 3, finding the flip-flop input values
• D flip-flops have only one input, so our table only needs two columns for
D1 and D0
Present Next Flip-flop

State Input State inputs Output
Q1 Q0 X Q1 Q0 D1 D0 Z
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 1 0 0
0 1 1 0 1 0
1 0 0 1 1 0
1 0 1 0 1 0
1 1 0 0 0 0
1 1 1 0 1 1
19
D flip-flop input values (Step 3)
• The D excitation table is pretty boring;

Q(t) Q(t+1) D Operation
set the D input to whatever the next
state should be 0 0 0 Reset
0 1 1 Set
• You don’t even need to show separate 1 0 0 Reset
columns for D1 and D0; you can just use 1 1 1 Set
the Next State columns
Present Next Flip flop

Q1 Q0 X Q1 Q0 D1 D0 Z
0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0
0 1 0 1 0 1 0 0
0 1 1 0 1 0 1 0
1 0 0 1 1 1 1 0
1 0 1 0 1 0 1 0
1 1 0 0 0 0 0 0
1 1 1 0 1 0 1 1
20
Finding equations (Step 4)
Present Next Flip flop

Q1 Q0 X Q1 Q0 D1 D0 Z
0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0
0 1 0 1 0 1 0 0
0 1 1 0 1 0 1 0
1 0 0 1 1 1 1 0
1 0 1 0 1 0 1 0
1 1 0 0 0 0 0 0
1 1 1 0 1 0 1 1
D1 Q1 Q0 D0 Q1 Q0 Z Q1 Q0
00 01 11 10 00 01 11 10 00 01 11 10
0 1 1 0 1 0
X X X
1 1 1 1 1 1 1 1
D1 = Q1 Q0’ X’ + Q1’ Q0 X’ D0 = X + Q1 Q0’ Z = X Q1 Q0 21

Building the circuit (Step 5)
22
Mixed Flip Flops
Present Next
Q1 Q0 X Q1 Q0 J1 K1 T0 Z
0 0 0 0 0 0 x 0 0
0 0 1 0 1 0 x 1 0
0 1 0 1 0 1 x 1 0
0 1 1 0 1 0 x 0 0
1 0 0 1 1 x 0 1 0
1 0 1 0 1 x 1 1 0
1 1 0 0 0 x 1 0 0
1 1 1 0 1 x 1 0 1
T0 Q1 Q0
00 01 11 10
0 0 1 0 1
X
1 1 0 0 1
23
Sequence recognizer (Moore)
• A sequence recognizer is a special kind of sequential circuit that looks

for a special bit pattern in some input
• The recognizer circuit has only one input, X

– One bit of input is supplied on every clock cycle
– This is an easy way to permit arbitrarily long input sequences
• There is one output, Z, which is 1 when the desired pattern is found
• Our example will detect the bit pattern ―1001‖:
Inputs: 1 1 1 0 01 1 0 1 00 1 00 1 1 0 …
Outputs: 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 …
• A sequential circuit is required because the circuit has to ―remember‖

the inputs from previous clock cycles, in order to determine whether
or not a match was found
24
Moore state diagram & table
0
1
1 0 0 1
A/0 B/0 C/0 D/0 E/1
1
0
0
1
Present Next
State Input State Output Z Q 2 Q1
A 0 A 0 00 01 11 10
A 1 B 0 A: 000 D: 100
B 0 C 0 0
B: 001 E: 101 Q0
B 1 B 0 1 1
C: 010
C 0 D 0
C 1 B 0
Z= Q2 Q1’ Q0
D 0 A 0
D 1 E 0
E 0 C 1
E 1 B 1
25

De Unit4 Notes

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

De Unit4 Notes

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

De Unit4 Notes

Uploaded by

Copyright:

Available Formats

DIGITAL ELECTRONICS

Department of Electrical & Electronics Engineering

Synchronous Sequential Networks

❖ Sequential Circuits are those which have the notion of

❖ This notion of Internal State is necessary because in

❖ The Internal State of a sequential circuit is nothing but the

❖ Now the Internal State of a Sequential Circuit is represented

❖ Each state variable can be in 1 of 2 possible states.

❖ This is because State Variables are physically implemented

❖ Therefore, if we have ‘N’ Flip-Flops, we can represent a

❖ A general sequential circuit network has memory section and

❖ Assume the followings structure of a general sequential circuit.

❖ The circuit memory section consists of the m of flip flops.

❖ There is a set X of i inputs X0 , X1 , ... Xi . These are applied to a

❖ The present state of Q changes on the clock transition(s) to

❖ The transition is by clock 1 or 0 or ↑ or ↓

❖ Further, a set Y with outputs Y0 , Y1 , Yj is obtained from the

Classification of sequential circuit as moore and mealy state

➢ A general clocked sequential circuit in which Y final stage

➢ A general sequential circuit in which the final stage outputs Y as

➢ Mealy Model Q′ = FQ (X, Q) (Next state outputs Q′ are the

Department of Electrical & Electronics Engineering

Synchronous Sequential Networks

❖Characteristic equation gives the next state equation of a given

❖To derive the characteristic equation of a FF, write the function

1. SR Flip Flop Characteristic Equation:

CLK S R Qn (present Q n+1 (next

The Next State Equation is Q n+1 = S+R’Q

2. JK Flip-Flop Characteristic Equation:

The Next State Equation is Q n+1 = JQ’+K’Q

3. Data Flip-Flop Characteristic Equation:

K-Map to determine Q n+1

K-Map to determine Q n+1

The Next State Equation is Q n+1 = TQ’+T’Q= T EXOR Q

Department of Electrical & Electronics Engineering

Synchronous Sequential Networks

❖ It gives present states and the inputs given at the memory

❖ Number of rows in each column equals 2m where m is the

❖ First column of excitation table gives a present state (Q1, Q2)

❖ The number of columns for the excitation inputs Q equals the

❖ For each set of inputs, there is a set of excitation inputs to the

❖ Mealy Model :The number of columns for the output Y also

❖ Moore Model :The number of column = 1 for the output Y as

❖ A transition table is a tabular representation of FQ and FO. It

❖ Number of rows in each column equals 2m for the m-FFs. First

❖ This is because there are four combinations possible for the

❖ The number of columns for the next state Q′ equals the

❖ For each set of inputs, there is a set of memory section

❖ Moore Model The number of column = 1 for the output Y as in

❖ A state table is a tabular representation of the present state

❖ The outputs are shown in next set of columns. Number of

❖ A state in a row on first column is written as either S0, S1, S2

❖ These are as per four possible values of (Q1, Q2) in case of

❖ The number of columns for the next state S equals the

❖ It equals 2i. For each set of inputs, there is a set of memory

❖ A state in a row is either S0 or S1, S2 or S3 as per the post

❖ Moore Model The number of columns for the output Y also

❖ Moore Model The number of column = 1 for the output Y as

❖ A state diagram is diagrammatic representation of the state