CSE140L: Components and Design
Techniques for Digital Systems Lab
FSMs
Tajana Simunic Rosing
1
Source: Vahid, Katz
Hardware Description Languages
and Sequential Logic
• Flip-flops
– representation of clocks - timing of state changes
– asynchronous vs. synchronous
• FSMs
– structural view (FFs separate from combinational logic)
– behavioral view (synthesis of sequencers – not in this course)
• Datapath = data computation (e.g., ALUs, comparators) +
registers
– use of arithmetic/logical operators
– control of storage elements
FSM design example – Moore vs. Mealy
• Remove one 1 from every string of 1s on the input
Moore Mealy
zero
[0] 0/0
zero
1 0 [0]
0 one1 0/0 1/0
[0]
one1
0 1 [0]
1 1/1
two1s
[1]
Verilog FSM - Reduce 1s example
• Moore machine
state assignment
(easy to change,
module reduce (clk, reset, in, out); if in one place)
input clk, reset, in;
output out;
parameter zero = 2’b00;
parameter one1 = 2’b01;
parameter two1s = 2’b10; zero
[0]
reg out;
reg [2:1] state; // state variables 1 0
reg [2:1] next_state;
0 one1
always @(posedge clk) [0]
if (reset) state = zero;
else state = next_state; 0 1
1
two1s
[1]
Moore Verilog FSM (cont’d)
always @(in or state)
crucial to include
case (state) all signals that are
zero:
// last input was a zero
input to state determination
begin
if (in) next_state = one1;
else next_state = zero;
end
one1: note that output
// we've seen one 1 depends only on state
begin
if (in) next_state = two1s;
else next_state = zero;
end
two1s: always @(state)
// we've seen at least 2 ones case (state)
begin zero: out = 0;
if (in) next_state = two1s; one1: out = 0;
else next_state = zero; two1s: out = 1;
end endcase
endcase
endmodule
Mealy Verilog FSM
module reduce (clk, reset, in, out);
input clk, reset, in;
output out;
reg out;
reg state; // state variables
reg next_state;
always @(posedge clk)
if (reset) state = zero;
else state = next_state;
0/0
always @(in or state) zero
case (state) [0]
zero: // last input was a zero
begin 0/0 1/0
out = 0;
if (in) next_state = one; one1
else next_state = zero; [0]
end 1/1
one: // we've seen one 1
if (in) begin
next_state = one; out = 1;
end else begin
next_state = zero; out = 0;
end
endcase
endmodule
Synchronous Mealy Machine
module reduce (clk, reset, in, out);
input clk, reset, in;
output out;
reg out;
reg state; // state variables
always @(posedge clk)
if (reset) state = zero;
else
case (state)
zero: // last input was a zero
begin
out = 0;
if (in) state = one;
else state = zero;
end
one: // we've seen one 1
if (in) begin
state = one; out = 1;
end else begin
state = zero; out = 0;
end
endcase
endmodule
Example: Traffic light controller
• Highway/farm road intersection
farm road
car sensors
highway
Traffic light controller (cont.)
• Detectors C sense the presence of cars waiting on the farm road
– with no car on farm road, light remain green in highway direction
– if vehicle on farm road, highway lights go from Green to Yellow to Red, allowing
the farm road lights to become green
– these stay green only as long as a farm road car is detected but never longer than
a set interval; after the interval expires, farm lights transition from Green to Yellow
to Red, allowing highway to return to green
– even if farm road vehicles are waiting, highway gets at least a set interval of green
• Assume you have an interval timer that generates:
– a short time pulse (TS) and
– a long time pulse (TL),
– in response to a set (ST) signal.
– TS is to be used for timing yellow lights and TL for green lights
Traffic light controller (cont.)
• inputs description outputs description
reset place FSM in initial state HG, HY, HR assert green/yellow/red highway lights
C detect vehicle on the farm road FG, FY, FR assert green/yellow/red highway lights
TS short time interval expired ST start timing a short or long interval
TL long time interval expired
• state
HG
description
highway green (farm road red) (TL•C)' Reset
HY highway yellow (farm road red)
FG farm road green (highway red)
FY farm road yellow (highway red) HG
TL•C / ST TS / ST
TS' HY FY TS'
TS / ST TL+C' / ST
FG
(TL+C')'
Traffic light controller (cont.)
• Generate state table with symbolic states
• Consider state assignments output encoding – similar problem
to state assignment
(Green = 00, Yellow = 01, Red = 10)
Inputs Present State Next State Outputs
C TL TS ST H F
0 – – HG HG 0 Green Red
– 0 – HG HG 0 Green Red
1 1 – HG HY 1 Green Red
– – 0 HY HY 0 Yellow Red
– – 1 HY FG 1 Yellow Red
1 0 – FG FG 0 Red Green
0 – – FG FY 1 Red Green
– 1 – FG FY 1 Red Green
– – 0 FY FY 0 Red Yellow
– – 1 FY HG 1 Red Yellow
SA1: HG = 00 HY = 01 FG = 11 FY = 10
SA2: HG = 00 HY = 10 FG = 01 FY = 11
SA3: HG = 0001 HY = 0010 FG = 0100 FY = 1000 (one-hot)
Traffic light controller FSM
• Specification of inputs, outputs, and state elements
module FSM(HR, HY, HG, FR, FY, FG, ST, TS, TL, C, reset, Clk);
output HR;
output HY;
output HG;
parameter highwaygreen = 6'b001100;
output FR;
parameter highwayyellow = 6'b010100;
output FY;
parameter farmroadgreen = 6'b100001;
output FG;
parameter farmroadyellow = 6'b100010;
output ST;
input TS;
input TL;
assign HR = state[6];
input C;
assign HY = state[5];
input reset;
assign HG = state[4];
input Clk;
assign FR = state[3];
assign FY = state[2];
reg [6:1] state;
assign FG = state[1];
reg ST;
specify state bits and codes
for each state as well as
connections to outputs
Traffic light controller FSM
initial begin state = highwaygreen; ST = 0; end
always @(posedge Clk)
case statement
begin
if (reset)
triggerred by
begin state = highwaygreen; ST = 1; end clock edge
else
begin
ST = 0;
case (state)
highwaygreen:
if (TL & C) begin state = highwayyellow; ST = 1; end
highwayyellow:
if (TS) begin state = farmroadgreen; ST = 1; end
farmroadgreen:
if (TL | !C) begin state = farmroadyellow; ST = 1; end
farmroadyellow:
if (TS) begin state = highwaygreen; ST = 1; end
endcase
end
end
endmodule
Timer FSM for traffic light controller
module Timer(TS, TL, ST, Clk);
output TS;
output TL;
input ST;
input Clk;
integer value;
assign TS = (value >= 4); // 5 cycles after reset
assign TL = (value >= 14); // 15 cycles after reset
always @(posedge ST) value = 0; // async reset
always @(posedge Clk) value = value + 1;
endmodule
Complete traffic light controller
• Tying it all together (FSM + timer) with structural Verilog (same as a
schematic drawing)
module main(HR, HY, HG, FR, FY, FG, reset, C, Clk);
output HR, HY, HG, FR, FY, FG;
input reset, C, Clk;
Timer part1(TS, TL, ST, Clk);
FSM part2(HR, HY, HG, FR, FY, FG, ST, TS, TL, C, reset, Clk);
endmodule
traffic light
controller
ST TS TL
timer
Finite state machines summary
• Models for representing sequential circuits
– abstraction of sequential elements
– finite state machines and their state diagrams
– inputs/outputs
– Mealy, Moore, and synchronous Mealy machines
• Finite state machine design procedure
– deriving state diagram
– deriving state transition table
– determining next state and output functions
– implementing combinational logic
• Hardware description languages
– Use good coding style
– Communicating FSMs
CSE140L: Components and Design
Techniques for Digital Systems Lab
Programmable Logic Devices
Tajana Simunic Rosing
17
Source: Vahid, Katz, Culler
Evolution of Programmable Technologies
• Discrete devices: relays, transistors (1940s-50s)
• Discrete logic gates (1950s-60s) trend toward
higher levels
• Integrated circuits (1960s-70s)
of integration
– Map circuit to Data Book parts
– e.g. TTL packages: Data Book for 100’s of different parts
• Gate Arrays (IBM 1970s)
– “Custom” integrated circuit chips
– Transistors are already on the chip
– Place and route software puts the chip together automatically
– + Large circuits on a chip
– + Automatic design tools (no tedious custom layout)
– - Only good if you want 1000’s of parts
Programmable Logic Technologies
• Fuse and anti-fuse
– Fuse makes or breaks link between two wires
– Typical connections are 50-300 ohm
– One-time programmable (testing before programming?)
– Very high density
• EPROM and EEPROM
– High power consumption
– Typical connections are 2K-4K ohm
– Fairly high density
• RAM-based
– Memory bit controls a switch that connects/disconnects two wires
– Typical connections are .5K-1K ohm
– Can be programmed and re-programmed in the circuit
– Low density
Comparing RAM
REGISTER FILE OUT1 OUT2 OUT3 OUT4
• Register file
– Fastest
R S R S R S R S
– But biggest size D Q D Q D Q D Q
CLK
IN1 IN2 IN3 IN4
SRAM
• SRAM
– Fast (e.g. 10ns)
– More compact than register file Data' Data
• DRAM
– Slowest (e.g. 20ns) DRAM
• And refreshing takes time
Data
– But very compact W
– Different technology for large caps.
20
ROM Types 1 data line 0 data line
cell cell
• Mask-programmed ROM word
enable
– Programmed at manufacturing time
• Fuse-Based Programmable ROM
1 data line 1 data line
– Programming blows fuses
cell cell
– One-Time Programmable ROM
• EPROM word
enable
– Erase with ultraviolet light
• EEPROM fuse blown fuse
– Erasing one word at a time electronically
• Flash
floating-gate
data line data line
– Erase large blocks of words simultaneously
transistor
cell cell
1 0
word eÐeÐ
enable
trapped electrons
21
Memory in Verilog
• Modeled as an array of registers
22
Source: John Wawrzynek
Programmable Logic Devices (PLD)
• PLDs combine PLA/PAL with memory and other advanced
structures
– Similar to PLA/PAL, hence Field-Programmable Gate Arrays
• Types:
– Antifuse PLDs
– EPLD & EEPLD
– FPGAs with RAMs
– FPGA with processing
• Digital Signal Processing
• General purpose CPU
23
Field-Programmable Gate Arrays
• Logic blocks
– To implement combinational
and sequential logic
• Interconnect
– Wires to connect inputs and
outputs to logic blocks
• I/O blocks
– Special logic blocks at
periphery of device for
external connections
• Key questions:
– How to make logic blocks programmable?
– How to connect the wires?
– After the chip has been manufactured
Antifuse PLDs
• Actel’s Axcelerator Family
• Antifuse:
– open when not programmed
– Low resistance when programmed25
Actel’s Axcelerator C-Cell
• C-Cell
– Basic multiplexer logic plus
more inputs and support for fast
carry calculation
– Carry connections are “direct”
and do not require propagation
through the programmable
interconnect
Actel’s Accelerator R-Cell
• R-Cell
– Core is D flip-flop
– Muxes for altering the clock and
selecting an input
– Feed back path for current value
of the flip-flop for simple hold
– Direct connection from one C-cell
output of logic module to an R-cell
input; Eliminates need to use the
programmable interconnect
• Interconnection Fabric
– Partitioned wires
– Special long wires
Altera’s Erasable Programmable Logic Devices (EPLDs)
• Historical Perspective
– PALs: same technology as programmed once bipolar PROM
– EPLDs: CMOS erasable programmable ROM (EPROM) erased by UV light
• Altera building block = MACROCELL
CLK
Clk
MUX
8 Product Term
AND-OR Array
+ I/O Pin
Output
AND pad
MUX
Programmable ARRAY
Q
MUX's Inv ert
Control
F/B
MUX Seq. Logic
Block
Programmable polarity Programmable feedback
Altera EPLD: Synchronous vs. Asynchronous Mode
Altera EPLDs contain 10s-100s of independently programmed macrocells
Global
Synchronous Mode
Personalized CLK Clk
by EPROM
MUX
1
bits: Flipflop controlled
OE/Local CLK by global clock signal
Q local signal computes
EPROM output enable
Cell
Global
CLK Clk Asynchronous Mode
MUX
1
Flipflop controlled
OE/Local CLK by locally generated
Q
clock signal
EPROM
Cell
+ Seq Logic: could be D, T positive or negative edge triggered
+ product term to implement clear function
Altera Multiple Array Matrix (MAX)
AND-OR structures are relatively limited
Cannot share signals/product terms among macrocells
Logic Global Routing:
Array LAB A LAB H
Programmable
Blocks Interconnect
Array
(similar to
macrocells) LAB B LAB G EPM5128:
P 8 Fixed Inputs
I 52 I/O Pins
A 8 LABs
LAB C LAB F 16 Macrocells/LAB
32 Expanders/LAB
LAB D LAB E
Altera’s EEPLD
• Altera’s MAX 7k Block Diagram
31
EEPLD
• Altera’s MAX 7k Logic Block
32
SRAM based PLD
• Altera’s Flex 10k Block Diagram
33
SRAM based PLD
• Altera’s Flex 10k Logic Array Block (LAB)
34
SRAM based PLD
• Altera’s Flex 10k Logic Element (LE)
35
FPGA with DSP
• Altera’s Stratix II: Block Diagram
36
FPGA with DSP
• Altera’s Stratix II:
– DSP Detail
37
FPGA with General Purpose CPU & Analog
• Actel’s Fusion Family Diagram
– FPGA with ARM 7 CPU and Analog Components
38
Programmable Logic Summary
• Discrete Gates
• Packaged Logic
• PLAs
• Ever more general architectures of programmable combinational +
sequential logic and interconnect
– Altera
– Actel
– Xilinx
