PadhaikoAll subjects

Sequential Machine Designs

Digital Logic (ENEX 152)

Open in the Padhaiko app

7.1 Machine design procedures

A synchronous sequential machine (finite state machine, FSM) is a clocked circuit made of flip-flops that store the present state and combinational logic that finds the next state and the output from the state and the inputs.

Mealy and Moore Machines
FeatureMealy machineMoore machine
Output depends onPresent state and present inputPresent state only
Output changesAs soon as the input changes (may glitch)Only after the clock edge
Number of statesUsually fewerUsually more
Output on diagramOn the arrows (input/output)Inside the state circle

Design procedure

  1. Write the word description and build a primitive state diagram (one state for each situation to be remembered).
  2. Convert it into a state table (flow table).
  3. Reduce the number of states by removing equivalent (redundant) states.
  4. Make a state assignment with flip-flops, where number of states.
  5. Write the transition table and find the flip-flop inputs from the excitation table.
  6. Draw excitation maps and minimise the input equations and the output equation.
  7. Draw the circuit and check it against the state diagram.

7.2 Primitive state diagrams

A state diagram shows each state as a circle and each transition as an arrow labelled input/output (Mealy) or just the input (Moore, with the output written inside the circle). A primitive diagram is the first, unreduced version in which every distinct history that matters gets its own state.

For a detector of the sequence 101 (overlapping allowed) the states are

7.3 Transition/flow tables

The state diagram is written as a state table (flow table) that lists the next state and the output for each present state and input.

State Table of the 101 Sequence Detector (Mealy)
Present stateNext state, X = 0Next state, X = 1Output Z, X = 0Output Z, X = 1
S0S0S100
S1S2S100
S2S0S101

7.4 Redundant states

Two states are equivalent if, for every possible input sequence, the machine gives the same output sequence whichever of the two it starts in. Equivalent states are redundant and can be merged, which saves flip-flops and gates.

Row-matching (simple) test: two states are equivalent if for each input they have the same output and go to the same next state (or to states already known to be equivalent). After merging, repeat the test because new equal rows may appear. For larger tables an implication table is used.

7.5 Pure binary assignment tables

In a state assignment each state gets a binary code. In the pure binary (straight) assignment the states are numbered in order with the smallest number of flip-flops: S0 = 00, S1 = 01, S2 = 10 for three states. The unused code (11) becomes a don't care, which helps minimisation. Other assignments (Gray, one-hot) give different amounts of logic, and there are possible assignments, so a good one is found by judgement.

Pure Binary State Assignment and Transition Table
Present Q1 Q0XNext Q1 Q0Output Z
000000
001010
010100
011010
100000
101011
110X XX
111X XX

7.6 Excitation maps

With D flip-flops the flip-flop input equals the next state, . With JK or T flip-flops the excitation table (Chapter 5) is used to convert each present-to-next change into the needed inputs. The inputs are then plotted on excitation maps, one K-map for each flip-flop input and one for the output, using the don't cares for unused states.

Excitation Map for D1 (rows Q1, columns Q0 X)
Q1 / Q0X00011110
00001
100XX

The only 1 (at ) joins the don't care 110, so . In the same way and .

7.7 Realization of the models

To realise a Mealy or Moore model, build the three blocks: the state register (D, JK or T flip-flops), the next-state logic from the excitation equations, and the output logic. In a Moore machine the output logic depends only on the flip-flop outputs, so it is placed after the register; in a Mealy machine the input also feeds the output logic, so the output can change between clock edges.

7.8 Circuit diagram of synchronous machine

The circuit of the 101 detector with two D flip-flops is described by the equations

It needs one inverter, two AND gates, two D flip-flops with a common clock, and the input goes both to and to the output gate. Every flip-flop has the same clock, and a reset line (not shown) sets the machine to S0 = 00.

7.9 One-bit and two-bit input sequence detectors

A one-bit input detector receives one bit per clock and watches for a bit pattern (for example 101, 1011 or 110). A two-bit input detector receives a pair per clock and watches for a pattern of pairs, so each state has four outgoing arrows.

Two things must be decided in every detector: whether the sequences may overlap (after a detection, the last bits can start the next pattern), and whether the output is Mealy (Z becomes 1 at the clock in which the last bit arrives) or Moore (Z becomes 1 one clock later, in a final state).


Worked Examples

Example 1

1 (12 marks)

Design a Mealy sequence detector with one input and one output that gives whenever the last three bits received are 101 (overlapping allowed). Use D flip-flops, and trace the output for the input stream 1101101.

State diagram and table. The three states S0, S1, S2 and their transitions are in the state table of section 7.3: S0 on 1 goes to S1; S1 on 0 goes to S2 and on 1 stays in S1; S2 on 1 gives and goes to S1 (the final 1 can start a new pattern because overlap is allowed); S2 on 0 goes to S0.

State assignment. Three states need two flip-flops: S0 = 00, S1 = 01, S2 = 10 and 11 unused (don't care). The transition table is in section 7.5.

Excitation equations (D flip-flops, ). only for (S1 with goes to S2 = 10), so with the don't cares at 110 and 111: . whenever (every state goes to S1 = 01 on a 1 and to 00 or 10 on a 0), so . only for , so using the don't care at 111.

Trace for 1101101. Start S0. Input 1: S1, . Input 1: S1, . Input 0: S2, . Input 1: S1, (found 101). Input 1: S1, . Input 0: S2, . Input 1: S1, .

Answer:

, , ; output stream 0, 0, 0, 1, 0, 0, 1 (two detections).

Example 2

2 (10 marks)

Reduce the following Mealy state table (next state/output for and ) to the minimum number of states: a: a/0, b/0; b: c/0, d/0; c: a/0, d/0; d: e/0, f/1; e: a/0, f/1; f: g/0, f/1; g: a/0, f/1.

Compare rows (row matching). States e and g both have the entries a/0 and f/1, so they are equivalent. Replace g by e everywhere.

Repeat the test. After the replacement, state f has the entries e/0 and f/1 and state d has e/0 and f/1. They are equal, so d and f are equivalent: replace f by d.

Check the other states. a, b, c and e have different next states or outputs, so no more can be merged. The final table has 5 states:

Reduced State Table
Present stateNext/out, X = 0Next/out, X = 1
aa/0b/0
bc/0d/0
ca/0d/0
de/0d/1
ea/0d/1
Answer:

The 7 states reduce to 5 (g merged into e, and f merged into d); 3 flip-flops are still needed, because .

Example 3

3 (8 marks)

A machine has a two-bit input . It gives when the input 01 is followed immediately by the input 10; otherwise . Design it with one D flip-flop and test it on the input sequence 01, 01, 10, 11, 01, 10.

States. Two situations are enough: A (the previous input was not 01) and B (the previous input was 01). Assign A = 0 and B = 1 with one flip-flop .

State table. From either state the machine goes to B if the present input is 01 and to A otherwise. The output is 1 only in state B with the input 10 (arrow B to A labelled 10/1).

State Table with Two-bit Input
Present QInput 00Input 01Input 10Input 11
A (0)A/0B/0A/0A/0
B (1)A/0B/0A/1A/0

Equations. The next state is 1 for the input , whichever the present state is, so . The output is 1 for and , so .

Test. Inputs 01, 01, 10, 11, 01, 10 give: first 01: becomes 1, . Second 01: , . 10: , becomes 0. 11: , . 01: , . 10: .

Answer:

, ; output stream 0, 0, 1, 0, 0, 1.


Exercises

Exercises: Sequential Machine Designs

Question 1

Distinguish between Mealy and Moore machines. For a Moore machine detecting the pattern 11, how many states are needed (overlap allowed) and why does it need more states than the Mealy version?

In a Mealy machine the output is a function of the state and the input; in a Moore machine it depends on the state only, so it changes only at clock edges.

A Mealy 11 detector needs 2 states: S0 (last bit not 1) and S1 (last bit was 1), with on the arrow S1 to S1 for . A Moore detector needs a state that represents the detection, because the output is part of the state: S0 (no 1), S1 (one 1) and S2 (at least two 1s, output 1), so 3 states.

Answer:

Mealy: output from state and input; Moore: from state only. The Moore 11 detector needs 3 states against 2 for Mealy, because the output must be attached to a state.

Question 2

Design a Mealy detector for the pattern 11 (overlapping) with one D flip-flop, and give its output for the input stream 0110111.

S0 = 0 (last bit was 0 or start) and S1 = 1 (last bit was 1). The next state is the input itself, so . The output is 1 when the machine is in S1 and , so .

Stream 0, 1, 1, 0, 1, 1, 1 from : = 0, 0, 1, 0, 0, 1, 1. Three overlapping pairs 11 are found (the last three ones give two).

Answer:

, ; output 0, 0, 1, 0, 0, 1, 1.

Question 3

Reduce the Mealy table (next/output): A: B/0, C/0 for X = 0, 1 respectively; B: A/0, D/1; C: A/0, E/1; D: B/0, D/0; E: B/0, D/0. How many flip-flops are needed before and after reduction?

D and E have the same entries (B/0 and D/0), so E is merged into D. Then B has A/0 and D/1 and C has A/0 and D/1 (E became D), so C is merged into B.

A then has B/0 and B/0 (C became B). The reduced machine has 3 states: A, B, D.

Before: 5 states need 3 flip-flops (). After: 3 states need 2 flip-flops.

Answer:

5 states reduce to 3 (A, B, D); the flip-flops fall from 3 to 2.

Question 4

For the 101 detector with the assignment S0 = 00, S1 = 01, S2 = 10, find the inputs if JK flip-flops are used.

Excitation table of JK: : ; : ; : ; : .

Flip-flop 1. goes only for , so . is 1 only in state 10 and always returns to 0 on the next clock, so .

Flip-flop 0. goes when and : . It goes when and : .

Answer:

, , , .

Question 5

How many flip-flops are needed for a machine with 9 states? Write the pure binary assignment for the first four states and state what is done with the unused codes.

, so 4 flip-flops are needed.

Pure binary assignment: S0 = 0000, S1 = 0001, S2 = 0010, S3 = 0011, and so on to S8 = 1000. The 7 unused codes 1001 to 1111 are treated as don't cares in the excitation maps (or a reset path is provided so the machine cannot stay in them).

Answer:

4 flip-flops; S0 = 0000, S1 = 0001, S2 = 0010, S3 = 0011; the 7 unused codes are don't cares.

← Registers and CountersDigital Integrated Circuits →