35.

[Top] [Next] [Prev]

12.3 Jump Counter

In Section 10.2 we described methods for implementing finite state machines using a counter as the state register. We called this the jump counter method. The approach uses MSI components, such as synchronous counters, multiplexers, and decoders, to implement the finite state machine. In this section we expand the description, showing how jump counters can be used to implement the control unit of a CPU.

Jump counters fall into two classes: pure and hybrid. A pure jump counter permits only one of four possible next states: the current state (the counter holds), the next sequential state (the counter counts), state 0 (the counter clears), or a single "jump" state (the counter loads). In the pure jump counter, the jump state is strictly a function of the current state. A hybrid counter supports the same kinds of transitions but allows the jump state to be a function of the inputs as well as the current state.

12.3.1 Pure Jump Counter

Figure 12.12 is a block diagram view of a pure jump counter. The jump state is a function of the current state, while the clear, load, and count inputs to the state register depend on the current state and the current inputs. We assume that clear takes precedence over load, which takes precedence over count. The logic blocks in the figure can be implemented with discrete logic gates, PALs/PLAs, or ROMs. We frequently use ROMs for the jump state logic.

The restricted sequencing of states in the pure jump counter is shown in Figure 12.13. To take maximum advantage of the counter state register, we should assign the states in count sequence. The most frequent target of a transition should be assigned state 0.

This usually proves too restrictive for states that require a more general multiway branch, such as the operation decode state in a processor state diagram. For states with multiway branches, a pure jump counter approach must introduce a number of extra states, as shown in Figure 12.14.

Figure 12.14(a) shows the operation decode state diagram fragment from Figures 11.23 and 12.1. To implement this as a pure jump counter, we would need the state diagram fragment of Figure 12.14(b). We must introduce two new decode states and increase the total number of states needed to execute a load, store, or add instruction. It is not too surprising that some enterprising designer invented the more general hybrid jump counter.

12.3.2 Hybrid Jump Counter

The hybrid jump counter solves the multiway branch problem. It simply makes the jump state a function of the inputs as well as the current state. This is made clear in the block diagram of Figure 12.15. The jump state, clear, load, and count logic are all functions of the input and the current state.

Mealy State Diagram for the Simple CPU Let's see how to implement the Mealy state diagram of Figure 11.23 with a hybrid jump counter. Our first consideration is how to assign encoded states to the state diagram. Most state transitions advance forward or hold in the current state, depending on the value of the Wait signal. Thus, we can use a natural depth-first state assignment. See Figure 12.16.

Next, we find a state to assign as 0. Since the RES state is the most frequent target of a transition, it is the best candidate. Starting with 0, we simply assign the states in sequence as we advance down through the state diagram.

The last consideration is to identify the branch states, those whose next-state transitions cannot be described simply in terms of hold (stay in the current state), count (advance to the next state in sequence), or reset (go to state 0). The only such state is OD, operation decode. Fortunately, we can describe the next-state transitions as a function of the current state and the IR op code bits. In fact, since this is the only multiway branch in the whole state diagram, the jump state logic is a function solely of the IR op code bits.

The complete state assignment is shown in Figure 12.16. We assume that the states are numbered S0 through S13. For the transitions to the RES state (S0), the state counter CLR signal should be asserted in states S7, S9 (if is also asserted), S12, and S13.

The counter LD signal is asserted only for states with a multiway branch. For this state diagram, it should be asserted in state S4, the OD state. The jump state logic, determined by the IR op code bits, generates the new state to be loaded into the state counter.

When to assert the CNT signal is slightly more complicated. The Boolean equations to count or to hold (don't count) are

The HOLD equation () is simpler than the CNT equation. You might save some logic by implementing HOLD and then inverting it to obtain the CNT signal.

The jump state logic for S4 (OD) is straightforward. It can be implemented by a 4 word by 4-bit ROM whose address inputs are the two IR op code bits.

Schematic Level Implementation of the Jump Counter A schematic description of the jump counter is shown in Figure 12.17.
The major components are (1) a synchronous counter (74163) used as the state register; (2) a 4-to-16 decoder (74154) to generate signals to identify the current state; (3) jump state logic implemented as a 4 word by 4-bit ROM, indexed by the IR's two op code bits; (4) a PAL implementing the Boolean logic for the state counter's CNT input; and (5) discrete logic implementing the state counter's CLR input (CLR could also have been implemented as an output of the CNT PAL). Since LD is asserted only in one state, S4, the decoder output for that state drives the load input directly.

Let's look at the logic for this hybrid jump counter controller in a -little more detail, starting with the contents of the jump state ROM. For each op code bit pattern, the appropriate next-state bits are stored in the ROM:

Address	Contents (Symbolic State)
00	0101 (LD0)
01	1000 (ST0)
10	1010 (AD0)
11	1101 (BR0)

The design of the rest of the jump counter implementation is reasonably straightforward, but there is one complication. This is the negative polarity of the 74163 counter's LD and CLR control signals, as well as the 74154 decoder's active low outputs. Let's look at the CLR signal first. In positive logic, it can be expressed as

Since the CLR input is active low, the function should be rewritten using DeMorgan's theorem:

Fortunately, the decoder delivers exactly these active low state signals. A five-input AND gate and a two-input OR gate implement the -signal.

Sometimes it is more convenient to implement HOLD (DON'T CNT) rather than CNT. In other words, the complement of HOLD is CNT. HOLD can be implemented by using a PAL with programmable output polarity and choosing the output to be negative logic. The PAL function becomes

Since the decoder gives the current state in negative logic, it is just as easy to specify the HOLD function using the active low versions of the state inputs. The PAL is actually programmed with the following:

Alternative MSI-Based Implementation of the Jump Counter In the previous subsection, we implemented the CLR, LD, and CNT signals with discrete logic or PALs. We can use another method, based on multiplexers, to compute these signals.

Figure 12.18 shows how to do this for the simple CPU's state diagram. We compute CLR, LD, and CNT by using the current state to select exactly one multiplexer input. For example, the LD signal should be asserted in state S4 (OD) and no other. When the LD multiplexer's select lines are driven to 0100 (state 4), the E4 input is gated to the EOUT output. E4 is tied high while all the other inputs to the multiplexer are tied low. The multiplexer's output is asserted active low in this case. It is unasserted high in all other cases.

The active low outputs of the multiplexer make this implementation a bit tricky. Since the counter's LD input is also active low, we maintain the correct polarity. An asserted positive logic input of the multiplexer generates an asserted negative logic output, which causes the counter to load.

Let's now turn to the CLR and CNT signals. The CLR signal from the multiplexer, CLRm, must be ORed with Reset to form the counter CLR signal:

CLR = CLRm + Reset

But since the counter's clear signal is active low, we must apply DeMorgan's theorem. Now it becomes a NOR function:

We use the second implementation in Figure 12.18 (AND is the same as OR with complemented inputs and output). The CLR multiplexer's active low output is now in the correct polarity. Combined with the global Reset signal, it can return the machine to S0.

Let's return to the inputs to the CLR multiplexer. Once again, they are active high: assert a multiplexer input high if the CLR signal is to take effect in the associated state. Thus E7, E12, and E13 are tied high, since these correspond to states S7, S12, and S13. We always return to S0 from these states. On the other hand, the transition from S9 to S0 takes place only when Wait is no longer asserted. Thus, the input to E9 is the signal , the condition for returning to S0.

The CNT control is the most complex, since the multiplexer's output is active low but the counter's control signal is active high. The solution is simply to "push the bubble" through to the inputs. In this case, assert a multiplexer input low if you want a count to take place. Since a count takes place unconditionally in states S0, S5, S8, and S10, then E0, E5, E8, and E10 are all tied low.

For the states in which the count is conditional, the multiplexer inputs are tied to the complement of the condition. Thus, S1 and S3 advance when Wait is asserted, and E1 and E3 are tied to . S2, S6, and S11 advance when is asserted, so E2, E6, and E11 are tied to Wait.

Generation of Microoperations Microoperations can be generated from the decoded state and the inputs. The logic expressions are shown below. To ensure proper synchronous operation, the Wait and Reset inputs should be synchronized before being used to form these -expressions:

0 --> PC: Reset
PC + 1 --> PC: S0
PC --> MAR: S0
MAR --> Memory Address Bus:
Wait (S1 + S2 + S5 + S6 + S8 + S9 + S11 + S12)
Memory Data Bus --> MBR:
(S2 + S6 + S11)
MBR --> Memory Data Bus:
Wait (S8 + S9)
MBR --> IR: Wait S3
MBR --> AC: Wait S7

AC --> MBR: IR15 IR14 S4
AC + MBR --> AC: Wait S12
IR<13:0> --> MAR:
( + IR14 + IR15 ) S4
IR<13:0> --> PC: AC15 S13
1 --> Read/:
Wait (S1 + S2 + S5 + S6 + S11 + S12)
0 --> Read/:
Wait (S8 + S9)
1 --> Request:
Wait (S1 + S2 + S5 + S6 + S8 + S9 + S11 + S12)

These are most easily implemented with some form of programmable logic.

Discussion We used several multiplexers in the schematic of Figure 12.18, which may not appear to be much of a savings in terms of package count. Nevertheless, this particular implementation approach is extraordinarily flexible. The regularity of the design makes it easier to debug: it is easy to trace the signals causing a state transition. It is just as easy to modify these transitions, simply by changing the inputs to the multiplexers. The jump counter is a reasonable way to organize state machines with a modest number of states, in the range of 16 to 32.

In a general hybrid jump counter, the jump state is a function of the current state and the inputs. But CNT, CLR, and LD are functions of exactly the same signals. Why implement them with discrete logic when they could be stored in the jump state ROM along with the jump states? We could simply extend the width of the ROM with 1 bit for each of the three output signals. Of course, since we have added five new inputs (Wait plus the four current-state bits), taking this approach increases the number of words in the ROM by a factor of 32.

This general strategy of replacing external logic, like gates, multiplexers, and PALs, with ones and zeros in a ROM is called microprogramming. We will learn more about this approach in the next two subsections.

[Top] [Next] [Prev]

---

This file last updated on 07/16/96 at 04:34:26.
[e-mail];