By the end of this chapter you should be able to:
- Carry out the complete design sequence — word statement, state diagram, state table, state reduction, state assignment, excitation table, equations, circuit — without omitting a step.
- Decide from a specification what has to be remembered, and turn that decision into a set of states with a defensible meaning for each.
- Distinguish Mealy and Moore machines, state the timing difference between their outputs, and explain why the Moore version of a given problem generally needs more states.
- Reduce a state table by the implication-table method, including the chained implications that only resolve on a second pass.
- Choose a state assignment using the adjacency guidelines, and explain why two assignments of the same machine can differ by a factor of two or more in gate count.
- Design an overlapping and a non-overlapping sequence detector as both a Mealy and a Moore machine, and verify the resulting equations against the specification.
- Check the behaviour of unused state codes and say whether a machine is self-starting.
Chapter 24 produced a procedure for designing a counter: write down the sequence of states, tabulate what each flip-flop must do to get from each state to the next, minimise those requirements on a Karnaugh map, and draw the gates. A counter, however, is a very special sequential circuit — it has no input, so its next state depends on nothing but its present state, and its sequence is fixed at the time the gates are wired. Almost nothing in a real system is like that. A traffic controller waits for a vehicle sensor, a serial receiver waits for a start bit, a lift decides where to go next from where it is and which buttons have been pressed.
Admit an input and the same procedure generalises into the single most useful design method in digital electronics: the finite state machine. The circuit has a small number of internal states, the input decides which state follows the present one, and an output is produced from the state, or from the state and the input together. Every controller and every protocol engine is one of these. This chapter sets out the full procedure from an English sentence to a gate-level schematic, distinguishes the two standard output conventions — Mealy and Moore — on the same problem, shows how to remove redundant states and why the choice of binary codes for the states changes the gate count, and then designs two complete machines with every intermediate table shown.
1 From a Word Statement to a Circuit
Every sequential circuit with an input has the same three parts. A state register of \(m\) flip-flops holds the present state; next-state logic computes from the present state and input what the flip-flops must take at the next edge; output logic produces the output. Chapter 21 supplied the flip-flops and Chapters 8 and 22 the means of designing both combinational blocks, so the only new work is deciding what the states are.
The procedure below is worth learning as a sequence, because skipping a step is the usual cause of a design that is nearly right.
- Decide what must be remembered. Each distinct thing the circuit needs to know about the past becomes a state, described by a sentence.
- Draw the state diagram. Circles for states, an arrow for every input–state combination. Every state must have an outgoing arrow for every possible input value, or the machine is incompletely specified.
- Write the state table, listing next state and output against present state and input.
- Reduce the table by finding and merging equivalent states.
- Assign binary codes to the states. With \(k\) states you need \(m = \lceil \log_2 k \rceil\) flip-flops.
- Choose the flip-flop type and build the excitation table, using Chapter 22 to turn each required state change into flip-flop inputs.
- Minimise the next-state and output expressions on Karnaugh maps, with the unused state codes entered as don’t-cares.
- Draw the circuit and check the unused states, confirming that the machine returns to a legal state if it powers up in an illegal one.
Step 1 is the one that requires judgement. A state is an equivalence class of input histories: two histories belong in the same state if, for every continuation, the machine would produce the same output. Take the running example of this chapter, a circuit that raises its output whenever the last three bits of a serial stream were \(101\). It need not remember the stream, nor even the last three bits, but only how much of the pattern is matched so far:
- nothing useful yet — the last bit was not the start of a match;
- the last bit was a 1, so one third of the pattern is in place;
- the last two bits were 10, so two thirds of the pattern is in place.
Three states. There is no state for "the last two bits were 11", because a machine that has just seen 11 is in the same position as one that has just seen a single 1: in both, the next two bits 01 would complete a match. Recognising that at the outset keeps the machine small; missing it produces a larger machine that the state reduction of Section 3 collapses back down anyway.
Before adding a state, ask whether any continuation of the input would make the machine behave differently in it than in a state already present. If none would, the two are equivalent and the extra state costs flip-flops and gates for nothing.
2 Mealy and Moore: Two Models of the Same Machine
Both blocks of logic take the present state; the question that separates the two standard models is whether the output logic also takes the input.
Named after E. F. Moore and G. H. Mealy, whose 1955–56 papers set out the two conventions. The next-state function is identical in form; only the output function differs.
That single path has two consequences, and both matter in practice.
The timing differs. A Moore output is a function of the flip-flop outputs alone, so it changes only just after a clock edge and is stable for a whole clock period. A Mealy output changes as soon as the input changes, part-way through a period, and any glitch on the input appears at the output. A Mealy output therefore announces a condition one clock period earlier — sometimes exactly what is wanted, sometimes a hazard, since it is synchronised to nothing. If it must drive another clocked block it is usually passed through one more flip-flop, which turns it into a Moore output and gives back the period that was saved.
The state count differs. In a Moore machine the output is attached to the state, so two situations requiring different outputs must be different states even if they behave identically thereafter.
The Mealy version needs the three states identified in Section 1. Its only output of 1 belongs to the arc from \(S_2\) on input 1: at that moment the last two bits were \(10\) and the arriving bit is \(1\), which completes the pattern. That arc leads to \(S_1\) and not back to \(S_0\), because the \(1\) just consumed can serve as the first bit of the next match — this is what overlapping detection means. For a non-overlapping detector the same arc goes to \(S_0\) instead, discarding the completed pattern and starting again from nothing.
The Moore version cannot label an arc, so it needs a fourth state \(S_3\) whose only purpose is to carry the output 1. It is entered from \(S_2\) on input 1 and left on the next clock, and its outgoing arcs duplicate those of \(S_1\) — 1 to \(S_1\), 0 to \(S_2\) — because a machine that has just completed \(101\) is in the same position as one that has just seen a single 1.
| Property | Mealy | Moore |
|---|---|---|
| Output written on | the arcs, as \(x\,/\,z\) | the states, as \(S\,/\,z\) |
| States for the 101 detector | 3 | 4 |
| Output appears | during the clock period in which the last bit arrives | one clock period later, after the edge |
| Output width | as long as the input condition holds | exactly one clock period |
| Sensitive to input glitches | yes — they pass straight through | no — the flip-flops filter them |
| Typical use | fast handshakes, where a cycle matters | control signals that must be clean and clock-aligned |
Converting between the two is mechanical: to make a Moore machine from a Mealy one, split every state entered by arcs carrying different outputs into one copy per output value; to go the other way, move each state’s output onto the arcs entering it and merge whatever becomes equivalent. Neither model can do anything the other cannot — the choice is about timing and cost, not capability.
3 State Reduction by the Implication Table
A state table written directly from a word statement usually contains states that behave identically. Removing them may reduce \(\lceil \log_2 k \rceil\) and save a whole flip-flop, and even when it does not, fewer states mean more unused codes, more don’t-cares on the excitation maps and smaller equations.
Two states \(p\) and \(q\) are equivalent if, started in either, the machine gives the same output sequence for every input sequence. There are infinitely many sequences, but the condition reduces to a finite one: \(p \equiv q\) if and only if, for every input value, they give the same output and their next states are themselves equivalent. That definition is recursive, so it must be applied by elimination, and the implication table is the bookkeeping that does it.
Draw a chart with one cell for every unordered pair of states. In each cell write a cross if the two states give different outputs for some input, and otherwise the pairs of next states that would have to be equivalent for this pair to be. Then sweep the chart repeatedly, crossing out any cell that contains a pair already crossed out, until a sweep changes nothing. The cells still standing are the equivalent pairs.
A Mealy machine with input \(x\) and output \(z\) has the state table
| Present state | Next state | Output \(z\) | ||
|---|---|---|---|---|
| \(x = 0\) | \(x = 1\) | \(x = 0\) | \(x = 1\) | |
| a | b | c | 0 | 1 |
| b | c | e | 0 | 0 |
| c | a | f | 0 | 1 |
| d | b | d | 0 | 1 |
| e | a | f | 0 | 1 |
| f | g | d | 0 | 1 |
| g | e | e | 0 | 0 |
States b and g give \(z = 0\) for \(x = 1\) while the other five give \(z = 1\), so every pair with one member from \(\{b, g\}\) and one from \(\{a, c, d, e, f\}\) is crossed out at once: ab, ag, bc, bd, be, bf, cg, dg, eg and fg. Eleven pairs remain, each filled with the next-state pairs implied by \(x = 0\) and \(x = 1\), dropping any whose members coincide:
| Pair | Implied by \(x = 0\) | Implied by \(x = 1\) | Fate |
|---|---|---|---|
| a–c | b–a | c–f | × pass 1, via ab |
| a–d | b–b ✓ | c–d | × pass 2, via cd |
| a–e | b–a | c–f | × pass 1, via ab |
| a–f | b–g | c–d | × pass 2, via cd |
| b–g | c–e | e–e ✓ | survives |
| c–d | a–b | f–d | × pass 1, via ab |
| c–e | a–a ✓ | f–f ✓ | survives (identical rows) |
| c–f | a–g | f–d | × pass 1, via ag |
| d–e | b–a | d–f | × pass 1, via ab |
| d–f | b–g | d–d ✓ | survives |
| e–f | a–g | f–d | × pass 1, via ag |
The first pass crosses out ac, ae, cd, cf, de and ef. The second pass is the one most often forgotten: ad and af both depend on cd, which went only on the first pass, so they must now go too. A third pass changes nothing and the process stops.
Three pairs survive — b–g, c–e and d–f — and they share no members, so the classes are \(\{a\}, \{b, g\}, \{c, e\}, \{d, f\}\). Naming them A, B, C, D:
| Present state | Next state | Output \(z\) | ||
|---|---|---|---|---|
| \(x = 0\) | \(x = 1\) | \(x = 0\) | \(x = 1\) | |
| A (a) | B | C | 0 | 1 |
| B (b, g) | C | C | 0 | 0 |
| C (c, e) | A | D | 0 | 1 |
| D (d, f) | B | D | 0 | 1 |
Seven states have become four, so \(\lceil \log_2 7 \rceil = 3\) flip-flops become \(\lceil \log_2 4 \rceil = 2\), and the next-state logic shrinks with the register. Simulating both tables against every input string up to length twelve confirms that they give identical outputs from corresponding starting states.
Grouping the surviving pairs into classes is legal only because equivalence in a completely specified machine really is an equivalence relation. If the table contains don’t-care outputs the relation becomes mere compatibility, which is not transitive: p may be compatible with q and q with r while p and r are not. Incompletely specified machines therefore need a covering procedure, not a simple partition.
4 State Assignment and Why It Matters
After reduction the states are still names. Turning them into bit patterns is the state assignment, the one step with no unique right answer: every assignment gives a correct machine, but different assignments give different amounts of logic. With \(k\) states and \(m\) flip-flops the number of distinct assignments is
which for three states in two flip-flops is \(4!/1! = 24\), and for eight states in three flip-flops is \(8! = 40320\). Many of these are related by permuting or complementing flip-flops and give identical gate counts, but plenty are genuinely different.
Minimising all twenty-four assignments of the three-state Mealy detector exactly gives a best case of five literals across \(D_1\), \(D_0\) and \(z\) and a worst case of nine — nearly twice the logic for the same behaviour. The four-state Moore version ranges from six literals to seventeen. Assignment is not a formality.
| Machine | Assignment | Equations | Literals |
|---|---|---|---|
| Mealy, best | \(S_0 = 00,\ S_1 = 01,\ S_2 = 10\) | \(D_1 = Q_0x'\), \(D_0 = x\), \(z = Q_1x\) | 5 |
| Mealy, worst | \(S_0 = 01,\ S_1 = 00,\ S_2 = 10\) | \(D_1 = Q_1'Q_0'x'\), \(D_0 = Q_0x' + Q_1x'\), \(z = Q_1x\) | 9 |
| Moore, natural | \(S_0 = 00,\ S_1 = 01,\ S_2 = 10,\ S_3 = 11\) | \(D_1 = Q_0x' + Q_1Q_0'x\), \(D_0 = x\), \(z = Q_1Q_0\) | 8 |
| Moore, best | \(S_0 = 00,\ S_1 = 11,\ S_2 = 10,\ S_3 = 01\) | \(D_1 = Q_1'x + Q_0\), \(D_0 = x\), \(z = Q_1'Q_0\) | 6 |
Exhaustive search is only practical for small machines, so three guidelines are used instead. They all aim at the same thing: making the 1s of each next-state function cluster on the Karnaugh map, since adjacent codes are adjacent map cells.
- States that have the same next state for a given input should be given adjacent codes.
- States that are the next states of the same present state, under different inputs, should be adjacent.
- States with the same output should be adjacent.
The first rule carries most weight and the third least; where they conflict, satisfy as many as the codes allow. Two special assignments are worth knowing. The reset state should be all-zeros, so that the ordinary asynchronous clear puts the machine into it. And in a programmable device, where flip-flops are plentiful and wide gates are not, a one-hot assignment gives each state its own flip-flop: \(k\) flip-flops instead of \(\lceil \log_2 k \rceil\), but next-state terms that are an AND of one state bit and one input. Chapter 28 returns to that trade-off for FPGAs.
5 Worked Design: the 101 Detector as a Mealy Machine
Design a synchronous circuit with one serial input \(x\) and one output \(z\). The output is to be 1 whenever the last three bits received are 101, with overlapping sequences counted.
States and table. The three states are those of Section 1: \(S_0\) nothing matched, \(S_1\) the last bit was 1, \(S_2\) the last two bits were 10. From the state diagram of Figure 26.2:
| Present state | Next state | Output \(z\) | ||
|---|---|---|---|---|
| \(x = 0\) | \(x = 1\) | \(x = 0\) | \(x = 1\) | |
| \(S_0\) | \(S_0\) | \(S_1\) | 0 | 0 |
| \(S_1\) | \(S_2\) | \(S_1\) | 0 | 0 |
| \(S_2\) | \(S_0\) | \(S_1\) | 0 | 1 |
No two rows have both the same next states and the same outputs, so no reduction is possible. Assignment: \(S_0 = 00\), \(S_1 = 01\), \(S_2 = 10\) — reset at all-zeros, and one of the cheapest of the twenty-four.
Excitation table. With D flip-flops \(D = Q^{+}\), so the transition table is the excitation table. The code 11 is unused, giving two rows of don’t-cares:
| \(Q_1\) | \(Q_0\) | \(x\) | \(Q_1^{+}\) | \(Q_0^{+}\) | \(D_1\) | \(D_0\) | \(z\) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | × | × | × | × | × |
| 1 | 1 | 1 | × | × | × | × | × |
Minimisation. Each function is mapped on a three-variable Karnaugh map with rows \(Q_1\) and columns \(Q_0x\) in the Gray order 00, 01, 11, 10 of Chapter 8.
| \(Q_1\) \\ \(Q_0x\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| \(D_1\) 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | × | × |
| \(D_0\) 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | × | × |
| \(z\) 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | × | × |
For \(D_1\) the single 1 sits at \(Q_1Q_0x = 010\); grouping it with the don’t-care at 110 gives the pair \(Q_0x'\). For \(D_0\) the 1s at 001, 011 and 101 group with the don’t-care at 111 into the whole \(x = 1\) column, giving simply \(x\). For \(z\) the single 1 at 101 pairs with the don’t-care at 111 to give \(Q_1x\). Hence
Five literals in all: one inverter, two two-input AND gates and two D flip-flops. \(D_0 = x\) says something pleasant about this machine — the lower flip-flop is simply a one-bit delay of the input, exactly as in the shift register of Chapter 25.
Verification. The equations were simulated clock by clock against a reference that scans for overlapping occurrences of 101, for every input string up to fourteen bits and for fifty thousand longer random ones. They agree in every case. That is the only check worth trusting on a sequential design; re-inspecting the state diagram proves nothing.
The unused state. Substituting \(Q_1Q_0 = 11\) gives \(D_1D_0 = 10 = S_2\) when \(x = 0\) and \(01 = S_1\) when \(x = 1\), so the machine is legal again after one clock and is self-starting. Note that \(z = Q_1x = 1\) in the illegal state with \(x = 1\), so a machine powering up at 11 can emit one spurious detection; the fix is an explicit reset, not a redesign.
The non-overlapping variant. One table entry changes: the next state from \(S_2\) with \(x = 1\) becomes \(S_0\), since the completed pattern is discarded. Row 101 of the transition table then has \(Q_1^{+}Q_0^{+} = 00\), which removes minterm 101 from \(D_0\); regrouping gives \(D_0 = Q_1'x\), with \(D_1 = Q_0x'\) and \(z = Q_1x\) unchanged. On the stream \(0110101101\) the overlapping machine gives 1s in clock periods 5, 7 and 10, the non-overlapping one only in 5 and 10.
6 The Same Detector as a Moore Machine
The four states of Figure 26.2 are \(S_0\) reset, \(S_1\) last bit 1, \(S_2\) last two bits 10 and \(S_3\) the pattern just completed, with outputs 0, 0, 0 and 1. Assign the natural binary codes \(S_0 = 00\), \(S_1 = 01\), \(S_2 = 10\), \(S_3 = 11\); with four states none of the codes is spare, so there are no don’t-cares this time.
| \(Q_1\) | \(Q_0\) | \(x\) | state | \(D_1\) | \(D_0\) | \(z\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | \(S_0 \to S_0\) | 0 | 0 | 0 |
| 0 | 0 | 1 | \(S_0 \to S_1\) | 0 | 1 | 0 |
| 0 | 1 | 0 | \(S_1 \to S_2\) | 1 | 0 | 0 |
| 0 | 1 | 1 | \(S_1 \to S_1\) | 0 | 1 | 0 |
| 1 | 0 | 0 | \(S_2 \to S_0\) | 0 | 0 | 0 |
| 1 | 0 | 1 | \(S_2 \to S_3\) | 1 | 1 | 0 |
| 1 | 1 | 0 | \(S_3 \to S_2\) | 1 | 0 | 1 |
| 1 | 1 | 1 | \(S_3 \to S_1\) | 0 | 1 | 1 |
\(D_1\) is 1 at \(Q_1Q_0x = 010\), \(101\) and \(110\). Cells 010 and 110 differ only in \(Q_1\) and pair into \(Q_0x'\); the 1 at 101 has no neighbour and stands alone as \(Q_1Q_0'x\). \(D_0\) is 1 in exactly the four cells with \(x = 1\), so \(D_0 = x\) again. \(z\) does not involve \(x\) at all — that is what makes this Moore — and is 1 only in state 11, so \(z = Q_1Q_0\). Hence
Eight literals against the Mealy machine’s five, for the same detection job. Simulated against the same reference over every string up to fourteen bits and fifty thousand random strings, the outputs match the specification exactly, one clock period later than the Mealy machine’s.
All four codes are used, so there is no illegal state and the self-starting question does not arise. For the non-overlapping version the arcs out of \(S_3\) change to \(S_0\) on 0 and \(S_1\) on 1, which alters only the last two rows of the table.
Figure 26.4 is the picture worth remembering. Take the input \(0110101101\). The Mealy output goes high inside clock period 5, as soon as the third bit of the first \(101\) is present at the input, and it goes low again when the input changes; the Moore output does not move until the edge at the end of period 5, and then stays high for the whole of period 6. Both machines report all three overlapping occurrences, in periods 5, 7 and 10 for the Mealy machine and 6, 8 and 11 for the Moore machine.
The choice follows from that picture. If a clock period genuinely cannot be spared, use the Mealy machine and accept that its output is only as clean as its input. If the output is a control signal for other clocked logic — a load enable, a bus request — use the Moore machine, whose output is free of any glitch the input carries. A common compromise is to design as Mealy for the smaller state count and then register the output.
7 A Second Example: the Serial Adder
A sequence detector is not the only shape a state machine takes, and it is worth seeing one whose states have an arithmetic meaning rather than a pattern-matching one. The serial adder adds two binary numbers one bit position per clock, least significant bit first, and it is the natural partner of the shift registers of Chapter 25: two registers supply the addend bits \(A\) and \(B\) from their serial outputs, and a third shifts the sum bit \(S\) back in.
What must be remembered between one bit position and the next? Only the carry — so the machine has two states, \(C_0\) and \(C_1\), and two inputs, giving a table of four columns.
| Present state | Next state / output \(S\), for \(AB =\) | |||
|---|---|---|---|---|
| 00 | 01 | 10 | 11 | |
| \(C_0\) (carry 0) | \(C_0\) / 0 | \(C_0\) / 1 | \(C_0\) / 1 | \(C_1\) / 0 |
| \(C_1\) (carry 1) | \(C_0\) / 1 | \(C_1\) / 0 | \(C_1\) / 0 | \(C_1\) / 1 |
This is a Mealy machine of necessity: a full adder’s sum is a function of all three of its inputs, so the sum bit depends on \(A\) and \(B\) as well as on the stored carry. Assigning \(C_0 = 0\) and \(C_1 = 1\) needs one flip-flop, whose output \(Q\) is the carry:
which is precisely the full adder of Chapter 16 with its carry output returned to its carry input through one flip-flop. All eight combinations of \(A\), \(B\) and \(Q\) were checked against the state table, and the whole circuit was checked against integer addition for twenty thousand random pairs of operands of up to sixteen bits; it agrees in every case, with the final state of the flip-flop giving the carry out of the most significant position.
The ripple-carry adder of Chapter 16 uses \(n\) full adders and completes in one clock; the serial adder uses one full adder and one flip-flop and completes in \(n\) clocks. Both compute the same sum, and the choice between them is the classic hardware-against-time trade that recurs in every part of this subject.
A Moore version of the same adder is instructive because it is worse. To make the output a function of the state alone, the state would have to encode the carry and the sum bit just produced: four states, two flip-flops, and a sum that appears a clock late and must be realigned with the register collecting it. Mealy machines are smaller, Moore machines cleaner, and the specification decides which matters.
Two habits are worth carrying out of this chapter. Write the meaning of each state beside it in the diagram; a diagram whose states are called \(S_0\) to \(S_5\) with no explanation cannot be checked by anyone, its author included. And simulate the final equations rather than the diagram: a slip in transcribing a Karnaugh map is invisible to inspection and obvious to a simulation of eight input combinations. Chapter 30 shows how to write the same machine in VHDL so that simulation and synthesised hardware come from one description.
8 Summary and Key Results
| Step | What is produced | Why it matters |
|---|---|---|
| State identification | One state per class of input histories that behave alike | Fixes the size of the machine; the only step needing judgement |
| State diagram and table | Next state and output for every state and input | Every state needs an arc for every input, or the machine is incomplete |
| State reduction | Equivalent states merged by the implication table | May remove a flip-flop, since \(m = \lceil \log_2 k \rceil\) |
| State assignment | A binary code per state, out of \((2^m)!/(2^m-k)!\) choices | Changed the 101 detector between 5 and 9 literals for the same behaviour |
| Excitation table | Flip-flop inputs for every transition; \(D = Q^{+}\) for D types | Unused codes become don't-cares and shrink the equations |
| Minimisation and circuit | Next-state and output equations, then gates | Two-level SOP from a K-map exactly as in Chapter 8 |
| Unused-state check | Where each illegal code goes on the next clock | Decides whether the machine is self-starting or can lock out |
9 Common Mistakes
A state diagram in which some state has an arrow for \(x = 1\) but none for \(x = 0\) is not a specification of anything: the hardware will do something when that input arrives, decided by whatever the minimisation happened to produce. Every state of a machine with one input needs exactly two outgoing arcs, and a machine with two inputs needs four. Counting arcs against states before writing the table catches this in seconds.
Crossing out the pairs whose outputs differ, then crossing out the pairs that depend on those, and then stopping, misses every chained implication. In Worked Example 26.1 the pairs a–d and a–f survive the first pass and are only removed on the second, once c–d has gone. The sweep must be repeated until a whole pass changes nothing, and the result of stopping early is a state table that claims two states are equivalent when they are not.
A Mealy output is combinational logic driven partly by the input, so it changes whenever the input changes, not at the clock edge, and it carries any glitch the input carries. Using one directly as a clock, a clock enable or an asynchronous reset for another block invites a spurious pulse. Either use a Moore output or pass the Mealy output through a flip-flop, which is the same thing at the cost of one clock period.
10 Chapter Review
1. Design the state diagram of a Mealy machine that detects the overlapping sequence 1101 on a serial input. How many states does it need, and how many would the Moore version need?
Four states for the Mealy machine, corresponding to how much of the pattern is matched: \(S_0\) nothing, \(S_1\) seen 1, \(S_2\) seen 11, \(S_3\) seen 110. From \(S_0\): 0 to \(S_0\), 1 to \(S_1\). From \(S_1\): 0 to \(S_0\), 1 to \(S_2\). From \(S_2\): 0 to \(S_3\), 1 to \(S_2\) — a further 1 leaves the last two bits still 11. From \(S_3\): 0 to \(S_0\), 1 to \(S_1\) with output 1, because after 1101 the only suffix that is also a prefix of the pattern is the final single 1. The Moore version needs five: one extra state carrying the output 1, entered from \(S_3\) on input 1, whose outgoing arcs duplicate those of \(S_1\).
2. Two states \(p\) and \(q\) of a completely specified machine produce the same output for every input value, and their next states for \(x = 0\) are \(p\) and \(q\) themselves. Are they equivalent? Justify the answer with the implication table.
The cell for the pair p–q would contain the implication p–q from \(x = 0\), which is the cell itself, plus whatever the \(x = 1\) column implies. A self-implication can never be crossed out, because doing so would require it to have been crossed out already, so it never causes elimination. The pair therefore survives provided the \(x = 1\) implication also survives. If the \(x = 1\) next states are the same state, or a pair that itself survives, then \(p \equiv q\). Cyclic implications of this kind are resolved in favour of equivalence, which is what makes the algorithm terminate.
3. A three-state machine is to be built with two flip-flops. How many distinct state assignments exist, and why can two of them give very different gate counts?
There are \((2^2)!/(2^2-3)! = 4!/1! = 24\) assignments. They differ because the binary codes decide where the 1s of each next-state function fall on the Karnaugh map, and adjacent codes are adjacent cells that can be combined. An assignment that places the states which share a next state at adjacent codes produces large groups and short product terms; one that scatters them produces isolated 1s that cannot be grouped. For the 101 detector the best of the 24 needs 5 literals across \(D_1\), \(D_0\) and \(z\) and the worst needs 9.
4. Verify that \(D_1 = Q_0x'\), \(D_0 = x\), \(z = Q_1x\) detects 101 by hand-simulating the input 1, 0, 1, 1, 0, 1 from the reset state 00.
Start at \(Q_1Q_0 = 00\). Bit 1 = 1: \(z = Q_1x = 0\); next \(Q_1 = Q_0x' = 0\), \(Q_0 = 1\) → 01. Bit 2 = 0: \(z = 0\); next \(Q_1 = 1\cdot 1 = 1\), \(Q_0 = 0\) → 10. Bit 3 = 1: \(z = 1 \cdot 1 = 1\) — the first detection, correct, since the last three bits are 101; next state \(Q_1 = 0\), \(Q_0 = 1\) → 01. Bit 4 = 1: \(z = 0\); next 01. Bit 5 = 0: \(z = 0\); next 10. Bit 6 = 1: \(z = 1\) — the second detection, and the last three bits are indeed 101. The output is 0, 0, 1, 0, 0, 1, which is what the specification demands.
5. Why does the Moore version of the 101 detector have no illegal state, while the Mealy version has one? What does the Mealy machine do if it powers up in it?
The Moore machine has four states and two flip-flops, so all four codes are used and no code is illegal. The Mealy machine has three states in two flip-flops, leaving 11 unused. Substituting \(Q_1Q_0 = 11\) into \(D_1 = Q_0x'\) and \(D_0 = x\) gives 10 when \(x = 0\) and 01 when \(x = 1\), both legal states, so the machine is self-starting and recovers within one clock. It is not entirely harmless, however: \(z = Q_1x\) evaluates to 1 in the illegal state with \(x = 1\), so one false detection can be emitted before recovery. An explicit power-on reset to 00 removes the possibility altogether.