EE 360M - Digital Systems Design Using VHDL

Chapter 5
Lizy K. John
University of Texas at Austin

© Copyright Dr. Lizy John, The University of Texas at Austin

 CHAPTER 5
 Chapter 5
 State Machine Charts (SM Charts)
 Microprogramming
STATE MACHINE CHARTS (SM CHARTS)
 State Machine Charts (SM Charts)
 a.k.a., Algorithmic State Machine Charts (ASM)
 Resemble Software Flow Charts
 Substitute for State Graph
 Advantages of SM Charts over State Graphs
 Easier to Understand Operation of Digital System
 Necessary Conditions for Transitions
Automatically Satisfied
 Directly Leads to Behavior Models and Hardware
Realization
PRINCIPAL COMPONENTS OF SM CHART
EXAMPLE OF SM BLOCK
EQUIVALENT SM BLOCKS
SM BLOCK FOR COMBINATIONAL CIRCUIT
DRAW CORRESPONDING HARDWARE
 SM BLOCK WITH FEEDBACK
 No Internal Feedback Allowed in SM Block
EQUIVALENT SM BLOCKS
CONVERSION FROM STATE GRAPH
TIMING CHART
SM CHART FOR BINARY MULTIPLIER
SM CHART FOR BINARY MULTIPLIER
entity Mult is
port(CLK, St, K, M: in bit;
Load, Sh, Ad, Done: out bit);
end Mult;
architecture SMbehave of Mult is
signal State, Nextstate: integer range 0 to 3;
begin
process(St, K, M, State) -- start if state or inputs change
begin
begin
Load <= '0'; Sh <= '0'; Ad <= '0'; Done <= '0';
case State is
when 0 =>
if St = '1' then -- St (state 0)
Load <= '1';
Nextstate <= 1;
else Nextstate <= 0; -- St'
end if;
when 1 =>
if M = '1' then -- M (state 1)
Ad <= '1';
Nextstate <= 2;
else -- M'
Sh <= '1';
if K = '1' then Nextstate <= 3; -- K
else Nextstate <= 1; -- K'
end if;
end if;
when 2 =>
Sh <= '1'; -- (state 2)
if K = '1' then Nextstate <= 3; -- K
else Nextstate <= 1; -- K'
end if;
when 3 =>
Done <= '1'; -- (state 3)
Nextstate <= 0;
end case;
 process(CLK)
begin
if CLK = '1' and CLK'event then
State <= Nextstate; -- update state on rising edge
end if;
end process;
end SMbehave;
 DICE GAME
 Two Dice – Each with Value 1 to 6
 After First Roll of Dice
• Player Wins If Sum 7 or 11
• Player Loses If Sum 2, 3, or 12
• Otherwise, Sum Obtained on First Roll Referred to as
Point
– Must Roll Again
 On Second or Subsequent Roll of Dice
• Player Wins If Sum Equals Point
– Loses If Sum 7
• Otherwise, Roll Again Until Win or Lose
FLOWCHART FOR DICE GAME
 BLOCK DIAGRAM FOR DICE GAME
 Architecture (Data Path)
 SIGNALS FOR DICE GAME
D7 = 1 if Sum of Dice 7
D711 = 1 if Sum of Dice 7 or 11
D23l2 = 1 if Sum of Dice 2, 3, or 12
Eq = 1 if Sum of Dice Equals Number Stored in Point Reg
Rb = 1 when Roll Button Pressed
Reset = 1 when Reset Rutton Pressed

Roll = 1 Enables Dice Counters

Sp = 1 Causes Sum to be Stored in Point Register
Win = 1 Turns on Win Light
Lose = 1 Turns on Lose Light
STATE GRAPH FOR DICE GAME
entity DiceGame is
port(Rb, Reset, CLK: in bit;
Sum: in integer range 2 to 12;
Roll, Win, Lose: out bit);
end DiceGame;
architecture DiceBehave of DiceGame is
signal State, Nextstate: integer range 0 to 5;
signal Point: integer range 2 to 12;
signal Sp: bit;
begin
process
begin
Sp <= '0'; Roll <= '0'; Win <= '0'; Lose <= '0';
case State is
when 0 => if Rb = '1' then Nextstate <= 1; end if;
when 1 =>
if Rb = '1' then Roll <= '1';
elsif Sum = 7 or Sum = 11 then Nextstate <= 2;
elsif Sum = 2 or Sum = 3 or Sum =12 then Nextstate <= 3;
else Sp <= '1'; Nextstate <= 4;
end if;
when 2 => Win <= '1';
if Reset = '1' then Nextstate <= 0; end if;
when 3 => Lose <= '1';
if Reset = '1' then Nextstate <= 0; end if;
when 4 => if Rb = '1' then Nextstate <= 5; end if;
when 5 =>
if Rb = '1' then Roll <= '1';
elsif Sum = Point then Nextstate <= 2;
elsif Sum = 7 then Nextstate <= 3;
else Nextstate <= 4;
end if;
end case;
end process;
 process(CLK)
begin
if CLK'event and CLK = '1' then
State <= Nextstate;
if Sp = '1' then Point <= Sum; end if;
end if;
end process;
end DiceBehave;
DICE GAME WITH TEST BENCH
 TEST BENCH
 Initially Supply Rb Signal
 When DiceGame Responds with Roll Signal
 Supply Sum Signal which Represents Sum of Two
Dice
 If No Win or Lose Signal Generated by DiceGame
 Repeat Steps 1 and 2 to Roll Again
 When Win or Lose Signal Detected
 Generate Reset Signal and Start Again
SM CHART FOR DICE GAME TEST
entity GameTest is
port(Rb, Reset: out bit;
Sum: out integer range 2 to 12;
CLK: inout bit;
Roll, Win, Lose: in bit);
end GameTest;
architecture dicetest of GameTest is
signal Tstate, Tnext: integer range 0 to 3;
signal Trig1: bit;
type arr is array(0 to 11) of integer;
constant Sumarray:arr := (7, 11, 2, 4, 7, 5, 6, 7, 6, 8, 9, 6);
begin
CLK <= not CLK after 20 ns;
 process(Roll, Win, Lose, Tstate)
variable i: natural; -- i is initialized to
0
begin
case Tstate is
when 0 => Rb <= '1'; -- wait for Roll
Reset <= '0';
if i >= 12 then Tnext <= 3;
elsif Roll = '1' then
Sum <= Sumarray(i); i := i + 1; Tnext <= 1;
end if;
when 1 => Rb <= '0'; Tnext <= 2;
when 2 => Tnext <= 0;
Trig1 <= not Trig1; -- toggle
Trig1
if (Win or Lose) = '1' then Reset <= '1'; end if;
when 3 => null; -- Stop state
end case;
end process;
 process(CLK)
begin
if CLK = '1' and CLK'event then
Tstate <= Tnext;
end if;
end process;
end dicetest;
entity tester is
end tester;
architecture test of tester is
component GameTest
port(Rb, Reset: out bit; Sum: out integer range 2 to 12; CLK: inout bit;
Roll, Win, Lose: in bit);
end component;
component DiceGame
port(Rb, Reset, CLK: in bit; Sum: in integer range 2 to 12;
Roll, Win, Lose: out bit);
end component;
signal rb1, reset1, clk1, roll1, win1, lose1: bit;
signal sum1: integer range 2 to 12;
begin
Dice: Dicegame port map (rb1, reset1, clk1, sum1, roll1, win1, lose1);
Dicetest: GameTest port map (rb1, reset1, sum1, clk1,
roll1,win1,lose1);
end test;
 SIMULATION AND COMMAND FILE
list /dicetest/trig1 -NOTrigger sum1 win1 lose1
/dice/point
run 2000
ns delta trig1 sum1 win1 lose1 point
0 +0 0 2 0 0 2
100 +3 0 7 1 0 2
260 +3 0 11 1 0 2
420 +3 0 2 0 1 2
580 +2 1 4 0 0 4
740 +3 1 7 0 1 4
900 +2 0 5 0 0 5
1060 +2 1 6 0 0 5
1220 +3 1 7 0 1 5
1380 +2 0 6 0 0 6
1540 +2 1 8 0 0 6
1700 +2 0 9 0 0 6
1860 +3 0 6 1 0 6
 REALIZATION OF SM CHARTS
 Procedure for Deriving Next State Equation
 Identify All States in Which Q=1
 For Each State
• Find Link Paths Leading into State
 For Each Link Path
• Find Term That is 1 When Link Path Followed
– For Link Path from Si to Sj, Term is 1 If
Machine in State Si and Will Exit to Sj
 Expression for Q+ Formed By ORing Together
Terms
 REALIZATION OF SM CHARTS

B+=

A+=
 SM CHART FOR MULTIPLIER
Load = A'B'St
Sh = A'BM'(K' + K) +
AB'(K' + K) = A'BM' + AB'
Ad = A'BM
Done = AB

A+ = A'BM'K + A'BM + AB'K =

A'B(M + K) + AB'K
B+ = A'B'St + A'BM'(K' + K) +
AB'(K' + K) = A'B'St + A'BM' + AB'
 STATE TRANSITION TABLE

 Calculate Size of ROM Implementation

 IMPLEMENTATION OF MULTIPLIER CONTROL

 Need to Implement
 2 Next State Equations
 4 Output Equations
 2 Flip-Flops to Store State

 ROM
 Discrete Gates
 PAL/GAL
 FPGA
 CPLD
Implementation of
Dice Game

What are the

involved steps?
 IMPLEMENTATION OF DICE GAME

 States 110 and 111 Not Used

 Can Treat as Don’t Cares
 K-MAPS FOR DICE GAME
Use map-entered variables in K-map

A+ B+ Win

E1 = D'711 D'2312 R = Reset

E2 = D'7 Eq' E3 = D711 + D'711 D2312 = D711 + D2312
E4 = Eq + Eq'D7 = Eq + D7
 RESULTING EQUATIONS
 A+ = A'B'C Rb'D'711D'2312 + AC ' + ARb + AD'7Eq'
 B+ = A'B'C Rb'(D711+ D2312) + BReset' + AC Rb'(Eq + D7)
 C+ = B'Rb + A'B'C D'711D2312 + BC Reset' + AC D7Eq'
 Win = BC '
 Lose = BC
 Roll = B'CRb
 Sp = A'B'C Rb'D'711D'2312
IMPLEMENTATION OF DICE GAME
architecture Dice_Eq of DiceGame is
signal Sp,Eq,D7,D711,D2312: bit:='0';
signal DA,DB,DC,A,B,C :bit:='0';
signal Point: integer range 2 to 12;
begin
process(CLK)
begin
if CLK = '1' and CLK'event then
A <= DA; B <= DB; C <= DC;
if Sp = '1' then Point <= Sum; end if;
end if;
end process;
 Win <= B and not C;
Lose <= B and C;
Roll <= not B and C and Rb;
Sp <= not A and not B and C and not Rb and not D711 and not D2312;
D7 <= '1' when Sum = 7 else '0';
D711 <= '1' when (Sum = 11) or (Sum = 7) else '0';
D2312 <= '1' when (Sum = 2) or (Sum = 3) or (Sum = 12) else '0';
Eq <= '1' when Point=Sum else '0';
DA <= (not A and not B and C and not Rb and not D711 and not
D2312) or (A and not C) or (A and Rb) or (A and not D7 and not Eq);
DB <= ((not A and not B and C and not Rb) and (D711 or D2312)) or
(B and not Reset) or ((A and C and not Rb) and (Eq or D7));
DC <= (not B and Rb) or (not A and not B and C and not D711 and
D2312) or (B and C and not Reset) or (A and C and D7 and not
Eq);
end Dice_Eq;
entity Counter is
port(Clk, Roll: in bit; Sum: out integer range 2 to 12);
end Counter;
architecture Count of Counter is
signal Cnt1, Cnt2: integer range 1 to 6 := 1;
begin
process(Clk)
begin
if Clk = '1' then
if Roll = '1' then
if Cnt1 = 6 then Cnt1 <= 1; else Cnt1 <= Cnt1 + 1; end if;
if Cnt1 = 6 then
if Cnt2 = 6 then Cnt2 <= 1; else Cnt2 <= Cnt2 + 1; end if;
end if;
end if;
end if;
end process;
Sum <= Cnt1 + Cnt2;
end Count;
entity Game is
port(Rb, Reset, Clk: in bit; Win, Lose: out bit);
end Game;
architecture Play1 of Game is
component Counter
port(Clk, Roll: in bit; Sum: out integer range 2 to 12);
end component;
component DiceGame
port(Rb, Reset, CLK: in bit; Sum: in integer range 2 to 12;
Roll, Win, Lose: out bit);
end component;
signal roll1: bit;
signal sum1: integer range 2 to 12;
begin
Dice: Dicegame port map (Rb, Reset, Clk, sum1, roll1, Win, Lose);
Count: Counter port map (Clk, roll1, sum1);
end Play1;
 PSEUDO-CODE OF CONTROLLER
S0: If St true, produce Load Signal and go to S1,
else return to S0
S1: If M is true, produce Ad and go to S2,
else produce Sh, check whether K is 1;
if K is 1 go to S3;
if K is 0, go to S1;
S2: Produce Sh;
If K=0, go to S1;
else go to S3;
S3: Produce Done and go to S0
 HARDWIRING
 Hardwiring
 Implement Controller with Discrete Gates
 Advantages
• Faster Controller
 Disadvantages
• Hard to Debug and Fix
• Not Easily Modifiable
 MICROPROGRAMMING
 Microprogramming
 Implement Algorithm of Controller as
Microinstructions in Memory (ROM)
• Memory Called
– Control Store
– Microprogram Memory
• Sequence Through Microinstructions
 Advantages
• Easy to Debug and Fix
• Easily Modifiable
 Disadvantage
• Slow
 MICROPROGRAMMING
 Used in Early Microprocessors
 E.g., Intel 8086, Motorola 68000
 Attractive for CISC Processors
 Useful when Debugging Difficult
 RISC (Reduced Instruction Set Computing)
 In Late 70’s, Controller Using Over Half Memory for
CISC Processor
 Developed Simple Instruction Sets with Simple
Controllers
 CAD Tools and Debugging More Effective
 Microprogramming Less Attractive today than long
ago, but still used.
TYPICAL MICROPROGRAM IMPLEMENTATION

 SM Chart Must Use Moore Outputs

 Two Possible Next States
 TRANSFORM SM CHART
 To Implement SM Chart in Microcontroller
 Transform SM Chart
• Eliminate Conditional Outputs
– Make All Outputs Moore Outputs
• Allow Only Single Input (“Qualifier”) Per State
 May Increase Number of States
• But Reduces Microprogram Size

Qualifier - means – Input to the SM Chart i.e. Diamond

TRANSFORMING MULTIPLIER SM CHART
2 steps

1. Convert all Mealy

Outputs to Moore
(add states if required)

2. Make sure only

1 qualifier per state
STATE MINIMIZATION
Combine states if possible
TYPICAL MICROPROGRAM IMPLEMENTATION

 MUX Size Depends on Number of Qualifiers

MULTIPLIER MICROCONTROLLER
TWO ADDRESS MICROPROGRAM

Add microprogram for state S3 to this table

Who invented microprogramming? When?

 SINGLE ADDRESS MICROPROGRAM
 Next State is Sequential Unless Qualifier True
 Only Next State True (NST) Specified
 Analogous Branches in Conventional Software
SERIAL STATE ASSIGNMENT
SINGLE ADDRESS MICROPROGRAM
State ABC TEST NST Load Ad Sh Done
S0 000 St’ 000 S0 1 0 0 0
S01 001 X 010 S1 1 0 0 0
S1 010 M 101 S11 0 0 0 0
S2 011 K’ 010 S1 0 0 1 0
S3 100 X 000 S0 0 0 0 1
S11 101 X 011 S2 0 1 0 0
 COMPARISON

Size of ROM

Method
#entries ×
# bits
width

ROM method original SM chart 32 × 6 192 bits

Two address microcode 6 × 12 72 bits

Single address microcode 6×9 54 bits

DICE GAME - TWO ADDRESS MICROPROGRAM
MUX FOR TWO-ADDRESS MICROPROGRAM
TWO-ADDRESS MICROPROGRAM FOR DICE GAME

 What is Size of ROM?

MUX FOR SINGLE ADDRESS MICROCODING
 SINGLE-ADDRESS MICROCODING
State ABCD TEST NST ROLL Sp Win Loose
S0 0000 000 0000 0 0 0 0
S1 0001 001 0001 1 0 0 0
S11 0010 010 1111 0 0 0 0
S12 0011 011 1001 0 0 0 0
S13 0100 111 0101 0 1 0 0
S4 0101 000 0101 0 0 0 0
S5 0110 001 0110 1 0 0 0
S51 0111 100 1111 0 0 0 0
S52 1000 101 0101 0 0 0 0
S3 1001 110 1001 0 0 0 1
Sx 1010 111 0000 0 0 0 0
S2 1111 110 1111 0 0 1 0
 COMPARISON

Size of ROM
Method
#entries ×
#bits
width

ROM method original SM chart 512 × 7 3584 bits

Two address microcode 11 × 15 165 bits

Single address microcode 12 × 11 132 bits

SERIALLY LINKED STATE MACHINES