Chapter 7 Notes

 

Moore Machine - Output depends only upon current state. Mod-4 counter.

The state description of the sequential system is:  Input:    None other than clock.  Output: z(t) element of {00,01,10,11}  State:    s(t) element of {A, B, C, D}  Initial:    s(0)=A  Functions:  Present |  Next     | Output s(t)    |  s(t+1)   | z(t)    A      |     B     | 00  B      |     C     | 01  C      |     D     | 10  D      |     A     | 11

Synchronous sequential systems change from the present state to the next state at discrete time intervals defined by a synchronizing clock signal. The state change occurs either on the rising or falling clock edge. The wave form above shows that the state and output changes with each rising clock edge.

Synchronous Systems in VHDL - The VHDL that would correspond to the above diagram and produce the wave form is given below:  Note that clk'EVENT AND clk='1' means that a change occurred in the clk signal and the clk signal is '1'.
 

Synchronous Sequential Systems with Input - Most interesting sequential systems require some external input for control of which state is executed next. Synchronized systems change from the present state to the next state on an active clock. The next state is determined based upon the present state and the input at the the active clock edge.

 

Mealy Machine - Output depends upon present state and input.

The state description of the sequential system is:  Input:    x(t) element of {0,1}  Output: z(t) element of {0,1}  State:    s(t) element of {A, B, C, D}  Initial:    s(0)=A  Functions:  Present |   Next, Output s(t)    |    Input x(t)               |      0      1     A      |     A,0    B,0  B      |     C,0    B,0  C      |     A,0    D,0  D      |     A,0    A,1           |    s(t+1), z(t)

An example where the input sequence is 1110... illustrates that the system stays in State B as long as in State B and the input remains 1. It is important to note that the input and present state determine the next state. The decision of the next state is made at the moment of the rising clock signal.

Graphical Representation Conventions

Unconditional transition from State A to State B, no output.
Moore machine Unconditional transition from State A to State B.  Output 00 while in State A, output 01 while in State B.
Moore machine Conditional transfer from State A to State B when input is 1.  Output 00 while in State A, output 01 while in State B.
Mealy machine Conditional transfer from State A to State B when input is 1, from A to A when input is 0.  Output 00 while in State A and input is 0, output 01 while in State A and input is 1.

Parity Generator State Diagram

Input:        x(t) element of {0,1}  Output:     z(t) element of {0,1}  State:        s(t) element of {Even, Odd}  Initial:        s(0) = Even  Function:   z(t) = 1 if x(0,t) contains odd number of 1's otherwise 0  Present |   Next, Output s(t)    |    Input x(t)              |      0      1       Even   |    Even,0  Odd, 1  Odd    |    Odd,1   Even,0          |    s(t+1), z(t)

t | 0    1    2    3   4   5    6    7   8   
x | 1    0    0    0   1   0    1    1       
s | Even Odd  Odd  Odd Odd Even Even Odd Even
z | 0    1    1    1   1   0    0    1   0 

• Finite State Machines - Have a finite number of states. The parity generator example has two states so is a finite state machine (FSM).
• Finite Memory -  Depends only upon a finite number of inputs, the parity generator is not a finite memory system since it depends upon all previous inputs.

In the diagram below the output, z=00, 01, 10, 11, etc. is from the Mod-4 counter. When a comparator detects the 11 is output, a bell is rang, otherwise a light is turned on for the other counts. Additional logic determines when the output of the Mod-4  counter is z=11. The counter is unchanged but through its output acts as a controller. Alternatively, the Mod-4 counter could have an additional output that was true when in State D.

Autonomous Controller

As a non-autonomous example, consider a Mod-4 counter that outputs a control signal true (1) when the count output z =11 and a pushbutton is down (true or 1), other logic of the system rings a bell. Otherwise the bell is silent.

Non-autonomous Controller

 

Functions: 

Present |  Next, Output
s(t)    |  Input PB(t)     
        |     0      1     
 A      |     B, 0   B, 0
 B      |     C, 0   C, 0
 C      |     D, 0   D, 0
 D      |     A, 0   A, 1  
        | s(t+1), Bell(t)

7.6 Equivalent Sequential Systems and Minimization of the Number of States

The key insight required for minimization is that if, given the same inputs, two systems produce the same output, the systems are equivalent, that is one can replace the other. A simplistic example is given in the following diagram at left where State A and B produce the same output given the same input, the more complex diagram may be functionally replaced by the simpler at right.
 

Equivalent State Diagrams

• Distinguishable states - Essentially, two states, A and B, are different if a given input produces a different output for A than for B.
• Equivalent states - A and B states are equivalent if the same output is produced by either given the same input.

Problem 7.15
Page 192

  |   Input 
PS| x=0 x=1 
a | f,0 b,0
b | d,0 c,0
c | f,0 e,0
d | g,1 a,0
e | d,0 c,0
f | f,1 b,1
g | g,0 h,1
h | g,1 a,0
  |NS, Output        
  

PS|Input x(t) 
  | a    b    
S0| S1,p S2,q        
S1| S1,r S0,p
S2| S1,p S2,s 
  | NS, Output
          z(t)

PS|Input x(t)  
  | 0     1    
00| 01,00 10,01
01| 01,10 00,00
10| 01,00 10,11
  | NS, Output
  |       z(t)

The text example of Example 7.19 (page 187) demonstrates the implementation of a Mealy machine, one in which the output depends on the present state and input and can change while in a state of the FSM. The Moore machine differs in that output depends only upon the present state and does not change while in a state but remains fixed until another state is entered. The key difference is that Moore machine outputs change only when the present state changes, on the active clock edge. This has two desirable effects: 1) synchronizing the FSM outputs with the system clock and, 2) output is stable throughout the state.

Unfortunately, Moore machines are also generally more complex, requiring more states since the output cannot vary while in a given state. For example, a Mealy machine can in one state produce output based upon the binary value of two input variables a and b when ab=00, 01, 10, and 11. A Moore machine would require four states, one for ab=00, 01, 10, and 11.

The weakness of pure Mealy machines is they produce output based upon input that can change at any time without regard to the system clock. This undesirable since asynchronous inputs can lead to small or runt pulses on the outputs (the very short 01 output in the first simulation figure below) while the Moore machine guarantees that all outputs will be stable throughout the time between clock pulses.

To combine the simplicity of Mealy with the stability of outputs of the Moore machines we will use Mealy machines but enforce synchronized inputs. The general approach followed in the example at right below, is to assign input x to a signal synchX only when the clock signal is rising. When the present state is changed, the outputs are computed based upon the present state and the synchronized input.

In the wave form simulation below note the output for the Mealy machine with input that is not synchronized with the clock (asynchronous inputs) leading to a small or runt pulse on the outputs (the very short 01 output) while the Mealy with synchronized inputs or a Moore machine guarantees that all outputs will be stable throughout the time between clock pulses.

One additional artifact of synchronizing inputs is that state changes are delayed by one clock after the inputs change. This is due to the one active clock required to synchronize the input. The next clock has the synchronized input for the state change. This is particularly noticeable in the last simulation where the synchronized version stays longer in state S0 because of the one clock delay. This form will be generally used in this class due to its relative clarity of presentation.
 
 

Mealy Design for Figure 7.19

PS|Input x(t)     | 0     1     S0| S0,00 S1,00         S1| S2,01 S3,10 S2| S0,10 S1,01 S3| S2,11 S3,11   | NS, Output           z(t)

Machine Simulation

-- Example 7.19  -- Mealy Machine with asynchronous input x   ENTITY mealy IS      PORT(          clk : IN BIT;            x  : IN BIT;            z  : OUT BIT_VECTOR(1 DOWNTO 0);   END moore;   ARCHITECTURE behavioral OF mealy IS        TYPE STATE_TYPE IS (S0, S1, S2, S3);        SIGNAL presentS, nextS: STATE_TYPE;   BEGIN       PROCESS (clk)  -- Change next State &       BEGIN                -- Output on RISING clock        IF clk'EVENT AND clk = '1' THEN           CASE presentS IS                 WHEN S0 =>                      IF x='0' THEN nextS <= S0;                                              z <= "00";                      ELSE               nextS <= S1;                                              z <= x & NOT (x);                      END IF;                 WHEN S1 =>                     IF x='0' THEN nextS <= S2;                                              z <= NOT(x) & x;                     ELSE               nextS <= S3;                                              z <= "11";                     END IF;                 WHEN S2 =>                     IF x='0' THEN nextS <= S0;                                             z <= "00";                     ELSE               nextS <= S1;                                             z <= x & NOT (x);                      END IF;                 WHEN S3 =>                     IF x='0' THEN nextS <= S2;                                             z <= NOT(x) & x;                     ELSE               nextS <= S3;                                             z <= "11";                     END IF;           END CASE;        END IF;      END PROCESS;      PROCESS (nextS)      BEGIN   -- Change present State to next State          presentS <= nextS;      END PROCESS;   END behavioral; -- Example 7.19  -- Mealy Machine with synchronous input x  ENTITY Ex7_19 IS      PORT(        clk : IN BIT;          x  : IN BIT;          z  : OUT BIT_VECTOR(1 DOWNTO 0));   END Ex7_19;   ARCHITECTURE behavioral OF Ex7_19 IS        TYPE STATE_TYPE IS (S0, S1, S2, S3);        SIGNAL state : STATE_TYPE;     SIGNAL synchX : BIT;   BEGIN       PROCESS (clk)       BEGIN         IF clk'EVENT AND clk = '1' THEN            synchX <= x;   -- synchronized input x            CASE state IS                 WHEN S0 =>                     IF synchX='0'  THEN state <= S0;                    ELSE                          state <= S1;                     END IF;                 WHEN S1 =>                     IF synchX='0' THEN state <= S2;                     ELSE                         state <= S3;                     END IF;                 WHEN S2 =>                     IF synchX='0' THEN state <= S0;                     ELSE                         state <= S1;                     END IF;                 WHEN S3 =>                     IF synchX='0' THEN state <= S2;                     ELSE                         state <= S3;                     END IF;           END CASE;        END IF;      END PROCESS;      PROCESS (state, synchX)  -- Change output      BEGIN                                -- on synchronized        CASE state IS                   -- input and state           WHEN S0 =>  z <= "00";           WHEN S1 =>  z <= synchX & NOT (synchX);           WHEN S2 =>  z <= NOT(synchX) & synchX;           WHEN S3 =>  z <= "11";         END CASE;      END PROCESS;   END behavioral;

Mealy Machine with Asynchronous Input x (Example 7.19)

Mealy Machine with Synchronized Input x (Modified Example 7.19)

-- Mealy Machine with synchronized inputs and separate present and next states  ENTITY synchFSM IS       PORT( clk   : IN BIT;                       x  : IN BIT;                       z  : OUT BIT_VECTOR(1 DOWNTO 0);    END synchFSM;   ARCHITECTURE behavioral OF synchFSM IS        TYPE STATE_TYPE IS (S0, S1, S2, S3);        SIGNAL presentS, nextS: STATE_TYPE;        SIGNAL synchX : BIT;   BEGIN       PROCESS (clk)                                 -- Present to Next State change on RISING clock edge       BEGIN        IF clk'EVENT AND clk = '1' THEN            synchX <= x;          CASE presentS IS                 WHEN S0 => IF synchX='0' THEN nextS <= S0;                                        ELSE                     nextS <= S1;                                        END IF;                 WHEN S1 => IF synchX='0' THEN nextS <= S2;                                        ELSE                      nextS <= S3;                                        END IF;                 WHEN S2 => IF synchX='0' THEN nextS <= S0;                                        ELSE                     nextS <= S1;                                        END IF;                 WHEN S3 => IF synchX='0' THEN nextS <= S2;                                        ELSE                     nextS <= S3;                                        END IF;           END CASE;        END IF;      END PROCESS;      PROCESS (nextS)               -- Change present State      BEGIN                                 -- after rising clock edge            presentS <= nextS;            CASE presentS IS                 WHEN S0 => z <= "00";                 WHEN S1 => z <= synchX & NOT(synchX);                 WHEN S2 => z <= NOT(synchX) & synchX;                WHEN S3 => z <= "11";           END CASE;      END PROCESS;   END behavioral;

The preferred implementation is the final example above. It is a Mealy machine with synchronized inputs and uses separate present and next state to more clearly distinguish the process of the FSM. The following example illustrates how the clock can serve to synchronize inputs. Notice that the x input occurs at any time relative to the active clock edge but the synchronized x occurs in synchronization with the clock.
 

-- synchronized input  ENTITY synchIN IS       PORT(   clk   : IN BIT;                         x  : IN BIT;             synchX : OUT BIT);   END synchIN;   ARCHITECTURE behavioral OF synchIN IS   BEGIN       PROCESS (clk)       BEGIN         IF clk'EVENT AND clk = '1'           THEN synchX <= x;          -- synchronized  input x         END IF;      END PROCESS;   END behavioral;