courses:system_design:synthesis:finite_state_machines_and_vhdl:medvedev

FSM: Medvedev

Fundamentals

Medvedev State Circuit

  • The output vector resembles the state vector: Y = S

Two Processes 

architecture RTL of MEDVEDEV is
     ...
begin
  REG: process (CLK, RESET)
  begin
    -- State Registers Inference
  end process REG;
 
  CMB: process (X, STATE)
  begin
    -- Next State Logic
  end process CMB;
 
   Y <= S;    -- no output logic
end RTL
no output logic

Notes

The difference between the three types of state machines known in theory (Medvedev, Moore and Mealy machines) is the way the output is generated.

In the Medvedev machine the value of the output is identical with the state vector of the finite state machine.

That means, the logic for the output consists only out of wires; namely the connection from the state vector registers to the output ports.

This is done in VHDL by a simple signal assignment which is shown in the example above.

Concurrent assignments are used here.

Problem with Medvedev:

  • Synthesis tools generally do their own “state-encoding” - that's a problem, if the output of the automaton has to controll an other component in a defined way, e.g. the state encoding must be “fixed” to a special encoding scheme.
  • Also, if it is not possible to get an encoding scheme suitable for the controlling of the next component, then an output logic must be designed → Moore-Automaton

Medvedev Example

Medvedev State Graph 

architecture RTL of MEDVEDEV_TEST is
  subtype STATE_TYPE is
    std_ulogic_vector(1 downto 0);
  constant START            : STATE_TYPE := "00";
  constant MIDDLE           : STATE_TYPE := "11";
  constant STOP             : STATE_TYPE := "01";
  signal   STATE, NEXTSTATE : STATE_TYPE;
begin
  REG : process (CLK, RESET)
  begin
    if RESET = '1' then
      STATE <= START;
    elsif (CLK'event and CLK = '1') then
      STATE <= NEXTSTATE;
    end if;
  end process REG;
 
  CMB : process (A, B, STATE)
  begin
    NEXTSTATE <= STATE;
    case STATE is
      when START =>
        if (A nor B) = '1' then
          NEXTSTATE <= MIDDLE;
        end if;
      when MIDDLE =>
        if (A and B) = '1' then
          NEXTSTATE <= STOP;
        end if;
      when STOP =>
        if (A xor B) = '1' then
          NEXTSTATE <= START;
        end if;
      when others =>
        NEXTSTATE <= START;
    end case;
  end process CMB;
  -- concurrent signal assignments
  -- for output
  (Y, Z) <= STATE;
end RTL;

Notes

Here, an example of a Medvedev machine is shown - using a fixed encoding scheme.

The bubble diagram contains the states of the machine (START, MIDDLE, STOP), the state encoding (“00”, “11”, “01”; see also the constant declarations) and the state transitions.

The so called weights (labels) of the transitions (arrows) determine the value of the input vector (here the signals A and B) for which the corresponding state transition will be executed.

For ’10| 01’, the state transition is executed when the input vector has either the value “10” or the value “01”.

The functionality of the state machine is described in the VHDL source code on the left side. The version with two processes was selected.

One can see that the output vector is wired with the state vector by a concurrent signal assignment.

Waveform Medvedev Example

Medvedev Waveform

  • (Y,Z) = STATE ⇒ Medvedev machine

Notes

In the waveform one can see the progression over time of the signal values of the design during simulation. It is apparent that it must be a Medvedev automaton, because the values of the output vector (represented by the two singals Y and Z) change synchronously with the state vector.

Chapters of System Design > Synthesis > Finite State Machines and VHDL

Chapters of System Design > Synthesis