Sunday, 6 October 2013

FSM Design with Counters

Synchronous counters are potentially attractive for implementing finite state machines. In a single package they provide a state register with mechanisms for advancing the state (CNT), resetting it to zero (CLR), and "jumping" to a new state (LD). Rather than encode the next-state function as actual state bits, you can implement it by asserting the counter control signals CNT, LD, and CLR under the right conditions. We examine a counter-based implementation strategy in this section.

For correct operation in state sequencing, the counter must be implemented with synchronous LD and CLR signals, such as the TTL 74163 binary up-counter. As pointed out in Section 7.5.2, asynchronous control signals lead to invalid behavior of the state machine.
Figure 10.19 shows the kinds of state transitions supported by a counter. You should choose the state assignment to exploit the special sequencing capabilities of a counter. The state encodings you assign to sequential states should follow the binary sequence supported by the counter. Let's look at an MSI counter-based implementation of the BCD-to-Excess-3 converter next.

BCD-to-Excess-3 Code Converter


Figure 10.20 gives a state assignment for the state diagram of the code converter. This assignment is reasonably well suited for a counter-based finite state machine implementation. As much as possible, we assign sequential state encodings to flows in the state diagram. We also try to reduce the number of transitions in which a jump (LD) to a state (other than 0) takes place. The figure shows three such jumps: from state 0 to 4, from 1 to 5, and from 5 to 3.
State Transition Table To implement a finite state machine with a counter, we replace the next-state bits with logic to generate the counter control signals. This is like remapping the next-state functions to flip-flop control inputs that we saw in Chapter 6. However, we must still directly specify the next-state bits for the jump cases.
Figure 10.21 shows the finite state machine state transition table, extended with output columns for the counter control signals , , EN (count), as well as the counter load inputs C, B, and A. Our basic procedure obtains minimized logic expressions for these signals rather than the next-state bits.

For the 74163 counter, the signal has precedence over , which in turn has precedence over EN (count). This makes it possible to exploit many more don't-care conditions within the K-maps.

We derive the state transition table in the following manner. We examine each state transition in turn. Consider the first transition, from state 0 to 1. If the machine is currently in state 0 with input 0, the finite state -machine changes to state 1 with output 1. Thus, and should be unasserted (left high) and EN asserted to cause the state register to count up from 0 to 1. These settings fill out the rest of the row in the transition table.
If the input is 1 in state 0, the next state is 4 with an output 0. This calls for a jump: is left unasserted high, is asserted low, and EN can be a don't care. The value to be loaded, 1 0 0, must be available on the C, B, A signals. The collection of values fill out the ninth row of the state transition table.

An example of a return to state 0 is the 0 transition from state 3. In this case, the signal is asserted low, while and EN can be don't cares. Rows 7 and 12 of the transition table provide other examples of these "return to 0" transitions.

Boolean Minimization of the Counter Control Signals Our next step is to minimize the functions for Z, , , and EN. The espresso input file is shown in Figure 10.22 and the resulting output file in Figure 10.23.

Because we are already using the signal for a control function, we need a separate RESET input to place the finite state machine in state 0 initially. Note that this is a synchronous reset; the reset on the 74175 quad registers used in some of the finite state machine implementations in this chapter is asynchronous. To be correctly "synchronous," we should include a reset signal as input to the ROM or PLA/PAL next-state logic (see Exercise 10.2).
Discussion For this implementation of the BCD-to-Excess-3 code converter, the logic is more complex than the others: 10 product terms, an additional input, and three additional outputs. The schematic is shown in Figure 10.24.
Since we are designing synchronous Mealy machines, we need a D flip-flop between the PLA and the output Z, adding yet another component. The timing behavior of this circuit is identical to that of Figure 10.7.

The counter-based implementation was a bad choice for this particular state machine. However, when the state diagram has fewer out-of-sequence jumps, a counter-based implementation can be very effective