07.Sequential circuits

Chapter 7 − Sequential Circuits

Page 11 of 36

C = 0	Q 1 Q 0	= 00 C = 1		Q 1 Q 0 = 01	C = 0	Clk
Y = 0
			Y = 0		Y = 0	C
	C = 1			C = 1		Q1
	Y = 1			Y = 0		Q0
			C = 1
C = 0	Q 1 Q 0	= 11		Q 1 Q 0 = 10	C = 0	Y
			Y = 0
Y = 0					Y = 0	t0 t1 t2	t3	t4 t5	t6 t7
			(c)					(d)

Figure 9. Analysis of a Mealy FSM: (a) output equation; (b) output table; (c) state diagram; (d) timing diagram.

7.3Synthesis of Sequential Circuits

The synthesis of sequential circuits is just the reverse of the analysis of sequential circuits. In synthesis, we start with what is usually an ambiguous functional description of the circuit that we want. From this description, we need to come up with the precise operation of the circuit using a state diagram. The state diagram allows us to construct the next-state and output tables. The circuit can then be derived from the next-state and output tables.

During the synthesis process, there are many possible circuit optimizations in terms of the circuit size, speed, and power consumption that can be performed. Circuit optimization is discussed in Section 7.7. In this section, we will focus only on synthesizing a functionally correct sequential circuit.

The steps for the synthesis of sequential circuits are as follows:

1.Produce a state diagram from the functional description of the circuit.

2.Derive the next-state table from the state diagram.

3.Derive the output table from the state diagram.

4.Convert the next-state table to the implementation table.

5.Derive the excitation equations for each flip-flop input from the implementation table.

6.Derive the output equations from the output table.

7.Draw the circuit diagram based on the excitation and output equations.

7.3.1 State Diagram, Next-state and Output Tables

Producing the state diagram requires a full understanding of the functional behavior of the circuit that we want to build. Sometimes the description available for the circuit is vague so the functional behavior of the circuit must be clarified before the precise state diagram can be drawn. In this section, unless the description is simple and straight forward, we will skip this step of producing a state diagram from the functional description; instead we will just start with a given state diagram. We will address this issue of deriving the state diagram in more detail in Chapter 10 where we actually need to build a circuit that controls the operation of the microprocessor.

Given a precise state diagram, it is straightforward to derive both the next-state and output tables from it. Since the next-state and output tables and the state diagram portrait the same information but depicted in a different format, therefore it only requires a simple translation from one to the other.

7.3.2 Implementation Table

The implementation table is derived from the next-state table. Whereas, the next-state table is independent of the flip-flop type used, the implementation table is dependent on the choice of flip-flop used. A FSM can be implemented using any one of the four different types of flip-flops (as discussed in Section 6.11) or combinations of them. Using different flip-flops or combinations of flip-flops can produce different size circuits but with the same functionality. We will however, use only D flip-flops because of their ease of use and because this is the current

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM

Chapter 7 − Sequential Circuits

Page 12 of 36

trend in microprocessor design. Section 7.7.3 discusses how sequential circuits are produced with other types of flipflops.

The implementation table shows what the flip-flop inputs ought to be in order to realize the next-state table. In other words, it shows the necessary inputs for the (D) flip-flops that will produce the next states as given in the nextstate table. Hence, to derive the implementation table, we need to determine the value that must be assigned to the input D such that it will cause the corresponding Qnext value as given in the next-state table. However, since the characteristic equation for the D flip-flop (i.e. the equation that describes the operation of the D flip-flop) is

Qnext = D

therefore, the values for Qnext and D are the same.

Thus, the entries in the implementation table using D flip-flops are identical to the entries in the next-state table. The only difference between the two tables is the labeling of the entries. In the next-state table (see Figure 10 (b)),

the label for the entries is Qnext for the next state to go to, whereas, in the implementation table (see Figure 10 (c)), the label for the entries is D for the input to the flip-flop. Be careful that if one of the other types of flip-flops is used

instead of the D flip-flop, the two tables will not be the same as discuss in Section 7.7.3.

7.3.3 Examples: Synthesis of Moore FSMs

We will now illustrate the synthesis of Moore FSMs with several examples. Example 7.3 illustrates the synthesis of a simple Moore FSM. Example 7.4 illustrates the synthesis of a Moore FSM that is more typical of what the control unit of a microprocessor is like. Example 7.5 illustrates the synthesis of a Mealy FSM.

Example 7.3

For our first synthesis example, we will design a modulo-6 up counter using D flip-flops having a count enable input C, and an output signal Y that is asserted when the count is equal to five. The count is to be represented directly by the contents of the flip-flops.

Step 1 is to construct the state diagram. From the above functional description, we need to construct a state diagram that will show the precise operation of the circuit. A modulo-6 counter counts from zero to five, and then back to zero. Since the count is represented by the flip-flop values and we have six different counts (from zero to five), we will need three flip-flops (Q2, Q1, Q0) that will produce the sequence 000, 001, 010, 011, 100, 101, 000, … when C is asserted, otherwise, when C is de-asserted, the counting stops. In other words, from state 000, which is count = 0, there will be an edge that goes to state 001 with the label C = 1. From state 001, there is an edge that goes to state 010 with the label C = 1, and so on. For the counting to stop at each count, there will be edges at each state that loop back to the same state with the label C = 0. Furthermore, we want to assert Y in state 101, so in this state, we set Y to a 1. For the rest of the states, Y is set to a 0. Hence, we obtain the state diagram in Figure 10 (a) for a modulo-6 up counter.

Step 2 is to derive the next-state table, which is a direct translation from the state diagram. We have three flipflops Q2, Q1, and Q 0, and one primary input C. For each entry in the next-state table, we need to determine what the

next state is for each of the three flip-flops, so there are three bit values Q2next, Q1next, and Q0next for each entry. For example, if the current state is Q2Q1Q0 = 010 and the input is C = 1, then the next state Q2nextQ1nextQ0next is 011. The next-state table is shown in Figure 10 (b).

Step 3 is to convert the next-state table to its implementation table. Since for the D flip-flop, the implementation table is the same as the next-state table, we can simply use the next-state table and just re-label the entry heading as shown in Figure 10 (c).

Step 4 is to derive the excitation equations for all the flip-flop inputs in terms of the current state and the primary input. These equations are obtained directly from the implementation table. In the example, there are three flip-flops with the three inputs D2, D1, and D0, which correspond to the three bits in the entries in the implementation table. To derive the equation for D2, we consider just the leftmost bit in each entry for the truth table for D2. Looking at all the leftmost bits, there are four 1-minterms giving the canonical equation

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM

Chapter 7 − Sequential Circuits

Page 13 of 36

D2 = C'Q2Q1'Q0' + C'Q2Q1'Q0 + CQ2'Q1Q0 + CQ2Q1'Q0'

Similarly, the equation for D1 is derived from considering just the middle bit for all the entries, and the equation for D0 from the rightmost bit. Since these equations will be used to construct the circuit, they should be simplified. The three K-maps and simplified excitation equations for D2, D1, and D0 are shown in Figure 10 (d).

Steps 5 and 6 are to derive the output table and equation. There is one equation for every output signal. Since the value of Y is labeled inside each node, it is therefore dependent only on the current state. From the state diagram, Y is asserted only in state 101, so Y has a 1 only in that current state entry, while the rest of them are 0’s. The output table and equation are shown in Figure 10 (e).

Finally, we can draw the circuit for the FSM. We know that the circuit is a Moore FSM that uses three D flipflops for its state memory having one primary input C and one output Y. The next-state function circuit is derived from the excitation equations and the output function circuit is derived from the output equation. The full circuit is

shown in Figure 10 (f).				♦
C= 0	Q2Q1Q0 = 000	C= 1	Q2Q1Q0 = 001	C= 0
	Y = 0		Y = 0
C= 1				C= 1
Q2Q1Q0 = 101	C= 0		C= 0	Q2Q1Q0 = 010
Y = 1				Y = 0
C= 1				C= 1
C= 0	Q2Q1Q0 = 100	C= 1	Q2Q1Q0 = 011	C= 0
	Y = 0		Y = 0
		(a)

	Current State	Next State
		Q2next	Q1next Q0next
	Q2Q1Q0
		C = 0		C = 1
	000	000		001
	001	001		010
	010	010		011
	011	011		100
	100	100		101
	101	101		000

(b)

	Current State	Implementation
		D2	D1 D0
	Q2Q1Q0
		C = 0		C = 1
	000	000		001
	001	001		010
	010	010		011
	011	011		100
	100	100		101
	101	101		000

(c)

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM

Chapter 7 − Sequential Circuits

Page 14 of 36

D2			Q Q 'Q '
	CQ2		2	1	0
Q1Q0
		00	01		11	10
	00		1		1
	01		1
	11					1
	10
		C'Q2Q1'			CQ2'Q1Q0

D1			CQ2'Q1'Q0
	CQ
		2
Q1Q0		00	01	11	10
	00
	01				1
	11	1
	10	1			1
C'Q2'Q1				Q2'Q1Q0'

D0	CQ	CQ1'Q0'		CQ2'Q0'
		2
Q1Q0		00	01	11	10
	00			1	1
	01	1	1
	11	1
	10				1
	C'Q2'Q0		C'Q1'Q0

D2 = Q2Q1'Q0' + C'Q2Q1' + CQ2'Q1Q0

D1 = C'Q2'Q1 + Q2'Q1Q0' + CQ2'Q1'Q0

D0 = C'Q1'Q0 + C'Q2'Q0 + CQ1'Q0' + CQ2'Q0'

			(d)
Current State		Output
Q2Q1Q0		Y
000		0
001		0	Y = Q2Q1'Q0
010		0
011		0

1000

1011

(e)

C
D2	Q2	Y
Clk
	Q'2
D1	Q1
Clk
	Q'1
D0	Q0
Clk
Clk	Q'0
(f)

Figure 10. Synthesis of a Moore FSM: (a) state diagram; (b) next-state table; (c) implementation table; (d) K-maps and excitation equations; (e) output table and equation; (f) FSM circuit.

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM

Chapter 7 − Sequential Circuits

Page 15 of 36

Example 7.4

In this example, we will synthesize a Moore FSM that is more typical of what the control unit of a microprocessor is like. The state diagram shown in Figure 11(a) has four states. Each state is labeled with a state name (s0, s1, s2, and s3) and has two output signals x and y. There are also two conditional status signals Start and (n=9) labeled on four of the edges, while the rest of the edges do not have any conditions. From state s2, the conditional edge with the label (n = 9) is taken when the variable n is equal to nine. If n is not equal to nine, then the edge with the label (n = 9)' is taken. Similarly, from state s0, the edge labeled Start is taken when Start = 1, otherwise, the edge labeled Start' is taken.

Two flip-flops Q0 and Q1 are needed in order to encode the four states. For simplicity, we will use the binary value of the index of the state name to be the encoding for that state. For example, the encoding for state s0 is Q1Q0 = 00 and the encoding for state s1 is Q1Q0 = 01, and so on.

From the above analysis, we are able to derive the next-state table as shown in Figure 11(b). The four current states (Q1Q0) are listed down the four rows. The four columns are for the four combinations of the two conditional signals Start and (n=9). For example, the column with the value Start, (n=9) = 10 means Start = 1 and (n=9) = 0. The condition (n=9) = 0 means that the condition (n=9) is false which means (n=9)' is true. The entries in the table

are the next states (Q1next Q0next) for the two flip-flops. For example, looking at the state diagram, from state s2 we go back to state s1 when the condition (n=9)' is true independent of the Start condition. Hence, for the s2 (10) current

state row in the next-state table, the two next-state entries where the column heading is (n=9) = 0 (i.e. Start, (n=9) = 00 and 10), is s1 (01).

Start'
s0
x=0
y=1
Start
s1
x=1
y=1
s2	(n = 9)'
x=1
y=1
(n = 9)
s3
x=1
y=0
(a)

	Current				Next State
					Q1next	Q0next
	State
					Start, (n=9)
	Q1Q0
		00		01		10	11
	s0 00		s0 00		s0 00	s1 01	s1 01
	s1 01		s2 10		s2 10	s2 10	s2 10
	s2 10		s1 01		s3 11	s1 01	s3 11
	s3 11		s0 00		s0 00	s0 00	s0 00
					(b)
	Current				Implementation
					D1	D0
	State
					Start, (n=9)
	Q1Q0
			00		01	10	11
	s0 00		s0 00		s0 00	s1 01	s1 01
	s1 01		s2 10		s2 10	s2 10	s2 10
	s2 10		s1 01		s3 11	s1 01	s3 11
	s3 11		s0 00		s0 00	s0 00	s0 00

(c)

Figure 11. Synthesis of a Moore FSM for Example 9.4: (a) state diagram; (b) next-state table; (c) implementation table.

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM

Chapter 7 − Sequential Circuits

Page 16 of 36

Using D flip-flops to implement the FSM, we get the implementation table shown in Figure 11(c). The implementation table and the next-state table are identical when D flip-flops are used. The only difference between them is the meaning given to the entries. For the next-state table, the entries are the next state of the flip-flops, whereas for the implementation table, the entries are the inputs to the flip-flops. They are the input values necessary to get to that next state. Again, since the next state is equal to the input value (Qnext = D) for a D flip-flop, therefore,

D1	Start,(n=9)					D	0	Start,(n=9)
Q1Q0		00	01	11	10
						Q1Q0			00	01	11	10
	00							00			1	1
	01	1	1	1	1			01
	11							11
	10		1	1				10	1	1	1	1
	Q1'Q0		Q1Q0'(n=9)						Q1Q0'		Q0'Start
	D1 = Q1'Q0 + Q1Q0'(n=9)					(d)		D0 = Q1Q0' + StartQ0'
				Current State		Output					x	Q0			y	Q0
											Q1		0	1	Q1		0	1
					Q1Q0	xy
												0	0	1		0	1	1
					00	01
												1	1	1		1	1	0
					01	11
					10	11
					11	10		(e)			x = Q1 + Q0				y = (Q1Q0)'
				Start (n=9)		Input
						signals
															x
								D1		Q1					y
								Clk							Output
										Q'1
															signals
								D0		Q0
								Clk
				Clk						Q'0
						Next-state logic		State memory						Output logic

(f)

Figure 10 continue. (d) K-maps and excitation equations for D1 and D0; (e) output table, K-maps and output equations; (f) FSM circuit.

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM

Chapter 7 − Sequential Circuits

Page 17 of 36

the entries in these two tables are the same.

The excitation equations are derived from the implementation table. There is one excitation equation for every data input of every flip-flop used. Since we have two D flip-flops, therefore, we will have two excitation equations; one for D1 and the second for D0. The equations are dependent on the four variables Q1, Q0, Start, and (n=9). We look at the implementation table as one having two truth tables merged together, one truth table for D1 and one for D0. Since the two bits in the entries are ordered D1D0, therefore, for the D1 truth table, we look at only the leftmost D1 bit in each entry, and for the D0 truth table, we look at only the rightmost D0 bit. Extracting the two truth tables from the implementation table in this manner, we obtain the two K-maps and corresponding excitation equations for D1 and D0 as shown in Figure 11(d). The excitation equations allow us to derive the next-state combinational circuit.

The output table is obtained from the output signals given in the state diagram. The output table is just the truth table for the two output signals x and y. The output signal equations derived from the output table are dependent on the current state Q1Q0. The output table, K-maps and output equations are shown in Figure 11(e).

Using Figure 2(a) as a template, our FSM circuit has two D flip-flops for its state memory. The next-state logic circuit is derived from the excitation equations and the output logic circuit is derived from the output equations. Connecting these three parts together produces the FSM circuit shown in Figure 11(f). ♦

7.3.4 Example: Synthesis of a Mealy FSM

We will now illustrate the synthesis of a Mealy FSM with an example. You will find that this process is almost identical to the synthesis of a Moore FSM with the one exception of deriving the output equations. The outputs for a Mealy FSM are dependent on both the current state and the input / status signals, whereas, for the Moore FSM, they are only dependent on the current state.

Example 7.5

In this example, we will synthesize a Mealy FSM based on the state diagram shown in Figure 12(a) using D flip-flops. The four states are already encoded with the values of the two flip-flops. There are two conditional status signals (x=0) and (x=y). Since these are conditions, the equal sign means the test for equality. There is one output signal A, which can be set to either a 0 or a 1 value. So the equal sign here means assignment. Notice that what makes this a Mealy FSM state diagram is the fact that the outputs are associated with the edges and not the nodes.

	Reset
	00
(x=0)		(x=0)'
A=1		A=0
01		10
A=0		A=1
	11	(x=y)
		A=0
(x=y)'
A=1
	(a)

				Next State
	Current State			Q1nextQ0next
	Q1Q0		(x=0), (x=y)
		00		01	10		11
	00	10		10	01		01
	01	11		11	11		11
	10	11		11	11		11
	11	01		00	01		00
		(b)
		Implementation
	Current State			D1D0
	Q1Q0		(x=0), (x=y)
		00		01	10		11
	00	10		10	01		01
	01	11		11	11		11
	10	11		11	11		11
	11	01		00	01		00

(c)

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM

Chapter 7 − Sequential Circuits

Page 18 of 36

D1	(x=0), (x=y)
Q1Q0		00	01	11	10
	00	1	1
	01	1	1	1	1
	11
	10	1	1	1	1

D0	(x=0), (x=y)
Q1Q0		00	01	11	10
	00			1	1
	01	1	1	1	1
	11	1		1
	10	1	1	1	1

D1 = Q1'Q0 + Q1Q0' + Q1' (x=0)'	D0 = Q1'Q0 + Q1Q0' + Q1' (x=0) + Q0(x=0)' (x=y)'
= (Q1 Q0) + Q1' (x=0)'	= (Q1 Q0) + Q1' (x=0) + Q0(x=0)' (x=y)'

					(d)
			Output		A	(x=0), (x=y)
	Current State			A
					Q1Q0		00	01	11	10
	Q1Q0		(x=0), (x=y)
						00			1	1
		00	01	10	11
						01
	00	0	0	1	1
	01	0	0	0	0	11	1	1	1	1
	10	1	1	1	1
						10
	11	1	0	1	0		1			1

	A = Q1Q0 + Q1(x=y)' + Q1'Q0' (x=0)
(e)
(x=0)(x=y)
D1	Q1
Clk	A
	Q'1
D0	Q0
Clk
Clk	Q'0
(f)

Figure 12. Synthesis of a Mealy FSM for Example 9.5: (a) state diagram; (b) next-state table; (c) implementation table; (d) K-maps and excitation equations for D1 and D0; (e) output table, K-maps and output equations; (f) FSM circuit.

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM

Chapter 7 − Sequential Circuits

Page 19 of 36

7.4* ASM Charts and State Action Tables

To concisely portrait the information depicted by the state diagram and the next-state and output tables, we can use algorithmic state machine (ASM) charts or state action tables. Both of them are just different ways of representing the information more conveniently. The state action table uses a tabular format while the ASM chart uses a graphical flowcharting format.

7.4.1 ASM Charts

Algorithmic state machine (ASM) charts are used to graphically represent the next-state and output tables of a FSM. They are similar to flowcharts used in computer programming by using different shape boxes as shown in Figure 13 to describe a sequence of actions. However, in addition to just describing a sequence of actions, ASM charts also describe the timing relationships between the states.

The rectangle shown in Figure 13(a) is the state box for representing a state in the FSM, which is equivalent to a node in the state diagram. A state in the FSM is for performing data manipulation actions or output actions, so the state box contains a list of these unconditional (Moore type) actions that are to be performed in that state. For example, a state box may contain the two unconditional actions count = count + 1 and output count. There is only one path going into the state box and one path coming out of the state box. Outside the rectangle at the top left corner is labeled with the symbolic state name while the top right corner is labeled with the state encoding (if known).

The diamond shape box shown in Figure 13(b) is the decision box to test whether the given condition in the box is true or false. There is one path going into the decision box and two paths coming out of the box. The two paths coming out of the decision box is labeled true or false. If the given condition is true, then the path labeled true is taken, otherwise, the path labeled false is taken. The decision box is used to determine the next state to go to as in the condition that is labeled on the edges in the state diagram. The decision box is also used for a Mealy FSM where actions are performed depending on the condition of an input. This is used in conjunction with the condition box. The decision box by itself is not equivalent to one state.

The oval shape condition box shown in Figure 13(c) is also for performing data manipulation actions such as variable assignments and data outputs like the state box. Whereas the state box is used for unconditional data manipulations, the condition box is only used for conditional data manipulations in Mealy FSMs. The testing of the condition, however, is not done within the condition box, but rather in a previous decision box. The condition box by itself is not equivalent to one state. It must be used together with a decision box within an ASM block.

The ASM block shown in Figure 13(d) allows a state box and zero or more decision and/or condition boxes to be grouped together in one state. All the actions specified inside an ASM block are executed within one state or one clock cycle. Like the state box, the ASM block is labeled with the state name on the outside top left corner and the state encoding on the top right corner. The ASM block must start with one state box containing zero or more unconditional data actions. The state box is then followed by zero or more decision boxes and/or condition boxes. The ASM block will have one entry point and one or more exit paths.

Figure 14 shows an example of an ASM block. The symbolic state name is s0 using the encoding 00. When the FSM enters this state, the variable Sum is initialized to 0 and the Start signal is tested. If there is no Start signal, the FSM re-enters this state at the next clock cycle. If there is a Start signal, an input is performed to load the variable n.

Figure 15 shows the ASM chart for the state diagram and next-state / output table of Example 9.4 shown in Figure 11. Since this is a Moore FSM, no condition boxes are needed.

State			State
name			code
Unconditional
variable assignment					True			False
and output
							Condition

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM

Chapter 7 − Sequential Circuits

Page 20 of 36

	State box (unconditional assignment)	Decision box
	(a)
		(b)
	State	State
	name	code
	Conditional
	variable assignment
	and output
	Condition box (conditional assignment)	ASM block
	(c)	(d)

Figure 13. Symbols use in an ASM chart: (a) state box; (b) decision box; (c) condition box; (d) ASM block.

s0		00
	Sum = 0
0	Start	1
		input n

Figure 14. A sample ASM block.

Microprocessor Design – Principles and Practices with VHDL

Last updated 7/18/2003 1:19 PM