Lecture 13
March 23, 2009
Chapter 7
Sequential Logic
Mathematical Background
Solving Boolean Equations.
Ex 1: Consider Y = X + Z, solve for X. i.e. Find X = f(Y,Z)
In ordinary algebra X = Y - Z.
For Boolean algebra
Z / Y / X0 / 0
0 / 1
1 / 1
1 / 0
Z / Y / Z / X
0 / 1
X / 1 / 1 / Y
Thus, the general solution is , with the constraint .
Rule: ,
There are two particular solutions depending on the value chosen for the don't care d.
For d = 0, . For d = 1, .
Ex 2: Solve for X. When
Z1 /Y
/ Z1 / X0 / d / - / 1
1 / 1 / - / 0 /
X
/Y
Z2 / Z2Ex 3: Solve for X. When
Z1 /Y
/ Z1 / X- / 0 / 1 / d
1 / 0 / - / 0 /
X
/Y
Z2 / Z2Transitions.
F / tF / t
F / t
F(t) / F(t+t) or F* / F
0 / 0 / 0 / F stays 0
0 / 1 / / True transition, F goes true. F changes from 0 to 1.
1 / 0 / / False transition, F goes false. F changes from 1 to 0.
1 / 1 / 1 / F stays 1
The equations for designing finite state machines (FSMs) are shown below.
Flip-Flop Q excitation equations for common flip-flops
Type / Always clockSR Latch or
clocked
flip-flop. / S(Q) = (; d, 1)
R(Q) = (; d, 0)
JK clocked
flip-flop. / J(Q) = (; d, 1, )
K(Q) = (; d, 0, )
D clocked
flip-flop. / D(Q) = (, 1; d)
T clocked
flip-flop. / T(Q) = (, ; d)
Q* gate feedback / Q*(Q) = (, 1; d)
D latch or
clocked D
flip-flop with
enable. /
Note: D = Q*
FSM Design example
Using JK flip-flops design a clocked finite state machine (FSM) with a single input X and a single output Z. X is read only on the falling edge of the clock. Z is always 0 except when X has changed form 0 to 1 then Z goes to 1 and stays 1 for two clock periods. X changes very slow compared to the clock, C, so that when X changes there are many falling edges of the clock before X changes again.
CX
Z
Q1 / Q1 / Q1 / Q2
X
/X
/Q3
Q2 / Q2Q1 /
Z
Q2The S-R Latch
1
S(t) / R(t) / Q / Q* / Q0 / 0 / 0 / 0 / 0
0 / 0 / 1 / 1 / 1
0 / 1 / 0 / 0 / 0
0 / 1 / 1 / 0 /
1 / 0 / 0 / 1 /
1 / 0 / 1 / 1 / 1
1 / 1 / 0 / - / -
1 / 1 / 1 / - / -
SR
Q / 00 / 01 / 11 / 10
0 / 0 / 0 / - / 1
1 / 1 / 0 / - / 1
The SR flip-flop state table
1
S / Q* / S / Q0 / 0 / - / 1 / 0 / 0 / - /
Q / 1 / 0 / - / 1 / Q / 1 / / - / 1
R / R
Q / S / R
0 / 0 / d
/ 1 / 0
1 / d / 0
/ 0 / 1
S(Q) = (; d, 1)
R(Q) = (; d, 0)
The D – Latch
Note: The book uses C for the enable input. I am using E for the enable input.
D / Q* / D / Q0 / 0 / 1 / 0 / 0 / 0 / / 0
Q / 1 / 0 / 1 / 1 / Q / 1 / / 1 / 1
E / E
Design a D latch using a SR latch.
D
/ Q / Q = / 0 / / 1 / /D
0 / 0 / / 0 / d / - / d / -Q / 1 / / 1 / 1 / Q / 0 / 1 / 1 / 0
E
Q = / 0 / / 1 / /E
d / 1 / d / 1J-K Flip-Flop (Clocked by C)
J / K / Q / Q* / Q0 / 0 / 0 / 0 / 0
0 / 0 / 1 / 1 / 1
0 / 1 / 0 / 0 / 0
0 / 1 / 1 / 0 /
1 / 0 / 0 / 1 /
1 / 0 / 1 / 1 / 1
1 / 1 / 0 / 1 /
1 / 1 / 1 / 0 /
J / Q
0 / 0 / /
Q / 1 / / / 1
K
Q / J / K
0 / 0 / d
/ 1 / d
1 / d / 0
/ d / 1
J(Q) = (; d, 1, )
K(Q) = (; d, 0, )
Mealy and Moore Machines
A sequential circuit is called a finite state machine. A finite state machine can be either a Moore machine or a Mealy machine. The distinction is that in a Moore machine the output depends only on the present state. In a Mealy machine the output depends not only on the present state, but also the present input.
Example: A Finite State Machine (FSM) that detects two consecutive ones on the input X by producing an output of one on Z.
1
Moore Machine state table: PS = present State, NS = next state
NS, X =PS / 0 / 1 / Z
S0 / S0 / S1 / 0
S1 / S0 / S2 / 0
S2 / S0 / S2 / 1
The equivalent Mealy Machine state table
NS/Zfor X =
PS / 0 / 1
A / A/0 / B/0
B / A/0 / B/1
1
CC
X
X / 0 / 1 / 0 / 1 / 1 / 1 / 0 / 0 / 1 / 0 / 1 / 1 / 0 / 0
Z / 0 / 0 / 0 / 0 / 1 / 1 / 0 / 0 / 0 / 0 / 0 / 1 / 0
C
Moore
Z
0 / 0 / 0 / 0 / 0 / 1 / 1 / 0 / 0 / 0 / 0 / 0 / 1 / 0
C
Mealy
Z
0 / 0 / 0 / 0 / 1 / 1 / 0 / 0 / 0 / 0 / 0 / 1 / 0 / 0
C
Mealy and Moore Machines Examples
1. Draw the state diagram for the Moore machine described by the state table shown below.
NS, X =PS / 0 / 1 / Z
S0 / S2 / S3 / 0
S1 / S1 / S3 / 1
S2 / S1 / S0 / 0
S3 / S1 / S2 / 1
2. Using the state assignment
Q1 / Q0S0 / 0 / 0
S1 / 0 / 1
S2 / 1 / 0
S3 / 1 / 1
Design the Moore machine using JK flip-flops and draw the circuit. Be sure to include the output Z, and a system clock C.
3. Draw the state diagram for the Mealy machine described by the state table shown below.
NS/Zfor X =
PS / 0 / 1
S0 / S0/0 / S2/0
S1 / S3/1 / S1/1
S2 / S1/0 / S3/1
S3 / S0/0 / S2/0
4. Using the same state assignment as in problem 2 design the Mealy machine using JK flip-flops and draw the circuit. Be sure to include the output Z, and a system clock C.
5. Are the two machines equivalent? If they are not equivalent explain why?
6. Draw the state diagram for a Moore machine that produces an output of 1 whenever the last three inputs were 011. If less that 3 inputs have been received, the output doesn’t matter.
7. Repeat 6 for a Mealy machine.
DDPP page 555AB
0 / 0 / A / A,0 / B,0 /
0 / 1 / B / B,0 / C,0 /
1 / 0 / C / C,0 / D,0
1 / 1 / D / D,0 / A,1 /
Q1 / Q0 / ST / X=0 / X=1
0 / 0 / A / 00/0 / 01/0
0 / 1 / B / 01/0 / 10/0
1 / 0 / C / 10/0 / 11/0
1 / 1 / D / 11/0 / 00/1
DC
0 / 0 / 1 / 1 / 0 / 1 / 1 / 0
X
/ 0 / / / 1 /X
/ / / / /Q3
Q0 / Q0Using D flip-flops.
Using JK flip-flops
Using SR flip-flops
Using T flip-flops
Q1 / Z0 / 0 / 0 / 0
X
/ 0 / 0 / 1 / 0Q0
Q1
/ Q1 / Q1 / Q0 / Q1 / Z0 / 0 / 1 / 1 / 0 / 1 / 1 / 0 / 0 / 0 / 0 / 0
/ / 1 / / Y / 0 / 1 / / 0 / Y / 1 / 0 / 0 / 0 / Y
X / / / 1 / / X / 0 / 1 / / 0 / X / 1 / 0 / 1 / 0
0 / / / 1 / / / / / 0 / 0 / 1 / 0
Q0
/ Q0 / Q0Using JK flip-flops
Sequential Circuit Examples
Example:
Using only NAND gates, build a circuit with input X and Y, and output Z. If Z = 0 then when X = 1, Z changes to 1. When Z = 1 if X = 0 and Y = 0 then Z changes to 0. Otherwise Z does not change.
The behavior is shown by the truth table below where Z* is the next value of Z.
Z / X / Y / Z*0 / 0 / 0 / 0
0 / 0 / 1 / 0
0 / 1 / 0 / 1
0 / 1 / 1 / 1
1 / 0 / 0 / 0
1 / 0 / 1 / 1
1 / 1 / 0 / 1
1 / 1 / 1 / 1
X /
Z*
0 / 0 / 1 / 10 / 1 / 1 / 1 /
Z
YX /
Z
0 / 0 / / / 1 / 1 / 1 /
Z
Y1