Finite State Machine

Next, we will consider a finite state machine.

Recall the ‘Truth Table Generator’ circuit from the beginning of the ‘Memory’ chapter of ‘How Computers Work’, which is reproduced below.

Truth Table Generator

truth table generator

The truth table for the circuit above is shown below.

A	B	G	H
0	0	1	0
0	1	0	1
1	0	0	0
1	1	1	1

Now consider the ‘Increment Circuit’ below. It is the almost the same as the circuit above, but has a different truth table.

Increment Circuit

increment circuit

The truth table for the ‘Increment Circuit’ is shown below.

Increment Truth Table

A	B	G	H
0	0	0	1
0	1	1	0
1	0	1	1
1	1	0	0

The following table indicates how we can represent the numbers 0 through 3 with values of A1 and A0.

Number Representations Table

A1	A0	Number
0	0	0
0	1	1
1	0	2
1	1	3

Substituting the numbers from the ‘Number Representation Table’ for the 1 and 0 patterns in the ‘Increment Truth Table’ above, gives the following table in place of the Increment Truth Table. This table shows that if you enter the number 0, 1, or 2 (as the patterns 00, 01, or 10) then the output is 1 greater than the input. If the input is 3 (pattern 11), then the output is 0. ‘Increment’ means ‘add 1’ and that’s what this circuit does (except that it makes 3 into 0 instead of 4). Thus, this circuit is called an increment circuit or an incrementer.

Increment Number Truth Table

AB	GH
0	1
1	2
2	3
3	0

Finite State Machine

Counter Circuit

Next, we will consider a counter circuit. This counter circuit is an example of a finite state machine.

In the circuit below, one can store a 1 in ‘LOOP A’ by simply pressing the key of loop A down. One can clear loop A back to value 0 by lifting up the key of loop A or by pressing the normally closed clear key, C1.

One can copy the value in ‘LATCH 1’ (loop A and loop B) to ‘LATCH 4’ (loop C and loop D) by temporarily pressing clear key C4 to clear latch 4 and then pressing key E4 to connect loop A to loop C and connect loop B to loop D.

two latches connected

In the circuit below, one can make the data flow in a circle as indicated by the oval with arrows. Initially, the data goes in latch 1. Then one temporarily presses C4 to clear latch 4. Next, E4 is temporarily pressed to copy the data in latch 1 to latch 4. Now the data is (also) in latch 4. Next, C1 is temporarily pressed to clear latch 1. Then E1 (not E4) is temporarily pressed to copy data from latch 4 to latch 1 through the top wires. Now, one can repeat the process to make the data go around again.

latches connected in circle

Below is a counter circuit. This counter circuit is an example of a finite state machine. It consists of an increment circuit (The increment circuit was shown a few pages back.) in the middle with latch 1 on the left and latch 4 on the right.

Initially, the number 0 is put in latch 1. The number 0 is represented by D1 = 0 and D0 = 0. The number 0 passes through the increment circuit and becomes number 1 at the output of the increment circuit. Number 1 is represented as D1 = 0 and D0 = 1. Next, C4 is temporarily pressed to clear latch 4. Then E4 is pressed to let the number 1 go into latch 4. Finally, C1 is temporarily pressed and then E1 is temporarily pressed to copy the number 1 (D1 = 0 and D0 = 1) from latch 4, through the top wires, to latch 1. All of this has incremented (increased by 1) the value in latch 1 from number 0 to number 1.

If one now repeats this process by temporarily pressing C4 then E4 then C1 then E1, the value in latch 1 will be incremented from number 1 (D1 = 0, D0 = 1) to number 2 (D1 = 1, D0 = 0). If we repeat the process again, then the number in latch 1 will be incremented from number 2 to number 3 (D1 = 1, D0 = 1). Thus the circuit is counting. It started with number 0 in latch 1, then made it number 1, then number 2, then number 3. If one temporarily presses C4, then E4, then C1, then E1, the number 3 will be ‘incremented’ to number 0 (D1 = 0, D0 = 0) and the counting will begin again. This circuit can only count to 3.

Detailed Finite State Machine

detailed finite state machine

The circuit above is an example of a ‘finite state machine.’ A finite state machine is a latch (like latch 1) followed by a circuit that does some function (like the increment circuit that does an increment) followed by another latch (like latch 4) that sends its value back to the first latch (as through the top wires in the circuit above).

The finite state machine is the circuit that one should usually use when one wants to update a state over and over again. The state of the finite state machine is the value in the latch.

Finite State Machine

finite state machine

The two diagrams above mean the same thing. The second diagram above just uses a more compact notation. In the more compact diagram, a block of logic is represented as a rectangle, a latch as an 'L' shape, a buffer as an arrow (>) (that points in the direction the data goes), and a bus as a line. The bus is represented as a line and represents two wires.

In a finite state machine, there is a clock that controls the buffers and latches, but it is not shown.

We can break up the logic in the "Detailed Finite State Machine" above into two parts as below.

logic in two pats

A delailed diagram of this circuit with extra buffers and latches in the middle is shown below.

Pipelined Detailed Finite State Machine Counter

pipelined finite state machine

A less detailed diagram of the circuit above is shown below.

Pipelined Finite State Machine

pipelined finite state machine

In the circuit above, two states can be processed at once. There can be one state (a number from 0 to 3) in latch 1. The clock is then allowed to move the state to latch 2 and latch 3. Then another state (a number from 0 to 3) can be put in latch 1. Then, while the state in latch 3 is advaced to latch 4, the state in latch 1 can be advanced to latch 2. In this way, two numbers are being counted at the same time. Each number will be incremented each time around the circuit.

A more complex logical operation, like execute a step of an instruction can be broken up into more piece. Below, the complex logical operation is broken up into 7 pieces with 8 latches. In this circuit, more states (sets of register values / simulated microprocessors) can be processed at once.

Eight Stage Pipelined Finite State Machine

Eight State Pipelined Finite State Machine


Page 41

Page 40 . . . Page 1 . . . Page 42