Digital Logic Design

Ch9

Sequential Logic Technologies

note 6
Topics

¨ FSM design with discrete logic gates and flip-flops

¤ shift registers
¤ counters
¨ FSM design with ROMs
¨ FSM design with PALs/PLAs
¨ FSM design with FPGAs
¨ Case Study: Traffic Light Controller

2 Digital Logic Design

Sequential design procedure

¨ State diagram
¨ State transition table
¨ State assignment
¨ Next state and Output functions

3 Digital Logic Design

Median filter FSM

¨ Remove single 0s between two 1s (output = PS3)

0 I PS1 PS2 PS3 NS1 NS2 NS3
0 0 0 0 0 0 0
0 0 0 1 0 0 0
000 Reset 0 0 1 0 0 0 1
0 0 1 1 0 0 1
0 1 0 1 0 0 0 1 0
0 1 0 1 0X X1 X0
100 0 1 1 0 0 1 1
0 1 0 1 1 1 0 1 1
1 1 0 0 0 1 0 0
1 0 0 1 1 0 0
010 110 1 0 1 0 1 10 1
0 1 1 0 1 0 1 1 1 10 1
1 1 0 0 1 1 0
0 1 1 0 1 1X X1 X0
001 1 111 011
1 1 1 1 0 1 1 1
0 1 1 1 1 1 1 1

4 Digital Logic Design

Median filter FSM

¨ Realized using the standard procedure and individual

FFs and gates
I PS1 PS2 PS3 NS1 NS2 NS3
0 0 0 0 0 0 0
0 0 0 1 0 0 0 NS1 = Reset’ × I
0 0 1 0 0 0 1
0 0 1 1 0 0 1 NS2 = Reset’× ( PS1 + PS2 × I )
0 1 0 0 0 1 0 NS3 = Reset’× PS2
0 1 0 1 X X X O = PS3
0 1 1 0 0 1 1
0 1 1 1 0 1 1
1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 1 1 1
1 0 1 1 1 1 1
1 1 0 0 1 1 0
1 1 0 1 X X X
1 1 1 0 1 1 1
1 1 1 1 1 1 1

5 Digital Logic Design

State diagram for shift register (Note 6)
OUT1 OUT2 OUT3

IN D Q D Q D Q

CLK

Input value shown

on transition arcs 1
100 110

1 0 1 1
1
1
000 1 010 101 0 111
0

0 0 0 1 0
001 011
Output values shown 0
within state node

6 Digital Logic Design

Median filter FSM

¨ But it looks like a shift register if you look at it right

0 0

000 Reset 000 Reset

0 1 0 1

100 100 0
101
0 1 0
1
1 1 1
1
010 110 010 110
0 1 1 0 0 1 0

0 0
001 1 111 011 001 1 111 011 1
1
0 0

7 Digital Logic Design

Median filter FSM

¨ An implementation without Reset

IN

OUT

D Q D Q D Q

CLK

NS1 = I
NS2 = PS1 + PS2 × I
NS3 = PS2
O = PS3

8 Digital Logic Design

 0

000 Reset

Median filter FSM 0

100
1

0 1
1
010 110
0 1 1 0
¨ An alternative implementation with S/R FFs 001 1 111
0
011
1
0

R = Reset
Reset S = PS2 × I
NS1 = I
NS2 = PS1
R S R S R S NS3 = PS2
In D Q D Q D Q Out O = PS3

CLK

¨ The set input (S) does the median filter function by making
the next state 111 whenever the input is 1 and PS2 is 1 (1
input to state x1x)

9 Digital Logic Design

 Reset
S0
0/0 1/0

Using a shift register 0/0

S1
1/0 1/0
S2
0/0

S3' S4'
0,1/0 0/0 1/0

¨ 4-bit string (0110, 1010) recognizer S7'

0/1
S10'
1/0
0,1/0

Reset
No need to minimize states!
4 FFs for the shift register
0/0 1/0 è can express up to 16 states

0/0 1/0 0/0 1/0

0/0 1/0 0/0 1/0 0/0 1/0 0/0 1/0

0/0 1/0 0/0 0/0 0/1 0/0 1/0 0/0 1/0 1/0
1/0 1/0 1/0 0/1 1/0 0/0

10 Digital Logic Design

 Using a shift register
0110
0
1
1

1010
Initial realization

Correction by adding a counter

11 Digital Logic Design
 FSM design with counters

¨ Synchronous counters: CLR, LD, CNT 0

¨ Four kinds of transition for each state: no

¤ To State 0 (CLR) CLR signals
n asserted
¤ To next state in sequence (CNT)
¤ To arbitrary next state (LD) CNT LD

¤ Loop in the current state

n+1 m

12 Digital Logic Design

 BCD to excess 3 serial converter
BCD Excess 3 Code
¨ Conversion Process
0000 0011
0001 0100
Bits are presented in bit serial fashion
0010 0101
starting with the least significant bit
0011 0110
0100 0111
Single input X, single output Z
0101 1000
0110 1001
0111 1010
1000 1011
1001 1100

13 Digital Logic Design

 BCD Excess 3 Code
0000 0011

BCD to excess 3 serial converter 0001

0010
0100
0101
0011 0110

Reset 0100 0111

0101 1000
S0 0110 1001
0/1 1/0 0111 1010
S1 S2 1000 1011
1/0 0/0,
0/1 State Diagram 1001 1100
1/1 1010 1101
S3 S4 1011 1110
0/0, 0/1 Partial orders
1/0 S0 S1 S3 S5 S0
1100 1111
1/1
S0 S1 S4 S5 S0 1101 don’t-care
S5 S6
S0 S1 S4 S6 S0 1110 outputs
0/0, 1/?
S0 S2 S4 S5 S0
1/1 0/1 S0 S2 S4 S6 S0
1111
? S6
Next State Output
Present State X=0 X=1 X=0 X=1
S0 000 (0) S1 S2 1 0 State Transition Table
S1 001 (1) S3 S4 1 0
S2 100 (4) S4 S4 0 1
S3 010 (2) S5 S5 0 1 Note the sequential nature of the
S4 101 (5) S5 S6 1 0
S5 011 (3) S0 S0 0
state assignment
1
S6 110 (6) S0 -- 1 --
14 Digital Logic Design
 BCD to excess 3 serial converter
Inputs/Current State Next State Outputs
X Q2 Q1 Q0 Q2+ Q1+ Q0+ Z CLR LD EN C B A
0 0 0 0 0 0 1 1 1 1 1 X X X
0 0 0 1 0 1 0 1 1 1 1 X X X
0 0 1 0 0 1 1 0 1 1 1 X X X
0 0 1 1 0 0 0 0 0 X X X X X
0 1 0 0 1 0 1 0 1 1 1 X X X
0 1 0 1 0 1 1 1 1 0 X 0 1 1
0 1 1 0 0 0 0 1 0 X X X X X
0 1 1 1 X X X X X X X X X X
1 0 0 0 1 0 0 0 1 0 X 1 0 0
1 0 0 1 1 0 1 0 1 0 X 1 0 1
1 0 1 0 0 1 1 1 1 1 1 X X X
1 0 1 1 0 0 0 1 0 X X X X X
1 1 0 0 1 0 1 1 1 1 1 X X X
1 1 0 1 1 1 0 0 1 1 1 X X X
1 1 1 0 X X X X X X X X X X
1 1 1 1 X X X X X X X X X X
CLR signal dominates LD which dominates Count
15 Digital Logic Design
 BCD to excess 3 serial converter

¨ Counter-based implementation of code converter

Combinational Registers

When the state diagram has fewer out-of-sequence jumps, a counter

based implementation can be very effective

16 Digital Logic Design

 Rom-based design
Combinational
Logic Registers

Inputs Output
Outputs
Function ¨ Block Diagram for
Next State Synchronous Mealy Machine
Function

State

ROM Registers
A0 D0 ¨ ROM-based Realization
Inputs Outputs
An-1 Dk-1 ¤ Inputs & Current State form the
An Dk address
An+m-1 Dk+m-1 ¤ ROM data bits form the Outputs
& Next State
State
17 Digital Logic Design
 000
S0
0/1 1/0

Rom-based design 001 S1

0/1
1/0
S2 010
0/0,
1/1
S3 011 S4 010
0/0, 0/1 1/0
ROM ADDRESS ROM Outputs 1/1
S5 S6
X Q2 Q1 Q0 Z D2 D1 D0 0/0,
110
101
0 0 0 0 1 0 0 1 1/1 0/1

0 0 0 1 1 0 1 1
0 0 1 0 0 1 0 0 1
0 0 1 1 0 1 0 1 CLK 9 CLK 15
QD Z
0 1 0 0 1 1 0 1 175 14
1 X converter ROM QD
0 1 0 1 0 0 0 0 X Z 13 D 10
0 C QC
D2 12 11
0 1 1 0 1 0 0 0 Q2
5 QC
Q1 D1 B
0 1 1 1 X X X X 4 A QB 7
Q0 D0
QB 6
1 0 0 0 0 0 1 0
2
1 0 0 1 0 1 0 0 1 QA
1 CLR 3
0 QA
1 0 1 0 1 1 0 0 \Reset
1 0 1 1 1 1 0 1
1 1 0 0 0 1 1 0
1 1 0 1 1 0 0 0
1 1 1 0 X X X X
1 1 1 1 X X X X Excess-3 synchronous Mealy ROM-based
implementation
18 Digital Logic Design
 PLA-based design

¨ State assignment with NOVA

Reset
S0 = 000
S0
S1 = 001 0/1 1/0
S2 = 011 S1 S2
1/0 0/0,
0/1
S3 = 110 1/1
S3 S4
S4 = 100 0/0, 0/1 1/0
S5 = 111 1/1
S5 S6
S6 = 101 0/0,
1/1 0/1

S0 S1 S2
S4 S6 S5 S3

19 Digital Logic Design

 PLA-based design
.i 4 Q2+ = Q2’Q0 + Q2Q0’
.o 4
.ilb x q2 q1 q0 Q1+ = X’Q2’Q1’Q0 + XQ2’Q0’
.ob d2 d1 d0 z + X’Q2Q0’ + Q1Q0’
.p 16
0 000 001 1 Q0+ = Q0’
1 000 011 0 Z = XQ1 + X’Q1’
0 001 110 1 .i 4
1 001 100 0 .o 4 9 product term implementation
0 011 100 0 .ilb x q2 q1 q0
1 011 100 1 .ob d2 d1 d0 z
0 110 111 0 .p 9 1
1 110 111 1 0001 0100 15
CLK 9 CLK
0 100 111 1 10-0 0100 QD 14 Z
1 100 101 0 01-0 0100 1 X converter PLA 175 QD 10
X Z 13 D
0 111 000 0 1-1- 0001 0 D2 12 C QC 11
-0-1 1000 Q2 QC
1 111 000 1 D1 5 B 7
Q1 QB
0 101 000 1 0-0- 0001 Q0 D0 4 A 6
-1-0 1000 QB
1 101 --- - 2
0 010 --- - --10 0100 1 1 CLR
QA
3
---0 0010 0 QA
1 010 --- - \Reset
.e .e

Espresso Inputs Espresso Outputs

20 Digital Logic Design
 PAL-based design
¨ PAL10H8: 10 inputs, 8 outputs, 2 product terms per OR gate
Q1+ = Q11+Q12
Q2+ = Q2’Q0 + Q2Q0’ Q11 = X’Q2’Q1’Q0 + XQ2’Q0’
Q1+ = X’Q2’Q1’Q0 + XQ2’Q0’ + X’Q2Q0’ + Q1Q0’ Q12 = X’Q2Q0’ + Q1Q0’
Q0+ = Q0’
0 1 2 3 45 89 12 13 16 17 20 21 24 25 28 29 30 31
Z = XQ1 + X’Q1’
+ X
0
1 Q2+
PAL10H8
Q2
X 1 20
8
Q2 2 19 Q2+ Q11
9
Q1 3 18 Q1
Q0 16
4 17 Q12
17
5 AND 16 Q1+
Gate Q0
6 15 Q0+ 24
Array Q1+
7 14 Z 25
8 13 Q11
9 12 32
Q0+
33
10 11
Q12
40
41 Z

21 Digital Logic Design

 Implementation using PALs

¨ Programmable logic building block for sequential logic

¤ macro-cell: FF + logic
n D-FF
n Two-level logic capability like PAL (e.g., 8 product terms)

DQ
Q

22 Digital Logic Design

 Alternative PAL architectures

D2’ = Q2Q0 + Q2’Q0’

D1’ = X’Q2’Q1’Q0’ + XQ2 + XQ0 + Q2Q0 + Q1Q0
D0’ = Q0
Z’ = XQ1’ + X’Q1

23 Digital Logic Design

 Vending machine (Moore PLD mapping)
D0 = reset'(Q0'N + Q0N' + Q1N + Q1D)
D1 = reset'(Q1 + D + Q0N)
CLK
OPEN = Q1Q0
Q0
DQ

Seq
N

Q1
DQ

Seq
D

Open
DQ

Com
Reset

24 Digital Logic Design

 Vending machine (synch. Mealy PLD)
OPEN = reset'(Q1Q0N' + Q1N + Q1D + Q0'ND + Q0N'D)
CLK

Q0
DQ

Seq
N

Q1
DQ

Seq
D

OPEN Open
DQ

Seq
Reset

25 Digital Logic Design

 22V10 PAL

¨ Combinational logic
elements (SoP)
¨ Sequential logic
elements (D-FFs)
¨ Up to 10 outputs
¨ Up to 10 FFs
¨ Up to 22 inputs

26 Digital Logic Design

 22V10 PAL macro cell

¨ Sequential logic element + output/input selection

OE

AR: Asynchronous Reset

SP: Synchronous Preset

27 Digital Logic Design