6.2.1. Analysis of Synchronous Sequential Circuits¶

We demonstrate the functional analysis of synchronous sequential circuits by means of the multiplexer loop, extended with a D-flipflop in the feedback loop. As shown in Figure 6.8, D-flipflop output \(Q\) drives the feedback input of the multiplexer, and clock signal \(\phi\) triggers the D-flipflop at the positive clock edge. At this point in time the D-flipflop stores its input \(Y\) for an entire clock cycle until the next positive clock edge occurs.

Figure 6.8: Multiplexer with D-flipflop in feedback loop triggered by clock signal \(\phi.\)

The value stored in the D-flipflop is called the state of the synchronous circuit. In Figure 6.8 the state is observable at D-flipflop output \(Q.\) The purpose of circuit analysis is to determine the next state of the next clock cycle. If we consider all possible input combinations, the analysis enables us to predict the sequence of output values given a sequence of input values. The next state of the multiplexer loop is the value of input \(Y\) of the D-flipflop at the time of the triggering clock edge. Signal \(Y\) is driven by the combinational multiplexer circuit, and is a function of inputs \(D\) and \(S,\) and state \(Q\):

We use an adapted form of transition table, the so-called state transition table, to list the next state as a function of the state and the inputs. Since the state of the circuit is equal to \(Q\) and the next state is equal to \(Y,\) the state transition table of the multiplexer loop in Figure 6.8 is:

state (\(Q\))	\(D\)	\(S\)	next state (\(Y\))
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

State transition tables are commonly drawn in form of a truth table, although we could use the equivalent K-map form as well. Under the assumption that the input values \(D\) and \(S\) are stable at the time of the triggering clock edge, we derive next state \(Y\) by evaluating equation \(Y(D,S,Q)\) for the combination of input values in each row. This equation specifies the next state logic implemented by the combinational multiplexer.

Although the state transition table specifies the transition behavior of a sequential circuit unambiguously, it can be advantageous to visualize the transition behavior by means of a directed graph, the so-called state transition diagram. Here, each vertex represents a state, and each arc a transition. We annotate the arcs with the combination of input values associated with the state transition. Separated by a slash, we also include output \(Y\) of the circuit, which happens to be equal to the next state in this example. Figure 6.9 shows the state transition diagram of the multiplexer loop in Figure 6.8. The vertices are marked with the value of state \(Q.\) The format of the arc annotations is \((D,S)/Y,\) i.e. the pair of input values followed by a slash followed by the output value.

Figure 6.9: State transition diagram of synchronous multiplexer loop. Arcs are marked with input and output values, separated by a slash.

We interpret the state transition diagram as follows. During the present clock cycle, the circuit is in one of the states represented by a vertex, for example in state 0. While in this state, the inputs may change causing the output to change. For example, in state 0, if we apply inputs \((D,S)=01,\) then output \(Y=0,\) as indicated by arc annotation \(01/0.\) If we apply inputs \((D,S)=11,\) then output \(Y=1,\) and the arc annotation is \(11/1.\) The input combination at the time of the triggering clock edge determines the next state. For example, arc \(11/1\) points from state 0 to state 1, because at the triggering clock edge next state \(Y=1\) is stored in the D-flipflop. The other three input combinations \(00/0,\) \(01/0,\) and \(10/0\) store next state \(Y=0\) at the triggering clock edge, which is also the present state. Therefore, the corresponding arc is a loop from state 0 to state 0 for all three input combinations. Comparison with the next state table shows that each arc annotation in the diagram corresponds to one row in the table. The diagram captures the transition behavior in a more compact form, that some designers find easier to comprehend than a table.

The state transition table and/or the state transition diagram enable us to derive the output sequence of the circuit if the inputs are synchronized with the clock, such that during each clock cycle one new pair of inputs arrive. For example, assume that the multiplexer loop is initially in state 0, and we apply the input sequence 00, 11, 10, 01, 10. Then, the corresponding output sequence is 0, 1, 1, 0, 0. Here is why. Initially, the circuit is in state 0, and we apply the first input pair 00. Hence, the output is \(Y=0.\) At the next triggering clock edge, the D-flipflop stores next state 0. Now, we apply the second input pair 11. The output changes to \(Y=1.\) At the next triggering clock edge the circuit transitions to state 1. The third input pair 10 holds output \(Y=1,\) and so on. Use the interactive model in Figure 6.10 to develop a feeling for the synchronous multiplexer loop. You can toggle inputs \(D\) and \(S\) and trigger a positive clock edge by pushing the \(\phi\) trigger button.

The multiplexer loop does not restrict the inputs to change only once per cycle. In fact, you can change inputs \(D\) and \(S\) as often as you like between triggering clock edges. The output follows the inputs through the combinational logic implemented by the multiplexer. State changes, however, occur only upon triggering a positive clock edge. At this time, the D-flipflop stores the next state supplied to its input by multiplexer output \(Y.\) In summary, if input \(S=1,\) the loop stores input \(D\) at the time of the clock trigger. Otherwise, while \(S=0,\) the loop holds its state across clock trigger events independent of \(D.\) The state transition table and diagram above contain the same information about the circuit.

In the following, we analyze several synchronous sequential circuits by deriving their state transition table and diagram. These circuits are sequential building blocks for the design of larger sequential circuits.

6.2.2. Binary Counter¶

An \(n\)-bit binary counter is a synchronous sequential circuit that increments its \(n\)-bit output \(Y\) at every triggering clock edge. Since \(n\) bits can represent unsigned numbers in range \([0, 2^n-1],\) the counter rolls over to 0 when incrementing the largest value \(2^n-1\) of the representable number range. Therefore, \(n\)-bit binary counters are also called modulo-\(2^n\) counters. Figure 6.11 shows a 3-bit binary counter with a reset input to force the counter to zero. While the reset input is 0, the reset signal is inactive. Whenever a positive clock edge occurs the counter increments the value stored in the 3-bit register. If the reset input is equal to 1 during a positive clock edge, the register is reset to zero.

The counter circuit is synchronous, because the feedback loop contains a clock triggered register. Output \(Y\) of the register feeds back into the 3-bit adder. The second input of the adder is hardwired to constant value \(1_{10}.\) We tacitly assume that the carry-in of the adder is grounded to value 0, and the carry-out is unused. Sum output \(S\) of the adder generates the 3-bit sum \(S=(Y+1) \bmod 8.\) Recall that the largest unsigned binary number representable with 3 bits is \(2^3-1 = 7_{10},\) and \(7+1=8_{10} = 1000_2\) requires 4 bits. Since the sum output of the adder excludes the most significant carry-out bit, we obtain \(S = 000_2 = 0_{10}\) for input \(Y=7_{10}.\) The multiplexer implements the reset logic. Next state signal \(Y'\) is the output of the combinational portion of the feedback loop, and obeys the multiplexer logic:

We analyze the behavior of the counter circuit by deriving the state transition diagram. The circuit has one input besides clock \(\phi,\) i.e. the reset signal, and one output, which is counter value \(Y.\) First assume that the reset signal is inactive, and the counter increments its output at every positive clock edge. During a clock cycle the register stores the present state and drives it on output \(Y,\) where we can observe the state. At the next positive clock edge, the circuit transitions to next state \(Y'.\) We draw the state transition diagram, we need to start with some state, for example state \(0_{10}.\) We represent the state with a new vertex and mark it with its identifying state value 0. The next state of state \(0_{10}\) is \(Y'=1_{10}.\) We draw a second vertex, mark it with state value \(1_{10},\) and draw an arc from vertex 0 to vertex 1.

Figure 6.12: State transition diagram of 3-bit binary counter. Arcs are marked with input values only. Vertices are augmented with the output values.

Rather than annotating the arc with the output value as we did in Figure 6.9, we annotate the vertices with the output values. The reason for this change is a subtle difference in the output behavior of the circuits. In the multiplexer loop of Figure 6.8 the combinational logic drives the output whereas in the counter loop of Figure 6.11 the register drives the output. Whereas the output of the multiplexer loop depends on the present inputs, this is not the case for the binary counter. Output \(Y\) of the binary counter is stable during the entire clock cycle, independent of the reset input. The output changes only at the positive clock edge. In the state transition diagram in Figure 6.12 we emphasize this behavior by marking arcs with the input value of the reset input, and augment the state vertices with the output value.

As long as the reset input is 0, the counter circuit transitions from state \(Y\) to state \((Y+1) \bmod 8\) at each triggering clock edge. Thus, the state transition graph is a single cycle with eight states. If the reset input is 1, however, the counter transitions to state 0, independent of the present state. The reset arcs form additional cycles in the state transition diagram. As shown in Figure 6.12, the complete diagram has nine cycles. We could join the output arcs of state 7, however, because both input values 0 and 1 cause a transition to state 0.

The state transition table is the equivalent representation of the state transition diagram in Figure 6.12. For the binary counter, it assumes the form of a truth table with one column for the present state and the reset signal as inputs, and the next state as output. Frequently, designers augment the state transition table with the output specification, here with one column for output \(Y\):

state	reset	next state	output
0	0	1	0
0	1	0	0
1	0	2	1
1	1	0	1
2	0	3	2
2	1	0	2
3	0	4	3
3	1	0	3
4	0	5	4
4	1	0	4
5	0	6	5
5	1	0	5
6	0	7	6
6	1	0	6
7	0	0	7
7	1	0	7

In case of the binary counter, specifying output \(Y\) in the state transition diagram or table is redundant, since the state and the output are equal. This is not the case in general, however. Note that we can deduce from the state transition table that the output is driven by the register rather than the combinational logic, because the output equals the present state, independent of the reset input.

6.2.3. Shift Register¶

An \(n\)-bit shift register has one serial input and \(n\) parallel outputs. Its function can be described as a serial-to-parallel converter. Figure 6.13 shows a 4-bit shift register with serial input \(S_{in}\) and four parallel outputs \(Y_i,\) where \(0 \le i < 4.\) Some implementations provide parallel output \(Y_{n-1}\) also as a separate serial output \(S_{out}.\) At each positive clock edge, the state is shifted by one D-flipflop to the right. After shifting four bits during four consecutive clock cycles into the shift register, all four bits are available at the parallel outputs. Considering the serial input and serial output only, the shift register implements a FIFO, short for first-in-first-out buffer. The first of multiple bits shifted in at \(S_{in}\) is the first bit to be shifted out at \(S_{out}.\) It takes four clock cycles for a bit to propagate through the FIFO.

The shift register is a synchronous sequential circuit, although the circuit diagram does not show any loops. The feedback loops are hidden inside the D-flipflops. In essence, a shift register is a series composition of D-flipflops, all triggered by the same clock signal. The state of the shift register can be observed at the outputs as binary number \(Y_3 Y_2 Y_1 Y_0.\) Figure 6.13 enables you to derive the state transition table of the 4-bit shift register:

state	\(S_{in}\)	next state	output
0	0	0	0000
0	1	8	0000
1	0	0	0001
1	1	8	0001
2	0	1	0010
2	1	9	0010
3	0	1	0011
3	1	9	0011
4	0	2	0100
4	1	10	0100
5	0	2	0101
5	1	10	0101
6	0	3	0110
6	1	11	0110
7	0	3	0111
7	1	11	0111
8	0	4	1000
8	1	12	1000
9	0	4	1001
9	1	12	1001
10	0	5	1010
10	1	13	1010
11	0	5	1011
11	1	13	1011
12	0	6	1100
12	1	14	1100
13	0	6	1101
13	1	14	1101
14	0	7	1110
14	1	15	1110
15	0	7	1111
15	1	15	1111

The state transition table confirms that the outputs are independent of input \(S_{in}.\) This is no surprise, because the outputs are driven by the D-flipflops. Besides, the shift register has no combinational logic other than wires. Therefore, when drawing the corresponding state transition diagram we associate the output with a state vertex and the value of input \(S_{in}\) with an arc, analogous to the state transition diagram of the binary counter in Figure 6.12. We leave it as an exercise to translate the state transition table into a state transition diagram. You may view the resulting state transition diagram as a directed graph, and find the shortest paths to transition from one state to another in order to minimize the number of clock cycles and the length of the serial input sequence. For example, given state 6 you need at least two cycles to transition to state 9. The path transitions through state 3 by first applying serial input 0 and then 1.

We can extend the shift register to function not only as a serial-to-parallel converter but also as a parallel-to-serial converter. To that end, we provide parallel data inputs and include a multiplexer at each D-flipflop input. Figure 6.14 shows the extended 4-bit shift register. The Load input selects the multiplexer inputs between the parallel data inputs \(D_i,\) \(0 \le i < 4,\) and the original serial inputs. When Load equals 1 at the triggering clock edge, all D-flipflops store the values provided at the parallel data inputs. Otherwise, when Load equals 0, the circuit performs a right shift. During each clock cycle, the circuit outputs the data serially, bit-by-bit, at output \(S_{out}.\)

Figure 6.14: 4-bit shift register with parallel load.

The shift register in Figure 6.14 can be used to implement the ports of a serial communication channel, such as RS-232. The sender uses the parallel-to-serial functionality to load a byte of data into the shift register, and transmit the byte serially across one wire to a receiver. The receiver shifts the bits serially into its shift register, and outputs the byte in parallel, using the serial-to-parallel functionality.

6.2.4. Memories¶

The memory elements discussed so far, including the D-flipflop, are relatively fast circuits but require more transistors than necessary to store a single bit. The hallmark of memory circuits is their density, i.e. the number of bits stored per unit of chip area.

Memory Organization¶

There exist serveral different technologies to implement a 1-bit memory element. However, independent of the technology virtually all memory architectures consist of a 2-dimensional array of such 1-bit memory elements, also called bit cells in this context. Figure 6.15 shows the block diagram of a \(4\times 3\) array of bit cells.

Figure 6.15: Memory array with 4 rows and 3 columns of bit cells.

The array has an address bus \(A\) as input, and a data bus \(D\) as input and output. In general, \(n\)-bit address \(A\) drives an \(n{:}2^n\)-decoder to assert one of \(2^n\) wordlines, thereby selecting one row of the array of bit cells. We call a group of \(m\) data bits a word, and consider a word the unit of data transfer in and out of the memory array. In order to read one word out of one row of bit cells, we apply the associated binary-coded address, and the \(m\)-bit data bus outputs the word via the bitlines. If we want to write a word into the memory, we drive the word onto the bitlines, and apply the desired address.

Each bit cell is responsible for implementing a tristate behavior depending on the select input driven by the wordline and the signal on the bitline. Figure 6.16 shows one bit cell with its select input \(S\) connected to the wordline and data port \(D\) connected to the bitline for input and output. If the wordline drives a 0 on select input \(S,\) the cell disables data port \(D,\) indicated by value \(Z\) in Figure 6.16. As a result the cell is invisible to the bitline. Otherwise, if the wordline drives a 1 on select input \(S\) the cell is enabled. The enabled cell performs a read or write operation depending on the state of the bitline. In order to write the cell, we use a tristate buffer to drive the desired value onto the bitline. This data input is enabled with signal \(D_{en}.\) While \(D_{en} = 1,\) the tristate buffer drives data input \(D_{in}\) onto the bitline, and writes \(D_{in}\) into the enabled cell. On the other hand, if \(D_{en}=0,\) the data input is disabled, and the enabled cell makes its stored bit visible to the bitline, where we can observe it at data output \(D_{out}.\)

wordline = 0    Den = 0    Din = 0 Figure 6.16: Interactive model for reading and writing a bit cell.

When multiple rows of bit cells are arranged in an array, all cells in a column are connected to the same bitline. To read one word from the array, at most one row may make its stored bits visible on the bitlines. The cells in all other rows must disable their data ports. Figure 6.17 illustrates the interplay of the rows in an array when reading one row. Note that the address decoder guarantees that at any point in time exactly one row of cells is enabled, because the decoder drives a one-hot encoding of the binary address onto the wordlines.

A1 = 0    A0 = 0 Figure 6.17: Interactive model for reading a 4x3 memory array.

Memory Technologies¶

If a memory cannot be written but read only, like the memory array in Figure 6.17, it is called read only memory, or ROM for short. ROMs are nonvolatile memories because they retain their data if the power supply is switched off. Historically, data were stored irreversibly in a ROM by burning a fuse in each bit cell. Most ROMs today are programmble ROMs or PROMs that can be written once. Popular examples for PROMs are CDs and DVDs. A memory that can be read and written is called random access memory or RAM. A RAM is a volatile memory that loses its data when the supply power is switched off. The name random access is historically motivated to distinguish a RAM, where each bit is assumed to have the same access time, from sequential access memories like tapes, where a bit is located in a particular position on the tape, and the mechanical winding of the tape into the bit position determines its access time. Today, two types of semiconductor RAMs are wide spread, the DRAM and the SRAM. We briefly introduce these two types of RAMs by discussing their characteristic bit cell technologies.

Figure 6.18: Deep trench DRAM bit cell.

A dynamic RAM, or DRAM for short, stores a bit in form of charge on a capacitor. Figure 6.19 shows the DRAM bit cell consisting of the capacitor and an nMOS transistor. If the capacitor is discharged to GND, we interpret the bit stored in the cell as logical 0. Otherwise, if the capacitor is charged to \(V_{DD},\) we interpret the stored bit as logical 1. The nMOS transistor controls the cell. If the wordline is 1, the nMOS transistor enables the cell by connecting the capacitor to the bitline. Otherwise, if the wordline is 0, the nMOS transistor is switched off, and disables the cell by disconnecting the capacitor from the bitline.

Figure 6.19: DRAM bit cell storing a 0 (left) and a 1 (right).

When reading the DRAM bit cell, the nMOS transistor connects the capacitor to the bitline. If the capacitor is discharged, we observe a zero voltage at the data output of the bitline. Otherwise, the charge of the capacitor diffuses onto the bitline, and we observe a logical 1 at the data output. Since the charge diffuses due to reading, we need to restore the bit cell after reading it. This is the reason why a DRAM is called dynamic RAM. Restoring the bit cell simply means writing the read value by driving it onto the bitline again, see Figure 6.16. The capacitor must be large enough so that a positive charge can be detected at the data output of the bitline. Figure 6.18 shows a deep trench capacitor, where a deep hole is drilled into a silicon wafer that is filled with metal. Since real capacitors leak, the charge stored on the capacitor must be restored periodically or the bit is lost.

The SRAM is a static RAM where the bit cell is stable because its state is continuously replenished by the power supply. An SRAM cell is essentially a bistable inverter pair. As shown in Figure 6.20, we control the inverter pair with two nMOS transistors and extend the memory array with a complemented bitline. Since each CMOS inverter requires two transistors, the bit cell as a whole consists of six transistors (6T). When the wordline is 0, the nMOS transistors disconnect the inverter pair from the bitlines. Otherwise, the bitlines are connected to the complemented and uncomplemented bit \(Q\) stored in the cell. We read the bit of the enabled cell at the data outputs of the bitlines. Writing a bit requires drivers at the data inputs of the bitlines that are stronger (larger) than the inverters of the cell, so as to overpower the inverter pair into the desired state.

Figure 6.20: 6T SRAM bit cell.

DRAM and SRAM memories are sequential circuits. However, neither memory design requires a clock signal for its operation. Therefore, DRAMs and SRAMs are asynchronous sequential circuits in principle. To operate within a synchronous design, memory arrays are wrapped into synchronous control logic to ensure that the read and write operations stabilize within a clock cycle. Figure 6.21 shows a black-box synchronous memory module. It has a clock input, a write-enable input WE, an \(n\)-bit address input, and an \(m\)-bit data input and \(m\)-bit data output.

Figure 6.21: Synchronous memory module.

The read operation of a synchronous memory module is considered a combinational operation, independent of the triggering clock edge. Reset the WE input to 0, apply the desired address \(A,\) and the associated data word appears at data output \(D_{out}\) after the propagation delay within one clock cycle. In contrast, the write operation is synchronized by the clock. Set the WE input to 1, apply the desired address \(A\) and data input \(D_{in},\) and the data is written into memory at the triggering positive clock edge.

The bus width of the address input specifies the number of rows, also called depth, of the memory array. Given \(n\) address wires, the \(n{:}2^n\) address decoder drives \(2^n\) wordlines, as shown in Figure 6.15, so that the depth of the memory array is \(2^n.\) The bus width of the data input and the data output is equal to the number of columns, also called width or word size, of the memory array. Thus, the memory array inside the synchronous memory module in Figure 6.21 has a width of \(m.\) The capacity of a memory is the number of bit cells, i.e. depth \(\times\) width bits. The memory array in Figure 6.15, for example, has 2 address bits, a depth of \(2^2 = 4,\) a width of 3, and a capacity of \(4 \times 3 = 12\) bits.

Logic in Memories¶

Memories serve not only their purpose as a storage medium but are also used as universal logic operators. Given a \(n\)-variable logic function, we use a \(2^n \times 1\) memory array with \(n\) address inputs and one data output as a lookup table to read the function values. We can configure a RAM to implement any logic function by storing one function value per row. Essentially, the memory stores the truth table of a given combinational function and we select the row by applying the desired input combination. Figure 6.22 shows a 2-input XOR function \(Y = A \oplus B,\) implemented by means of a \(4\times 1\) memory array.

A = 0    B = 0 Figure 6.22: 2-input XOR gate implemented with a \(4\times 1\) memory array.

Memories can implement multioutput functions by including one column per output. Thus, a multioutput function with \(m\) outputs can be realized with a memory array of width \(m.\) Since RAMs permit configuring any multioutput function that fits the depth and width of the memory array, RAMs serve as lookup tables in reconfigurable logic devices, including FPGAs.

---

6.2

Analyze the synchronous sequential NAND loop.

1. Derive the next-state logic.
2. Derive a state transition table.
3. Derive a state transition diagram.
4. Use a time table to analyze the transitions of input sequence \(A = \langle 0, 0, 1, 0, 0, 0, 1, 1, 1, 1 \rangle.\)

1. The sequential NAND loop has a register on the feedback path. The state of the present clock cycle is observable at register output \(Q.\) The next state is the value of the data input of the register, and is stored at the next positive clock edge. In the NAND loop, the next state equals output \(Y,\) and is a function of present state \(Q\) and input \(A\):

   \[Y(A,Q) = \overline{A Q}\,.\]

   This function is the combinational next state logic of the circuit.

2. The state transition table is the truth table of the next state logic:

   \(A\)	\(Q\)	\(Y\)
   0	0	1
   0	1	1
   1	0	1
   1	1	0

3. The state transition diagram is the graphical representation of the state transition table. It has one vertex per state, here \(Q \in \{ 0, 1 \},\) and one arc per transition. We annotate the arcs with input \(A\) and output \(Y,\) separated by a slash. Note that output \(Y\) is also the next state of the NAND loop.

   

   The diagram shows that the NAND loop transitions from state \(Q=0\) to state \(Q=1\) regardless of input \(A.\) Thus, when the circuit transitions into state \(Q=0,\) it remains there for one clock cycle before returning to state \(Q=1.\) It remains in state \(Q=1\) while input \(A=0,\) and transitions to state \(Q=0\) when input \(A=1.\) If we hold input \(A\) at value 1, the circuit toggles between states 0 and 1 at every positive clock edge. This behavior resembles the oscillation in Exercise 6.1.

4. We use a time table to study the behavior of the NAND loop over time given input sequence \(A\) for ten clock cycles, \(0 \le t < 10\):

   t	0	1	2	3	4	5	6	7	8	9
   Q	X	1	1	0	1	1	1	0	1	0
   A	0	0	1	0	0	0	1	1	1	1
   Y	1	1	0	1	1	1	0	1	0	1

   We do not need to know initial state \(Q[0]\) during clock cycle \(t = 0\) to conclude that next state \(Y[0]=1\) if \(A=0.\) Therefore, we mark \(Q[0] = X\) as unspecified. While \(A=0,\) the circuit stays in state 1, and toggles between states 0 and 1 while \(A=1.\)

Solution

6.3.1. Mealy and Moore Machines¶

Our study of synchronous circuits has revealed nuances in the behavior of such circuits. In particular, the multiplexer loop has an output which is a function of the input and the state, whereas the output of the binary counter is a function of the state only. Since the output of the multiplexer loop is a function of the input, the output may change during a clock cycle if the input changes. In contrast, the output of the binary counter remains stable during the clock cycle. We exploit this difference by tailoring the annotations in the state transition diagrams of Figure 6.9 and Figure 6.12 to their respective needs. In fact, these circuits examplify two distinct types of synchronous sequential circuits.

Machine Models¶

FSMs are generalizing models of synchronous sequential circuits. Figure 6.23 shows the Mealy machine model, named after George H. Mealy, and Figure 6.24 shows the Moore machine model, named after Edward F. Moore. Both machines have

• input bus \(I\) with \(m \ge 0\) signals \(I_0, I_1, \ldots, I_{m-1},\)
• output bus \(O\) with \(n \ge 0\) signals \(O_0, O_1, \ldots, O_{n-1},\)
• current state \(S\) stored in a \(k\)-bit state register with output signals \(S_0, S_1, \ldots, S_{k-1},\) \(k > 0,\) and capable of encoding up to \(2^k\) distinct states,
• next state \(S'\) with \(k\) signals \(S'_0, S'_1, \ldots, S'_{k-1},\)
• combinational next state logic \(\sigma,\) and
• combinational output logic \(\omega.\)

The next state logic of both Mealy and Moore machines is a combinational function \(\sigma: \mathcal{B}^{m+k}\rightarrow \mathcal{B}^k\) that computes next state \(S' = \sigma(S,I).\) The next state computation receives the present or current state \(S\) via the feedback loop. The loop includes the state register triggered by clock signal \(\phi,\) which qualifies both machines as synchronous sequential circuits.

Figure 6.23: Mealy machine model. Output \(O\) depends on state \(S\) and input \(I.\)

The essential difference between the two machine models is the combinational output logic \(\omega.\) For the Mealy machine, output function \(\omega: \mathcal{B}^{m+k} \rightarrow \mathcal{B}^n\) computes output \(O = \omega(S,I)\) as a function of current state \(S\) and input \(I.\) In contrast, the output function of the Moore machine \(\omega: \mathcal{B}^k \rightarrow \mathcal{B}^n\) computes output \(O = \omega(S)\) as a function of current state \(S\) only. The only difference in the circuit diagrams is that the Mealy machine connects input terminal \(I\) to combinational output logic \(\omega\) whereas the Moore machine does not. As a matter of convention for this chapter, we distinguish combinational and sequential logic in circuit diagrams by drawing black-box subcircuits of combinational logic as rectangles with round corners.

Figure 6.24: Moore machine model. Output \(O\) depends on state \(S\) only.

Machine Identification¶

It is not always immediately obvious which type of machine, Mealy or Moore, a synchronous sequential circuit implements. In fact, it may take several attempts of restructuring a circuit before it fits the structure of the Mealy machine in Figure 6.23 or the Moore machine in Figure 6.24. However, the distinguishing characteristic is usually straightfoward to check, i.e. whether the output is a function of the input or not. Consider the multiplexer loop in Figure 6.8, for example. Output \(Y\) is a function of state \(Q\) and inputs \(D\) and \(S.\) Therefore, the circuit is a Mealy machine. But, what is its next state logic \(\sigma\) and what its output logic \(\omega\)? Since the multiplexer output drives both output \(Y\) and the next state input of the D-flipflop, the circuit in Figure 6.8 does not have the structure of the Mealy machine in Figure 6.23. Nevertheless, duplicating the multiplexer, as shown in Figure 6.25, reveals that the multiplexer loop is an optimized version of a vanilla Mealy machine that reuses the next state logic as output logic or vice versa.

Figure 6.25: Multiplexer loop of Figure 6.8 (left) with duplicated multiplexer to match the Mealy machine model of Figure 6.23 (right).

As another example, consider the shift register in Figure 6.13. The outputs \(Y_0,\) \(Y_1,\) \(Y_2,\) and \(Y_3 = S_{out}\) are driven by the registers. Therefore, the outputs are a function of the current state but not a function of input \(S_{in}.\) We conclude that the circuit is a Moore machine. The topology of the circuit in Figure 6.13 is simpler than that of the equivalent vanilla Moore machine in Figure 6.26, where the next state logic \(\sigma\) and output logic \(\omega\) are identity functions.

Figure 6.26: Shift register of Figure 6.13 (left) and with alternative topology of a Moore machine, see Figure 6.24 (right).

Since Mealy and Moore machines differ in their output behavior only, we can often use either type to solve a given problem. However, if we wish to generate the output within the cycle of a particular state and input, then a Mealy machine is required. A Moore machine cannot change the output while in the particular state. Instead, in a Moore machine we must wait until the next triggering clock edge, where the machine assumes the next state as a function of the particular state and input, and can then produce the desired output. On the other hand, a Moore machine has a more robust timing behavior, because the consumer of the output can rely on the fact that the output is stable during the entire cloci cycle after the propagation delay of the output logic has elapsed follwing the triggering clock edge. This delay is independent of changes of the input of the machine.

Machine Transformations¶

Occasionally FSM designers perceive a Moore machine as more natural than a Mealy machine. If a particular type of machine is desired, such perceptions can be overcome because we may translate one machine type systematically into the other. Figure 6.27 shows the two graphical rules for translating state \(A\) from a Mealy type into a Moore type state transition diagram and vice versa. Recall that we associate the output in a Mealy diagram with the input and in a Moore machine with the state.

Figure 6.27: Rules for transforming a Mealy state diagram into a Moore state diagram and vice versa.

Rule 1 states that state \(A\) in Mealy machine can be translated into an equivalent state \(A\) in a Moore machine if all incoming transitions of the Mealy machine have the same output. In this case, we associate the output with state \(A\) of the Moore machine. Conversely, we translate state \(A\) of a Moore machine into a Mealy machine by associating output \(O\) of the Moore machine with all inputs in the Mealy machine. Rule 2 covers the case where the incoming arcs of state \(A\) in the Mealy machine have different outputs. In this case, we replicate Mealy state \(A\) in the Moore machine for each distinct output. Conversely, we transform the Moore machine into a Mealy machine by merging Moore states \(A_1\) and \(A_2\) into Mealy state \(A,\) and by associating the outputs of the Moore states with the inputs of the Mealy transitions.

Rule 2 is the reason why, in general, Mealy machines require fewer states than Moore machines to solve a given problem. Hence, a Mealy machine may be constructed with fewer D-flipflops than the equivalent Moore machine. Whether the reduction in state bits leads to an overall savings in logic, including the next state and output logic, depends on the particular implementation, and requires a direct comparison of alternative designs.

6.3.2. Synthesis of Finite State Machines¶

The FSM designer uses the tools for the analysis of synchronous circuits, in particular the state transition diagram and the state transition table, to specify a FSM for a given problem description, and to implement the FSM as a synchronous sequential circuit. FSM synthesis may be viewed as reversal of the analysis procedure. Although synthesis requires more creativity than analysis, the synthesis of FSMs is a relatively systematic process.

The design methodology for an FSM can be summarized as a 6-step recipe:

1. Identify inputs and outputs.
2. Design a state transition diagram.
3. Select a state encoding.
4. Derive the state transition table.
5. Minimize the next state and output logic.
6. Synthesize the circuit.

Most of a designer’s creativity flows into step 2, where a problem description, typically provided as an informal statement, is formalized by means of a state transition diagram either of Mealy type or of Moore type. The other five steps are comparatively straightforward applications of established techniques.

Before we illustrate the FSM design methodology by means of several examples, let us clarify the role of the state register as the central element of every FSM. The state register holds the current state \(S,\) which we may observe at its output \(Q.\) State \(S\) remains stable for the entire clock cycle between triggering clock edges. Next state \(S'\) is stored at the next triggering clock edge. The next state logic computes \(S'\) as a function of the inputs \(I\) and current state \(S.\) Next state \(S'\) must be stable before the next triggering clock edge so that the state register can store the next state reliably. In Moore machines, the state register decouples the outputs from the inputs. Since the outputs are a function of current state \(S\) only, the inputs affect the outputs of the next state indirectly. In contrast, in a Mealy machine, the inputs bypass the state register so that the outputs react to changes at the inputs within the current clock cycle.

Serial Adder¶

We wish to design a serial version of a ripple carry adder. Assume that the binary summands appear one bit per clock cycle at inputs \(A\) and \(B,\) least significant bits first. The adder shall output the sum bits one per clock cycle, lsb first.

Following the design recipe, we find that step 1 is trivial whereas step 2 requires some thought. Recall that bit position \(i\) might generate a carry into position \(i+1.\) Since the summands appear at the inputs lsb first, imagine the lsb‘s appear in cycle 0, the bits of next position 1 in cycle 1, and so on. Thus, the bits of the summands in position \(i\) are available in cycle \(i,\) and we need to make the carry out of position \(i\) available as carry input during cycle \(i+1.\) We conclude that we need a 1-bit register that stores the carry-out at the next triggering clock edge, which separates current cycle \(i\) and next cycle \(i+1\) in time. The output of the register is the carry-in during cycle \(i+1.\) Since bit position \(i\) generates a carry or not, a 1-bit register suffices to distinguish these two states. Therefore, we decide to design the FSM with a 1-bit state register. Furthermore, we decide to design a Mealy machine.

We develop the state transition diagram of the Mealy machine, starting with two state vertices for state S0, meaning the carry-in is 0, and state S1 to represent a carry-in equal to 1 during the current clock cycle. Figure 6.28(a) shows the two state vertices. Next, we consider the state transitions. Since the current state represents the carry-in, the next state represents the carry out. Thus, our next state logic must implement the carry-out function of a full adder. The carry-out, i.e. the next state, is a combinational function that depends on the two inputs \(A\) and \(B\) and the carry-in, i.e. the current state \(S.\)

Figure 6.28: Design of state transition diagram for serial adder.

Recall that the carry-out of a full adder is 1 if two or three inputs are 1, and otherwise the carry-out is 0. First, we consider the outgoing transitions of state S0, see Figure 6.28(b). The only input combination that can generate a carry-out of 1 is \(A = B = 1.\) We draw an arc from S0 to S1, and annotate it with input combination \((A,B)=11.\) The remaining three input combinations do not generate a carry out. Therefore, we draw a looping arc at state S0, and annotate it with the three remaining input combinations. The outgoing transitions of state S1 are shown in Figure 6.28(c). With a carry-in equal to 1, the only input combination that causes the carry-out to be 0 is \(A = B = 0.\) We draw an arc from S1 to S0 for input combination \((A,B) = 00.\) The other three input combinations cause a carry-out of 1, represented by the loop pointing from S1 to S1. In Figure 6.28(d), we add the outputs to each input combination. The output of the serial adder is the sum bit. If the carry-in is 0, i.e. in state S0, the sum is 1 if exactly one of the inputs \(A\) or \(B\) is 1, otherwise the sum is 0. In state S1, representing a carry-in of 1, the sum is 1 if inputs \(A\) and \(B\) are equal. We also mark state S0 with another circle, indicating that S0 is the start state of the Mealy machine, because initially the carry into lsb position 0 should be 0.

Step 3 of the FSM recipe requires selecting a state encoding. We choose the natural encoding suggested by our design, \(S0 = 0\) and \(S1 = 1,\) because the state register should store the value of the carry. Using the opposite encoding is possible, but would be rather confusing. Next, we derive the state transition table according to step 4 of the FSM recipe. It shouldn’t come as a surprise that converting the state transition diagram of Figure 6.28(d) into a state transition table yields the truth table for the carry-out of a full adder, where the current state is the carry-in:

state	A	B	next state	Sum
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

We have included the Sum output of the serial adder in the state transition table, because it adds just one more column to the truth table. Since the output of a Mealy machine is a function of the current state and the inputs, needed for the next state as well, this is faster and less error-prone than compiling a separate truth table for the output function. Note that the translation of the state transition diagram into the state transition table is a straightforward transliteration of the directed graph into truth table format. No knowledge specific to the purpose of our adder design is required, except the state encoding.

Step 5 of the FSM recipe asks us to minimize the next state and output logic. To that end, we apply the techniques developed for combinational logic design, for example K-maps. The K-maps for the next state \(S'\) and the Sum output

yield the well-known SOP expressions of the majority and odd-parity functions

\[\begin{eqnarray*} S' &=& A S + B S + A B\,, \\ Sum &=& \overline{S}\,\overline{A}\,B + \overline{S}\,A\,\overline{B} + S\,\overline{A}\,\overline{B} + S A B\,. \end{eqnarray*}\]

Without further logic optimizations or technology mapping, we complete step 6 of the FSM recipe, and synthesize a circuit diagram for the serial adder using two-level combinational logic. Figure 6.29 shows the resulting Mealy machine in the topological form of Figure 6.23. The next state logic \(\sigma\) is the majority function and output logic \(\omega\) is a 3-variable XOR function.

Figure 6.29: Mealy machine for serial adder.

Figure 6.29 completes the FSM design of the serial adder. Note that the serial adder consists of the combinational logic of one full adder plus one register. Compared to a ripple carry adder, which requires \(n\) full adders to add two \(n\)-bit summands, our serial adder FSM requires only one full adder, independent of \(n.\) However, our serial adder FSM requires \(n\) clock cycles to produce all sum bits. This is a typical example for the trade-off between space and time in digital logic.

Now that we have a Mealy machine, we have two options to design a Moore machine for the serial adder. Option 1 is to start from scratch, working ourselves through the six steps of the FSM recipe. However, step 2 of the recipe requires more creativity for a Moore machine than for the Mealy machine. This becomes clear after working through Option 2, deriving the Moore machine from the Mealy machine using machine transformations. The state transition diagram of the Mealy machine in Figure 6.28(d) shows four incoming transitions for each state with different outputs, 0 or 1. Therefore, we apply Rule 2 and split each Mealy state into two Moore states, as shown in Figure 6.30. Moore state \(S0_0\) represents a carry-in of 0 with sum output 0 and Moore state \(S0_1\) represents a carry-in of 0 with sum output 1. Analogously, Moore states \(S1_0\) and \(S1_1\) represent a carry-in of 1 with the corresponding outputs.

Figure 6.30: State transition diagram of Moore machine for serial adder.

The state transition diagram of the Moore machine in Figure 6.30 is significantly more complex than the corresponding diagram of the Mealy machine. This is, of course, why we present the design of the Mealy machine for the serial adder to begin with. We leave it as an exercise to complete the design of the Moore FSM.

Pattern Recognizer¶

We receive a periodic binary signal and wish to recognize patterns of two consecutive 1’s. To solve this problem, we follow the FSM design recipe.

At the first glance, the problem description appears to be rather vague. However, step 1 of the recipe gives us a chance to tie up loose ends by defining the inputs and outputs of our pattern recognizer machine. The binary signal constitutes a 1-bit input; call it \(A.\) Since the binary signal is periodic, we assume a clock signal \(\phi\) with the period of input \(A.\) To indicate recognition of two consecutive 1’s in input \(A,\) we attach a 1-bit output, say \(Y,\) to the machine. Our goal is to set output \(Y\) to 1 after recognizing two consecutive 1’s in \(A\) and to 0 otherwise. The block diagram on the right summarizes our findings.

Following step 2 of the design recipe, we model the problem as a state transition diagram. With little information in the problem description to go on, our best bet is to examine the sampling behavior of the input signal with a concrete example. As shown in Figure 6.31, we assume that clock \(\phi\) and input \(A\) have the same period. Furthermore, to facilitate reliable sampling, input signal \(A\) must be stable before and at the positive clock edge. As shown in the waveform diagram, we assume that signal \(A\) changes shortly after the positive clock edge. Thus, \(A\) is stable during most of the clock cycle and, in particular, at the triggering clock edge at the end of the cycle. This timing behavior gives our machine enough slack to compute the next state during the clock cycle, and store the next state at the end of the cycle. Under these assumptions, we count time in the waveform diagram in multiples of clock cycles.

Figure 6.31: Waveform diagram of Moore type pattern recognizer.

To simplify the problem even further, we ignore the details of the timing behavior, and use abstract binary sequences for the input and output signals of the machine. The input sequence in Figure 6.31 is

\[A = \langle 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0 \rangle\,.\]

In the following, we refer to element \(i\) of sequence \(A\) as \(A[i],\) and interpret \(A[i]\) as the Boolean value of input signal \(A\) during cycle \(i.\) For example, \(A[0] = 0\) and \(A[2] = 1.\)

Next, we develop the desired output signal for input sequence \(A.\) Assume output \(Y\) is initially 0, until we have seen the first pair of inputs \(A[0] = 0\) in cycle 0 and \(A[1] = 0\) in cycle 1. Since two consecutive 0’s differ from the 11-pattern we are looking for, we set the output to 0. Since we need to inspect the inputs during cycles 0 and 1, it seems natural to assign 0 to output \(Y\) during cycle 2 after receiving two input bits. Thus, we pursue a timing behavior where the machine inspects the first input bit \(A[t]\) during cycle \(t,\) the second input bit \(A[t+1]\) during cycle \(t+1,\) and asserts the corresponding output \(Y[t+2]\) during cycle \(t+2.\) In Figure 6.31, the first pair of consecutive 1’s is \(A[2]=1\) and \(A[3]=1,\) so that cycle 4 is the first cycle where we set \(Y[4]=1.\) During cycle 5 we set \(Y[5]=0,\) because \(A[3] =1\) and \(A[4]=0.\) The second pair of consecutive 1’s appears in cycles 8 and 9, \(A[8]=1\) and \(A[9]=1.\) Therefore, we set \(Y[10]=1.\) Cycle 9 presents a notable case, because \(A[9]=1\) and \(A[10]=1.\) Hence, we set \(Y[11]=1.\) This case is notable, because input \(A[9]=1\) belongs to two overlapping pairs of 11-patterns. We interpret our problem description to recognize 11-patterns as recognizing every 11-pattern, and include overlapping patterns. As a result our pattern recognizer should produce the output sequence

\[Y = \langle 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0 \rangle\]

for input sequence \(A.\)

The sequence abstraction is crucial for the design of a finite state machine. First, however, we have to decide on the type of the machine, Mealy or Moore machine. Our earlier decision to assign the output during the cycle after inspecting two consecutive input bits implies a Moore machine. The waveform diagram in Figure 6.31 clarifies this implication. Consider cycle 4, where output \(Y[4]=1\) in response to recognizing 11-pattern \(A[2] = A[3] = 1.\) Output \(Y\) should be independent of input \(A,\) or \(Y\) might switch to 0 during cycle 4 when \(A\) switches from 1 to 0. In a Moore machine, output \(Y\) is independent of the input and, therefore, switches at the triggering clock edges only, as indicated by the arrows in Figure 6.31.

We are ready to design the state transition diagram for a Moore type pattern recognizer. Since the number of required states is not immediately obvious, we develop the states incrementally. We begin with start state S0, where we wait for the first 1 to appear in input \(A.\) When the first 1 occurs, we transition to a new state S1. Otherwise, we stay in state S0 and output \(Y=0.\) Figure 6.32(a) shows start state S0 and its two outgoing transitions. Next, consider state S1. We transition into S1 after observing one 1 on input \(A.\) Since we have not observed two 1’s, we output \(Y=0.\) If we observe input 0 while in S1, we return to S0, and wait for the next 1 to appear. Otherwise, if we observe input 1, we transition to new state S2, see Figure 6.32(b). In state S2, we have received two consecutive 1’s in the two preceding cycles. Therefore, we output \(Y=1.\) The transitions out of state S2 are shown in Figure 6.32(c). If we observe input 1, we encounter the case of overlapping 11-patterns. We remain in state S2 and output \(Y=1.\) Otherwise, if input \(A=0,\) we return to state S0 and wait for the next 1 to appear in the input. This completes the state transition diagram.

Figure 6.32: Design of state transition diagram for Moore type pattern recognizer.

We continue with step 3 of the design recipe, and select a state encoding. The Moore machine in Figure 6.32(c) has three states. Thus, we need at least \(\lceil \lg 3\rceil = 2\) bits to encode three states. We choose a binary encoding of the state number:

state	binary encoding
S0	00
S1	01
S2	10

The binary encoding seems natural, but is not necessarily the best choice. Other choices may reduce the cost of the next state and output logic. However, the binary state representation minimizes the width of the state register. For our Moore machine, we need a 2-bit state register with binary state \(S = S_1 S_0.\)

Given the state encoding, we can develop the state transition table according to step 4 of the design recipe. The table defines the state \(S' = S_1' S_0'\) as a function of the current state \(S = S_1 S_0\) and input \(A.\) For clarity, we also include columns for the corresponding state names used in the state transition diagram of Figure 6.32(c).

\(S\)	\(S_1\)	\(S_0\)	\(A\)	\(S'\)	\(S_1'\)	\(S_0'\)
S0	0	0	0	S0	0	0
S0	0	0	1	S1	0	1
S1	0	1	0	S0	0	0
S1	0	1	1	S2	1	0
S2	1	0	0	S0	0	0
S2	1	0	1	S2	1	0

The state transition table is a truth table that specifies the combinational next state logic. More succinctly, the next state logic is a multioutput function \(S' = \sigma(S, A)\) where \(S_1'\) and \(S_0'\) are Boolean functions in three variables, \(S_1,\) \(S_0,\) and \(A.\)

Furthermore, we compile a truth table for the output logic. Output \(Y\) of the Moore machine is a function of the current state \(S = S_1 S_0.\) The state transition diagram in Figure 6.32(c), specifies in each state vertex the associated output, which we summarize in a separate truth table.

\(S\)	\(S_1\)	\(S_0\)	\(Y\)
S0	0	0	0
S1	0	1	0
S2	1	0	1

Following step 5 of the design recipe, we minimize the next state and output logic. We use K-maps for the incompletely specified functions

to derive the minimal SOP expressions

\[\begin{eqnarray*} S_1' &=& A S_0 + A S_1 \\ S_0' &=& A\,\overline{S}_0\,\overline{S}_1 \\ Y &=& S_1\,. \end{eqnarray*}\]

Last but not least, we obtain the circuit diagram in Figure 6.33, which realizes step 6 of the design recipe. The output logic is the trivial identity function. To enter start state S0, we assume that the register has a separate reset input that enables us to reset all D-flipflops.

Figure 6.33: Pattern recognizer as Moore machine.

Now that we have a complete design for the pattern recognizer as a Moore machine, we amortize our intellectual investment by designing a Mealy machine for direct comparison. We restart the design process at step 2 of the recipe. Figure 6.34 shows the waveform diagram with the same input signal as in Figure 6.31, assuming that output \(Y\) depends not only on the state but also on input \(A.\) We exploit the combinational dependence on input \(A\) to redefine the timing behavior of output \(Y,\) such that \(Y=1\) during the clock cycle when the second 1 appears on input \(A.\) More precisely, if \(A[t] = 1\) during cycle \(t\) and \(A[t+1] = 1\) during cycle \(t+1,\) then we can set \(Y[t+1]=1\) in a Mealy machine, which is one cycle earlier than in the Moore machine.

Figure 6.34: Waveform diagram of Mealy type pattern recognizer.

Consider the first occurance of two consecutive 1’s in cycles 2 and 3. The Mealy machine sets output \(Y\) to 1 during cycle 3 already. Note that output \(Y\) will remain 1 at the beginning of cycle 4 until \(A\) changes from 1 to 0. Indeed, the timing behavior of output \(Y\) of the Mealy machine is not as clean as that of the Moore machine. The output may even exhibit glitches as at the beginning of cycle 6. However, if we sample output \(Y\) toward the end of the cycle, then the behavior is as expected: we observe \(Y=1\) at the positive clock edges at the end of cycle 3, cycle 9, and cycle 10.

The state transition diagram of the Mealy machine requires only two states. State S0 is the start state, which waits for the first 1 to appear on input \(A.\) When \(A=1,\) we transition to state S1, and output \(Y=0.\) If \(A=1\) in state S1, the 1 input must have been preceded by another 1, so we output \(Y=1\) and remain in state S1. If input \(A = 0\) in state S0 or S1, the machine outputs \(Y=0\) and transitions to next state S0. The Mealy machine saves one state compared to the Moore machine.

Figure 6.35: State transition diagram for Mealy type pattern recognizer.

The remaining steps of the design recipe involve straightforward design work. Since the Mealy machine has two states, we need a 1-bit register to store \(S=0\) representing state S0 and \(S=1\) for state S1. We translate the state transition diagram in Figure 6.35 into the combined truth table for the next state logic and output logic:

\(S\)	\(A\)	\(S'\)	\(Y\)
0	0	0	0
0	1	1	0
1	0	0	0
1	1	1	1

We can spot the minimal Boolean expressions in the truth table without the aid of K-maps: next state \(S' = A\) and output \(Y = A \cdot S.\) The resulting circuit diagram of the Mealy machine is shown in Figure 6.36. The machine is a degenerate Mealy machine without a feedback loop.

Figure 6.36: Pattern recognizer as Mealy machine.

Comparison with the Moore machine in Figure 6.33 shows that the Mealy machine needs one D-flipflop rather than two and only one gate rather than four. These hardware savings come at the expense of a noisy timing behavior. If the clean timing behavior of the Moore machine output is desired, we can have it albeit at increased hardware cost.

Traffic Light¶

Perhaps the seminal application of finite state machines is the traffic light controller. The animation in Figure 6.37 shows the baroque Austrian style, which ends the green phase in a flashy trill.

  Figure 6.37: Austrian traffic light animation.

Designing a controller FSM for the traffic light requires determining a suitable clock period. A simple, natural choice is the shortest duration that any light is switched on or off. Assume that the blinking green light at the end of the green phase determines the clock period \(T,\) and all other phases last a multiple of \(T\):

phase	duration
red	\(13\,T\)
red-yellow	\(4\,T\)
green	\(5\,T\)
green blinking	\(1\,T \times 4\)
yellow	\(4\,T\)

Given this problem description, we design an Austrian traffic light controller follwing the FSM recipe. First, step 1, we define the inputs and outputs. Other than the clock signal, our rudimentary controller receives no data inputs. Standard traffic lights consist of three colored lights, red, yellow, and green. The controller switches each of the three lights on or off. Therefore, we attach three 1-bit outputs, \(R,\) \(Y,\) and \(G.\) If the output is 1, the associated light shall be switched on and otherwise off.

Next, step 2, we design a state transition diagram. Since the controller has no input signals, we do not have a choice but construct a Moore machine. We introduce one state per clock cycle, for a total of 34 states. The green blinking phase consists of four times two cycles, one cycle green off plus one cycle green on. Figure 6.38 shows the Moore type state transition diagram. If an output equals 1, we include the associated output letter in the state vertex. Absence of the output letter means the output shall be 0.

Figure 6.38: State transition diagram for traffic light controller.

To encode 34 states, step 3, we need \(\lceil \lg 34\rceil = 6\) bits if we use a binary state encoding \(S = S_5 S_4 S_3 S_2 S_1 S_0.\) The number of states is large enough to get us into trouble with the minimization of the next state and output logic. K-maps for six variables do exist, but algorithmic minimization methods may be preferable in this case. Rather than following the FSM recipe, we develop a more creative solution to turn the state transition diagram into a synchronous circuit. We note that the state sequence equals that of a binary counter modulo 34. Thus, rather than deriving minimal expressions for each of the six next state functions, we extend the binary counter in Figure 6.11 to generate the desired state sequence. We transition from state S33 to S0 by asserting the reset signal if the current state is equal to \(33_{10} = 100001_2,\) or in terms of Boolean algebra:

\[\mathit{reset} = S_5 \overline{S}_4 \overline{S}_3 \overline{S}_2 \overline{S}_1 S_0\,.\]

Minimizing the output functions individually, we find the SOP expressions as functions of the current state:

\[\begin{eqnarray*} R &=& \overline{S}_5 \overline{S}_4 + S_4 \overline{S}_3 \overline{S}_2 \overline{S}_1 \overline{S}_0 \\ Y &=& S_5 + S_3 S_2 S_1 + \overline{S}_4 S_3 S_2 S_0 + S_4 \overline{S}_3 \overline{S}_2 \overline{S}_1 \overline{S}_0 \\ G &=& S_4 \overline{S}_2 S_0 + S_4 \overline{S}_3 S_0 + S_4 S_2 \overline{S}_1 S_0 + S_4 \overline{S}_3 \overline{S}_2 S_1 + S_4 \overline{S}_3 S_2 \overline{S}_1\,. \end{eqnarray*}\]

The resulting circuit diagram of the traffic controller is shown in Figure 6.39, with the output logic hidden in a black box,

Figure 6.39: Circuit diagram of traffic light controller.

This example illustrates the design problem with monolithic finite state machines. If the number of states becomes too large, steps 4-6 of the FSM design recipe become unmanageable. At this point, we may compose the machine out of smaller machines. We discuss the composition of FSMs as an alternative design methodology below.

---

6.3

A divide-by-2 frequency divider asserts output \(Y\) for one clock cycle out of 2:

1. Design a synchronous divide-by-2 frequency divider.
2. Verify your circuit by deriving its state transition diagram.

1. The waveform of the divide-by-2 frequency divider suggests that output \(Y\) toggles between 0 and 1 at every positive clock edge. Thus, we may use a register to store present state \(Q,\) and use an inverter to toggle next state \(Q' = \overline{Q}.\) The sequential circuit below connects output \(Y\) to the output of the inverter, so that \(Y = Q'.\)

   

   The problem is simple enough to ignore the FSM recipe and derive the frequency divider machine in an ad hoc fashion.

2. We analyze our machine design by deriving its state transition diagram. Since the state register stores one of two states \(Q \in \{ 0, 1\},\) the transition diagram has two vertices. The machine has no inputs other than clock signal \(\phi.\) Instead, whenever the machine is in state \(Q = 0\) it transitions to state \(Q = 1\) and vice versa. Therefore, we annotate the arcs with the corresponding output \(Y=Q'\) only.

   

   The state transition diagram enables us to grasp the behavior of the frequency divider easily. The machine toggles between states 0 and 1, and outputs 1 in state 0 and 0 in state 1. This is the expected behavior given the waveform above. In fact, we could have connected output \(Y\) to the output of the register rather than the output of the inverter, so that \(Y = Q.\) The behavior observed at output \(Y\) would be the same as for \(Y=Q',\) if we ignore the startup behavior of the machine. The only change in the state transition diagram would be complementing the outputs annotated at the arcs.

Solution

6.4

A divide-by-3 frequency divider asserts output \(Y\) for one clock cycle out of 3.

Design a state machine for the frequency divider following the FSM recipe:

1. Identify inputs and outputs.
2. Design a state transition diagram.
3. Select a state encoding.
4. Derive the state transition table.
5. Minimize the next state and output logic.
6. Synthesize the circuit, and determine the cost of the logic.

1. Given the waveform diagram, the frequency divider needs no input other than clock signal \(\phi,\) and one output signal \(Y.\)

2. The creative part of the design process consists of identifying the states for the state transition diagram. The divide-by-3 frequency divider exhibits periodic behavior with a period of 3 clock cycles. We set output \(Y=1\) during one of the 3 cycles and \(Y=0\) during the other two cycles of one period. Therefore, we introduce three states, \(S0,\) \(S1,\) and \(S2,\) corresponding to each of the three clock cycles:

   

   We choose state \(S0\) to set output \(Y=1.\) This decision is arbitrary in the sense that the observer of output \(Y\) cannot distinguish the particular choice of the state unless the startup behavior of the machine is relevant. The states transition at every positive clock edge, so that each state is visited for exactly one clock cycle, and the output transitions accordingly. Since we associate an output with each state, our state transition diagram models a Moore machine.

3. To encode 3 states we need at least \(\lceil \lg 3\rceil = 2\) bits. We choose the natural binary encoding where \(S = S_1 S_0\) is an unsigned binary number:

   state	\(S_1\)	\(S_0\)
   \(S0\)	0	0
   \(S1\)	0	1
   \(S2\)	1	0

4. Given the state encoding, we derive the state transition table by transliterating the state transition diagram. For each current state \(S,\) we include the next state \(S'\) and output \(Y\):

   \(S_1\)	\(S_0\)	\(S'_1\)	\(S'_0\)	\(Y\)
   0	0	0	1	1
   0	1	1	0	0
   1	0	0	0	0

   This table specifies next state functions \(S'_1(S_1, S_0)\) and \(S'_0(S_1, S_0)\) and output function \(Y(S_1,S_0).\) These functions are incompletely specified, because the state transition table omits state \(S = 11_2.\)

5. We minimize the next state and output logic using K-map minimization for incompletely specified functions:

   

   We find minimal covers \(S'_1 = S_0,\) \(S'_0 = \overline{S}_1\,\overline{S}_0,\) and \(Y = \overline{S}_1\,\overline{S}_0.\) Note that \(Y = S'_0,\) which is obvious because the columns in the state transition table are identical. Thus, we could have saved the minimization of \(Y.\)

6. We synthesize the frequency divider circuit at the gate level. The schematic includes a 2-bit state register, and the minimized next state logic and output logic using NOR technology:

   

   The cost of the combinational logic of the frequency divider is the cost of two 2-input NOR gates for a total of \(\mathcal{C} = 4.\) The cost of the machine is the cost of the logic plus two 1-bit registers.

Solution

6.5

Redesign the divide-by-3 frequency divider of Exercise 6.4 with a one-hot state encoding.

Follow the FSM recipe:

1. Identify inputs and outputs.
2. Design a state transition diagram.
3. Use a one-hot state encoding.
4. Derive the state transition table.
5. Minimize the next state and output logic.
6. Synthesize the circuit, and determine the cost of the logic.

We redesign the divide-by-3 frequency divider of Exercise 6.4. This exercise requests a one-hot state encoding. Steps (1) and (2) of the FSM recipe remain unaffected by the state encoding. Therefore, we reuse the state transition diagram of step (2) in Exercise 6.4, and continue with step (3) of the FSM recipe.

3. A one-hot encoding of three states \(S0,\) \(S1,\) and \(S2,\) sets one bit out of three to 1. Therefore, our one-hot code words consist of three bits, \(S = S_2 S_1 S_0,\) such that:

   state	\(S_2\)	\(S_1\)	\(S_0\)
   S0	0	0	1
   S1	0	1	0
   S2	1	0	0

4. Given the one-hot state encoding, we derive the state transition table by transliterating the state transition diagram of Exercise 6.4 into a truth table:

   \(S_2\)	\(S_1\)	\(S_0\)	\(S'_2\)	\(S'_1\)	\(S'_0\)	\(Y\)
   0	0	1	0	1	0	1
   0	1	0	1	0	0	0
   1	0	0	0	0	1	0

5. The state transition table specifies four incomplete Boolean functions in three variables. We minimize these functions using K-map minimization:

   

   We find the minimal covers \(S'_2 = S_1,\) \(S'_1 = S_0,\) \(S'_0 = S_2,\) and \(Y = S_0 (= S'_1).\)

6. The synthesized circuit requires a 3-bit register and no logic gates:

   

   The cost of the combinational logic is \(\mathcal{C} = 0.\) Compared to the binary encoding in Exercise 6.4, the one-hot encoding saves the logic cost entirely at the expense of one additional 1-bit register. Note that the one-hot frequency divider is a cyclically wired shift register.

Solution

6.6

Given a bit-serial input stream, design an odd parity checker that asserts its output when the input stream contains an odd number of 1’s.

Follow the FSM recipe:

1. Identify inputs and outputs.
2. Design a state transition diagram.
3. Select a state encoding.
4. Derive the state transition table.
5. Minimize the next state and output logic.
6. Synthesize the circuit.

1. The black-box diagram of the parity checker shows one input \(A\) and one output \(Y.\) We assume that the clock signal is supplied implicitly.

2. We design a state transition diagram for the odd parity checker with bit-serial input \(A\) and output \(Y.\) The specification requires that output \(Y\) is 1 when the number of 1’s in the input stream is odd. Before formalizing the specification, we clarify several details. To observe the number of 1’s in the input bit stream, we need to specify the start of the observation. Thus, we introduce clock cycle \(t,\) and let \(t = 0\) be the start cycle. Assuming our machine inspects input \(A[t-1]\) during cycle \(t-1,\) we set \(Y[t] = 1\) if the number of 1’s in sequence \(A[0{:}t-1] = \langle A[0], A[1], \ldots, A[t-1]\rangle\) is odd. A time table illustrates our design:

   t	0	1	2	3	4	5	6	7	8	9
   A	0	1	0	1	1	1	1	0	0	0
   Y	0	0	1	1	0	1	0	1	1	1

   During start cycle \(t=0,\) we set output \(Y=0\) indicating that no 1’s have been detected before the start cycle. Note that zero is an even number. The machine inspects input \(A[0] = 0,\) and computes the next output \(Y[1]=0,\) because the number of 1’s in sequence \(A[0{:}0] = A[0]\) is zero. During cycle \(t=1,\) the machine outputs \(Y[1]=0,\) and inspects input \(A[1]=1.\) Since the number of 1’s in sequence \(A[0{:}1] = \langle 0, 1\rangle\) is 1, i.e. an odd number, the next output is \(Y[2]=1.\) The remaining entries in the time table are derived analogously.

   Next, we formalize our parity checker by designing the state transition diagram. The machine has two states \(Q \in \{ \text{even}, \text{odd}\}\) indicating whether the current number of 1’s in input sequence \(A\) is even or odd. If current state \(Q\) is even and input \(A=0,\) we remain in state even. Otherwise, if \(A=1,\) we transition into next state \(Q' = \text{odd.}\) If current state \(Q = \text{odd}\) and input \(A=0,\) we remain in state odd, and if \(A=1,\) we transition into next state even. The state transition diagram below captures these arguments in form of a graph:

   

   We associate output \(Y\) with the states, keeping in mind that the state during clock cycle \(t\) and associated output \(Y[t]\) reflect the parity of the number of 1’s in input sequence \(A[0,t-1].\) Thus, our design is a Moore machine. We handle the remaining steps of the FSM recipe in a systematic fashion.

3. The state transition diagram suggests the state encoding:

   state	\(S\)
   even	0
   odd	1

   This encoding is convenient, and likely to produce a low-cost circuit, because output \(Y=S.\)

4. The state transition table specifies next state \(S'\) and output \(Y\) as functions of current state \(S\) and input \(A.\) We generate the table by straightforward transliteration of the state transition diagram and the chosen state encoding:

   \(S\)	\(A\)	\(S'\)	\(Y\)
   0	0	0	0
   0	1	1	0
   1	0	1	1
   1	1	0	1

5. We recognize Boolean functions \(S'\) and \(Y\) in the state transition table as \(S' = A \oplus S\) and \(Y = S.\)

6. The synthesized gate-level circuit for the odd parity checker is:

   

   Note that output \(Y\) is not a function of input \(A\) but is a function of state \(S\) only. Thus, our parity checker is a Moore machine, indeed.

Solution

6.7

Consider a pattern recognizer for bit pattern 011.

1. Design the state transition diagram of a Mealy machine.
2. Design the state transition diagram of a Moore machine.

A pattern recognizer has input \(A\) and output \(Y.\) We set output \(Y = 1\) for one clock cycle if pattern 011 appears on input \(A.\)

1. A Mealy machine can respond to changes at its inputs within the current clock cycle, because the output is a function of the current state and the inputs. Therefore, we design the state transition diagram such that output \(Y\) is associated with the transition arcs. First, we study a concrete input sequence by means of a time table, however:

   t	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
   A	0	0	1	0	1	1	0	1	1	1	1	0	1	1	0	0
   Y	0	0	0	0	0	1	0	0	1	0	0	0	0	1	0	0

   Observe that pattern 011 appears at input sequence \(A\) during cycle interval \(3 \le t \le 5,\) interval \(6 \le t \le 8,\) and \(11 \le t \le 13.\) In a Mealy machine, we set output \(Y = 1\) during the cycle when the last 1 of the pattern appears, i.e. during cycles 5, 8, and 13. During all other cycles, we set output \(Y=0,\) as shown in the time table.

   A Mealy machine needs three states to recognize pattern 011. State \(S0\) is the start state, were the machine waits until the first 0 appears at input \(A.\) Then, the machine transitions into state \(S1.\) If input \(A=1\) in state \(S1,\) the machine transitions into state \(S2.\) If input \(A=1\) in state \(S2,\) the machine recognizes pattern 011, and transitions back to start state \(S0.\) We include arcs from \(S0\) to \(S1\) for \(A/Y = 0/0,\) from \(S1\) to \(S2\) for \(A/Y = 1/0,\) and from \(S2\) to \(S0\) for \(A/Y = 1/1.\)

   

   To complete the state transition diagram, we observe that each state must have two outgoing arcs, one for input \(A=0,\) and the other for \(A=1.\) Thus, we inspect each state and attach the outgoing arcs not discussed above. We need an arc from state \(S0\) to itself for \(A/Y = 1/0,\) because we wait in \(S0\) while input \(A=1\) until the first 0 appears. State \(S1\) waits until a 1 appears at the input. Thus, we need an arc from state \(S1\) to itself for \(A/Y = 0/0.\) If input \(A=0\) in state \(S2,\) the input pattern is 010, which differs from pattern 011. The last 0 may be the first 0 of pattern 011, however. Therefore, we need an arc from state \(S2\) to state \(S1\) for \(A/Y = 0/0.\)

2. A Moore machine computes its output as a function of the current state only. Therefore, a Moore machine responds to an input in the next clock cycle at earliest. The state transition diagram of a Moore machine associates the output with the state vertices. Before, designing the state transition diagram, we revisit the concrete example of subproblem (a), with output \(Y\) specified as expected for a Moore machine:

   t	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
   A	0	0	1	0	1	1	0	1	1	1	1	0	1	1	0	0
   Y	0	0	0	0	0	0	1	0	0	1	0	0	0	0	1	0

   Compared to the Mealy machine, we set output \(Y=1\) during the clock cycle after receiving the third bit of pattern 011, i.e. during clock cycles 6, 9, and 14. The Moore machine needs four states to recognize pattern 011. State \(S0\) is the start state. If input \(A=0,\) the machine transitions to state \(S1,\) from there to state \(S2\) if \(A=1,\) and to state \(S3\) if \(A=1\) again. In state \(S3,\) the machine signals that it recognizes pattern 011 by setting output \(Y=1.\) In the other states, output \(Y=0.\)

   

   We complete the state diagram by visiting each state, and attaching the missing outgoing arcs. Since the machine has one input, each state vertex must have two outgoing arcs one for input \(A=0\) and the other for \(A=1,\) as in the Mealy machine. If input \(A=1\) in start state \(S0,\) we wait for the first 0. Thus, we need an arc from \(S0\) to itself for \(A=1.\) In state \(S1,\) we wait for one or more 0’s in the input. Thus, for input \(A=0\) we need an arc from \(S1\) to itself. In state \(S2,\) we have seen pattern prefix 01. If the input is \(A=0,\) this 0 may be the first 0 of pattern 011. Therefore, we include an arc from \(S2\) to \(S1\) for \(A=0.\) In state \(S3,\) we recognize pattern 011. If input \(A=0,\) this 0 may be the first 0 of pattern 011, and we include an arc from \(S3\) to \(S1.\) On the other hand, input \(A=1\) does not start pattern 011, and we include an arc to start state \(S0\) to wait for the next 0 again.

   We conclude that the Moore machine requires one more state than the Mealy machine and the output responds one clock cycle later. We note that the synthesized circuit for the Moore machine is often more costly than the Mealy machine. In contrast the timing behavior of output \(Y\) of the Moore machine is less sensitive to the timing behavior of input \(A\) than the Mealy machine.

Solution

6.4.1. Primitive State Machines¶

We introduce several primitive state machines that serve as building blocks for larger state machines. We assume that all primitive state machines have a clock input and a reset input, without drawing them explicitly in our circuit diagrams. All clock inputs shall be driven by the same clock signal \(\phi\) so that the resulting state machine is a synchronous circuit. Similarly, all reset inputs shall be driven by the same reset signal, used to reset all D-flipflops to 0, for example to guarantee a well-defined start state.

Delay Element¶

The simplest primitive state machine is the delay element, which resembles a 1-bit shift register. The symbol of the delay element on the left in Figure 6.40 omits the clock and reset inputs by convention. The implementation of the delay element consists of a single D-flipflop. We assume that the triggering clock edge is the positive clock edge. Furthermore, we assume a resettable D-flipflop with a synchronous reset input. If the reset input is 1 at the triggering clock edge the D-flipflop stores a 0. Otherwise, if the reset input is 0, it stores the signal at input \(D.\)

Figure 6.40: Symbol of delay element (left) and implementation as Moore machine (right).

The delay element constitutes a degenerate Moore machine without a feedback loop. Both the next state logic \(\sigma(I) = I\) and the output logic \(\omega(S) = S\) implement identity functions, so that \(S' = I\) and \(O = S.\) We describe the time dependent behavior of the delay element abstractly as a function of clock cycle \(t,\) where \(t\) is a nonnegative integer. We use brackets, such as \(O[t],\) to refer to signal \(O\) in clock cycle \(t.\) With this notation, we model the behavior of the delay element for \(t \ge 0\) as

\[\begin{split}O[t] = \begin{cases} I[t-1]\,, & \text{if}\ t > 0\,, \\ 0\,, & \text{if}\, t = 0\,. \end{cases}\end{split}\]

We assume that the reset signal is asserted before the beginning of time to enforce initial state \(O[0] = 0.\) Thereafter, in cycle \(t\) the delay element outputs the input of previous cycle \(t-1.\) If the input signal consists of sequence

\[I = \langle x_0, x_1, x_2, x_3, \ldots \rangle\,,\]

then the output produces the same sequence with a delay of one cycle, with an initial value of \(O[0] = 0\):

\[O = \langle 0, x_0, x_1, x_2, \ldots \rangle\,.\]

Cycle \(t\) serves as selector of the \(t^{th}\) element of a sequence, starting with \(t=0.\) For example, during cycle \(t=2\,\) we find \(I[2] = x_2\) and \(O[2] = x_1.\) Since \(x_1 = I[1],\) we have \(O[2] = I[1]\) as expected from expression \(O[t] = I[t-1].\)

As a concrete example, consider binary input sequence \(I = \langle 1, 1, 0, 1, 0, 0, 1\rangle.\) The delay element transduces input sequence \(I\) into output sequence \(O.\) We illustrate the sequences in a time table with one column per cycle:

cycle	0	1	2	3	4	5	6
I	1	1	0	1	0	0	1
O	0	1	1	0	1	0	0

The time table serves as an abstract version of a waveform diagram. By default, we assume that the delay element stores 0 initially, so that in cycle 0, \(O[0] = 0.\) Then, in cycle 1, we have \(O[1] = I[0] = 1,\) and so on.

Accumulator State Machine¶

A \(n\)-bit accumulator state machine outputs the sum of its inputs modulo \(2^n.\) We may design Mealy type and Moore type accumulators, as shown in Figure 6.41. The output of the Moore machine is delayed by one cycle compared to the Mealy machine. All buses comprise \(n\) signals, except the clock and reset signals.

Figure 6.41: Accumulator as Mealy machine (left) and Moore machine (right).

The Mealy machine computes next state \(S' = (S + I) \bmod 2^n\) and output \(O = (S + I) \bmod 2^n = S'.\) Thus, we may save one adder by rearranging the feedback loop analgous to the multiplexer loop in Figure 6.25. Assuming that the machine is reset to start state \(S[0] = 0,\) the time dependent output of the Mealy accumulator is

\[\begin{split}O[t] = \begin{cases} \Bigl(\sum_{\tau = 0}^t I[\tau]\Bigr) \bmod 2^n\,, & \text{if}\ t > 0\,, \\ I[0]\,, & \text{if}\, t = 0\,. \end{cases}\end{split}\]

The Moore machine computes the same next state \(S' = (S + I) \bmod 2^n\) as the Mealy machine, but outputs the current state \(O = S.\) With start state \(S[0] = 0,\) the output of the Moore accumulator is

\[\begin{split}O[t] = \begin{cases} \Bigl(\sum_{\tau = 0}^{t-1} I[\tau]\Bigr) \bmod 2^n\,, & \text{if}\ t > 0\,, \\ 0\,, & \text{if}\, t = 0\,. \end{cases}\end{split}\]

The difference between the two machine types becomes clear by considering a concrete example. Assume we apply input sequence

\[I = \langle x_0, x_1, x_2, x_3, \ldots \rangle\]

to both machines with bit width \(n\) large enough for the sums not to overflow. Then, the Mealy accumulator produces output sequence

\[O = \langle x_0, x_0 + x_1, x_0 + x_1 + x_2, x_0 + x_1 + x_2 + x_3, \ldots \rangle\]

whereas the Moore accumulator has output sequence

\[O = \langle 0, x_0, x_0 + x_1, x_0 + x_1 + x_2, \ldots \rangle\,.\]

Thus, except that the output of the Moore machine is delayed by one clock cycle compared to the Mealy machine, both accumulators compute a prefix sum serially. The time table illustrates the accumulation of an input sequence of 4-bit unsigned binary numbers with a Moore accumulator:

cycle	0	1	2	3	4	5	6
I	9	3	11	6	1	0	8
O	0	9	12	7	13	14	14

The output sequence is easy to verify, if we notice that a 4-bit Moore accumulator has output function \(O[t] = (O[t-1] + I[t-1]) \bmod 16\) with start value \(O[0] = 0.\)

For bit width \(n = 1,\) the arithmetic adder reduces to a logical 2-input XOR gate, and the accumulator computes a prefix XOR function. The time table illustrates a Moore version of the prefix XOR transduction:

cycle	0	1	2	3	4	5	6
I	1	1	0	1	0	0	1
O	0	1	0	0	1	1	1

Element \(O[t]\) of the output sequence obeys the Boolean equation \(O[t] = O[t-1] \oplus I[t-1]\) with start value \(O[0] = 0.\)

Average State Machine¶

An averaging machine computes the arithmetic average of a window of \(k\) inputs. For example, given a window size of \(k = 3,\) the average of three consecutive inputs \(I[t],\) \(I[t-1],\) and \(I[t-2]\) is

\[avg_3(t) = \frac{I[t] + I[t-1] + I[t-2]}{3}\,.\]

The group of inputs \(I[t],\) \(I[t-1],\) and \(I[t-2]\) constitute a window that slides across the input sequence as time progresses. Figure 6.42 illustrates the window in cycles \(t=3\) and \(t=4.\)

Figure 6.42: Sliding window of size \(k = 3.\)

A machine that outputs \(avg_3(t)\) during cycle \(t,\) such that \(O[t] = avg_3(t),\) must be a Mealy machine with output function

\[\begin{split}O[t] = \begin{cases} (I[t] + I[t-1] + I[t-2]) / 3\,, & \text{if}\ t > 1\,, \\ (I[1] + I[0]) / 3\,, & \text{if}\ t = 1\,, \\ I[0] / 3\,, & \text{if}\ t = 0\,. \\ \end{cases}\end{split}\]

Figure 6.43 shows the corresponding Mealy version of the average machine. The next states are \(S_1' = I\) and \(S_2' = S_1,\) and output \(O = (I + S_1 + S_2)/3.\) We assume the divider implements an integer division by 3 for binary numbers. Furthermore, the machine shall be reset to start state \(S_1[0] = 0\) and \(S_2[0] = 0.\)

Figure 6.43: \(n\)-bit average state machine of Mealy type with window size 3.

The time table shows the averages of signed binary numbers in decimal format, assuming \(n\) is large enough to prevent overflows in the combinational arithmetic units:

cycle	0	1	2	3	4	5	6
I	10	2	-3	-8	5	12	4
O	3	4	3	-3	-2	3	7

By inserting another D-flipflop at input \(I\) in Figure 6.43, we transform the Mealy average machine into a Moore average machine, with output function

\[\begin{split}O[t] = \begin{cases} (I[t-1] + I[t-2] + I[t-3]) / 3\,, & \text{if}\ t > 2\,, \\ (I[1] + I[0]) / 3\,, & \text{if}\ t = 2\,, \\ I[0] / 3\,, & \text{if}\ t = 1\,, \\ 0\,, & \text{if}\ t = 0\,. \\ \end{cases}\end{split}\]

Average machines with various window sizes serve as low-pass filters in digital signal processing applications.

6.4.2. Series Composition¶

We compose two state machines in series just like we compose two resistors, two capacitors, or two switches in series. Given two state machines \(M_1: I_1 \rightarrow O_1\) and \(M_2: I_2 \rightarrow O_2,\) such that output \(O_1\) of \(M_1\) and input \(I_2\) of \(M_2\) have the same bit width. Then, the series composition has input \(I = I_1,\) output \(O = O_2,\) and connects output \(O_1\) to input \(I_2,\) enforcing \(I_2 = O_1.\)

Figure 6.44: Series composition of state machines \(M_1\) and \(M_2.\)

As an example, consider the series composition of two delay elements. We wish to characterize the behavior of the series composition by expressing output \(O\) as a time dependent function of input \(I.\) In cycle \(t,\) the output of delay element \(M_1\) is \(O_1[t] = I_1[t-1] = I[t-1],\) and for delay element \(M_2,\) we have \(O[t] = O_2[t] = I_2[t-1].\) The series composition enforces \(I_2[t-1] = O_1[t-1].\) Therefore, we find \(O[t] = I[t-2]\) since \(O_1[t-1] = I[t-2].\) Next, we determine the start behavior. In cycle 0, each delay machine outputs \(O_1[0] = O_2[0] = 0.\) Therefore, in cycle 0 output \(O[0] = 0,\) and in cycle 1 \(M_2\) outputs the start value of \(M_1,\) i.e. \(O[1] = O_1[0] = 0.\) In summary, the time dependent output function of the series composition of two delay elements is

The time table illustrates the transduction of input sequence \(I\) by the series composition of two delay elements into output sequence \(O.\)

cycle	0	1	2	3	4	5	6
\(I = I_1\)	1	1	0	1	0	0	1
\(O_1 = I_2\)	0	1	1	0	1	0	0
\(O = O_2\)	0	0	1	1	0	1	0

This time table assumes that the connecting wire \(O_1 = I_2\) is visible. However, for a specification of the functional behavior of the series composition as a whole, the sequence on the internal node is irrelevant.

6.4.3. Parallel Composition¶

The parallel composition of two state machines \(M_1: I_1 \rightarrow O_1\) and \(M_2: I_2 \rightarrow O_2\) instantiates \(M_1\) and \(M_2\) and arranges the inputs and outputs side by side such that the combined machine maps \(I_1 \times I_2 \rightarrow O_1 \times O_2.\) Parallel composition is the easiest composition we can accomplish in hardware. We impose no constraints on machines \(M_1\) and \(M_2\) other than synchronizing them with the same clock and reset signals.

Figure 6.45: Parallel composition of state machines \(M_1\) and \(M_2.\)

As an example, consider the parallel composition of two delay elements in Figure 6.46. Interpret the inputs as a 2-bit bus and the outputs as a 2-bit bus, and the parallel composition is a delay element for a 2-bit bus. This construction extends directly to \(n\) parallel delay elements for \(n\)-bit buses.

Figure 6.46: Parallel composition of two delay elements (left) and symbol for \(n\) parallel delay elements (right).

If we use the \(n\)-bit buses on the right of Figure 6.46 to carry signals that we interpret as unsigned binary numbers, then we have a delay element for numbers. The time table illustrates the behavior with unsigned binary numbers shown in decimal format:

cycle	0	1	2	3	4	5	6
I	42	7	1	36	15	2	29
O	0	42	7	1	36	15	2

Figure 6.47 shows a composite state machine with a parallel composition of a series composition of two delay elements and a single delay element. The counter drives both inputs of a parallel composition. A combinational adder combines the outputs of the parallel composition. The composite machine has no input and \(n\)-bit output \(O.\)

Figure 6.47: Composite state machine including a parallel composition with connected inputs and a combinational adder.

We analyze the time dependent behavior of the machine starting at output \(O,\) and working ourselves toward the counter. We find that output \(O\) combines the outputs of the parallel composition, \(O_1\) and \(O_2,\) by means of an arithmetic addition. As for every combinational module, we assume that the output of the adder appears within the same cycle \(t\) as the inputs:

Next, we determine the outputs of the parallel composition. Output \(O_1\) is the output of the series compositon of two delay elements, which transduces input \(I_1\) such that

Output \(O_2\) delays input \(I_2\) by one clock cycle:

Both inputs of the parallel composition are driven by the \(n\)-bit counter. Assuming that the counter is a Moore machine, we have

Substituting the signals in the equation for output \(O[t],\) we obtain

We analyze the start behavior of the composite machine by means of a time table, assuming bit width \(n\) is large enough, so that we can ignore the modulo operations.

cycle	0	1	2	3	4	5	6	7	8	9
\(I_1 = I_2\)	0	1	2	3	4	5	6	7	8	9
\(O_1\)	0	0	0	1	2	3	4	5	6	7
\(O_2\)	0	0	1	2	3	4	5	6	7	8
\(O\)	0	0	1	3	5	7	9	11	13	15

The Moore type counter drives the cycle number on inputs \(I_1\) and \(I_2,\) shown in the top row of the time table. The two delay elements in series output two 0’s initially in cycles 0 and 1, i.e. \(O_1[0] = O_1[1] = 0.\) Then, \(O_1\) outputs input \(I_1,\) so that \(O_1[2] = I_1[0] = 0,\) \(O_1[3] = I_1[1] = 1,\) and so on. Similarly, the delay element of output \(O_2\) produces a 0 initially, \(O_2[0],\) and thereafter outputs input \(I_2.\) The adder combines outputs \(O_1\) and \(O_2\) cycle-by-cycle into output \(O.\) We observe that the state machine in Figure 6.47 implements an odd number generator, with a startup delay of two clock cycles.

6.4.4. Feedback Composition¶

The feedback composition connects output \(O\) of state machine \(M\) to one of its inputs. Since \(M\) may be a composite state machine, the feedback composition generalizes the simple feedback loops of Mealy and Moore machines. For a feedback composition to qualify as synchronous circuit, we require that \(M\) is not a combinational logic module, but a state machine with at least one delay element on the loop segment from \(I_2\) to \(O.\)

Figure 6.48: Feedback composition of state machine \(M.\)

The feedback composition enables us to produce complex feedback behavior if \(M\) itself is a composite state machine. However, we may also use the feedback composition to construct primitive state machines. For example, Figure 6.49 shows a primitive counter state machine, based on a feedback composition of machine \(M,\) which is a series composition of a combinational adder and a delay element.

Figure 6.49: Counter state machine based on feedback composition.

We check whether output \(O\) of the state machine implements the same behavior as our earlier primitive counter state machine by analyzing the time dependent behavior of the feedback composition. We begin with machine \(M.\) Output \(O_1\) of the combinational adder produces the \(n\)-bit sum of \(I_1\) and constant 1:

The delay element introduces one clock cycle of delay at output \(O\) of machine \(M,\) such that

The feedback composition connects output \(O\) to input \(I_1,\) which enforces

Substituting the equations into the expression for \(O[t]\) yields

The base case of this recurrence is the start state of the delay element, \(O[0] = 0.\) The recurrence itself holds for cycles \(t > 0.\) We construct the time table interpreting the \(n\)-bit signals as unsigned binary numbers for large bit with \(n\) large enough to ignore the modulo operation. The start state is \(O[0] = 0.\) Then, according to the output recurrence, in cycle 1 we have \(O[1] = O[0] + 1 = 1,\) in cycle 2 \(O[2] = O[1] + 1 = 2,\) and so on.

cycle	0	1	2	3	4	5	6
O	0	1	2	3	4	5	6

Thus, the machine has the output behavior of the primitive \(n\)-bit binary counter machine, \(O[t] = t \bmod 2^n,\) indeed.

Example 6.3: Factorial State Machine

We analyze the composite state machine in Figure 6.50. Upon resetting the machine, the delay elements shall have start state \(S_0 = 1\) rather than default value \(S_0 = 0.\) Machine \(M_1\) is the counter machine of Figure 6.49. Machine \(M_2\) replaces the adder of \(M_1\) with a combinational multiplier for unsigned binary numbers modulo bit width \(n.\)

Figure 6.50: Factorial state machine as a series composition of two feedback compositions.

The machine is a series composition of two feedback compositions \(M_1\) and \(M_2.\) For a back-of-the-envelope analysis, we consider numbers with a bit width small enough to ignore the modulo operations of the adder and the multiplier.

Machine \(M_1\) is a primitive counter state machine with output function \(O_1[t] = O_1[t-1] + 1\) with start state \(S_0 = 1.\) We construct a time table to deduce the effect of the start state on the output function. In cycle 0, the output is equal to the start state, \(O_1[0] = 1.\) According to the recurrence, in cycle \(t=1,\) the output is \(O_1[0]+1 = 2,\) and so on:

cycle	0	1	2	3	4	5	6
\(O_1\)	1	2	3	4	5	6	7

We conclude that counter \(M_1\) with initial output \(O_1[0] = 1\) generates output

\[O_1[t] = 1 + t\,.\]

Machine \(M_2\) multiplies the current output with the current input. The delay element introduces a delay of one clock cycle. Thus, we have

\[\begin{eqnarray*} O_2[t] &=& O_1[t-1] * O_2[t-1] \\ &=& t * O_2[t-1]\,. \end{eqnarray*}\]

Given initial output \(O_2[0] = 1\) of the delay element of \(M_2,\) we construct a time table to derive the output of \(M_2\) as a function of \(O_1.\) In initial cycle \(t=0,\) output \(O_2[0] = 1,\) as determined by the start state of the delay element. Then, in cycle 1, the output is the arithmetic product of outputs \(O_1[0]\) and \(O_2[0]\) of the previous cycle, such that \(O_2[1] = 1 * 1 = 1.\) In cycle 2, we find \(O_2[2] = O_1[1] * O_2[1] = 2,\) and so on:

cycle	0	1	2	3	4	5	6
\(O_1\)	1	2	3	4	5	6	7
\(O_2\)	1	1	2	6	24	120	720

We recognize the output sequence of the composite machine \(O[t] = O_2[t]\) as the factorial sequence

\[O[t] = t! = \prod_{\tau = 1}^t t\,,\]

including base case \(0! = 1,\) which is commonly assumed by definition of the factorial function.

Example 6.4: Fibonacci State Machine

We analyze the output function of the composite state machine in Figure 6.51. The machine consists of a parallel composition of delay elements, similar to Figure 6.47. However, we assume that two of the delay elements have start state \(S_0 = 1\) rather than default start state \(S_0 = 0.\) Instead of driving the parallel inputs with a counter, as in Figure 6.47, we connect output \(y\) of the combinational adder to the delay elements, forming in a feedback composition.

Figure 6.51: Fibonacci state machine as a feedback composition.

As in Example 6.3 we perform a back-of-the-envelope analysis, ignoring the modulo operation of the arithmetic addition when the sum exceeds bit width \(n.\) We construct a time table to deduce the sequences at the outputs of the delay elements \(O[t] = y[t-2]\) and \(x[t] = y[t-1].\) Signal \(y\) is the combinational sum of \(O\) and \(x,\) i.e. \(y[t] = O[t] + x[t].\) The start states of the delay elements determine the initial states \(x[0] = 1,\) \(O[0] = 0,\) and \(O[1] = 1,\) so that \(y[0] = O[0] + x[0] = 1.\) Then, we find \(x[1] = y[0] = 1\) which implies \(y[1] = O[1] + x[1] = 2.\) Furthermore, since \(y[0] = 1,\) we deduce \(O[2] = y[0] = 1,\) and so on.

cycle	0	1	2	3	4	5	6	7	8	9
\(O\)	0	1	1	2	3	5	8	13	21	34
\(x\)	1	1	2	3	5	8	13	21	34	55
\(y\)	1	2	3	5	8	13	21	34	55	89

We recognize output \(O[t]\) as the Fibonacci sequence of Example 5.1, where \(O[t] = Fib(t).\)

Example 6.5: Traffic Light Controller

We revisit the traffic light controller, whose synthesis as a monolithic Moore machine caused us some difficulties due to the large number of states. Now that we know how to compose state machines, we redesign the traffic light controller as a composition of smaller state machines.

The key to factoring the monolithic traffic light controller is to realize that an Austrian traffic light loops through five phases, each with its own duration, and the green-blinking phase exhibiting the extravagant flashing feature. Hence, a natural design employs a phase state machine to loop through the five phases, with one state per phase: red (R), red-yellow (RY), green (G), green blinking (GB), and yellow (Y). The provisional state diagram below shows the loop of phase transitions.

The controller visits each of the states for a different number of clock cycles. Thus, we design a parameterizable timer state machine, that effects the transition from one phase state to the next. When entering a phase state, we start the timer for the desired number of cycles. Once the timer expires, the phase state machine transitions into the next phase state. For example, the red state initializes the timer to expire after another 12 cycles, keeping the red light on for a total of 13 cycles. Thereafter, the phase state machine transitions into the red-yellow state.

The block diagram on the right shows the traffic light controller factored into two communicating state machines. The phase state machine starts the timer with a desired number of cycles. When the timer expires, it informs the phase state machine which, in turn, transitions into the next state.

We design the timer by adopting the primitive counter state machine, see Figure 6.52. Rather than counting up, we count down, and compute the expired signal by means of a combinational equality-to-zero comparator. When the comparator counts down to zero, it retains value zero until the state register stores a new counter value, supplied via the cycles input, when the start signal is asserted.

Figure 6.52: Timer state machine.

Given the timer state machine, we can now refine the phase state machine. In each state, the phase state machine outputs the number of cycles, which is the duration in cycles minus two, and issues a start pulse to the timer. The phase state loops to itself until the timer is expired. The green blinking phase requires special treatment. We split state \(GB\) into two states, \(GB_0\) and \(GB_1.\) In state \(GB_0\) all lights are off, whereas in \(GB_1\) the green light is switched on.

Figure 6.53: Phase state machine with outputs annotated below each state vertex.

Since the phase state machine has only six states, the synthesis procedure, including next state and output logic minimization, does not pose any difficulties. Thus, we leave the synthesis of the Moore type phase state machine as exercise.

6.5.1. Sequencing Logic¶

We illustrate the design of the sequencing logic for a state machine by extending the AddR machine shown in Figure 6.55. Machine AddR is a series composition of a combinational adder and a delay element consisting of a register. We classify the machine as a register machine to emphasize that it stores the result of the combinational addition in a register. The bit width depends on the application, and is left unspecified.

Figure 6.55: The AddR register machine stores the sum of \(A\) and \(B\) in its register.

Output \(Y\) of AddR has the time dependent behavior

because the register introduces a delay of one clock cycle. The output behavior with input sequences \(A = \langle 1, 2, 3, \ldots \rangle\) and \(B = \langle 3, 4, 5, \ldots \rangle\) is illustrated in the waveform diagram below. In cycle 0 output \(Y\) depends on the start state of the register. Since we do not care about the initial value, we mark \(Y[0]\) as undefined. The essential observation is that the outputs appear cycle-by-cycle whether we use them or not. For as long as the input sequences change, the output follows. The machine has no provisions to pause or stop the computation. However, such a feature is desirable, for instance, if we want to reuse a particular output value several times, say \(Y[4]\) in cycles 4, 5, and 6.

This is where sequencing enters the stage. Assuming that the timing behavior of inputs \(A\) and \(B\) is beyond our control, we wish to be able to start and stop the machine independently. The important insight is that we can stop register machine AddR by retaining the state of its register. Otherwise, AddR executes by storing a new sum at every triggering clock edge.

We introduce an enabled register to control whether a register stores its input at a triggering clock edge or not, see Figure 6.56. The enabled register obeys the time dependent functional specification

If the enable input is 1, the enabled register behaves like a regular register or delay element. Otherwise, if enable equals 0, the register retains its current state.

Figure 6.56: Enabled register symbol (left) and implementation with feedback loop (right).

The first step towards adding a sequencing capability to the AddR machine is to replace the register with an enabled register, and to connect the doit signal to the enable input. Figure 6.57 shows the doit extension of the AddR machine on the left. The doit input changes the behavior of the AddR machine such that the output function is now

If the doit signal is 1, the AddR machine computes the sum of the inputs with a single-cycle delay as before. Otherwise, if the doit signal is 0, the AddR machine retains its state. Thus, by setting the doit signal to 0, we effectively freeze the machine independent of input signals \(A\) and \(B.\)

Figure 6.57: AddR machine extension with doit input (left) and done output (right).

As the second step, we introduce a done output to signal that the machine has terminated and the result is available at output \(Y.\) Since the enabled register introduces one cycle of delay, we produce the done signal by delaying the doit signal by one cycle. Therefore, we extend the AddR machine with a D-flipflop between the doit input and the done output, as shown on the right in Figure 6.57. The done output implements the time dependent function of a delay element:

The resulting AddR machine is capable of sequencing. It outputs a new sum only if we assert the doit signal. If we apply a doit pulse in cycle \(t_1,\) then we observe a done pulse in cycle \(t_1+1\) and the sum \(Y[t_1+1] = A[t_1]+B[t_1]\) at the output. This sum remains visible until we issue another doit pulse in cycle \(t_2 > t_1,\) independent of inputs \(A\) and \(B.\) Figure 6.58 illustrates the output behavior by means of a waveform diagram. We apply doit pulses in cycles 0, 1, 4, and 6. Due to the 1-cycle delay of the AddR machine, we expect valid ouputs in cycles 1, 2, 5, and 7. Otherwise, output \(Y\) retains the output associated with the last done pulse.

Figure 6.58: Waveform diagram of sequenced AddR machine.

Note that the abstract behavior of the sequenced AddR machine is quite easy to comprehend, even without analyzing every detail of the synchronous sequential circuit.

6.5.2. Sequencing Series Compositions¶

We arrange a series composition of sequenced state machines \(M_1\) and \(M_2\) as shown in Figure 6.59, assuming output \(O_1\) of \(M_1\) and input \(I_2\) of \(M_2\) are compatible. Composite machine \(M\) is capable of sequencing by means of the doit and done signals. The delay of \(M\) is the sum of the delays of constituent machines \(M_1\) and \(M_2.\)

Figure 6.59: Series composition of sequenced state machines.

As an example, we study the sequenced version of an average machine for computing the average of two binary numbers

Assume we have a supply of sequenced AddR machines, as shown in Figure 6.57 on the right, and, furthermore, sequenced HalfR machines with a combinational divider-by-2 and a register. Then, we can construct an average machine with the series composition of Figure 6.60.

Figure 6.60: Composite average machine with sequencing capability.

Without the sequencing logic, the average machine exhibits the output behavior

because the series composition of AddR and HalfR results in substituting \(X[t] = A[t-1] + B[t-1]\) for \(X[t-1]\) in \(Y[t] = X[t-1]/2.\)

Including the sequencing logic, the composite average machine still has a delay of two clock cycles, such that \(done[t] = doit[t-2],\) and output function

Figure 6.61 illustrates the output behavior by means of a waveform diagram. We apply doit pulses in cycles 0, 1, 4, and 6. Due to the 2-cycle delay of the series composition, we expect valid ouputs in cycles 2, 3, 6, and 8. Otherwise, output \(Y\) retains the output associated with the last done pulse. For example, in cycles 4 and 5, the machine outputs the result of the last computation in cycle 3, i.e. the average \(Y[3] = (A[1] + B[1])/2 = 3.\)

Figure 6.61: Waveform diagram of sequenced average machine.

We interpret the waveform diagram such that the average machine samples the inputs during the doit pulses, outputs the average two cycles later accompanied by a done pulse, and retains the last average between two average computations.

Example 6.6: Sequencing Series Assignments

Consider the composite state machine in Figure 6.62. We have a series composition of three R machines. An R machine is a sequenced delay element or register, with output behavior

\[\begin{split}O[t] = \begin{cases} I[t-1]\,, & \text{if}\ doit[t-1] = 1\,, \\ O[t-1]\,, & \text{if}\ doit[t-1] = 0\,. \end{cases}\end{split}\]

The R machine stores the input when a doit pulse arrives, and outputs the input with a 1-cycle delay. The corresponding sequencing logic produces done pulse \(done[t] = doit[t-1].\) The series composition in Figure 6.62 connects input \(X\) to the input of each R machine.

Figure 6.62: Sequencing a series composition of three register machines.

Our goal is to understand the behavior of outputs \(A,\) \(B,\) and \(C\) as a time dependent function of \(X.\) To that end, we analyze the behavior of the series composition by deducing a time table for input sequence \(X = \langle 1, 2, 3, \ldots \rangle.\) We assume that in cycle 0, all registers are reset to value 0. Furthermore, we apply a single doit pulse during cycle 0.

cycle	0	1	2	3	4	5	6
\(X\)	1	2	3	4	5	6	7
doit	1	0	0	0	0	0	0
\(A\)	0	1	1	1	1	1	1
\(B\)	0	0	2	2	2	2	2
\(C\)	0	0	0	3	3	3	3

The doit pulse starts R machine \(A\) in cycle 0. Next in the series composition, it starts R machine \(B\) in cycle 1, and R machine \(C\) in cycle 2. In cycle 3, a done pulse signals termination. Thereafter, the composite machine retains its state until we apply another doit pulse. Tracing the doit pulse, we find that the doit pulse in cycle 0 triggers output \(A[1] = X[0] = 1,\) then in cycle 1 \(B[2] = X[1] = 2,\) and in cycle 2 \(C[3] = X[2] = 3.\) Output \(A\) retains its value after cycle 1, output \(B\) after cycle 2, and output \(C\) after cycle 3.

We can express this behavior by means of a simple program in your favorite programming language, e.g. C, Java, or Python, as a sequence of assignment statements:

A = 1;
B = 2;
C = 3;

The semantics of a semicolon in a programming language signifies that the assigments must be executed in textual order, from top to botton, in subsequent time steps. Actually, since newlines do not matter in programs, the one-liner:

A = 1;  B = 2;  C = 3;

constitutes an equivalent program, except that the textual order is now interpreted as left-to-right rather than top-to-bottom by convention. The sequenced series composition in Figure 6.62 implements the programs above in form of a synchronous sequential circuit in hardware. Like a program, you can execute the state machine repeatedly by applying input sequence \(X\) accompanied by a doit pulse.

We can reprogram our series composition of R machines by rewiring their inputs and outputs. For example, Figure 6.63 shows the series composition with a cyclic connection of the R machines. The internal wiring of the R machines is omitted for clarity. The output of machine \(A\) connects to the input of machine \(C,\) the output of \(C\) to the input of \(B,\) and the output of \(B\) to the input of \(A.\)

Figure 6.63: The sequenced series composition of R machines implements program: A = B; B = C; C = A;.

When we apply a doit pulse, then during the first cycle we store the output of \(B\) in \(A,\) which corresponds to program statement A = B;. In the second cycle, we store the output of \(C\) in \(B,\) i.e. execute statement B = C;, and in the third cycle we store the output of \(A\) in \(C,\) corresponding to statement C = A;. Thus, the rewired state machine executes the program:

A = B;
B = C;
C = A;

You may recognize these three statements as a program for swapping registers \(B\) and \(C\) using \(A\) as temporary register. Note that a cyclic composition of registers without sequencing logic implements a different functionality.

6.5.3. Sequencing Parallel Compositions¶

Parallel compositions of sequenced state machines can be difficult to tame. However, if we restrict ourselves to simplifying assumptions, then it becomes straightforward to extend a parallel composition with a sequencing capability. Figure 6.64 shows two sequenced state machines \(M_1\) and \(M_2\) arranged in parallel, and the sequencing logic with a doit input and a done output.

Figure 6.64: Parallel composition of sequenced state machines.

This parallel composition exhibits the desired sequencing behavior, if

1. input pairs \(I_1\) and \(I_2\) arrive simultaneously, so that with a single doit signal suffices, and
2. both machines \(M_1\) and \(M_2\) have the same delay.

If the inputs arrive in different clock cycles, then each input must be associated with its own doit signal. Such a scenario requires more complex synchronization circuitry than needed if we restrict all machines to the black-box specification of Figure 6.54. On the other hand, the first assumption is trivially fulfilled in case where a single input \(I\) drives \(I_1 = I\) and \(I_2 = I.\) Then, the doit signal associated with input \(I\) is a valid doit signal for both parallel machines \(M_1\) and \(M_2.\)

The second assumption is necessary to ensure that the output pairs \(O_1\) and \(O_2\) appear simultaneously, so that a single done output suffices. If we compose two machines with unequal delays, we can equalize the delays by increasing the delay of the faster machine using a series composition with sequenced delay elements. Then, the delay of the parallel composition is the maximum of the delays of \(M_1\) and \(M_2.\) Note that the AND gate is redundant if both assumptions are fulfilled. We could use either of the two done signals as composite done output, and ignore the other one.

Example 6.7: Sequencing Parallel Assignments

Consider the parallel composition of three R machines shown in Figure 6.65 with a single input \(X\) accompanied by a doit signal, and outputs \(A,\) \(B,\) and \(C\) accompanied by a done signal. The state machine shown on the left resembles the parallel composition template in Figure 6.64. As shown on the right, we can save two sequencing D-flipflops and the AND gate, and obtain the equivalent register machine R3.

Figure 6.65: Sequencing a parallel composition of three R machines (left), and optimized version (right).

To understand the behavior of outputs \(A,\) \(B,\) and \(C\) as a time dependent function of \(X,\) we repeat our experiment of Example 6.6, and deduce a time table for input sequence \(X = \langle 1, 2, 3, \ldots \rangle.\) We assume that in cycle 0, all registers are reset to value 0, and we apply a single doit pulse.

cycle	0	1	2	3	4	5	6
\(X\)	1	2	3	4	5	6	7
doit	1	0	0	0	0	0	0
\(A\)	0	1	1	1	1	1	1
\(B\)	0	1	1	1	1	1	1
\(C\)	0	1	1	1	1	1	1

In reponse to the doit pulse in cycle 0, all registers store \(X[0],\) so that \(A[1] = B[1] = C[1] = X[0] = 1.\) Also in cycle 1, the done pulse signals termination. Thus, the state of the machine does not change after cycle 1 until the next doit pulse arrives. The behavior of the parallel machine is simpler than that of the series composition. We can express the behavior as a program by means of three assignments:

A = 1;
B = 1;
C = 1;

The semantics of this program suggests an order of execution where, first, 1 is assigned to register \(A,\) then 1 to register \(B,\) and thereafter 1 to register \(C.\) This serial semantics is inherent in most of today’s programming languages. However, in our parallel machine, all three assignments occur simultaneously in cycle 0. Such a parallel assignment cannot be expressed in C and Java, but Python [2] does support a parallel assignment by using the list data structure:

[A, B, C] = [1, 1, 1];

Parallel assignments are natural in digital circuits, but tend to confuse serial programmers. Consider the cyclic parallel composition in Figure 6.66. The wiring connects the same register inputs and outputs as in Figure 6.63. The output of \(B\) is connected to the input of \(A,\) the output of \(C\) to the input of \(B,\) and the output of \(A\) to the input of \(C.\) A doit pulse in cycle 0 causes all registers to store their inputs, such that \(A[1] = B[0],\) \(B[1] = C[0],\) and \(C[1] = A[0].\) These equations expose the dependence on time, and in particular the values of the registers in cycle 1 as a function of their values in cycle 0.

Figure 6.66: Parallel assignment: [A, B, C] = [B, C, A].

If we express the state changes in terms of program statements, we sacrifice the time information. We write assignment A = B; to express \(A[1] = B[0],\) B = C; for \(B[1] = C[0],\) and C = A; for \(C[1] = A[0].\) Combining these three assignments into a one-liner yields:

A = B;  B = C;  C = A;

Interpreting this one-liner as a serial program does not reflect the behavior of the R3 machine in Figure 6.66. For example, given initial state \(A = 1,\) \(B = 2,\) and \(C = 3,\) then executing the sequence of assignment statements of the one-liner left-to-right results in \(A=2,\) \(B=3,\) and \(C=2.\) The effect is a swap of registers \(B\) and \(C\) using \(A\) as temporary register. In contrast, register machine R3 transforms initial state \(A=1,\) \(B=2,\) and \(C=3\) within a single cycle into state \(A=2,\) \(B=3,\) and \(C=1,\) which is a rotation. A doit pulse triggers a parallel assigment in the R3 machine, that we express in Python as:

[A, B, C] = [B, C, A];

Although this Python version of a parallel assignment is written compactly as a one-liner, today’s computers need at least four clock cycles for its execution, and use one additional temporary register.

As an aside, we can design a composite state machine to swap two registers without a third temporary register as a straightforward parallel composition. Take the R3 machine and remove register \(A.\) Connect the output of register \(B\) to the input of register \(C,\) and the output of \(C\) to the input of \(B.\) The resulting swap machine has a single cycle delay and performs the parallel assignment [B, C] = [C, B] by executing state transition \(B[t] = C[t-1]\) and \(C[t] = B[t-1]\) in response to a doit pulse in cycle \(t-1.\)

6.5.4. Conditional Composition¶

Every programming language offers a decision capability, typically in form of an if-then-else statement. We present the sequencing logic for a composite state machine capable of executing the program:

if (predicate == 1) then
   consequent;
else
   alternative;

The combinational predicate and the sequenced state machines for the consequent and the alternative logic depend on the application. Figure 6.67 shows the conditional composition of the consequent and alternative state machines. Inputs and outputs, except those of the sequencing logic, are omitted. In case no alternative is desired, replace the alternative state machine with a sequencing D-flipflop.

Figure 6.67: Sequencing logic for a conditional composition.

The combinational predicate logic outputs the a predicate signal. The composite machine receives doit pulses from the doit input. While the predicate equals 1, doit pulses are steered to the consequent state machine. Otherwise, if the predicate signal is 0, a doit pulse is steered to the alternative state machine. Hence, either the consequent or the alternative machine are started in response to a doit pulse, depending on the predicate signal. When one of the consequent or alternative machines outputs a done pulse, the OR gate steers the done pulse to the done output of the composite machine. The delay of the conditional composition is at least one clock cycle, because the consequent and alternative are sequenced state machines, which require at least one sequencing D-flipflop. The actual delay of the conditional composition may vary, depending on the delays of the consequent and alternative machines.

Example 6.8: Up-Down Counter Machine

We wish to design a sequenced state machine for an up-down counter. An up-down counter receives the counting direction dir as an input. If the dir signal equals 1, the counter shall increment its value by 1, like the counter state machine. Otherwise, if dir equals 0, the counter shall decrement its value by 1. We summarize the behavior of the up-down counter machine in form of a program, given counter register \(C\) and input dir:

if (dir == 1) then
   C = C + 1;
else
   C = C - 1;

Figure 6.68: Up-down counter machine with conditional composition.

Before translating this program into a sequenced state machine, we notice that a single counter register \(C\) suffices to store the counter value. Therefore, we do not honor the clean separation into independent consequent and alternative state machines suggested in Figure 6.67, but share register \(C\) between them. Figure 6.68 shows the resulting state machine design.

The predicate logic implements an identity function, such that a doit pulse is steered to the consequent when the dir input equals 1 and to the alternative when dir equals 0. The consequent portion of the machine has a combinational adder to increment \(C\) by 1, and the alternative portion has a combinational substractor to decrement \(C\) by 1. The tristate buffers at the adder and subtractor outputs implement a multiplexer. If the dir signal equals 1, then the consequent tristate buffer is enabled during a doit pulse, steering \(C+1\) to the input of register \(C.\) Otherwise, if the dir signal equals 0 during a doit pulse, the alternative tristate buffer steers \(C-1\) to the input of register \(C\)

The D-flipflops of the sequencing logic in both consequent and alternative portions of the machine delay the doit pulse by one clock cycle. Consequently, we have \(done[t] = doit[t-1],\) independent of the dir signal. Furthermore, the OR gate at the enable input of register \(C\) guarantees that the doit pulse enables \(C\) independent of its path through the consequent or alternative portions of the machine. Thus, when the up-down counter receives a doit pulse in cycle \(t-1\) and the dir signal is 1, requesting a counter increment, then the counter register transitions to \(C[t] = C[t-1] + 1.\) Otherwise, if the dir signal is 1, the doit pulse triggers the state transtition \(C[t] = C[t-1] - 1.\)

cycle	0	1	2	3	4	5	6	7	8	9
dir	1	1	1	1	0	0	0	1	1	0
doit	1	1	0	1	1	1	0	0	1	0
C	0	1	2	2	3	2	1	1	1	2

The time table above illustrates the behavior of the up-down counter, assuming the counter register is reset to \(C=0\) in cycle 0. Since the machine is sequenced, the counter changes in response to receiving a doit pulse only.

6.5.5. Loop Composition¶

We cap our study of sequenced state machines with another fundamental sequencing construct, the while loop. Well known among computer programmers, a while loop has the general program structure:

while (predicate == 1)
   body;

The semantics of the while loop is to exit the loop if the predicate is not equal to 1 or, otherwise, to execute its body and then restarting the loop execution. Figure 6.69 shows the sequencing logic for a loop composition of a combinational predicate and a sequenced body state machine. Inputs and outputs, besides doit and done, are omitted because they are application specific.

Figure 6.69: Sequencing logic for loop composition.

The combinational predicate logic outputs a predicate signal. When a doit pulse arrives at the doit input and the predicate equals 1, the doit pulse starts the body state machine. Upon termination, the body outputs a done pulse, which is fed back through the OR gate, where we reinterpret it as a doit pulse to restart the body machine provided the predicate is still 1. Otherwise, if the predicate is 0, the doit pulse enters the sequencing D-flipflop at the done output of the loop machine, and is output as a done pulse after a delay of one clock cycle. Thus, if the predicate is 0 upon receiving an external doit pulse or an internal done pulse from the body machine, we terminate the loop and output a done pulse.

The delay of the loop composition is at least one clock cycle to compute the predicate and to start the body or terminate the loop. Otherwise, the delay depends on the delay of the body machine, which is at least one clock cycle as for any sequenced state machine, and on the number of loop iterations.

Example 6.9: Loop Counter Machine

We wish to design a loop machine that counts from 0 up to 3 and terminates. We can specify the desired behavior as a program with a while loop, assuming we have a register to store iteration count \(i\):

i = 0;
while (i < 3)
   i = i + 1;

This program generates state sequence \(i = \langle 0, 1, 2, 3\rangle\) and terminates, as desired. The loop machine shown in Figure 6.70 implements the program.

Figure 6.70: Counter machine based on loop composition.

The predicate logic performs the comparison \(i < 3,\) which we can implement with a combinational magnitude comparator. Assume the comparator output is equal to 1 if \(i < 3,\) and 0 otherwise. Then, the comparator output matches the requirements of the predicate test in the loop composition pattern in Figure 6.69. The body machine is essentially the AddR machine of Figure 6.57 with one input tied to constant 1, and the other input connected to the output of register \(i.\)

We examine the behavior of the loop counter machine by studying the time table below. Assume that register \(i\) of the body machine is reset to value 0 in cycle 0, and we apply a doit pulse in cycle 0.

cycle	0	1	2	3	4	5	6	7	8	9
doit	1	0	0	0	0	0	0	0	0	0
i	0	1	2	3	3	3	3	3	3	3
done	0	0	0	0	1	0	0	0	0	0

In cycle 0, the value of the counter register is \(i = 0,\) which is less than 3. Therefore, the magnitude comparator of the predicate logic outputs a 1. As a result, the external doit pulse in cycle 0 starts the body machine. The body machine transitions to \(i[1] = i[0] + 1 = 1\) and outputs a done pulse during cycle 1.

In cycle 1, the magnitude comparator finds that \(i = 1\) is less than 3, and outputs a 1. Consequently, the done pulse of the body machine, which passes through the OR gate, starts the body machine again. The body machine transitions to \(i[2] = i[1] + 1 = 2\) and outputs a done pulse during cycle 2. During cycle 2, the loop machine executes analogously to cycle 1, with the result that the body machine transitions to \(i[3] = 3\) and issues a done pulse during cycle 3.

In cycle 3, the magnitude comparator outputs a 0, because \(i = 3\) is not less than 3. Therefore, the done pulse of the body machine now enters the sequencing D-flipflop of the done output of the counter machine. After a delay of one cycle, i.e. during cycle 4, the done pulse appears on the done output, and signals termination of the counter execution.

6.8

We are given a state machine with value ranges and state transition table:

1. Describe the functionality of the state machine.

2. Which output sequence does the machine generate for input sequence

   \[\text{in} = \langle 2, 0, 0, 1, 1, 1, 2, 0, 1 \rangle\,.\]

3. Give an input sequence that generates output sequence

   \[\text{out} = \langle 0, 2, 1, 0, 0, 1, 2, 0, 1 \rangle\]

   with initial state \(S[0] = 0.\)

while (x < 15)
   x = x / 2 + 8;

6.6.1. Timing Characteristics in Synchronous Logic¶

Synchronous logic consists of registers and combinational logic. Recall the timing behavior of combinational logic. Figure 6.71 illustrates the characteristic delays. The contamination delay \(t_{cd}\) is the minimum delay from the input transition to the output to start its transition. The propagation delay \(t_{pd}\) is the maximum delay from the input transition to the output transition to stabilize.

Figure 6.71: Timing behavior of combinational logic.

In synchronous sequential circuits, all registers are triggered by the same global clock signal. Proper timing behavior of all registers is a prerequisite for reliable operation of the circuit as a whole. Registers consist of one or more D-flipflops. The timing behavior of a D-flipflop as a series composition of two D-latches is determined by the timing behavior of the master D-latch. The triggering clock edge of a D-flipflop is the clock edge that switches the master D-latch from transparent into opaque mode. For the master D-latch to capture the input signal properly, input \(D\) must be stable for the setup time \(t_{setup}\) before the clock edge and for the hold time \(t_{hold}\) after the clock edge.

Figure 6.72: Characteristic time periods of a register at the triggering clock edge.

Figure 6.72 illustrates the setup time and hold time around the triggering positive clock edge. Depending on the transistor-level design of the register, the transition of output \(Q\) is not necessarily a sharp edge, but may take some time. In general, the output of a register starts to transition after the clock edge, and may exhibit glitches or multiple transitions before stabilizing, as we know from the timing behavior of feedback loops. We define the start and end times of the output transition relative to the triggering clock edge:

The contamination delay \(t_{ccq}\) (contamination delay clock-to-Q) of a register is the time after the triggering clock edge when output \(Q\) starts transitioning.

The propagation delay \(t_{pcq}\) (propagation delay clock-to-Q) of a register is the time period after the triggering clock edge beyond which output \(Q\) is guaranteed to be stable.

We note that the hold time of a register affects the timing behavior of the master D-latch. Although the hold time is typically less than \(t_{ccq},\) as indicated in Figure 6.72, different register circuits may have hold times that exceed \(t_{ccq}\) and even exceed \(t_{pcq}.\)

A synchronous sequential circuit combines registers with combinational logic. In Figure 6.73, we show the characteristic time periods of a simple feedback loop, whose timing behavior is representative for any synchronous circuit. The clock period \(T_\phi\) spans the time period between triggering clock edges. The register requires that next state input \(S'\) is stable during the setup time before and the hold time after the triggering clock edge. The earliest time next state \(S'\) begins to transition depends on the contamination delay of the register and the combinational logic. Output \(S'\) of the next state logic stabilizes at latest depending on the propagation delay of the register and the combinational logic.

Figure 6.73: Characteristic time periods of a synchronous sequential circuit.

The clock period of the circuit is equal the sum of the characteristic delays

where \(t_{pcq}\) is the register specific propagation delay from the triggering clock edge until output \(S\) has stabilized, \(t_{setup}\) is the register specific setup time, \(t_{pd}\) is the propagation delay of the combinational logic, and \(t_{pslack}\) is the propagation slack of the design. We discuss the propagation slack, as well as the contamination slack \(t_{cslack}\) shown in the timing diagram, below. The register specific delays \(t_{pcq}\) and \(t_{setup}\) are commonly referred to as sequencing overhead. An ideal register would have zero sequencing overhead.

6.6.2. Setup-Time Constraint¶

If we are interested in maximizing the performance of a circuit by minimizing the clock period, we must be sure that next state signal \(S'\) is stable before the setup time of the register begins. In Figure 6.73, propagation slack \(t_{pslack}\) is the time period between \(S'\) having stabilized and the begin of the setup time. If we have the choice, we may shorten clock period \(T_\phi\) such the \(t_{pslack}=0.\) Since this is the shortest clock period the circuit supports reliably, we formulate the setup-time constraint for synchronous circuits as the inequality

If \(T_\phi\) is equal to the sum \(t_{pcq} + t_{pd} + t_{setup},\) then our design has no propagation slack. We may characterize a violation of the setup-time constraint with a negative propagation slack \(t_{pslack} < 0.\)

Typical synchronous circuits consist of many registers with combinational logic in between, each of which with its own propagation delay. For reliable operation of the circuit as a whole, we must substitute the maximum propagation delay of all combinational circuits for \(t_{pd}\) in the setup-time constraint. Consequently, paths with faster combinational logic than the maximum propagation delay have propagation slack \(t_{pslack} > 0.\) This slack represents a safety margin for the timing behavior of the logic path. On the flip side, the slack also represents an inefficiency, because the path does not exhaust the entire propagation delay available within the clock period.

In practice, the design of synchronous sequential circuits is often guided by a desired maximum clock period. Since digital designers have little to no control over the register specific delays \(t_{pcq}\) and \(t_{setup},\) because they are given by the manufacturer of the circuit, the only tuning knob available to the designer is the propagation delay of the combinational logic. Rearranging the setup-time constraint, we find

Given clock period \(T_\phi,\) the setup-time constraint presents an upper bound on the propagation delay of the combinational logic. Thus, to the first order, the setup-time constraint limits the maximum number of stages on logic paths. When designing digital circuits, we typically design a correct circuit according to the functional specification first, and then obtain timing closure by reducing the delay of critical paths so as to guarantee that the propagation delay does not exceed the upper bound given by the setup time constraint. There is no reason to minimize the propagation delay further. Just the opposite, positive propagation slack indicates optimization potential with respect to other design features including area and energy consumption.

Example 6.10: Timing Analysis

We wish to determine the maximum clock frequency to operate the sequential circuit in Figure 6.74. The operands of the 4-bit combinational ripple-carry adder are driven by registers \(A\) and \(B,\) and the sum, including the carry-out bit, is stored in register \(S.\) The manufacturer specifies the register delays in normalized time units of \(\tau = 10\,\mathit{ps}\) such that \(t_{ccq} = 5,\) \(t_{pcq} = 8,\) \(t_{setup} = 19,\) and \(t_{hold} = 16.\)

Figure 6.74: Timing analysis of ripple-carry adder. The annotations are pairs of combinational delays \((t_{cd}, t_{pd}),\) see Example 5.16.

Recall our timing analysis of the combinational RCA in Example 5.16. The logic delays \((t_{cd}, t_{pd})\) in normalized time units are reproduced in Figure 6.74. The propagation delay of the critical paths, \(A_0 \longrightarrow S_3,\) \(B_0 \longrightarrow S_3,\) and \(C_{in} \longrightarrow S_3,\) is \(t_{pd} = 56\) time units.

The maximum clock frequency \(f_{max}\) is the reciprocal of minimum clock period \(T_\phi.\) According to the setup-time constraint, the minimum clock period requires zero propagation slack. Then, the minimum clock period is equal to the sum of the \(t_{pcq}\) delay of one of the input registers, e.g. register \(A,\) the propagation delay of the RCA, and the setup time of sum register \(S\):

\[\begin{eqnarray*} T_\phi &=& t_{pcq}(\phi \longrightarrow A_0) + t_{pd}(A_0 \longrightarrow S_3) + t_{setup}(S_3 \longrightarrow \phi) \\ &=& 8 + 56 + 19\ =\ 83 \end{eqnarray*}\]

time units. The reciprocal of the clock period

\[f_{max} = \frac{1}{\tau\, T_\phi} = \frac{1}{830\,\mathit{ps}} = 1.2\,GHz\]

is the maximum clock frequency of the circuit.

6.6.3. Hold-Time Constraint¶

For the registers of a synchronous circuit to operate reliably, we must observe the register specific hold time. In Figure 6.73, next state input \(S'\) must not change for the hold time after the triggering clock edge. The earliest the next state \(S'\) can change after the clock edge is after the sum of the contamination delays of the register and the combinational logic \(t_{ccq} + t_{cd}.\) Therefore, this sum must not be shorter than the hold time of the register. We formulate this condition as the hold-time contraint:

In Figure 6.73, the hold-time constraint is fulfilled, because \(t_{hold}\) is shorter than the sum \(t_{ccq} + t_{cd}.\) The contamination slack quantifies how much shorter the hold time is:

Analogous to the propagation slack, a positive contamination slack is a safety margin. A negative \(t_{cslack}\) can be interpreted as a violation of the hold-time constraint.

Since the contamination delay \(t_{ccq}\) and hold time \(t_{hold}\) are register specific constants determined by the manufacturer, digital designers can only vary the contamination delay of the combinational logic to ensure that the hold-time constraint is observed:

The hold-time constraint serves as lower bound for contamination delay \(t_{cd}\) of the combinational logic. A violation of the hold-time constraint can occur if the combinational portion of a synchronous circuit is too fast or, more succinctly, if \(t_{cd}\) is too small. Typical register designs prevent such hold-time violations by ensuring that \(t_{hold} \le t_{ccq}.\) In this case, the hold-time constraint simplifies to \(t_{cd} \ge 0,\) meaning that a synchronous circuit without combinational logic between register output and input will still operate properly. For register designs where \(t_{hold} > t_{ccq},\) we can prevent violating the hold-time constraint by placing logic on every path between register output and input, for example by inserting buffers.

Example 6.11: Hold-Time Constraint

We examine whether the sequential RCA circuit in Example 6.10 fulfills or violates the hold-time constraint. The manufacturer’s register delays are given as \(t_{ccq} = 5\) and \(t_{hold} = 16\) time units. The timing analysis of the combinational portion of the circuit reveals shortest paths \(A_3 \longrightarrow C_{out}\) and \(B_3 \longrightarrow C_{out}\) with a contamination delay of \(t_{cd} = 9\) time units. Thus, the hold-time constraint

\[\begin{eqnarray*} t_{hold} &\le& t_{ccq} + t_{cd} \\ 16 &\not\le& 5 + 9\ =\ 14 \end{eqnarray*}\]

is violated. The shortest paths of the RCA are too fast for the sum register to capture the carry output reliably, because \(C_{out}\) may begin to transition before the end of the hold time period of the sum register.

We can fix the hold-time violation by increasing the delay of the shortest paths. In general, we want to increase the contamination delay without increasing the propagation delay of the combination logic. This is possible in the RCA circuit. For example, we may insert back-to-back inverters between the carry output of the combinational RCA and the sum register.

Assuming that each inverter has a normalized delay of \(d_{inv} = 2\) time units, we increase the contamination delay of the RCA from \(t_{cd} = 9\) to \(t_{cd} = 13\) time units. The propagation delay of the carry path also increases from \(t_{pd}(C_{out}) = 36\) to \(t_{pd}(C_{out}) = 40\) time units. However, this is still less than propagation delay \(t_{pd} = 56\) time units of the critical paths. The hold-time constraint of the modified circuit

\[\begin{eqnarray*} t_{hold} &\le& t_{ccq} + t_{cd} \\ 16 &\le& 5 + 13\ =\ 18 \end{eqnarray*}\]

is fulfilled without increasing the minimum clock period. Our fix even produces a contamination slack of \(t_{cslack} = 2\) time units as safety margin.

6.6.4. Clock Skew¶

Our discussion of the setup-time and hold-time constraints assumes that the triggering edges of the global clock signal arrive at all registers at exactly the same time. This is an idealizing assumption which is virtually impossible to guarantee in real designs, where the arrival times of the triggering edges vary across registers. The difference of the arrival times is called clock skew. Figure 6.75 illustrates the clock skew in a sequential circuit, where two registers receive the global clock signal with slight timing variations such that \(\phi_1\) arrives slightly earlier than \(\phi_2.\) The difference is of the arrival times of the triggering clock edges is clock skew \(t_{skew}.\)

Figure 6.75: Clock skew is the difference of the arrival times of triggering clock edges across registers.

The presence of clock skew requires a refinement of the setup-time and hold-time constraints to guarantee reliable operation of synchronous circuits. We assume that \(t_{skew}\) is the maximum skew of our global clock signal between any two registers connected by combinational logic. Furthermore, we consider the worst-case scenario of the triggering edges arriving in order \(\phi_1\) before \(\phi_2\) or vice versa.

We consider the setup-time constraint first. If \(\phi_1\) arrives earlier than \(\phi_2\) the clock skew increases the propagation slack. In this case, the clock skew increases the safety margin. On the other hand, if \(\phi_2\) arrives earlier than \(\phi_1,\) then the clock skew reduces the propagation slack, as illustrated in Figure 6.76.

Figure 6.76: Clock skew cuts into the propagation slack of the setup-time constraint.

To guarantee that signal \(S'\) is stable before the setup time begins w.r.t. clock \(\phi_2,\) we refine the setup-time constraint with clock skew:

The added clock skew tightens the upper bound on the propagation delay of the combinational logic:

For the digital designer, this refinement implies that tolerating clock skew requires fewer stages on the combinational logic paths. In practice, this usually means increasing the design effort to obtain timing closure.

For the hold-time constraint, the worst-case scenario occurs if the triggering edge of clock signal \(\phi_1\) arrives earlier than the triggering edge of \(\phi_2.\) Figure 6.77 illustrates this case. We need to hold signal \(S'\) stable for the hold time after the triggering clock edge of \(\phi_2.\) If \(\phi_2\) arrives by \(t_{skew}\) later than \(\phi_1,\) the clock skew reduces the contamination slack.

Figure 6.77: Clock skew cuts into the contamination slack of the hold-time constraint.

We refine the hold-time constraint with clock skew:

The clock skew tightens the lower bound on the contamination delay of the combinational logic:

Fixing hold-time violations in the presence of clock skew requires increasing the delay of the shortest paths further by the clock skew.

6.12

Given the FSM in the diagram with timing data for the next state logic and the register:

1. Determine the minimum clock period \(T_\phi\) for the machine.
2. Determine the slack of the hold-time constraint.
3. Does the machine observe the hold-time constraint?

6.6.5. Dynamic Discipline¶

The timing behavior of synchronous circuits can be confusing at times, even to seasoned designers. However, observing the setup-time and hold-time constraints does produce reliable synchronous sequential circuits. The dynamic discipline summarizes the key aspects of synchronous circuit design and serves as a guideline for digital designers:

• No combinational feedback loops are permitted.
• A single clock signal triggers all registers.
• All register inputs must be stable around the triggering clock edge, and obey the setup-time and hold-time constraints.
• The clock period must be at least as large as the maximum combinational propagation delay plus the sequencing overhead of the registers.
• The next state of the circuit is determined by the output signals of the combinational circuits just before the triggering clock edge.

The dynamic discipline enables us to view the continuous, time dependent behavior of signals in a synchronous sequential circuit as an abstract state machine that produces a discrete sequence of states. Figure 6.78 contrasts boths views. From the circuit perspective, signals \(S[t]\) and \(S[t+1]\) coexist simultaneously during cycle \(t.\) The register drives signal \(S[t]\) into the combinational logic. After the propagation delay of the combinational logic, next state signal \(S[t+1]\) appears at the combinational outputs, where it coexists with state \(S[t]\) of the register. In accordance with the setup-time constraint, next state \(S[t+1]\) exists at the register inputs during the setup-time period before the triggering clock edge at the end of current cycle \(t.\)

Figure 6.78: Progression of continuous signals and discrete states in time.

From the perspective of a state machine, state \(S[t]\) precedes next state \(S[t+1].\) In clock cycle \(t,\) the register stores current state \(S[t],\) and in the next clock cycle \(t+1,\) the register stores next state \(S[t+1].\) The fact that most of the cycle may be spent to prepare the transition between the two states is irrelevant for the digial abstraction of a state sequence. However, without this abstract, perhaps even simplistic view of a state sequence, it is not only cumbersome but virtually impossible to argue about the complex sequences finite state machines are capable of producing.

6.7.1. Combinational Pipelines¶

We consider our options for performing multiple computations on the combinational AND tree shown in Figure 6.79. Assume that the tree is symmetric and each 2-input AND gate has delay \(t_{and} = 50\,\mathit{ps}.\) Thus, the delay from each input to the output is \(t_{pd} = 4\,t_{and} = 200\,\mathit{ps},\) because the number of tree levels is 4. Note that the contamination delay \(t_{cd}\) is equal to the propagation delay \(t_{pd}\) of the circuit. The waveform diagram in Figure 6.79 illustrates the signal propagation from any of the inputs at level 0 to the output at level 4, where the inputs are applied at time 0.

Figure 6.79: Signal propagation through 4-level AND tree.

If we wish to perform ten AND computations, we might want to reuse the circuit as soon as one result has been produced. In this sequential mode of operation, we apply the inputs, wait for \(t_{pd}\) time units until the output has stabilized, and apply the next input. Then, each AND computation has a latency of \(t_{pd} = 200\,\mathit{ps},\) and ten AND computations take \(T_{10} = 10 \cdot 200\,\mathit{ps} = 2\,\mathit{ns}.\) The throughput \(X_{seq}\) of ten AND computations executed one after another is the average number of computations per time unit, here one second:

Note that the throughput is actually independent of the particular number of AND computations we perform.

Now, observe that the sequential mode of operation utilizes the AND gates of the tree rather inefficiently. Rather than waiting until the output of the tree has stabilized, we only need to wait until the level-1 outputs of the stage-1 AND gates have stabilized before applying the next input. If we apply a new input every \(t_{and} = 50\,\mathit{ps},\) we obtain waves of signals propagating through the levels of the combinational AND tree. Figure 6.80 illustrates this pipelined mode of operation.[4] The AND tree with four levels acts like a pipeline with up to five signals that are active simultaneously. If we keep the inputs stable for \(t_{and}\) time units, the corresponding output of the AND computation is stable for \(t_{and}\) time units. In Figure 6.80, time \(t_A\) is suitable point in time to capture the conjunction of input signal \(A\) at the output of the tree, i.e. at tree level 4. At the same time \(t_A,\) four more signals activate the tree. Signal \(E\) is applied to the inputs of the tree at level 0, signal \(D\) has propagated through the first stage of AND gates to level 1, signal \(C\) to level 2, and signal \(B\) to level 3.

Figure 6.80: Pipelined mode of operation with signal wavefronts propagating through the levels of the AND tree.

We analyze the performance of the pipelined mode of operation by deducing the latency of one AND computation and the throughput of multiple AND computations. The latency of one AND computation is the same as in the sequential mode, because pipelining does not affect the propagation delay of a particular input signal through the tree. Therefore, the latency of one AND computation is still \(t_{pd} = 4\,t_{and} = 200\,\mathit{ps}.\) However, the pipelined mode increases the throughput. Once the pipeline is full, every \(t_{and} = 50\,\mathit{ps}\) a new input enters and a new output exits the tree. Therefore, throughput \(X_{pipe}\) in pipelined mode of operation is four times larger than in sequential mode:

The efficiency of pipelining hinges on the contamination and propagation delays of the subcircuits. The AND tree is a best-case example, where each AND gate has equal contamination and propagtion delays, \(t_{and} = t_{cd}(and) = t_{pd}(and).\) If the subcircuits have distinct delays, \(t_{cd} < t_{pd},\) signals on faster paths outpace signals on slower paths. Consider an adder tree of combinational ripple-carry adders. Each subcircuit is an RCA, as in Example 5.16, but with a contamination delay of \(t_{cd}(rca) = 40\) time units and a propagation delay of \(t_{pd}(rca) = 50\) time units. An adder tree with four levels can add 16 binary numbers, and has a timing behavior similar to the AND tree. However, the transitions spread out, the deeper the partial sums propagate into the tree. More succinctly, the transition period at level \(k\) of the adder tree lasts \(k (t_{pd}(rca) - t_{cd}(rca))\) time units. Figure 6.81 illustrates the increasing spread of the transitions towards deeper logic levels.

Figure 6.81: Pipelined adder tree with \(t_{cd}(rca) = 0.8\,t_{pd}(rca).\)

To prevent the signals on the shortest paths from racing ahead of the previous input on the critical paths, we must delay the signal transitions at the inputs of the tree. In Figure 6.81, we assume \(t_{pd}(rca)/t_{cd}(rca) = 5/4,\) and apply new inputs every \(2\,t_{pd}(rca)\) time units only. Then, the output of the adder tree at level 4 is stable for \(5/4\,t_{pd}(rca)\) time units. We can capture the stable sum signals at times \(t_{A}\) and \(t_{B},\) for example. The minimum delay between new inputs is determined by the spread of the transitions at the output. For example, if we require the output to be stable for \(1\,t_{pd}(rca)\) time units, then we can reduce the delay between new inputs to \(7/4\,t_{pd}(rca)\) time units.

The latency of one addition of 16 numbers on the adder tree is \(4\,t_{pd}(rca)\) time units, independent of whether we operate the adder tree in sequential or pipelined mode. The rate of sums exiting the adder tree is equal to the rate of inputs entering the tree. This rate is the throughput of the adder tree in terms of additions per time unit. In Figure 6.81, we perform 1 addition every \(2\,t_{pd}(rca)\) time units, which is half of the maximum throughput we could achieve using RCA circuits with \(t_{cd}(rca) = t_{pd}(rca).\) We conclude that distinct contamination and propagation delays of the subcircuits cause inefficiencies in the pipelined mode of operation.

6.7.2. Synchronous Pipelines¶

Operating a combinational circuit in pipelined mode requires careful circuit design, including the contamination and propagation delays of all subcircuits. Significantly simpler to implement, although in general less efficient, is the pipelining of synchronous circuits. Figure 6.82 shows a synchronous circuit with four stages of combinational logic and registers. Input signal \(S_{in}\) enters the combinational logic of stage 0, and output signal \(S_{out}\) is driven by the register of stage 3. At each triggering clock edge, the signal propagates from one stage to the next. After four triggering clock edges, the result of the computation exits the circuit. Therefore, the latency of a computation is 4 clock cycles.

Figure 6.82: Signal propagation through synchronous pipeline with 4 stages.

Pipelining is the natural mode of operation for such a synchronous circuit. There is no reason to operate the circuit in sequential mode by applying the inputs to \(S_{in},\) and then waiting for 4 cycles until the output appears at \(S_{out}\) before applying the next input. The latency of such a sequential computation is 4 cycles and the throughput is 1 computation per 4 cycles. In the natural pipelined mode, we apply a new input in every clock cycle, as illustrated with the waveform diagram in Figure 6.82. The throughput is 1 computation per clock cycle, which is 4 times larger than in sequential mode. The crucial improvement compared to a combinational pipeline is that the transition delays are confined to each pipeline stage. We do not need to worry about increasing transition times when increasing the number of pipeline stages that effect combinational pipelines. Instead, the minimum clock period \(T_\phi\) is determined by the maximum propagation delay as in every synchronous sequential circuit. In fact, when designing synchronous pipelines, we do not need to worry about contamination delays other than observing the hold-time constraint.

Synchronous pipelines permit a simple abstraction, that hides the details of the timing behavior of the underlying circuit. We sketch the pipeline as a row of cells with one cell per stage, and assume that each stage has a register at its output. Inputs enter the pipeline on the left and outputs exit the pipeline on the right.

We track the signal propagation of computations in the pipeline using a Gantt chart to visualize the allocation of the pipeline stages to computations over time. Figure 6.83 shows a Gantt chart of six computations, \(A, B, C, D, E, F,\) on a 4-stage pipeline. The vertical axis tracks the sequence of computations, and the horizontal axis spans the clock cycles. In the row of a computation, we draw the abstract pipeline aligned to the columns of the clock cycles when the computation occurs. Computation \(A\) occupies stage 0 in cycle 0, \(B\) in cycle 1, \(C\) in cycle 2, and so on.

Figure 6.83: Gantt chart of computations on a 4-stage pipeline.

The Gantt chart tells us which computation occupies which pipeline stage in which clock cycle. For example, computation \(C\) occupies stage 1 of the pipeline in clock cycle 3. Since each row of the chart corresponds to one computation, the position of the pipeline sketch in the chart encodes the time of execution. For example, computation \(C\) starts at the beginning of cycle 2 and terminates at the end of cycle 5. Each column of the chart informs us about the computations that occupy the pipeline simultaneously within one clock cycle. In cycle 4, for instance, the pipeline is occupied by computations \(B,\) \(C,\) \(D,\) and \(E.\) Moreover, it is easy to determine the execution time of multiple computations. For example, a sequence of five computations that enters the pipeline in consecutive clock cycles has an execution time of 8 cycles. Let the first computation be \(B\) and the fifth computation \(F,\) then the sequence of computations starts in cycle 1 when \(B\) occupies stage 0 and ends in cycle 8 when \(F\) occupies stage 3, for a total of 8 cycles.

The pipeline in Figure 6.83 is fully utilized in cycles 3, 4, and 5 only. In cycles 0, 1, and 2, the stages at the tail of the pipeline idle. This is the startup phase of the pipeline, where we fill an initially empty pipeline with computations from head to tail. Similarly, cycles 6, 7, and 8 are the drain phase of the pipeline. When no computations enter the pipeline any longer, the pipeline empties out from head to tail. The startup and drain phases affect the utilization of the pipeline. Assume we execute a sequence of \(n\) computations on a pipeline of depth \(k.\) Then we characterize the performance of the pipeline with these metrics:

Startup time \(T_s\): length of startup phase in clock cycles \(T_s = k - 1\) cycles. By symmetry, the drain time equals the startup time.

Latency \(T_n\): total number of clock cycles to execute \(n\) computations, \(T_n = T_s + n = n + k - 1\) cycles.

Throughput \(X_n\): throughput of \(n\) computations, \(X_n = n / T_n\) computations per clock cycle.

Speedup \(S_n\): speedup of pipelined execution versus sequential execution, \(S_n = n T_1 / T_n.\)

We illustrate these metrics with the aid of the Gantt chart in Figure 6.83. The pipeline has \(k = 4\) stages, and a startup time of \(T_s = 3\) cycles. The latency of \(n=6\) computations is \(T_6 = T_s + n = 9\) cycles. These are the cycles \(0, \ldots, 8\) in the Gantt chart. One computation has a latency of \(T_1 = 4\) cycles. As expected, the number of cycles of \(T_1\) equals the number of stages \(k\) of the pipeline. The throughput of \(n=6\) computations is \(X_6 = 2/3\) computations per cycle, or 2 computations every 3 clock cycles. Only when \(n \rightarrow \infty,\) do we approach the maximum throughput of \(X_\infty = 1\) computation per cycle, supported by the pipeline. The maximum throughput matches the observation that in a full pipeline, one computation can enter and another exit the pipeline within the same cycle. If we perform a finite number of computations only, then the actual throughput decreases because of the startup and drain phases.

The throughput reflects the utilization of the pipeline stages. We may want to know how many computations we need for utilization of 50%, which corresponds to a throughput \(X_n = 1/2\) computations per cycle, or 1 computation every 2 cycles. For a pipeline of depth \(k\) we obtain:

Thus, \(n = 3\) computations achieve a throughput of \(X_3 = 1/2\) computations per cycle on our 4-stage pipeline. More computations increase the throughput. To increase the throughput beyond 90%, we find \(n\) where \(X_n = 9/10.\) Analogous to the algebra above, we obtain \(n = 9 (k - 1).\) Thus, for \(n \ge 27\) computations, the throughput of our 4-stage pipeline is \(X_n \ge 9/10.\) The deeper a pipeline the more computations we need to utilize it efficiently.

The speedup of a pipeline is the performance gain of operating a circuit in pipelined mode compared to sequential mode. If we operate a synchronous pipeline of depth \(k\) sequentially, each computation has a latency of \(T_1 = k\) cycles, and the latency of \(n\) computations is \(n T_1 = n k\) cycles. The speedup

is the factor by which the pipelined execution of \(n\) computations outperforms the sequential execution. For example, \(n = 3\) computations achieve a speedup of \(S_3 = 12/6 = 2\) on our 4-stage pipeline. The pipelined mode of execution is 2 times faster than the sequential mode. The maximum speedup achievable on a \(k\)-stage pipeline is \(S_\infty = k,\) by taking the limit of \(S_n\) for \(n \rightarrow \infty.\) Thus, the deeper a pipeline the larger the maximum speedup we can achieve.

6.7.3. Register-Push Method¶

Synchronous pipelines are of considerable practical value, because they can improve the performance of a digital circuit by increasing its throughput, even if we cannot reduce its latency any further. Therefore, we are interested in transforming a given combinational circuit into a synchronous pipeline. In this section, we introduce the register-push method that facilitates this transformation in a systematic fashion.

Figure 6.84: An acyclic combinational circuit with four subcircuits.

We begin by extending our notion of a \(k\)-stage pipeline to acyclic circuit topologies. Consider the acyclic combinational circuit in Figure 6.84 with inputs \(A\) and \(B\) and outputs \(X\) and \(Y.\) Combinational subcircuits \(C1,\) \(C2,\) \(C3,\) and \(C4\) are shown as black boxes, because we wish to treat them as indivisible subcircuits, like a single CMOS gate for example. Since the circuit topology does not match the simple linear structure of the synchronous pipeline in Figure 6.82, it is not necessarily obvious where we can insert registers to transform the combinational circuit into a synchronous pipeline. The following definition of a k-stage pipeline is the key:

A k-stage pipeline is a synchronous sequential circuit where every path from input to output contains \(k\) registers.

The idea of a \(k\)-stage pipeline is easily understood by example. The circuit below extends the combinational circuit of Figure 6.84 with four registers. We ask whether this circuit is a \(k\)-stage pipeline, and if this is the case, we want to know the value of \(k.\)

The circuit has five paths from inputs to outputs, \(A \longrightarrow C2 \longrightarrow X,\) \(A \longrightarrow C3 \longrightarrow X,\) \(A \longrightarrow Y,\) \(B \longrightarrow X,\) and \(B \longrightarrow Y.\) Consider path \(A \longrightarrow C2 \longrightarrow X,\) and we find 2 registers. Thus, we hypothesize that the circuit is a 2-stage pipeline, and check whether all other paths have 2 registers. This is not the case for path \(A \longrightarrow Y,\) which has 1 register only. We conclude that the circuit is not a \(k\)-stage pipeline.

As a second example, consider the modified circuit below, where we have shifted the register from the output of \(C2\) to the output of \(C1.\)

In this circuit, each of the five paths from inputs to outputs has 2 registers. Therefore, the circuit is a \(k\)-stage pipeline with \(k = 2.\)

The register-push method transforms an acyclic combinational circuit of indivisible subcircuits into a functionally equivalent \(k\)-stage pipeline:

1. Determine the critical path and its propagation delay \(T_{crit}\) between all inputs and outputs.
2. Choose clock period \(T_C\) to be at least the maximum propagation delay of all indivisible subcircuits.
3. Choose the number of pipeline stages \(k\) such that \(k = \lceil T_{crit} / T_C\rceil.\)
4. Place \(k\) registers on every output node.
5. Push registers toward the inputs such that at least one register remains on each output node, and the circuit remains a \(k\)-stage pipeline.
6. Stop pushing when no registers can be pushed without violating the property of being a \(k\)-stage pipeline, and when the propagation delay between any two registers is less than or equal to \(T_C.\) If the propagation delay of a path between an input and the first register is larger than \(T_C,\) set \(k = k + 1,\) place one additional register on every output node, and goto step 5.

We illustrate the register-push method by transforming the circuit in Figure 6.85 into a \(k\)-stage pipeline.

Figure 6.85: Acyclic combinational circuit with propagation delays of subcircuits.

We begin by identifying the critical path \(A \longrightarrow C1 \longrightarrow C2 \longrightarrow C4 \longrightarrow X\) with propagation delay \(T_{crit} = 70\,\mathit{ns}.\) The maximum propagation delay among all subcircuits is \(30\,\mathit{ns}\) of subcircuit \(C1.\) Therefore, we choose a clock period of \(T_C = 30\,\mathit{ns}.\) We could choose a larger clock period but this might result in a smaller clock frequency than necessary for the pipelined circuit. Given \(T_{crit}\) and \(T_C,\) we can choose the number of pipeline stages \(k = \lceil 70 / 30 \rceil = 3.\) This completes the first three steps of the register-push method. The remaining steps specify a graphical method for inserting registers in the combinational circuit, that resembles the bubble-push method. Figure 6.86 shows the register pushing from outputs toward the inputs of the circuit. Step 4 of the register-push method initiates the register pushing by placing \(k=3\) registers on each output node. As shown Figure 6.86(a), we use a simple stroke to represent a register rather than drawing register symbols.

Figure 6.86: Register pushing shifts the output registers toward the inputs forming a 3-stage pipeline. Each stroke represents one register.

Similar to bubble pushing, we push registers across a subcircuit by removing a register from each output, and placing a register on each input. In Figure 6.86(b), we push two registers across subcircuit \(C4,\) leaving one register behind on output \(X.\) Note that subcircuit \(C4\) is now framed by registers. If we operate the circuit with a clock period of \(T_C = 30\,\mathit{ns},\) subcircuit \(C4\) stabilizes its output signal earlier than necessary, because its propagation delay of \(t_{pd}(C4) = 20\,\mathit{ns}\) is less than \(T_C.\)

Next, in Figure 6.86(c), we push two registers across the wire fork. We remove two registers from each of the two output wires, and insert two registers on the input wire of the fork. This transformation does not affect the timing behavior of the circuit. One register remains on output \(Y.\)

In Figure 6.86(d), we push both registers from the output of subcircuit \(C3\) to its inputs. This step is justified by observing that the propagation delays between the registers at the inputs of \(C3\) and the registers on all output paths of \(C3\) are less than clock period \(T_C = 30\,\mathit{ns}.\) There are two such paths. The path between the input registers of \(C3\) to the register on output \(Y\) has a propagation delay of \(5\,\mathit{ns}.\) The other path through \(C4\) to the register on output \(X\) has a propagation delay of \(t_{pd}(C3) + t_{pd}(C4) = 25\,\mathit{ns}.\)

We cannot push both registers on the output of subcircuit \(C2\) to its input, because this would create a path between the register at the input of \(C2\) and the register at output \(X.\) This path would have a propagation delay of \(t_{pd}(C2) + t_{pd}(C4) = 40\,\mathit{ns},\) which is larger than the choosen clock period \(T_C = 30\,\mathit{ns}.\) Instead, we push only one register across \(C2\) as shown in Figure 6.86(e). The paths between two registers through \(C2\) and through \(C4\) each have a propagation delay of \(20\,\mathit{ns},\) which is less than \(T_C.\)

The register push across the wire fork in Figure 6.86(f) saves one register without changing the timing behavior of the circuit. We cannot push the register across subcircuit \(C1,\) because the propagation delay of the resulting path through \(C1\) and \(C2\) would exceed the clock period. Since there are no more opportunities to push registers, the register-push method terminates. The resulting synchronous circuit is the desired 3-stage pipeline. You may verify that each of the five paths between inputs and outputs has 3 registers, and that every path between two registers or from an input to the first register has a propagation delay less than or equal to clock period \(T_C.\)

Now that we have a pipelined version of the original combinational circuit, we analyze the performance benefit of our pipelining efforts. We compare the performance of the 3-stage pipeline in Figure 6.86(f) with the performance of the combinational circuit in Figure 6.85. The combinational circuit has a latency of \(T_{crit} = 70\,\mathit{ns}.\) Operated in sequential mode, the throughput of the combinational circuit is

Next, we consider the pipelined circuit. The 3-stage pipeline has a clock period of \(T_C = 30\,\mathit{ns}.\) Therefore, the latency of one computation is \(T_1 = k \cdot T_C = 90\,\mathit{ns}.\) We note that pipelining increases the latency by \(20\,\mathit{ns},\) or by nearly 30%. For infinitely many computations, the maximum throughput of the pipeline is 1 computation per clock cycle, or

The speedup of \(n\) computations due to pipelining is the ratio of the execution time of \(n\) computations on the combinational circuit, \(n \cdot T_{crit},\) divided by the corresponding execution time on the pipelined circuit \(T_n = (T_s + n)\,T_C.\) In the limit, for infinitely many computations we obtain speedup \(S_\infty\) of the pipelined versus the combinational circuit:

Thus, the speedup of our pipeline is \(S_\infty = 2.33.\) This speedup is below the maximum speedup 3 of a pipeline with \(k=3\) stages. The reason for this loss is the imbalance of the propagation delays in the stages. Only if the propagation delays of all subcircuits are equal is the speedup equal to the number of pipeline stages.

The 3-stage pipeline suffers an additional slowdown, if we include the sequencing overheads of the registers in our analysis. To observe the setup-time constraint, we must increase clock period \(T_C\) to account for the \(t_{pcq}\) and \(t_{setup}\) delays within a pipeline stage. Furthermore, we may have to worry about clock skew \(t_{skew}.\) Thus, the refined clock period for the pipeline is

The sum within the parentheses is the so-called pipelining overhead. The pipelining overhead increases the latency of the pipeline from \(k\cdot T_C\) to \(k \cdot T_\phi,\) and reduces the speedup compared to the combinational circuit from \(T_{crit}/T_C\) to \(T_{crit}/T_\phi.\) Because of the pipelining overhead, we do not want to partition a given combinational circuit into too many stages. Increasing the number of stages increases the maximum speedup but also the pipelining overhead due to the pipeline registers. In fact, for most combinational circuits there exists a best number of stages that maximizes the speedup by balancing the tradeoff between the number of stages and the pipelining overhead.

Example 6.13: Pipelined Ripple Carry Adder

We wish to pipeline the ripple-carry adder for 4-bit numbers shown in Figure 6.87.

Figure 6.87: 4-bit ripple-carry adder.

We treat the full adder (FA) as an indivisible circuit. Assuming that all FA’s have the same propagation delay from inputs to outputs, we can determine the number of pipeline stages \(k\) skipping steps 1 and 2 of the register-push method. The critical path of the 4-bit RCA stretches through the carry chain from the inputs in position 0, \(A_0,\) \(B_0,\) and \(C_{in},\) to the outputs in position 3, \(S_3\) and \(C_{out}.\) Since the carry chain contains 4 FA’s, we choose to allocate one FA per pipeline stage, so that \(k = 4.\) Since all stages have the same propagation delay of the FA, the FA stages of the pipeline will be perfectly balanced.

We initialize the register configuration for the pipelined RCA by placing \(k=4\) registers on each output of the combinational RCA, \(S_0,\) \(S_1,\) \(S_2,\) \(S_3,\) and \(C_{out}.\) Figure 6.88(a) shows the RCA with register strokes on its outputs.

Figure 6.88: Register pushing on 4-bit ripple-carry adder.

We begin to push registers in bit position 3 of the RCA, because the FA is the only one with registers on all outputs to push towards its inputs. Leaving one register behind on outputs \(C_{out}\) and \(S_3,\) we can push three registers across the FA. Figure 6.88(b) shows the RCA with three registers removed from the outputs of the FA in bit position 3, and three registers added to each of its inputs \(A_3,\) \(B_3,\) and \(C_2.\) Now, we have registers on all outputs of the FA in bit position 2. We need to keep one register on \(C_2\) to turn the carry chain into a 4-stage pipeline. Thus, two of the three registers on \(C_2\) are available for pushing. We remove two registers from each output of the FA in bit position 2, \(S_2\) and \(C_2,\) and place two registers on each of its inputs, \(A_2,\) \(B_2,\) and \(C_1,\) as shown in Figure 6.88(c). Finally, we push one register across the FA in bit position 1, to obtain the 4-stage pipeline in Figure 6.88(d). You may verify that all paths from inputs to outputs have 4 registers, and no pipeline stage has a propagation delay larger than that of a full adder.

The manufacturer of our 4-stage pipeline has full adders with a propagation delay of \(t_{pd}(FA) = 100\,\mathit{ps},\) registers with \(t_{pcq} = 10\,\mathit{ps}\) and \(t_{setup} = 15\,\mathit{ps},\) and claims that the clock signal will have negligible skew. We are interested in the speedup of our pipelined RCA compared to the combinational RCA. First, however, let’s step back, and use the timing data to verify our choice of \(k=4\) pipeline stages by means of steps 1-3 of the register-push method. The critical path of the combinational RCA in Figure 6.87 is the carry chain with propagation delay \(T_{crit} = 4\,t_{pd}(FA) = 400\,\mathit{ps}.\) The subcircuit with the largest propagation delay is an FA with a propagation delay of \(t_{pd}(FA) = 100\,\mathit{ps}.\) Thus, we choose the clock period to be \(T_C = t_{pd}(FA) = 100\,\mathit{ps}.\) Then, we choose the number of pipeline stages

\[k = \Bigl\lceil \frac{T_{crit}}{T_C}\Bigr\rceil = \Bigl\lceil \frac{4\,t_{pd}(FA)}{t_{pd}(FA)} \Bigr\rceil = 4\,.\]

Note that the propagation delays of the FA cancel out, justifying our argument that the number of pipeline stages equals the number of FA’s on the critical path.

The combinational RCA is our reference design. The latency of one addition on the combinational RCA is the propagation delay of the critical path \(T_{crit} = 400\,\mathit{ps}.\) If we operate the combinational RCA in sequential mode, we obtain a throughput of

\[X_{comb} = \frac{1\ \text{addition}}{400\,\mathit{ps}} = 2.5 \times 10^9 \frac{\text{additions}}{s}\,.\]

Next, we analyze the performance of the pipelined RCA. Without pipelining overhead, the 4-stage pipeline has the same latency and a four times larger throughput than the combinational RCA, because the pipeline can produce one addition per clock cycle with a period of \(T_C = 100\,\mathit{ps}.\) Thus, the maximum throughput for infinitely many additions is \(10^{10}\) additions\(/s\) on an ideal pipeline. Accounting for the pipelining overhead, we must increase the clock period to observe the setup-time constraint:

\[T_\phi = T_C + t_{pcq} + t_{setup} = (100 + 10 + 15)\,\mathit{ps} = 125\,\mathit{ps}\,.\]

The increased clock period increases the latency of the 4-stage pipeline to \(T_1 = 4\,T_\phi = 500\,\mathit{ps},\) and the throughput decreases to

\[X_{pipe} = \frac{1\ \text{addition}}{125\,\mathit{ps}} = 8 \times 10^9 \frac{\text{additions}}{s}\,.\]

We find that the speedup of our pipelined RCA compared to the combinational RCA is

\[S = \frac{X_{pipe}}{X_{comb}} = 3.2\,,\]

in terms of maximum throughput for infinitely many additions. The pipelining overhead reduces the speedup by 25% compared to the ideal speedup of 4 of a 4-stage pipeline. We conclude that pipelining increases the throughput of a combinational RCA by up to a factor of 3.2 at the expense of increasing the latency by 25%.

6.14

Consider the combinational circuit with subcircuits \(A, B, \ldots, F\):

1. Apply the register-push method to pipeline the circuit.
   1. Determine \(T_{crit}\) of the longest path.
   2. Determine minimum clock period \(T_C.\)
   3. Choose \(k = \lceil T_{crit} / T_C \rceil.\)
   4. Push registers from output toward input.
2. Use register pushing to derive a 2-stage and a 3-stage pipeline.
3. Given registers with sequencing overhead \(t_{pcq} + t_{setup} = 1\,\mathit{ns},\) which number of stages maximizes throughput?

6.15

Consider the combinational circuit with subcircuits \(A, B, \ldots, F\):

1. Apply the register-push method to pipeline the circuit.
2. Calculate speedup \(S_n\) w.r.t. the sequential pipeline execution.
3. Calculate the speedup w.r.t. \(n\) combinational executions.
4. What is the speedup if circuit \(A\) had a delay of \(50\,\mathit{ps}\)?

6.16

Consider the Gantt chart of 5 computations \(A, B, \ldots, E\) executed on a 4-stage pipeline:

1. Identify all pipeline stalls with arrows.
2. Determine latency, throughput, and speedup w.r.t.the sequential pipeline execution.
3. Determine the speedup assuming there were no pipeline stalls.

Footnotes