FSM Design & Implementation

CT213 Computing System Organization

FSM Design
This presentation deals with front to end design of finite state machines, both Mealy and Moore types. Design example is provided for a modulo 6 counter

Modulo 6 Counter - Specification

A module 6 counter is a 3-bit counter that counts through the following sequence:
000->001->010->011->100->101->000-> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0

It doesnt use value 6 (110) nor 7 (111) It has an input U that controls the counter:
When U=1 the counter increments its value on the rising edge of the clock When U=0 the counter retains its value on the rising edge of the clock

The value of the count is represented as three bit value (V2V1V0) There is an additional output C (Carry) that is 1 when going from 5 to 0 and 0 otherwise (the C output remains 1 until the counter goes from 0 to 1)

Modulo 6 Counter State table

Present State S0 S0 S1 S1 S2 S2 S3 S3 S4 S4 S5 S5 U Next C V2V1V0 State 0 1 0 1 0 1 0 1 0 1 0 1 S0 S1 S1 S2 S2 S3 S3 S4 S4 S5 S5 S0 1 0 0 0 0 0 0 0 0 0 0 1 000 001 001 010 010 011 011 100 100 101 101 000

For each state examine what happens for all possible values of the inputs
In state S0 input U can be either 0 or 1 If U=0 the state machine remains in state S0 and outputs C=1 and V2V1V0=000 If U=1 the state machine goes in state S1, outputs C=1 and V2V1V0=001

In the same manner, each state goes to the next state if U=1 and remains in the same state if U=0

Modulo 6 Counter - Mealy state diagram

The outputs are represented on the arcs as CV2V1V0

Modulo 6 Counter Moore state diagram

The outputs are represented adjacent to the state The inputs are represented on the arcs

FSM Implementation
Converting a problem to equivalent state table and state diagram is just the first step in the design process The next step is to design the system hardware that implements the state machine. This section deals with the process involved to design the digital logic to implement a finite state machine. First step is to assign a uniquely binary value to each of the state that the machine can be in. The state must be encoded in binary. Next we design the hardware to go from the current state to the correct next state. This logic converts the current state and the current input values to the next state values and stores that value. The final stage would be to generate the outputs of the state machine. This is done using combinatorial logic.

Assigning State Values

Each state must be assigned to a unique binary value; for a machine with n states we have [log2n] bits; For the modulo 6 counter example, we have six states. We will assign state value 000 to S0, 001 to S1, and so on, up to 101 to S5.

Assigning State Values

Any values can be assigned to the states, some values can be better than others (in terms of minimizing the logic to create the output and the next state values) This is actually an iterative process: first the designer creates a preliminary design to generate the outputs and the next states, then modifies the state values and repeats the process. There is a rule of thumb, that simplifies the process: whenever possible, the state should be assigned the same with the output values associated with that state. In this case, same logic can be used to generate the next state and the output

Mealy and Moore Machine Implementations

The current state value is stored into the register The state value together with the machine inputs, are input to a logic block (CLC) that generates the next state value and machine outputs The next state is loaded into the register on the rising edge of the clock signal

Mod 6 Counter Mealy Implementation block (CLC) is The logic

specific to every system and may consist of combinatorial logic gates, multiplexers, lookup ROMs and other logic components The logic block cant include any sequential components, since it must generate its value in one clock cycle The logic block contains two parts:
One that generates the outputs (f function, CLC1) One that generates the next state (g function, CLC2)

Mod 6 Counter Moore Implementation

The outputs depend only on the present state and not on its inputs Its configuration is different than the Mealy machine
The system output depends only on the present state, so the implementation of the output logic is done separately The next state is obtained from the input and the present state (same as for the Mealy machine)

Generating the Next State

Since the Mealy and Moore machines must traverse the same states under the same conditions, their next state logic is identical We will present three methods to generate the next state logic:
(i) Combinatorial logic gates (ii) Using multiplexers (iii) Using lookup ROM

To begin with, we need to setup the truth table for the next state logic

Modulo 6 Counter - Next State Logic (i)

Present State P2P1P0 000 000 001 001 010 010 011 011 100 100 101 101 U Next State N2N1N0 0 1 0 1 0 1 0 1 0 1 0 1 000 001 001 010 010 011 011 100 100 101 101 000

The system inputs and the present states are the inputs of the truth table Next state bits are the outputs We have to construct a Karnaugh map for each output bit and obtain its equation After that we design the logic to match the equations

Modulo 6 Counter Next State Logic (i)

N2 = P2P0 + P2U +P1P0U N1 = P1P0 + P1U + P2P1P0U N0 = P0U + P0U

 Modulo 6 Counter Next State implementatio n using logic gates (i)

Modulo 6 Counter Next State Logic (ii)

An alternative approach to design the next state logic is to use multiplexers. Each input to the multiplexer corresponds to the next state under one possible value of the system inputs; the inputs drive the input signals of the multiplexer For the modulo 6 counter, we use the U input to drive the multiplexer; U is choosing one of two possible next states, the next state if U=0 and the next state if U = 1 To determine the inputs of the multiplexer we begin with splitting the truth table into multiple truth tables, one for each possible value of the system inputs Then we follow the procedure we have used to obtain the next state using combinatorial logic gate

Modulo 6 Counter Next State Logic (ii)

Present Next State State N2N1N0 P2P1P0 000 001 010 011 100 101 000 001 010 011 100 101 Present Next State State N2N1N0 P2P1P0 000 001 010 011 100 101 001 010 011 100 101 000

U=0
Initial truth table is broken into two tables:
One for U=0 One for U=1

U=1

Create Karnaugh maps from these tables to obtain the equations for N2, N1 and N0 when U=0 and when U=1

Modulo 6 Counter Next State Logic (ii)

P1P0

N2

00 0 1 00 0 0 00 1 1

01 0 0 01 1 0 01 0 0

11

10

P2

U = 0 we observe that the next state is the same with current state:
N2 = P2 N1 = P1 N0 = P0

0 1
P1P0

0 x

x 11

N1

10 1

P2

0 1
P1P0

x 11

U = 1:
N2 = P2P0+P1P0 N1 = P1P0 + P2P1P0 N0 = P0

N0

10

P2

0 1

U=1

Modulo 6 Counter Next State Logic (ii)

Next state logic implementation using multiplexers and logic gates. Please note that using multiplexers simplifies the combinatorial logic circuitry

Modulo 6 Counter Next State Logic (iii)

Another approach to generate the next state logic for a FSM is to use a lookup ROM. In this approach, the present state values and inputs are connected to the address bus of a ROM; the next state is obtained from the ROM outputs The correct value must be stored in each location of the ROM to ensure proper operation

Modulo 6 Counter Next State Logic (iii)

The three bits that encode the present state (P2P1P0) are connected to the three high-order address inputs to the ROM (A3A2A1) The one condition bit U is connected to the low order address bit A0 The data in each location is the value of the next state for present state and the input values

Generating System Outputs

Both for Mealy and Moore machines we follow the same design procedure to develop their output logic There are two approaches to generate the output (similar to generate the next state logic):
Using combinatorial logic gates Using lookup ROM

We are beginning by creating the truth table:

For Mealy machine, the truth table inputs will be the present state and the system inputs, and the table outputs are the system outputs For Moore machine, only the state bits are inputs of the truth table, since only these bits are used to generate the system outputs; the table outputs are the system outputs

Modulo 6 Counter Outputs (i)

P2P1P0 000 000 001 001 010 010 011 011 100 100 101 101 U C 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 V2V1V0 000 001 001 010 010 011 011 100 100 101 101 000 P2P1P0 C 000 001 010 011 100 101 1 0 0 0 0 0 V2V1V0 000 001 010 011 100 101

Moore

Mealy

Outputs - Mealy (i)

P0U P2P1

00 0 0 X

01 0 0

11

10
P2P1

P0U

00 0 1 X 0

01 0 1

11 1 0 X 0

10

00 01 11 10

0 0

00 01 11 10

1 X 0

X 1

X 0

V2 = P2P0 + P1P0U + P2U

P0U P2P1

V1 = P2P1P0U + P1P0 + P1U

P0U P2P1

00 0 0 X 0

01 1 1

11

10

00 1 0 X 0

01 0 0

11

10

00 01 11 10

00 01 11 10

0 0

0 0

0 X 0

X 1

X 1

X 0

V1 = P0U + P0U

C = P2P1P0U + P2P0U

Modulo 6 Counter Outputs (i)

Mealy machine (note that the equations for V2, V1, V0 are exactly the same as for the N2, N1, N0. This is the result of optimally assignation of the state values. Same combinatorial logic can be use to obtain the outputs):
V2 = P2P0+P2U+P1P0U V1 = P1P0+P1U+P2P1P0U V0 = P0U+P0U C = P2P1P0U+P2P0U V2 = P2 V1 = P1 V0 = P0 C = P2P1P0 = (P2+P1+P0)

Moore machine:

Modulo 6 Counter Mealy Implementation (i)

Modulo 6 Counter Moore Implementation (i)

Modulo 6 Counter System Outputs (ii)

It is possible to generate the system outputs using a lookup ROM The inputs of the lookup ROM are the present states and the system inputs. The outputs of the ROM are the system outputs We can use same ROM to generate next state and system outputs Since for the Mealy machine V2 = N2, V1 = N1 and V0 = N0, only one output is used for each pair. If the outputs werent the same as the next state, separate output bits would be needed.

Modulo 6 Counter Moore Implementation (ii)

FSM Alternative Design

There are some other methods to implement a FSM; one of them is to use a a counter to store the current state and a decoder to generate signals corresponding to each state The counter can be incremented, cleared or loaded with a value to go from one state to another. Unlike the other methods, you dont have to generate the same state value in order to remain in the same state; this can be accomplished by neither incrementing, clearing nor loading the counter

FSM with Counter and Decoder

The counter plays the role of the register in Mealy and Moore designs, as well as a portion of the next state logic The state value is input to a decoder; each output of the decoder represents one state The decoder outputs and system inputs are input to the logic bloc that generates the system outputs and the information needed to generate the next state value

FSM with Counter and Decoder

If the system inputs are used to generate both the next state and the system outputs, this design can be used to implement a Mealy machine. If the system outputs are generated solely by using the state value, and the system inputs are used only to generate the next state, then it implements a Moore machine Modulo 6 counter Moore implementation using this approach

Modulo 6 Counter Moore Implementation with Counter and Decoder

Unused States
The FSM presented so far works well if it is in a known state There will be a problem if the machine enters an unused state, also called unknown state or undefined state This could be caused by a flaw in the design but most of the times, this is happening when the machine powers-up.

Modulo 6 Counter Analysis

The modulo 6 counter (consider Moore machine implementation) has six states with binary state values from 000 to 101 The state value is stored in the register of the finite state machine hardware; an unused state is entered when an unused state is stored in this register; The unused states for this design example are 110 and 111

Modulo 6 Counter Revised (acceptable) diagram

When present state is 110, the next state is 110 if U=0 or 111 if U=1 When present state is 111, the next state is 111 if U=0 or 000 if U=1

Modulo 6 Counter Revised (wrong) diagram

If a circuit that implements this diagram powers-up in state 110 or 111 will never reach a valid state

Modulo 6 Counter State diagram with dummy states

Create dummy states for all unused states Each dummy state would go to a known state on the next clock cycle (usually to a reset state) Two dummy states: 110 and 111 By convention, the values 1 on the arcs indicate that the transfer is unconditional that is always taken Note also the output values: C=0 and 111 indicates the user that the machine is in an invalid state (it is a design decision)

Modulo 6 Counter State table with dummy states

P2P1P0 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 U 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 N2N1N0 000 001 001 010 010 011 011 100 100 101 101 000 000 000 000 000 C 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 V2V1V0 000 001 001 010 010 011 011 100 100 101 101 000 111 111 111 111

Use this table to construct Karnaugh maps which yield to the following values for next state and outputs: Next state:
N2 = P2P1P0 + P2P1U + P1P0U N1 = P2P1P0 + P2P1U + P2P1P0U N0 = P2P0U + P1P0U + P1P0U

Outputs:
C = P2P1P0 V2 = P1 V1 = P1 V0 = P0 + P2P1

References
Computer Systems Organization & Architecture, John D. Carpinelli, ISBN: 0201-61253-4