Mealy machine

A finite state machine is a quintuple Q,T,6,qo F) with Q being a finite nonempty set of states, S the finite nonempty input alphabet, 6 the transition mapping, qo a start state, and F the set of accepting states. In terms of a logic circuit, we usually let the input symbols correspond to data bits on a number of input lines and the states correspond to the values contained in the registers. In hardware applications, it is customary to introduce two derived machine concepts, known as the Moore and Mealy type machines. A (deterministic) Moore machine is described by a six-tuple (Q, S,<5,/m, r, < ), where Init is a set of initial states, T the output alphabet, and (j> Q — T the output function. In a Mealy machine, outputs are associated with the edges in the state diagram so we have Q x E —F. We will call a machine incompletely specified if the 6 function is not fully defined over its domain of states and symbols. 

Incompleteness of a machine is resolved by introducing a special state. Whenever 6 is undefined in a state, we add edges labeled with the missing symbols and directed toward that special state. The special state itself has an outgoing transition for each input symbol ending on itself. In an incompletely specified Mealy machine, the output function depends both on the current state and the current input. We then need to add a clause for each binary output signal stating for what state/input-conditions it is true. 

The equivalence test in this case is somewhat complicated in fact, we are comparing a Mealy machine implementation (the circuit) against a Moore machine specification. In the circuit, Z is valid after the first three clock ticks and from then on after every fourth tick. In the state machine, Success might be reached after every fourth clock tick. We therefore introduce a simple modulo-four ring counter to serve as a time base ... 

It took our program only 0.1 seconds (on an HP9000/S750 workstation) to verify this statement. A 52 CMOS-transistor 4 2 flip-fiops circuit (not discussed here) was verified against an 11-state Mealy machine in 1.1 seconds. 

A sequential state machine whose outputs depend on both the current state and the inputs is called a Mealy machine, as shown in Figure 2.4. In other words, the functionality can be expressed as. 

In this section, we describe a Mealy machine and discuss two possible ways (Example 2.7 and Example 2.8) of coding the same in both VHDL and Verilog. Consider a Mealy machine with one input (X) and one ou ut (Z). When X = 0, the current state of the state machine remains unchanged and output Z remains at 0. When X =1, the state machine makes a transition from one state to the next binary state, that is, 00 -> 01 -> 10 -> 11 -> 00 and so on. The output Z is equal to 1, only when the state is 11 and the input X is equal to 1, else Z is equal to 0 as shown in the state transition Table2.1 and state transition diagram in Figure 2-3. 

Control FSMs generated by the above two methods are different type of FSMs. The FSM of the former is a usual Mealy machine, but the FSM of the latter is a Mealy machine with status variables. The latter FSM is discussed later. 

In a Mealy finite state machine, the output is dependent both on the machine state as well as on the inputs to the finite state machine. This is shown pictorially in Figure 3-8. Notice that in this case, outputs can change asynchronously with respect to clock. 

Here is an example of a Mealy finite state machine. Variable MealyState holds the machine state, while NextState is used to pass information from the combinational logic always statement to the sequential logic always statement. Input Reset asynchronously resets the state to STO. 

Turing Machine (TM) is driven by a program which is interpreted by its Control Unit (CUTM). The Control Unit CUTM is a finite automaton (Mealy s or Moore s sequential machine). The program for the TM consists of the finite sequence rj of instructions jj j... 

It is now common practice, for verification as well as for synthesis purposes, to take the deterministic Mealy finite state machine (FSM hereafter for short) as abstract model for clock-synchronized circuits described at the register transfer level. The model is based on the following hypotheses ... 

A finite state machine (FSM) consists of a current state (P) and a next state (N), iq>uts (I) and outputs (O). State Machines can be classified as Mealy or Moore machines depending on how the outputs are generated. 

---