Mealy State Machine - 2020.2 English

Vivado Design Suite Reference Guide: Model-Based DSP Design Using System Generator (UG958)

Document ID
UG958
Release Date
2020-11-18
Version
2020.2 English

A “Mealy machine” is a finite state machine whose output is a function of state transition, for example, a function of the machine’s current state and current input. A Mealy machine can be described with the following block diagram:

Figure 1. Mealy Machine Block Diagram

There are many ways to implement such state machines in System Generator (e.g., using the MCode block to implement the transition function, and registers to implement state variables). This reference block provides a method for implementing a Mealy machine using block and distributed memory. The implementation is very fast and efficient. For example, a state machine with 8 states, 1 input, and 2 outputs that are registered can be realized with a single block RAM that runs at more than 150 MHz in a Xilinx Virtex device.

The transition function and output mapping are each represented as an N x M matrix, where N is the number of states, and M is the size of the input alphabet (e.g., M = 2 for a binary input). It is convenient to number rows and columns from 0 to N – 1 and 0 to M – 1 respectively. Each state is represented as an unsigned integer from 0 to N - 1, and each alphabet character is represented as an unsigned integer from 0 to M - 1. The row index of each matrix represents the current state, and the column index represents the input character

For the purpose of discussion, let F be the N x M transition function matrix, and O be the N x M output function matrix. Then F(i,j) is the next state when the current state is i and the current input character is j, and O(i,j) is the corresponding output of the Mealy machine.

Example

Consider the problem of designing a Mealy machine to recognize the pattern '1011' in a serial stream of bits. The state transition diagram and equivalent transition table are shown below.

Figure 2. State Transition Diagram

The table lists the next state and output that result from the current state and input. For example, if the current state is 3 and the input is 1, the next state is 1 and the output is 1, indicating the detection of the desired sequence.

The Mealy State Machine block is configured with next state and output matrices obtained from the next state/output table discussed above. These matrices are constructed as shown below:

Figure 3. Next State Output Table

Block Parameters

The block parameters dialog box can be invoked by double-clicking the icon in your Simulink model.

The next state logic, state register, and output logic are implemented using high speed dedicated block RAM. The output logic is implemented using a distributed RAM configured as a lookup table, and therefore has zero latency.

The number of bits used to implement a Mealy state machine is given by the equations:

depth = (2 k )(2 i ) = 2 k+i

width = k+o

N = depth*width = (k+o)(2 k+i )

where

N = total number of block RAM bits

s = number of states

k = ceil(log2(s))

i = number of input bits

o = number of output bits

The following table gives examples of block RAM sizes necessary for various state machines:

Table 1. Block RAM Sizes
Number of States Number of Input Bits Number of Output Bits Block RAM Bits Needed
2 5 10 704
4 1 2 32
8 6 7 5120
16 5 4 4096
32 4 3 4096
52 1 11 2176
100 4 5 24576

The block RAM width and depth limitations are described in the online help for the Single Port RAM block.