(
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. 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.
(
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.
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.clk = `1' and not clk'stable
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.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.(
REG)
associated with particular output pins. The P22V10 PAL also supports negative logic outputs as well as outputs that bypass the internal flip-flops.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.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.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.