Lecture 15
Finite State Machine Implementation
Prith Banerjee
ECE C03
Advanced Digital Design
Spring 1998
ECE C03 Lecture 15 1
Outline
Mapping FSM to random logic
Mapping FSM to ROMS
Mapping FSM to PLAs
Mapping FSM to Programmable Logic Devices
(Xilinx)
READING: Katz 10.1.1, 10.1.2, 10.3, Dewey 9.5
ECE C03 Lecture 15 2
FSM Implementation Strategies
Discrete Gate Logic
Emphasis so far
MSI Logic (e.g., Counters)
Structured Logic (e.g., PLA/PAL, ROM)
Field Programmable Gate Arrays (FPGAs)
Function can be configured "on the fly" or in the field
Flipflops/Registers plus discrete gates on the same chip
ECE C03 Lecture 15 3
FSM Design with Structured Logic
Combinational
Logic Registers
Output Block Diagram for
Inputs Outputs
Function Synchronous Mealy Machine
Next State
Function
State
ROM-based Realization
ROM Registers
A0 D0 Inputs & Current State
Inputs Outputs
Dk-1
form the address
An-1
An Dk ROM data bits form the
Outputs & Next State
An+m-1 Dk+m-1
State
ECE C03 Lecture 15 4
ROM-Based Implementation
Example: BCD to Excess 3 Serial Converter
BCD Excess 3 Code
0000 0011
Conversion Process 0001 0100
0010 0101
Bits are presented in bit serial fashion 0011 0110
starting with the least significant bit 0100 0111
0101 1000
Single input X, single output Z 0110 1001
0111 1010
1000 1011
1001 1100
ECE C03 Lecture 15 5
BCD to Excess-3 Converter
Next State Output
Present State X=0 X=1 X=0 X=1
S0 S1 S2 1 0
S1 S3 S4 1 0 State Transition Table
S2 S4 S4 0 1
S3 S5 S5 0 1
S4 S5 S6 1 0
S5 S0 S0 0 1
S6 S0 -- 1 --
Reset
S0
0/1 1/0
S1 S2
1/0
0/1 0/0, Derived State Diagram
1/1
S3 S4
0/0, 0/1 1/0
1/1
S5 S6
0/0, 0/1
1/1 ECE C03 Lecture 15 6
ROM-Based Implementation
BCD to Excess 3 Converter
ROM Address ROM Outputs
X Q2 Q1 Q0 Z D2 D1 D0
0 0 0 0 1 0 0 1 1
0 0 0 1 1 0 1 1 15
CLK 9 CLK
0 0 1 0 0 1 0 0 QD 14 Z
0 0 1 1 0 1 0 1 1 X converter ROM 175 QD 10
X Z 13 D
0 1 0 0 1 1 0 1 0 C QC 11
Q2 D2 12
0 1 0 1 0 0 0 0 5 QC
Q1 D1 B 7
0 1 1 0 1 0 0 0 4 A QB
Q0 D0 6
QB
0 1 1 1 X X X X 2
1 0 0 0 0 0 1 0 1 QA
1 CLR 3
1 0 0 1 0 1 0 0 0 QA
\Reset
1 0 1 0 1 1 0 0
1 0 1 1 1 1 0 1
1 1 0 0 0 1 1 0
1 1 0 1 1 0 0 0
Circuit Level Realization
1 1 1 0 X X X X
1 1 1 1 X X X X
74175 = 4 x positive edge triggered D FFs
Truth Table/ROM I/Os
In ROM-based designs,ECE
noC03
need to consider state assignment
Lecture 15 7
ROM Based Implementation
BCD to Excess-3 Converter
LSB MSB
Timing Behavior for input strings 0 0 0 0 (0) and 1 1 1 0 (7)
0 0 0 0 1 1 1 0
1 1 0 0 0 1 0 1
0000 1100 1110 0101
LSB LSB
ECE C03 Lecture 15 8
PLA Based Design
BCD to Excess 3 Converter
State Assignment with NOVA
0 S0 S1 1 S0 = 000
1 S0 S2 0 S1 = 001
0 S1 S3 1 S2 = 011
1 S1 S4 0 S3 = 110
0 S2 S4 0 S4 = 100
1 S2 S4 1 S5 = 111
0 S3 S5 0 S6 = 101
1 S3 S5 1
0 S4 S5 1 NOVA derived
1 S4 S6 0 state assignment
0 S5 S0 0
1 S5 S0 1
0 S6 S0 1 9 product term
NOVA input file implementation
ECE C03 Lecture 15 9
PLA Implementation
BCD to Excess 3 Converter
.i 4 Espresso Inputs .i 4
.o 4 .o 4
.ilb x q2 q1 q0 .ilb x q2 q1 q0
.ob d2 d1 d0 z .ob d2 d1 d0 z
.p 16 .p 9
0 000 001 1 0001 0100
1 000 011 0 10-0 0100
0 001 110 1 01-0 0100
1 001 100 0 1-1- 0001
0 011 100 0 -0-1 1000
1 011 100 1 0-0- 0001
0 110 111 0 -1-0 1000
1 110 111 1 --10 0100
0 100 111 1 ---0 0010
1 100 101 0 Espresso Outputs .e
0 111 000 0
1 111 000 1
0 101 000 1
1 101 --- -
0 010 --- -
1 010 --- -
.e ECE C03 Lecture 15 10
PLA Implementation
BCD to Excess 3 Converter
D2 = Q2 Q0 + Q2 Q0
D1 = X Q2 Q1 Q0 + X Q2 Q0 + X Q2 Q0 + Q1 Q0
D0 = Q0
Z = X Q1 + X Q1
1
CLK 9 15
CLK QD
14 Z
1 X
conv erter PLA 175 QD
Z 13 D 10
X QC
0 D2 12 C 11
Q2 QC
D1 5 B 7
Q1 QB
D0 4 A 6
Q0 QB
2
1 1 CLR QA
3
0 QA
\Reset
ECE C03 Lecture 15 11
PAL Implementation
BCD to Excess 3 Serial Converter
10H8 PAL: 10 inputs, 8 outputs, 2 product terms per OR gate
D1 = D11 + D12
D11 = X Q2 Q1 Q0 + X Q2 Q0
D12 = X Q2 Q0 + Q1 Q0
0 1 2 3 45 89 12 13 16 17 20 21 24 25 28 29 30 31
X
0
1 D2
0. Q2 Q0 Q2
1. Q2 Q0 8
9
D11
8. X Q2 Q1 Q0 Q1
9. X Q2 Q0 16
D12
16. X Q2 Q0 Q0
17
17. Q1 Q0 24
D1
24. D11 25
D11
25. D12 32
32. Q0 33
D0
33. not used D12
40
40. X Q1 41 Z
41. X Q1
ECE C03 Lecture 15 12
PAL Implementation
BCD to Excess 3 Serial Converter
0 1 2 3 45 89 12 13 16 17 20 21 24 25 28 29 30 31
X
0
1 D2
Q2
8
D11
9
Q1
16
17 D12
Q0
24
D1
25
D11
32
D0
33
D12
40
41 Z
ECE C03 Lecture 15 13
More Advanced PAL Architectures
Registered PAL Architecture
Buffered Input
or product term
CLK OE
Q2 Q0 + Q2 Q0
Q2 Q0
Q2 Q0
D2 Q2+ Q2+
DQ
Q
Q2+
Q2 Q0 + Q2 Q0
X
Q2 Q2 Q0 Q0
Negative Logic
D2 = Q2 Q0 + Q2 Q0 Feedback
D1 = X Q2 Q1 Q0 + X Q2 + X Q0 + Q2 Q0 + Q1 Q0
D0 = Q0
ECE C03 Lecture 15 14
Z = X Q1 + X Q1
Advanced PAL Architectures
Programmable Output Polarity/XOR PALs
CLK OE
Buried Registers: decouple
DQ FF from the output pin
Q
Advantage of XOR PALs: Parity and Arithmetic Operations
AB C D
AB C D
A B C D AB
AB C D A B C D
AB C D AB
AB C D
CD
AB C D
CD
AB C D
AB C D
ECE C03 Lecture 15 15
Examples of XOR and Registered PALs
Example of XOR PAL Example of Registered PAL
INCREMEN
INCREMEN T
T 1
1 0 4 8 12 16 20 24 28
0 4 8 12 16 20 24 28 32 36 0
FIRST 0 FIRST 32
FUSE 40 FUSE 64
D Q 23
NUMBER 80 NUMBER 96 19
120 S 128
Q 160
192
224
2
2
160
200
D Q 22 256
240 288
280 320
Q 352 D Q 18
384
3 416
448 Q
480
320
360 3
D Q 21
400
440
512
Q 544
576
4 608 D Q 17
640
480 672
704 Q
520
D Q 20 736
560
600 4
Q
768
5 800
832
640 864 D Q 16
680 896
D Q 19
720 928
960 Q
760
Q 992
5
6
1024
800 1056
840 18 1088
D Q
880 1120 D Q 15
920 1152
Q 1184
1216 Q
1248
7
6
960
1000
D Q 17 1280
1040 1312
1080 1344
Q 1376 D Q 14
1408
8 1440
1472 Q
1504
1120
1160
D Q 16 7
1200
1240
1536
Q 1568
1600
9 1632 D Q 13
1664
1280 1696
1320 1728 Q
D Q 15 1760
1360
1400 8
Q
1792
10 1824
1856
1440 1888
1480 12
14 1920
D Q 1952
1520
1560 1984
Q 2016
9 11
11 13
INCREMEN 0 4 8 12 16 20 24 28 32 36
T
NOTE: FUSE NUMBER = FIRST FUSE NUMBER +
INCREMENT
ECE C03 Lecture 15 16
FSM Design With Counters
Synchronous Counters: CLR, LD, CNT
0
Four kinds of transitions for each state:
no
(1) to State 0 (CLR)
CLR signals
(2) to next state in sequence (CNT) n asserted
(3) to arbitrary next state (LD) CNT LD
(4) loop in current state
n+1 m
Careful state assignment is needed to reflect basic sequencing
of the counter
ECE C03 Lecture 15 17
Implementation Strategies
FSM Design with Counters
Excess 3 Converter Revisited
Reset
0
0/1 1/0
1 4 Note the sequential nature
1/0 of the state assignments
0/1 0/0,
1/1
2 5
0/0, 0/1
1/1 1/0
3 6
0/0, 0/1
1/1
ECE C03 Lecture 15 18
Implementation Strategies
FSM Design with Counters
Excess 3 Converter
Inputs/Current Next
State 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 1 1 1 1 X X X
0 1 0 1 0 1 1 0 1 0 X 0 1 0
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 0 1 1 1 X X X
1 1 0 1 1 1 0 1 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
ECE C03 Lecture 15 19
Implementation FSM With Counters
Excess 3 Converter
.i 5 Espresso Input File .i 5
.o 7 .o 7
.ilb res x q2 q1 q0 .ilb res x q2 q1 q0
.ob z clr ld en c b a .ob z clr ld en c b a
.p 17 .p 10
1---- -0----- 0-001 0101101
00000 1111--- -0-01 1000000
00001 1111--- -11-0 1000000
00010 0111--- 0-0-0 0101100
00011 00----- -000- 1010000
00100 0111--- -0--0 0010000
00101 110-011 0-10- 0101011
00110 10----- --11- 1000000
00111 ------- -11-- 0010000
01000 010-100 -1-1- 1010000
01001 010-101 .e
01010 1111---
01011 10----- Espresso Output File
01100 1111---
01101 0111---
01110 -------
01111 ------- ECE C03 Lecture 15 20
.e
Implementing FSM with Counters
Excess 3 Converter Schematic
CLK
excess 3 PLA 7 Z
1 P D Q
Z 10
T
163
0
X Rese t \CLR 2 RCO15 C Q
1 \L D CLK
X
0 6 D QD 11
Q2 EN
5 C QC 12
Q1 C 4 B
Q0 B QB 13
3 A 14
A QA
9 LOAD
1
CLR
Synchronous Output Register
ECE C03 Lecture 15 21
FSM Design with FPGAs
Programmable Logic Devices = PLD
PALs, PLAs = 10 - 100 Gate Equivalents
Field Programmable Gate Arrays = FPGAs
Altera MAX Family
Actel Programmable Gate Array
Xilinx Logical Cell Array
100 - 1000(s) of Gate Equivalents!
ECE C03 Lecture 15 22
Xilinx Logic Cell Arrays
CMOS Static RAM Technology: programmable on the fly!
All personality elements connected into serial shift register
Shift in string of 1's and 0's on power up
IOB IOB IOB IOB
IOB
General Chip Architecture:
Logic Blocks (CLBs)
IO Blocks (IOBs) CLB CLB
Wiring Channels
IOB
Wiring Channels
IOB
CLB CLB
IOB
ECE C03 Lecture 15 23
Xilinx LCA Architecture
Inputs: Program Controlled Options
Tri-state enable Vcc
OUT TS OUTPUT SLEW PASSIVE
bit to output INV INV SOURCE RATE PULLUP
input, output clocks
Enable
Output
Outputs:
input bit
MUX PAD
Internal FFs for Out D Q Output
input & output paths Buffer
R
Direct In
Fast/Slow outputs
5 ns vs. 30 ns rise Registered In
Q D
TTL or CMOS
Input Buffer
R
Pull-up used with
unused IOBs Clocks Global Reset
ECE C03 Lecture 15 24
Xilinx LCA Architecture
Configurable Logic Block: CLB
2 FFs
Reset
DIN Mux D RD
Q
Any function of CE
5 Variables Q1 Mux X
F
A
B Combinational
Global Reset C Function
D Generator
E G
Q2 Mux Y
Clock, Clock Enb Mux D RD
Q
Clock Mux CE
Independent DIN Clock
Enable
ECE C03 Lecture 15 25
Xilinx CLB Function Generator
CLB Function Generator
Q1
A
Q1 B Mux
Function
A of 4 F
B Mux F C Mux
Variables
Function D
C Mux of 5 Mux
E
Variables
D G Q2
E
Q1
Q2
A
Any function of 5 variables B Mux
Function
C Mux of 4 G
Variables
D Mux
E
Q2
Two Independent Functions
ECE C03 Lecture 15 of 4 variables each 26
Xilinx CLB Function Generator
Q1
A
B Mux
Function
C Mux of 4
Variables
D E
Certain Limited F
Q2
Functions of 6 Variables
Mux
Q1
A G
B Mux
Function
C Mux of 4
Variables
D
Q2
ECE C03 Lecture 15 27
Xilinx Interconnect Architecture
Direct
Connections
Interconnect DI CE A DI CE A
B X B X
C CLB0 C CLB1
K Y K Y
Direct Connections E D R E D R
Horizontal
Global Long Line Long Line
Switching
Horizontal/Vertical Matrix
Long Lines
Horizontal
Switching Matrix Long Line
Connections DI CE A DI CE A
B X B X
C CLB2 C CLB3
K Y K Y
E D R E D R
Vertical Global
Long Lines Long Line
ECE C03 Lecture 15 28
Implementing FSM with Xilinx LCA
Implementing the BCD to Excess 3 FSM
Q2+ = Q2 Q0 + Q2 Q0
Q1+ = X Q2 Q1 Q0 + X Q2 Q0 + X Q2 Q0 + Q1 Q0
Q0+ = Q0
Z = Z Q1 + X Q1
No function more complex than 4 variables
4 FFs implies 2 CLBs
Synchronous Mealy Machine
Global Reset to be used
Place Q2+, Q0+ in once CLB
Q1, Z in second CLB
maximize use of direct & general purpose interconnections
ECE C03 Lecture 15 29
Implementing FSM with Xilinx LCA
Implementing the BCD to Excess 3 FSM
Clk
Clk
CE
CE A CE A
DI X DI X
X
Q2 Q2 Q2 Q1
FG FG
B Q0 Q1
B Q0
C C
Y X Y
Q0 Z
K Q0 K Q1
FG FG
E E
D RES D RES
CLB1 CLB2
ECE C03 Lecture 15 30
Summary
Mapping FSM to random logic
Mapping FSM to ROMS
Mapping FSM to PLAs
Mapping FSM to Programmable Logic Devices
(Xilinx)
NEXT LECTURE: VHDL Language
READING: Dewey 11.2, 11.3, 11.4, 11.5, 11.6,
12.2, 12.2
ECE C03 Lecture 15 31