91.

[Top] [Next] [Prev]

8.3 Alternative State Machine Representations

You have already seen how to describe finite state machines in terms of state diagrams and tables. However, it can be difficult to describe complex finite state machines in this way. Recently, hardware designers have shifted toward using alternative representations of FSM behavior that look more like software descriptions. In this section, we introduce algorithmic state machine (ASM) notation and hardware description languages (HDLs). ASMs are similar to program flowcharts, but they have a more rigorous concept of timing. HDLs look much like modern programming languages, but they explicitly support computations that can occur in parallel.

You may wonder what is wrong with state diagrams. The problem is that they do not adequately capture the notion of an algorithm-a well-defined sequence of steps that produce a desired sequence of actions based on input data. State diagrams are weak at capturing the structure behind complex sequencing. The representations discussed next do a better job of making this sequencing structure explicit.

8.3.1 Algorithmic State Machine Notation

The ASM notation consists of three primitive elements: the state box, the decision box, and the output box, as shown in Figure 8.19.

Each major unit, called an ASM block, consists of a state box and, optionally, a network of condition and output boxes. A state machine is in exactly one state or ASM block during the stable portion of the state time.

State Boxes There is one state box per ASM block, reached from other ASM blocks through a single state entry path. In addition, for each combination of inputs there is a single unambiguous exit path from the ASM block. The state box is identified by a symbolic state name-in a circle-and a binary-encoded state code, and it contains an output signal list.

The output list describes the signals that are asserted whenever the state is entered. Because signals may be expressed in either positive or negative logic, it is customary to place an "L." or "H." prefix before the signal name, indicating whether it is asserted low or high. You can also specify whether the signal is asserted immediately (I) or is delayed (no special prefix) until the next clocking event. A signal not mentioned in the output list is left unasserted.

Condition Boxes The condition box tests an input to determine an exit path from the current ASM block to the block to be entered next. The order in which condition boxes are cascaded has no effect on the determination of the next ASM block.

Figure 8.20(a) and (b) show functionally equivalent ASM blocks: state B is to be entered next if I0 and I1 are both 1; otherwise state C is next.

Output Boxes Any output boxes on the path from the state box to an exit contain signals that should be asserted along with the signals mentioned in the state box. The state machine advances from one state to the next in discrete rather than continuous steps. In this sense, ASM charts have different timing semantics than program flowcharts.

Example The Parity Checker As an example, we give the parity checker's ASM chart in Figure 8.21.

It consists of two states, Even and Odd, encoded as 0 and 1, respectively. The input is the single bit X; the output is the single bit Z, asserted high when the finite state machine is in the Odd state.

We can derive the state transition table from the ASM chart. We simply list all the possible transition paths from one state to another and the input combinations that cause the transition to take place. For example, in state Even, when the input is 1, we go to state Odd. Otherwise we stay in state Even. For state Odd, if the input is 1, we advance to Even. Otherwise we remain in state Odd. The output Z is asserted only in state Odd. The transition table becomes:

Input X

Present State



Next State

Output Z

F

Even



Even

Not asserted

T

Even



Odd

Not asserted

F

Odd



Odd

Asserted

T

Odd



Even

Asserted


Example Vending Machine Controller We show the ASM chart for the vending machine in Figure 8.22.

To extract the state transition table, we simply examine all exit paths from each state. For example, in the state 0¢, we advance to state 10¢ when input D is asserted. If N is asserted, we go to state 5¢. Otherwise, we stay in state 0¢. The rest of the table can be determined by looking at the remaining states in turn.

8.3.2 Hardware Description Languages: VHDL

Hardware description languages provide another way to specify finite state machine behavior. Such descriptions bear some resemblance to a program written in a modern structured programming language. But again, the concept of timing is radically different from that in a program written in a sequential programming language. Unlike state diagrams or ASM charts, specifications in a hardware description language can actually be simulated. They are executable descriptions that can be used to verify that the digital system they describe behaves as expected.

VHDL (VHSIC hardware description language) is an industry standard. Although its basic concepts are relatively straightforward, its detailed syntax is beyond the scope of this text. However, we can illustrate its capabilities for describing finite state machines by examining a description of the parity checker written in VHDL:

ENTITY parity_checker IS PORT ( x, clk: IN BIT; z: OUT BIT); END parity_checker;
ARCHITECTURE behavioral OF parity_checker IS BEGIN main: BLOCK (clk = `1' and not clk'STABLE)
 TYPE state IS (Even, Odd); SIGNAL state_register: state := Even;
 BEGIN state_even: BLOCK ((state_register = Even) AND GUARD) BEGIN state_register <= Odd WHEN x = `1' ELSE Even END BLOCK state_even;
 BEGIN state_odd: BLOCK ((state_register = Odd) AND GUARD) BEGIN state_register <= Even WHEN x = `1' ELSE Odd; END BLOCK state_odd;
 z <= `0' WHEN state_register = Even ELSE   `1' WHEN state_register = Odd; END BLOCK main; END behavioral;
Every VHDL description has two components: an interface description and an architectural body. The former defines the input and output connections or "ports" to the hardware entity being designed; the latter describes the entity's behavior.

The architecture block defines the behavior of the finite state machine. The values the state register can take on are defined by the type state, consisting of the symbols Even and Odd. We write VHDL statements that assign new values to the state register and the output Z, depending on the current value of input X, whenever we detect a rising clock edge.

Checking for events like a clock transition is handled through the VHDL concept of the guard, an expression that enables certain statements in the description when it evaluates to true. For example, the expression

clk = `1' and not clk'stable
is a guard that evaluates to true whenever the clock signal has recently undergone a 0-to-1 transition. The main block is enabled for evaluation when this particular guard becomes true.

The description contains two subblocks, state_even and state_odd, that are enabled whenever the main guard is true and the machine is in the indicated state. Within each subblock, the state register receives a new assignment depending on the value of the input. Outside the subblocks, the output becomes 0 when the machine enters state Even and 1 when it enters state Odd.

8.3.3 ABEL Hardware Description Language

ABEL is a hardware description language closely tied to the specification of programmable logic components. It is also an industry standard and enjoys widespread use. The language is suitable for describing either combinational or sequential logic and supports hardware specification in terms of Boolean equations, truth tables, or state diagram descriptions. Although the detailed syntax and semantics of the language are beyond our scope, we can highlight its features with the parity checker finite state machine.

Let's look at the ABEL description of the parity checker:

module parity title 'odd parity checker state machine  Joe Engineer, Itty Bity Machines, Inc.' u1   device   'p22v10';
"Input Pins clk, X, RESET pin 1, 2, 3;
"Output Pins Q, Z  pin 21, 22; Q, Z  istype 'pos,reg';
"State registers SREG =  [Q, Z]; EVEN =  [0, 0]; " even number of 0's ODD  =  [1, 1];  " odd number of 0's
equations [Q.ar, Z.ar] = RESET; "Reset to state S0
state_diagram SREG state EVEN: if X then ODD  else EVEN; state ODD: if X then EVEN  else ODD;
test_vectors ([clk, RESET, X] -> [SREG]) [0,1,.X.] -> [EVEN]; [.C.,0,1] -> [ODD]; [.C.,0,1] -> [EVEN]; [.C.,0,1] -> [ODD]; [.C.,0,0] -> [ODD]; [.C.,0,1] -> [EVEN]; [.C.,0,1] -> [ODD]; [.C.,0,0] -> [ODD]; [.C.,0,0] -> [ODD]; [.C.,0,0] -> [ODD]; end parity; 
An ABEL description consists of several sections: module, title, descriptions, equations, truth tables, state diagrams, and test vectors, some of which are optional. Every ABEL description begins with a module statement and an optional title statement. These name the module and provide some basic documentation about its function.

These are followed by the description section. The elements of this section are the kind of device being programmed, the specification of inputs and outputs, and the declaration of which signals constitute the state of the finite state machine.

We must first describe the device selected for the implementation. It is a P22V10 PAL, with 12 inputs, 10 outputs, and embedded flip-flops associated with the outputs. For identification within the schematic, we call the device u1.

Next come the pin descriptions. The finite state machine's inputs are the clock clk, data X, and the RESET signal. The outputs are the state Q and the output Z. These are assigned to specific pins on the PAL. For example, pin 1 is connected to the clock inputs of the internal flip-flops.

Many of the attributes of a PAL are selectable, so the description may need to make explicit choices. The next line of the description tells ABEL that Q and Z are POSitive logic outputs of the PAL's internal flip-flops (REG) associated with particular output pins. The P22V10 PAL also supports negative logic outputs as well as outputs that bypass the internal flip-flops.

The state of the finite state machine is represented by the outputs Q and Z. EVEN is defined as the state where Q and Z are 0. ODD is defined as the state where Q and Z are 1.

The equation section defines outputs in terms of Boolean equations of the inputs. In this case, the asynchronous reset (.ar) inputs of the Q and Z flip-flops are driven high when the RESET signal is asserted.

The state_diagram section describes the transitions among states using a programming language-like syntax. If we are in EVEN and the input X is asserted, we change to ODD. Otherwise we stay in EVEN. Similarly, if we are in ODD and X is asserted, we return to EVEN. Other-wise we stay in state ODD. ABEL supports a variety of control constructs, including such things as case statements.

The final section in this example is for test_vectors. This is a tabular listing of the expected input/output behavior of the finite state machine. The first entry describes what happens when RESET is asserted: independent of the current value of X, the machine is forced to EVEN. The rest of the entries describe the state sequence for the input string 111011000. The ABEL system simulates the description to ensure that the behavior matches the specified behavior of the test vectors.

The major weakness of an ABEL description is that it forces the designer to understand many low-level details about the target PAL. Nevertheless, the state diagram description is an intuitively simple way to describe the behavior of a state machine.

[Top] [Next] [Prev]


This file last updated on 07/14/96 at 21:28:46.
randy@cs.Berkeley.edu;


What is Sarbanes-Oxley[q]
What is Sarbanes-Oxley[q]
ISBN: 71437967
EAN: N/A
Year: 2006
Pages: 101

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net