5.3 From state diagram to circuit

Why this matters

A state diagram says what a machine does, but a circuit is made of gates and flip-flops. This section is the translation between the two, and every step of it is mechanical: give each state a code, turn the arrows into a truth table, and minimize each output with a K-map. Doing it by hand once shows the kind of work a synthesis tool does when it reads a state machine written in SystemVerilog, although a tool may choose other codes, such as one flip-flop per state, and so arrive at different equations.

Learning goals

• Describe a state machine circuit as a register that holds the state plus combinational logic that computes the next state and the output.
• Choose a code for every state and work out how many state bits a machine needs.
• Build the encoded truth table of a machine, with the unused codes as don't cares.
• Derive a minimal equation for each next-state bit and each output from a K-map.
• Predict what a circuit does if it ever lands in a state code that the diagram does not use.

Intuition first

Think of a board game played by one person. The position of the pieces is all that matters about the past: the game does not care how the pieces got there. A table of rules says, for each position and each die roll, what the new position is and what you announce. Each tick of the clock is one turn.

A state machine circuit has exactly these two parts. The position has to be written down between turns, and that is the job of the flip-flops: they hold a number, the code of the current state. The table of rules is a function with no memory of its own, so it is combinational logic: it reads the stored number and the input, and produces the number to store next and the output.

If you program, this is a function next(state, input) and a variable state that you assign the result to, once per iteration of a loop. The analogy breaks in one way: in hardware the function is not called, it is built from gates, one equation for each bit that comes out of it, and all the equations are always evaluating together.

The shape of the circuit

Illustration a block diagram that explains an idea; its behavior is not checked

A block diagram with inputs In and clk and output Out.

Block "combinational logic" cl: In is In, PS is n2, Out is Out, NS is n1.

2-bit register reg: d is n1, q is n2, clocked by clk.

This diagram is illustrative: its behavior is not checked.

Description: A block diagram. A box labeled combinational logic has inputs In and PS and outputs Out and NS. The NS wire, two bits wide, goes to the d input of a register drawn as a flip-flop box, two bits wide. The register's q output, PS, goes back to the logic's PS input. The clock enters only the register.

Figure 5.3.1. Every state machine circuit has this shape. The register holds the state, the logic computes the next state and the output.

Definition 5.3.1(present state and next state).

The output of the register is the present state, written PS. It is the code of the state the machine is in during the current clock cycle. The input of the register is the next state, written NS: the code that the register will hold after the next rising clock edge. The logic computes NS, and the output, from PS and the input.

Read Figure 5.3.1 as a loop. The present state and the input go into the logic, the next state comes out and enters the register, and one clock edge later it is the present state. Every loop in the circuit passes through the register, so the state changes only at clock edges.

For the register to hold a state, the state needs a number.

Definition 5.3.2(state code).

A state code is the bit pattern the register holds while the machine is in that state. Every state needs its own code, because two states that shared one could not be told apart by the logic. The bits of the register are the state bits.

Counting works the same way as for any binary number. A register of $s$ bits can hold $2^s$ different patterns, so a machine with $S$ states needs the smallest $s$ with $2^s \ge S$, which is $\lceil \log_2 S \rceil$. The long-press detector of Section 5.2 has three states, so it needs two state bits. Two bits hold four patterns, so one pattern is left over: an unused code. Whenever $S$ is not a power of two there are unused codes.

Two more counts say how big the logic is. By the rule of Definition 5.2.2, each input value that can occur is carried by exactly one arrow leaving a state, so a state has at most $2^I$ arrows when the machine has $I$ inputs. Combining arrows, or leaving out a combination that can never occur, makes the number smaller. And the logic has $s + I$ inputs, so its truth table has $2^{s+I}$ rows.

From the diagram to the truth table

Example 5.3.1(the encoded table of the long-press detector).

Take the long-press detector of Figure 5.2.1, where Out is 1 in the cycle that shows the third 1 of a run. We give the three states the codes 00, 01 and 10: S0 = 00, S1 = 01 and S2 = 10. Which patterns go to which states is a free choice; this one is simple and leaves 11 unused. The reset state is given the all-zero code here, a common habit and not a requirement.

The logic has three inputs, PS1, PS0 and In, and three outputs, NS1, NS0 and Out. Each arrow of the diagram becomes one row (an arrow that carries several input values becomes several rows): the code of the state it leaves and its input go on the left, the code of the state it enters and its output go on the right. The diagram has six arrows, and the table has $2^{3} = 8$ rows, so two rows are left. They are the two rows of the unused code 11, one for each value of In.

Encoded truth table of ch05/long-press: present-state bits PS1, PS0 and inputs In on the left, NS1, NS0, Out on the right; 8 rows in ascending binary order, PS1 most significant; X means don't care (unused state codes and impossible inputs)

State	$\mathrm{PS}_{1}$	$\mathrm{PS}_{0}$	$\mathrm{In}$	$\mathrm{NS}_{1}$	$\mathrm{NS}_{0}$	$\mathrm{Out}$
S0	0	0	0	0	0	0
S0	0	0	1	0	1	0
S1	0	1	0	0	0	0
S1	0	1	1	1	0	0
S2	1	0	0	0	0	0
S2	1	0	1	0	0	1
unused	1	1	0	X	X	X
unused	1	1	1	X	X	X

The rows of the unused code have X in every output column. The machine starts in S0 after a reset and only follows arrows, so it can never be in the code 11, and nobody is asking what the logic should do there. X is a don't care, as in Section 3.7: a freedom for the designer, to be used when it makes the logic smaller.

One K-map for every output

The logic has three outputs, so there are three functions to minimize, one K-map each. For a state machine the state bits go on the columns, in Gray order, and the input goes on the row.

Example 5.3.2(minimizing the three outputs).

Start with NS1, the high bit of the next state. It is 1 only when the machine goes to S2, whose code is 10, and that happens only from S1 on a 1. So the only 1 on the map is the cell where PS1, PS0 and In are 0, 1 and 1.

NS1 = $\mathrm{PS}_{0} \cdot \mathrm{In}$

• $\mathrm{PS}_{0} \cdot \mathrm{In}$horizontal pair: row 1, columns 01 and 11 (2 cells); 1 of the cells is a don't care

Karnaugh map of NS1: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	0	X	0
In=1	0	1	X	0

Groups drawn:

1. PS0 and In: horizontal pair in row In=1, columns PS1,PS0=01 and 11; 2 cells, 1 of them don't care.

Description: A Karnaugh map of NS1 with columns PS1 PS0 and rows In. One cell is 1, two cells are X and the rest are 0. One group is drawn.

Figure 5.3.2. NS1 with the don't cares of the unused code. The group takes the 1 together with a don't care.

The two X cells are the two rows of the code 11. Next to the 1 there is an X, so we make a group of two: the horizontal pair in row In=1, columns PS1,PS0=01 and 11. Inside it PS1 takes both values, so it drops out, while PS0 and In are 1 throughout. The equation is $\mathrm{NS}_1 =$ $\mathrm{PS}_{0} \cdot \mathrm{In}$.

Next NS0, the low bit of the next state. It is 1 only when the machine goes to S1, whose code is 01, and that happens only from S0 on a 1.

NS0 = $\overline{\mathrm{PS}_{1}} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$

• $\overline{\mathrm{PS}_{1}} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$single cell: row 1, column 00

Karnaugh map of NS0: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	0	X	0
In=1	1	0	X	0

Groups drawn:

1. not PS1 and not PS0 and In: single cell in row In=1, column PS1,PS0=00; 1 cell.

Description: A Karnaugh map of NS0 with columns PS1 PS0 and rows In. One cell is 1, two cells are X and the rest are 0. One single-cell group is drawn.

Figure 5.3.3. NS0. The only 1 has no neighbor that is a 1 or an X, so it stands alone.

This 1 has no neighbor that is a 1 or an X, wrap-around neighbors included. The X cells belong to the code 11, which differs from 00 in both state bits, so they are not its neighbors. The 1 cannot be grouped with anything, and its term uses all three variables: $\mathrm{NS}_0 =$ $\overline{\mathrm{PS}_{1}} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$.

Last, Out. It is 1 in S2 on a 1, which is the cell where PS1, PS0 and In are 1, 0 and 1. That cell has an X next to it, so again we use a group of two.

Out = $\mathrm{PS}_{1} \cdot \mathrm{In}$

• $\mathrm{PS}_{1} \cdot \mathrm{In}$horizontal pair: row 1, columns 11 and 10 (2 cells); 1 of the cells is a don't care

Karnaugh map of Out: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	0	X	0
In=1	0	0	X	1

Groups drawn:

1. PS1 and In: horizontal pair in row In=1, columns PS1,PS0=11 and 10; 2 cells, 1 of them don't care.

Description: A Karnaugh map of Out with columns PS1 PS0 and rows In. One cell is 1, two cells are X and the rest are 0. One group is drawn.

Figure 5.3.4. Out, with the group that uses the don't care.

The horizontal pair in row In=1, columns PS1,PS0=11 and 10 has PS1 and In fixed at 1 and PS0 changing, so $\mathrm{Out} =$ $\mathrm{PS}_{1} \cdot \mathrm{In}$. It says: in S2, and the input is 1.

Two of the three equations used a don't care. That was a choice, and the other choice is also correct. Leaving the X cells alone, NS1 and Out each shrink to a single-cell group:

NS1 = $\overline{\mathrm{PS}_{1}} \cdot \mathrm{PS}_{0} \cdot \mathrm{In}$

• $\overline{\mathrm{PS}_{1}} \cdot \mathrm{PS}_{0} \cdot \mathrm{In}$single cell: row 1, column 01

Karnaugh map of NS1: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	0	X	0
In=1	0	1	X	0

Groups drawn:

1. not PS1 and PS0 and In: single cell in row In=1, column PS1,PS0=01; 1 cell.

Description: The same Karnaugh map of NS1 with one single-cell group around the 1.

Figure 5.3.5. NS1 again, this time without using the don't care.

Out = $\mathrm{PS}_{1} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$

• $\mathrm{PS}_{1} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$single cell: row 1, column 10

Karnaugh map of Out: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	0	X	0
In=1	0	0	X	1

Groups drawn:

1. PS1 and not PS0 and In: single cell in row In=1, column PS1,PS0=10; 1 cell.

Description: The same Karnaugh map of Out with one single-cell group around the 1.

Figure 5.3.6. Out again, without using the don't care.

Those give $\mathrm{NS}_1 =$ $\overline{\mathrm{PS}_{1}} \cdot \mathrm{PS}_{0} \cdot \mathrm{In}$ and $\mathrm{Out} =$ $\mathrm{PS}_{1} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$, which are the same on the six rows that matter: $\mathrm{PS}_{0} \cdot \mathrm{In}$ $= \overline{\mathrm{PS}_{1}} \cdot \mathrm{PS}_{0} \cdot \mathrm{In}$ (for every input that is not a don't care) and $\mathrm{PS}_{1} \cdot \mathrm{In}$ $= \mathrm{PS}_{1} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$ (for every input that is not a don't care). Each is one literal longer. NS0 is the same either way, since its don't cares were never used.

The gates and flip-flops

Example 5.3.3(the long-press detector as a circuit).

The three equations of the larger groups are all products, so each becomes one AND gate. Two flip-flops hold the two state bits, PS1 and PS0, and each flip-flop's input is the matching next-state bit. A bubble on a gate input inverts that input.

A logic schematic with inputs In, clk and reset and output Out.

AND gate g1: inputs n1 and In; output n2.

AND gate g2: inputs inverted n3, inverted n1 and In; output n4.

AND gate g3: inputs n3 and In; output Out.

Flip-flop ff0: d is n4, q is n1, clocked by clk, synchronous reset reset.

Flip-flop ff1: d is n2, q is n3, clocked by clk, synchronous reset reset.

It is checked against the module hdl:ch05/long_press.

Description: A circuit with inputs In, clk and reset and output Out. Three AND gates. One takes PS0 and In and feeds the d input of the PS1 flip-flop. One takes PS1 and PS0, each through an inverting bubble, and In, and feeds the d input of the PS0 flip-flop. One takes PS1 and In and drives Out. The flip-flop outputs return to the gates, and clk and reset go to both flip-flops.

Figure 5.3.7. The long-press detector built from three AND gates and two flip-flops. The three-input gate has bubbles on the inputs for PS1 and PS0.

Each AND gate in Figure 5.3.7 is one of the equations: the gate for $\mathrm{NS}_1$ takes PS0 and In, the three-input gate for $\mathrm{NS}_0$ takes the complements of PS1 and PS0 and In, and the gate that drives Out takes PS1 and In. A reset clears both flip-flops, and the code 00 is the code of S0, so reset puts the machine in its initial state. The book's tools simulate this drawing next to the Section 5.2 module, with random inputs and resets, and compare the outputs around every clock edge. The two agree, which is the check that this circuit does the same job as the machine of Figure 5.2.1.

In SystemVerilog

Written as assign statements, the same logic is a combinational module with a port for each input and each output of the table.

long_press_cl.sv

// The combinational logic of the long-press detector, written as the three equations derived from its truth table.
module long_press_cl(input logic PS1, PS0, In, output logic NS1, NS0, Out);
  assign NS1 = PS0 & In;
  assign NS0 = ~PS1 & ~PS0 & In;
  assign Out = PS1 & In;
endmodule

The testbench visits every row of the truth table, including the two rows of the unused code. Each // expect: comment lists what the logic should give on that row. Because this is combinational logic with no clock, the comment reports what the inputs on its own line produce.

long_press_cl_tb.sv

// Testbench for long_press_cl: every row of the encoded truth table, including the two rows of the unused code 11.
module long_press_cl_tb();
  logic PS1, PS0, In, NS1, NS0, Out;

  long_press_cl dut(.*);

  initial begin
    {PS1, PS0, In} = 3'b000; #10;   // expect: NS1=0, NS0=0, Out=0
    {PS1, PS0, In} = 3'b001; #10;   // expect: NS1=0, NS0=1, Out=0
    {PS1, PS0, In} = 3'b010; #10;   // expect: NS1=0, NS0=0, Out=0
    {PS1, PS0, In} = 3'b011; #10;   // expect: NS1=1, NS0=0, Out=0
    {PS1, PS0, In} = 3'b100; #10;   // expect: NS1=0, NS0=0, Out=0
    {PS1, PS0, In} = 3'b101; #10;   // expect: NS1=0, NS0=0, Out=1
    // The unused code 11: no row of the table says what to do here, so the equations decide.
    {PS1, PS0, In} = 3'b110; #10;   // expect: NS1=0, NS0=0, Out=0
    $display("DD ns_unused_in0=%b%b", NS1, NS0);
    $display("DD out_unused_in0=%b", Out);
    {PS1, PS0, In} = 3'b111; #10;   // expect: NS1=1, NS0=0, Out=1
    $display("DD ns_unused_in1=%b%b", NS1, NS0);
    $display("DD out_unused_in1=%b", Out);
    $stop;
  end
endmodule

Time in ps; one column is 10 ps.

Timing diagram from simulation, ch05/long-press-cl-rows: time in ps from 0 to 80, 8 columns of 10 ps.

PS1: 0 at 0, then 1 at 40.

PS0: 0 at 0, then 1 at 20, 0 at 40, 1 at 60.

In: 0 at 0, then 1 at 10, 0 at 20, 1 at 30, 0 at 40, 1 at 50, 0 at 60, 1 at 70.

NS1: 0 at 0, then 1 at 30, 0 at 40, 1 at 70.

NS0: 0 at 0, then 1 at 10, 0 at 20.

Out: 0 at 0, then 1 at 50, 0 at 60, 1 at 70.

Description: A timing diagram of PS1, PS0, In, NS1, NS0 and Out over eight steps. The inputs count up in binary from 000 to 111. NS1 is high in steps 4 and 8. NS0 is high only in step 2. Out is high in steps 6 and 8.

Figure 5.3.8. The eight rows of the table in order, one row per step: the first six are the arrows of the diagram, the last two are the unused code.

In Figure 5.3.8 the inputs count up through the table, so each step is one row. Step 2 is the row where the machine is in S0 and sees a 1: NS0 is the only output that is high. Step 4 is S1 with a 1: NS1 is high. Step 6 is S2 with a 1: Out is high, and both next-state bits are 0, which is S0 again.

What the circuit does in an unused code

Steps 7 and 8 of the figure are the rows we said nobody asks about. The circuit still computes something there, and the equations decide what, not the table.

The register somehow holds the unused code 11, and In is 0. Which code does the register hold after the next clock edge?

00111001

Example 5.3.4(reading the groups on the unused cells).

Which X cells became 1 and which became 0 depends only on the groups we drew. The group for NS1 covers the cell of the code 11 with In = 1, so NS1 is 1 there, and it does not cover the cell with In = 0, so NS1 is 0 there. No group of NS0 covers either cell, so NS0 is 0 in both. The group for Out covers the cell of 11 with In = 1, so Out is 1 there and 0 for In = 0.

That gives two cases, and the testbench's two last rows confirm them. With In = 0 the next code is 00 and Out is 0. With In = 1 the next code is 10 and Out is 1.

So this circuit does not get stuck in the unused code: one clock edge later it is back in S0 or S2. But with In = 1 it shows an Out pulse that the diagram never allows. Nothing in the diagram forbids this, because the diagram says nothing about the code 11.

Does it matter? After a reset the register holds 00, and the equations only ever lead from the legal codes to legal codes, so the machine cannot reach 11 by following arrows. It could start there only if something else puts it there, such as a fault in a flip-flop. A design where such a fault must never cause a wrong output has to say what the unused codes do, and in the equations it does that by turning the X cells into ordinary rows. If both rows of 11 are sent to S0 with Out equal to 0, every X in the three maps becomes a 0, and the equations become the longer forms of Figure 5.3.5 and Figure 5.3.6. The default arm in the SystemVerilog module of Section 5.2 writes the same decision in code. In that module, as written and as the book simulates it, the machine goes to S0 from the unused code for both values of In, with Out equal to 0, while the equations above go to S2, with Out = 1, when In is 1. A synthesis tool is free to choose its own encoding for the states and may remove the logic for codes it takes to be unreachable, so a default in the source is not by itself a promise about the finished circuit.^{? (not machine-checked: A property of synthesis tools that nobody here has run or confirmed, including the course's tool; the book's checks cover only the simulated module.)} The two forms agree on every state the machine can reach from reset.

The other path is to leave the X cells free and check where the chosen groups send the machine, as above. It can save gates, as it did for NS1 and Out, and it is safe when the only way into an unused code is a fault you can live with.

Course conventions

How CSE 369 writes this

In CSE 369 we write the register's output as PS and its input as NS, with the state bits subscripted, as in $\mathrm{PS}_1$ and $\mathrm{NS}_0$. The truth table lists PS and then the inputs to the left of the rule, and NS and then the outputs to the right of it. Its K-maps put the state bits on the columns in Gray order and the input on the row, the course's layout for three variables. With one state bit and one input the map is the ordinary two-variable map, with PS on the rows. When a product has more than one letter in a name, the equations separate the factors with a dot.

Pitfalls

Common pitfall

• Giving two states the same code. The logic then cannot tell them apart, and the machine merges them.
• Using one K-map for everything. Each next-state bit and each output is a separate function and needs its own map.
• Reading X as "this cannot happen, so it does not matter what the circuit does". The circuit still computes something there, and the groups you drew decide what.
• Writing the logic in terms of NS. The logic reads PS, the register's output, and the input; NS is what it produces.
• Mixing up the order of the bits of a code. Write PS1 before PS0 in the table and in the map's column labels, and read the code 10 as PS1 = 1 and PS0 = 0.
• Calling a machine with three states a one-bit or a three-bit machine. Two bits hold four patterns, which is the smallest register that holds three states.

Check your understanding

Take the quiz (6 questions)

How many state bits does the long-press detector need?

231

How many rows does the encoded truth table of the long-press detector have?

864

How many state codes does the long-press encoding leave unused?

102

Which expression is the next-state bit NS0 of the long-press detector?

$\overline{\mathrm{PS}_{1}} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$$\mathrm{PS}_{1} \cdot \mathrm{PS}_{0} \cdot \mathrm{In}$$\overline{\mathrm{PS}_{1}} \cdot \mathrm{PS}_{0} \cdot \mathrm{In}$

With the equations of this section, the register holds the unused code 11 and In is 1. Which code does it hold after the next clock edge?

100011

A designer replaces the X rows of the table by ordinary rows: from the unused code the machine goes to S0 with output 0, whatever the input. What happens to the equations? Every X in the maps becomes a 0, so the groups that used X cells shrink and their terms get longer. Nothing changes, because the unused code is never reached. The equations get shorter, because there are fewer don't cares to deal with.

Exercises

Exercise 5.3.1

A machine has 6 states and 3 inputs. How many state bits does it need, how many arrows can leave one state at most, and how many rows does its encoded truth table have?

Hint

The first number is the smallest $s$ with $2^s \ge 6$. The rows are one for every combination of the state bits and the inputs.

Solution

Two bits hold only 4 patterns and three bits hold 8, so the machine needs 3 state bits, and 2 patterns are unused. With 3 inputs there are $2^3 = 8$ input values, and each value that can occur is carried by exactly one arrow leaving a state, so at most 8 arrows leave a state. The logic has $3 + 3 = 6$ inputs, so the table has $2^6 = 64$ rows. Of them, $6 \times 8 = 48$ rows belong to the six states, and the other 16 belong to the two unused codes.

Tags: Warm-upFinite state machines

Exercise 5.3.2

This machine counts the 1s on its input, modulo 3. A 0 changes nothing: it does not start the count over. Out is 1 in the cycle that shows the third 1, the sixth 1 and so on. The states Zero, One and Two have the codes 00, 01 and 10.

Description: State diagram with three circles Zero, One and Two. Each has a self-loop labeled 0/0. Zero has an arrow to One labeled 1/0, One has an arrow to Two labeled 1/0, and Two has an arrow back to Zero labeled 1/1.

Figure 5.3.9. A tally machine: it counts 1s modulo 3.

Write the encoded truth table, with columns PS1, PS0 and In on the left and NS1, NS0 and Out on the right.

Hint

The table has one row for every combination of PS1, PS0 and In, in ascending binary order. Fill the six rows that come from arrows first, then mark what is left.

Solution

The six arrows give six rows, and the code 11 gives the other two, with X in all outputs.

Encoded truth table of ch05/s03-tally3: present-state bits PS1, PS0 and inputs In on the left, NS1, NS0, Out on the right; 8 rows in ascending binary order, PS1 most significant; X means don't care (unused state codes and impossible inputs)

State	$\mathrm{PS}_{1}$	$\mathrm{PS}_{0}$	$\mathrm{In}$	$\mathrm{NS}_{1}$	$\mathrm{NS}_{0}$	$\mathrm{Out}$
Zero	0	0	0	0	0	0
Zero	0	0	1	0	1	0
One	0	1	0	0	1	0
One	0	1	1	1	0	0
Two	1	0	0	1	0	0
Two	1	0	1	0	0	1
unused	1	1	0	X	X	X
unused	1	1	1	X	X	X

Tags: Warm-upFinite state machinesTruth tables

Exercise 5.3.3

For the tally machine of Figure 5.3.9, draw a K-map for each of NS1, NS0 and Out, with PS1 and PS0 on the columns and In on the row. Group the 1s, using the don't cares where they help, and write the minimal equations.

Hint

Each map has at most two 1s; start by marking them from the table. On every map, at least one 1 can grow into the unused code.

Solution

NS1 is 1 in two cases: the machine is in Two and the input is 0, and it is in One and the input is 1. The first is the cell where PS1, PS0 and In are 1, 0 and 0, the second the cell where they are 0, 1 and 1. Each of them has a don't care next to it in the code 11, so each becomes a group of two.

NS1 = $\mathrm{PS}_{1} \cdot \overline{\mathrm{In}} + \mathrm{PS}_{0} \cdot \mathrm{In}$

• $\mathrm{PS}_{1} \cdot \overline{\mathrm{In}}$horizontal pair: row 0, columns 11 and 10 (2 cells); 1 of the cells is a don't care
• $\mathrm{PS}_{0} \cdot \mathrm{In}$horizontal pair: row 1, columns 01 and 11 (2 cells); 1 of the cells is a don't care

Karnaugh map of NS1: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	0	X	1
In=1	0	1	X	0

Groups drawn:

1. PS1 and not In: horizontal pair in row In=0, columns PS1,PS0=11 and 10; 2 cells, 1 of them don't care.
2. PS0 and In: horizontal pair in row In=1, columns PS1,PS0=01 and 11; 2 cells, 1 of them don't care.

Description: A Karnaugh map of NS1 with columns PS1 PS0 and rows In. Two cells are 1, two are X and the rest are 0. Two groups of two cells are drawn.

Figure 5.3.10. NS1 of the tally machine.

The horizontal pair in row In=0, columns PS1,PS0=11 and 10 has PS1 fixed at 1 and In fixed at 0, so its term is $\mathrm{PS}_{1} \cdot \overline{\mathrm{In}}$. The horizontal pair in row In=1, columns PS1,PS0=01 and 11 has PS0 and In fixed at 1: $\mathrm{PS}_{0} \cdot \mathrm{In}$.

NS0 is 1 when the machine stays in One on a 0 and when it goes from Zero to One on a 1.

NS0 = $\mathrm{PS}_{0} \cdot \overline{\mathrm{In}} + \overline{\mathrm{PS}_{1}} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$

• $\mathrm{PS}_{0} \cdot \overline{\mathrm{In}}$horizontal pair: row 0, columns 01 and 11 (2 cells); 1 of the cells is a don't care
• $\overline{\mathrm{PS}_{1}} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$single cell: row 1, column 00

Karnaugh map of NS0: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	1	X	0
In=1	1	0	X	0

Groups drawn:

1. PS0 and not In: horizontal pair in row In=0, columns PS1,PS0=01 and 11; 2 cells, 1 of them don't care.
2. not PS1 and not PS0 and In: single cell in row In=1, column PS1,PS0=00; 1 cell.

Description: A Karnaugh map of NS0 with columns PS1 PS0 and rows In. Two cells are 1, two are X and the rest are 0. One group of two cells and one single-cell group are drawn.

Figure 5.3.11. NS0 of the tally machine.

The cell where PS1, PS0 and In are 0, 1 and 0 has a don't care next to it in the code 11, and it forms the pair with term $\mathrm{PS}_{0} \cdot \overline{\mathrm{In}}$. The cell for Zero on a 1 has no neighbor that is 1 or X, so it is a group of one with the term $\overline{\mathrm{PS}_{1}} \cdot \overline{\mathrm{PS}_{0}} \cdot \mathrm{In}$.

Out is 1 only in Two on a 1.

Out = $\mathrm{PS}_{1} \cdot \mathrm{In}$

• $\mathrm{PS}_{1} \cdot \mathrm{In}$horizontal pair: row 1, columns 11 and 10 (2 cells); 1 of the cells is a don't care

Karnaugh map of Out: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	0	X	0
In=1	0	0	X	1

Groups drawn:

1. PS1 and In: horizontal pair in row In=1, columns PS1,PS0=11 and 10; 2 cells, 1 of them don't care.

Description: A Karnaugh map of Out with columns PS1 PS0 and rows In. One cell is 1, two are X and the rest are 0. One group of two cells is drawn.

Figure 5.3.12. Out of the tally machine.

That gives $\mathrm{Out} =$ $\mathrm{PS}_{1} \cdot \mathrm{In}$.

Tags: StandardFinite state machinesKarnaugh maps

Exercise 5.3.4

Do the tally machine again with another set of codes: Zero = 00, One = 01 and Two = 11, so that the steps from Zero to One and from One to Two each change only one bit. The step from Two back to Zero changes both bits, and with three states in a ring no choice of two-bit codes avoids that. Which code is unused now? Write the minimal equation for each output, and compare them with those of Exercise 5.3.3.

Hint

Only the table's code columns change. Rebuild the three maps from the new table; the unused code is now in a different column of the maps.

Solution

The code 10 is unused now. The three maps are drawn from the machine with the new codes.

Encoded truth table of ch05/s03-tally3-gray: present-state bits PS1, PS0 and inputs In on the left, NS1, NS0, Out on the right; 8 rows in ascending binary order, PS1 most significant; X means don't care (unused state codes and impossible inputs)

State	$\mathrm{PS}_{1}$	$\mathrm{PS}_{0}$	$\mathrm{In}$	$\mathrm{NS}_{1}$	$\mathrm{NS}_{0}$	$\mathrm{Out}$
Zero	0	0	0	0	0	0
Zero	0	0	1	0	1	0
One	0	1	0	0	1	0
One	0	1	1	1	1	0
unused	1	0	0	X	X	X
unused	1	0	1	X	X	X
Two	1	1	0	1	1	0
Two	1	1	1	0	0	1

NS1 = $\mathrm{PS}_{1} \cdot \overline{\mathrm{In}} + \overline{\mathrm{PS}_{1}} \cdot \mathrm{PS}_{0} \cdot \mathrm{In}$

• $\mathrm{PS}_{1} \cdot \overline{\mathrm{In}}$horizontal pair: row 0, columns 11 and 10 (2 cells); 1 of the cells is a don't care
• $\overline{\mathrm{PS}_{1}} \cdot \mathrm{PS}_{0} \cdot \mathrm{In}$single cell: row 1, column 01

Karnaugh map of NS1: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	0	1	X
In=1	0	1	0	X

Groups drawn:

1. PS1 and not In: horizontal pair in row In=0, columns PS1,PS0=11 and 10; 2 cells, 1 of them don't care.
2. not PS1 and PS0 and In: single cell in row In=1, column PS1,PS0=01; 1 cell.

Description: A Karnaugh map of NS1 with columns PS1 PS0 and rows In. Two cells are 1, two are X and the rest are 0. One group of two cells and one single-cell group are drawn.

Figure 5.3.13. NS1 with the codes 00, 01 and 11.

NS0 = $\mathrm{PS}_{0} \cdot \overline{\mathrm{In}} + \overline{\mathrm{PS}_{1}} \cdot \mathrm{In}$

• $\mathrm{PS}_{0} \cdot \overline{\mathrm{In}}$horizontal pair: row 0, columns 01 and 11 (2 cells)
• $\overline{\mathrm{PS}_{1}} \cdot \mathrm{In}$horizontal pair: row 1, columns 00 and 01 (2 cells)

Karnaugh map of NS0: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	1	1	X
In=1	1	1	0	X

Groups drawn:

1. PS0 and not In: horizontal pair in row In=0, columns PS1,PS0=01 and 11; 2 cells.
2. not PS1 and In: horizontal pair in row In=1, columns PS1,PS0=00 and 01; 2 cells.

Description: A Karnaugh map of NS0 with columns PS1 PS0 and rows In. Four cells are 1, two are X and the rest are 0. Two groups of two cells are drawn.

Figure 5.3.14. NS0 with the codes 00, 01 and 11.

Out = $\mathrm{PS}_{1} \cdot \mathrm{In}$

• $\mathrm{PS}_{1} \cdot \mathrm{In}$horizontal pair: row 1, columns 11 and 10 (2 cells); 1 of the cells is a don't care

Karnaugh map of Out: columns PS1,PS0, rows In; cell values are 0, 1 or X for don't care

	PS1PS0=00	PS1PS0=01	PS1PS0=11	PS1PS0=10
In=0	0	0	0	X
In=1	0	0	1	X

Groups drawn:

1. PS1 and In: horizontal pair in row In=1, columns PS1,PS0=11 and 10; 2 cells, 1 of them don't care.

Description: A Karnaugh map of Out with columns PS1 PS0 and rows In. One cell is 1, two are X and the rest are 0. One group of two cells is drawn.

Figure 5.3.15. Out with the codes 00, 01 and 11.

The equations are $\mathrm{NS}_1 =$ $\mathrm{PS}_{1} \cdot \overline{\mathrm{In}} +$ $\overline{\mathrm{PS}_{1}} \cdot \mathrm{PS}_{0} \cdot \mathrm{In}$, $\mathrm{NS}_0 =$ $\mathrm{PS}_{0} \cdot \overline{\mathrm{In}} +$ $\overline{\mathrm{PS}_{1}} \cdot \mathrm{In}$ and $\mathrm{Out} =$ $\mathrm{PS}_{1} \cdot \mathrm{In}$. Only Out is the same as before. NS1 is longer now and NS0 is shorter, so the choice of codes changes the logic, and a different choice of codes is a different circuit for the same diagram. Nothing says in advance which choice is the cheapest; the way to find out is to work both out.

Tags: StandardFinite state machinesKarnaugh maps

Exercise 5.3.5

Design a machine with one input In and one output Out. Out is 1 in a cycle when the number of 1s seen so far, counting the current input, is odd. Draw the state diagram, choose codes, write the truth table, and find the equations with K-maps.

Hint

What is the smallest thing worth remembering about the 1s so far? Two states are enough. With two states, how many state bits do you need, and how many unused codes are there?

Solution

All that matters about the past is whether the number of 1s already sampled at earlier clock edges is even or odd, so there are two states, Even and Odd. A 1 changes the parity and a 0 does not. The state counts only the earlier inputs, so the output, which counts the current input as well, is 1 whenever the parity after the current input is odd: in Even with In = 1, and in Odd with In = 0.

Description: State diagram with two circles Even and Odd. Even has a self-loop labeled 0/0 and an arrow to Odd labeled 1/1. Odd has a self-loop labeled 0/1 and an arrow back to Even labeled 1/0.

Figure 5.3.16. A parity machine: Odd records an odd number of previously sampled 1s. The arrow's output includes the current input.

Two states need one state bit, with Even = 0 and Odd = 1, and no code is unused. The logic has two inputs, PS and In, so the table has four rows.

Encoded truth table of ch05/s03-parity: present-state bits PS and inputs In on the left, NS, Out on the right; 4 rows in ascending binary order, PS most significant

State	$\mathrm{PS}$	$\mathrm{In}$	$\mathrm{NS}$	$\mathrm{Out}$
Even	0	0	0	0
Even	0	1	1	1
Odd	1	0	1	1
Odd	1	1	0	0

The two maps are the same, because NS and Out are the same function of PS and In. On each map the 1s are the two cells where PS and In differ. No two of them are neighbors, so each is a group of one.

NS = $\mathrm{PS} \cdot \overline{\mathrm{In}} + \overline{\mathrm{PS}} \cdot \mathrm{In}$

• $\mathrm{PS} \cdot \overline{\mathrm{In}}$single cell: row 1, column 0
• $\overline{\mathrm{PS}} \cdot \mathrm{In}$single cell: row 0, column 1

Karnaugh map of NS: columns In, rows PS; cell values are 0, 1 or X for don't care

	In=0	In=1
PS=0	0	1
PS=1	1	0

Groups drawn:

1. PS and not In: single cell in row PS=1, column In=0; 1 cell.
2. not PS and In: single cell in row PS=0, column In=1; 1 cell.

Description: A Karnaugh map of NS with columns In and rows PS. Two cells are 1 and two are 0. Two single-cell groups are drawn.

Figure 5.3.17. NS of the parity machine. Out has the same map.

So $\mathrm{NS} =$ $\mathrm{PS} \cdot \overline{\mathrm{In}} +$ $\overline{\mathrm{PS}} \cdot \mathrm{In}$ and the same for Out. This is the exclusive OR of PS and In, as the check $\mathrm{PS} \cdot \overline{\mathrm{In}} +$ $\overline{\mathrm{PS}} \cdot \mathrm{In}$ $= \mathrm{PS} \oplus \mathrm{In}$ shows, and one XOR gate can replace both AND gates and the OR gate.

Tags: StandardFinite state machinesKarnaugh maps

Exercise 5.3.6

Take the equations you found for the tally machine in Exercise 5.3.3. Suppose the register holds the unused code 11. For each value of In, find the next code and Out. Can this circuit stay in the unused code?

Hint

Substitute PS1 = 1 and PS0 = 1 into the three equations, once for In = 0 and once for In = 1.

Solution

With PS1 = PS0 = 1 the term PS1 and not In is 1 exactly when In is 0, and PS0 and In is 1 exactly when In is 1. So NS1 is 1 for both values of In. In NS0, the term PS0 and not In is 1 when In is 0, and the second term, which needs PS0 to be 0, is never 1. So NS0 equals not In. Out equals In. Here is the logic as a module, and a testbench that checks the six rows of the table and then the two rows of the unused code.

tally3_cl.sv

// Exercise solution: the combinational logic of the tally machine, from the equations the exercise derives.
module tally3_cl(input logic PS1, PS0, In, output logic NS1, NS0, Out);
  assign NS1 = (PS1 & ~In) | (PS0 & In);
  assign NS0 = (PS0 & ~In) | (~PS1 & ~PS0 & In);
  assign Out = PS1 & In;
endmodule

tally3_cl_tb.sv

// Testbench for tally3_cl: the six rows of the table, then the two rows of the unused code 11.
module tally3_cl_tb();
  logic PS1, PS0, In, NS1, NS0, Out;

  tally3_cl dut(.*);

  initial begin
    {PS1, PS0, In} = 3'b000; #10;   // expect: NS1=0, NS0=0, Out=0
    {PS1, PS0, In} = 3'b001; #10;   // expect: NS1=0, NS0=1, Out=0
    {PS1, PS0, In} = 3'b010; #10;   // expect: NS1=0, NS0=1, Out=0
    {PS1, PS0, In} = 3'b011; #10;   // expect: NS1=1, NS0=0, Out=0
    {PS1, PS0, In} = 3'b100; #10;   // expect: NS1=1, NS0=0, Out=0
    {PS1, PS0, In} = 3'b101; #10;   // expect: NS1=0, NS0=0, Out=1
    {PS1, PS0, In} = 3'b110; #10;   // expect: NS1=1, NS0=1, Out=0
    $display("DD ns_unused_in0=%b%b", NS1, NS0);
    {PS1, PS0, In} = 3'b111; #10;   // expect: NS1=1, NS0=0, Out=1
    $display("DD ns_unused_in1=%b%b", NS1, NS0);
    $display("DD out_unused_in1=%b", Out);
    $stop;
  end
endmodule

With In = 0 the next code is 11, which is the unused code itself, and Out is 0. With In = 1 the next code is 10, which is Two, and Out is 1.

So this circuit can stay in the unused code for as long as In stays 0, and leaves it on the first 1 with a pulse on Out that no third 1 caused. The long-press circuit in the text always left the unused code after one edge. Both were designed with the same freedom, and only reading the groups tells them apart.

Tags: ChallengeFinite state machinesKarnaugh maps