456 C H A P T E R 9 • Counters and Shift Registers
nously set to 960. Create a MAX PLUS II simulation to verify the operation of the design.
9.9Shift Register Counters
9.56Write the VHDL code for a ring counter of generic width and instantiate it as an 8-bit ring counter. List the sequence of states in a table, assuming the counter is initially cleared, and create a simulation to verify the circuit’s operation. Include a clear input (synchronous).
9.57Construct the count sequence table of a 5-bit Johnson counter, assuming the counter is initially cleared. What changes must be made to the decoder part of the circuit in Figure 9.84 (p. 446) if it is to decode the 5-bit Johnson counter?
“double twist” in the data path.
A N S W E R S T O S E C T I O N R E V I E W P R O B L E M S
Section 9.1
9.1 A mod-24 UP counter goes from 00000 to 10111 (0 to 23). This requires 5 outputs. The counter is a truncated sequence since its modulus is less than 25 32.
Section 9.2
9.2 1001, 0000
Section 9.3
9.3JK flip-flops: J3K3 X0, J2K2 1X, J1K1 X1, J0K0 X1 D flip-flops: D3 1, D2 1, D1 0, D0 0
Section 9.4
9.4 If (clock‘EVENT AND clock = ‘0’) THEN
count := count + 1;
END IF;
9.58A control sequence has ten steps, each activated by a logic HIGH. Use MAX PLUS II to design a counter and decoder in each of the following configurations to produce the required sequence: binary counter, ring counter, and Johnson counter. You may use a Graphic Design File or VHDL. Create a simulation for each counter and decoder.
9.59 Use the MAX PLUS II Graphic Editor to design a 4-bit ring counter that can be asynchronously initialized to Q3Q2Q1Q0 1000 by using only the clear inputs of its flip-flops. No presets allowed. Hint: use a circuit with a
Section 9.5
9.5 The completed timing diagram is shown in Figure 9.93.
Section 9.6
9.6 Asynchronous clear: PROCESS (clock, clear); Synchronous clear: PROCESS (clock)
Section 9.7
9.7 JK flip-flops can be used in the shift register of Figure 9.58. The Q output of any stage connects to the J input of the next stage and the Q output of any stage connects to the K input of the next. The serial_in input connects directly to the J input of the first flip-flop. Serial_in is applied to K of the first flip-flop through an inverter (NOT gate).
Section 9.8
9.8 A shift register output is defined as a port of mode BUFFER because this mode allows a signal to be fed back into the PLD matrix and reused as an input to another part of the circuit.
Section 9.9
Binary: 5 flip-flops, 24 5-inputs NANDs; Ring: 24 flip-flops, no
LOAD |
|
|
|
|
|
|
|
|
|
|
|
|
|
RESET |
|
|
|
|
|
|
|
|
|
|
|
|
|
CLOCK |
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
0 |
|
|
|
|
|
8 |
|
|
|
|
5 |
|
QA 0 |
1 |
2 |
3 |
4 |
|
8 |
9 |
A |
0 |
1 |
2 |
5 |
6 |
QS 0 |
1 |
2 |
3 |
|
4 |
8 |
9 |
A |
0 |
1 |
2 |
|
5 6 |
FIGURE 9.93
Answer to Section Review Problem 9.5
C H A P T E R 10
State Machine Design
O U T L I N E C H A P T E R O B J E C T I V E S
10.1State Machines
10.2State Machines with No Control Inputs
10.3State Machines with Control Inputs
10.4Switch Debouncer for a Normally Open Pushbutton Switch
10.5Unused States in State Machines
10.6Traffic Light Controller
Upon successful completion of this chapter you will be able to:
•Describe the components of a state machine.
•Distinguish between Moore and Mealy implementations of state machines.
•Draw the state diagram of a state machine from a verbal description.
•Use the “classical” (state table) method of state machine design to determine the Boolean equations of the state machine.
•Translate the Boolean equations of a state machine into a Graphic Design File in Altera’s MAX PLUS II software.
•Write VHDL code to implement state machines.
•Create simulations in MAX PLUS II to verify the function of a state machine design.
•Determine whether the output of a state machine is vulnerable to asynchronous changes of input.
•Design state machine applications, such as a switch debouncer, a singlepulse generator, and a traffic light controller.
10.1 State Machines
K E Y T E R M S
State machine A synchronous sequential circuit, consisting of a sequential logic section and a combinational logic section, whose outputs and internal flip-flops progress through a predictable sequence of states in response to a clock and other input signals.
Moore machine A state machine whose output is determined only by the sequential logic of the machine.
Mealy machine A state machine whose output is determined by both the sequential logic and the combinational logic of the machine.
State variables The variables held in the flip-flops of a state machine that determine its present state. The number of state variables in a machine is equivalent to the number of flip-flops.
458 C H A P T E R 1 0 • State Machine Design
FIGURE 10.1
Moore-Type State Machine
The synchronous counters and shift registers we examined in Chapter 9 are examples of a larger class of circuits known as state machines. As described for synchronous counters in Section 9.2, a state machine consists of a memory section that holds the present state of the machine and a control section that determines the machine’s next state. These sections communicate via a series of command and status lines. Depending on the type of machine, the outputs will either be functions of the present state only or of the present and next states.
Figure 10.1 shows the block diagram of a Moore machine. The outputs of a Moore machine are determined solely by the present state of the machine’s memory section. The output may be directly connected to the Q outputs of the internal flip-flops, or the Q outputs might pass through a decoder circuit. The output of a Moore machine is synchronous to the system clock, since the output can only change when the machine’s internal state variables change.
The block diagram of a Mealy machine is shown in Figure 10.2. The outputs of the Mealy machine are derived from the combinational (control) section of the machine, as
FIGURE 10.2
Mealy-Type State Machine
10.2 • State Machines with No Control Inputs |
459 |
well as the sequential (memory) part of the machine. Therefore, the outputs can change asynchronously when the combinational circuit inputs change out of phase with the clock. (When we say that the outputs change asynchronously, we generally do not mean a change via a function such as asynchronous reset that directly affects the machine’s flip-flops.)
SECTION 10.1 REVIEW PROBLEM
10.1What is the main difference between a Moore-type state machine and a Mealy-type state machine?
10.2State Machines with No Control Inputs
K E Y T E R M S
Bubble A circle in a state diagram containing the state name and values of the
state variables.
A state machine can be designed using a classical technique, similar to that used to design a synchronous counter. We can also use a VHDL design method. We will design several state machines, using both classical and VHDL techniques.
As an example of these techniques, we will design a state machine whose output depends only on the clock input: a 3-bit counter with a Gray code count sequence. A 3-bit Gray code, shown in Table 10.1, changes only one bit between adjacent codes and is therefore not a binary-weighted sequence.
Table 10.1 3-bit Gray
Code Sequence
Q2Q1Q0
000
001
011
010
110
111
101
100
Gray code is often used in situations where it is important to minimize the effect of single-bit errors. For example, suppose the angle of a motor shaft is measured by a detected code on a Gray-coded shaft encoder, shown in Figure 10.3. The encoder indicates a 3-bit number for each of eight angular positions by having three concentric circular segments for each code. A dark band indicates a 1 and a transparent band indicates a 0, with the MSB as the outermost band. The dark or transparent bands are detected by three sensors that detect
FIGURE 10.3 |
100 |
000 |
Gray Code on a Shaft Encoder |
|
|
101 |
|
001 |
111 |
|
011 |
460 C H A P T E R 1 0 • State Machine Design
light shining through a transparent band. (A real shaft encoder has more bits to indicate an angle more precisely. For example, a shaft encoder that measures an angle of one degree would require nine bits, since there are 360 degrees in a circle and 28 360 29.)
For most positions on the encoder, the error of a single bit results in a positional error of only one eighth of the circle. This is not true with binary coding, where single bit errors can give larger positional errors. For example if the positional decoder reads 100 instead of 000, this is a difference of 4 in binary. The same codes differ by only one position in Gray code.
Classical Design Techniques
We can summarize the classical design technique for a state machine, as follows:
1.Define the problem.
2.Draw a state diagram.
3.Make a state table that lists all possible present states and inputs and the next state and output state for each present state/input combination. List the present states and inputs in binary order.
4.Use flip-flop excitation tables to determine at what states the flip-flop synchronous inputs must be to make the circuit go from each present state to its next state. The next state variables are functions of the inputs and present state variables.
5.Write the output value for each present state/input combination. The output variables are functions of the inputs and present state variables.
6.Simplify the Boolean expression for each output and synchronous input.
7.Use the Boolean expressions found in step 6 to draw the required logic circuit.
Let us follow this procedure to design a 3-bit Gray code counter. We will modify the procedure to account for the fact that there are no inputs other than the clock and no outputs that must be designed apart from the counter itself.
1.Define the problem. Design a counter whose outputs progress in the sequence defined in Table 10.1.
2.Draw a state diagram. The state diagram is shown in Figure 10.4. In addition to the values of state variables shown in each circle (or bubble), we also indicate a state name, such as s0, s1, s2, and so on. This name is independent of the value of state variables. We use numbered states (s0, s1, . . .) for convenience, but we could use any names we wanted to.
FIGURE 10.4 |
|
S0 |
State Diagram for a 3-bit Gray |
|
|
000 |
Code Counter |
|
S7 |
S1 |
|
100 |
001 |
|
S6 |
S2 |
|
101 |
011 |
|
S5 |
S3 |
|
111 |
010 |
|
|
S4 |
|
|
010 |
3.Make a state table. The state table, based on D flip-flops, is shown in Table 10.2. Since there are eight unique states in the state diagram, we require three state variables (23
8), and hence three flip-flops. Note that the present states are in binary-weighted order, even though the count does not progress in this order. In such a case, it is essential to have an accurate state diagram, from which we derive each next state. For example, if
