Question 3.2: Implement, in ROM, a sequential machine whose state table is...
Implement, in ROM, a sequential machine whose state table is given in Figure 3-7: You may note that this is the BCD to Excess-3 code converter that we designed in Chapter 1.
A sequential circuit can easily be designed using a ROM and flip-flops. The combi- national part of the sequential circuit can be realized using the ROM. The ROM can be used to realize the output functions and the next state functions. The state of the circuit can then be stored in a register of D flip-flops and fed back to the input of the ROM. Use of D flip- flops is preferable to J-K flip-flops since using 2-input flip-flops would require increasing the number of inputs for the flip-flops (which are outputs from the ROM). The fact that the D flip-flop input equations would generally require more gates than the J-K equations is of no consequence since the size of the ROM depends only on the number of inputs and outputs and not on the complexity of the equations being realized. For this reason, the state assign- ment used is also of little importance, and generally, a state assignment in straight binary order is as good as any.
In order to realize this sequential machine, a ROM and three D flip-flops are necessary. The ROM will generate the next-state equations and output Z from the present states and input X. Hence, the ROM needs four address lines (three coming from flip-flops and one for X), and it should provide four outputs (three next state bits and output Z). Figure 3-8 illustrates the general organization of the implementation. Since the ROM has four inputs, it contains 2^{4} = 16 words. In general, a Mealy sequential circuit with i inputs, j outputs, and k state variables can be realized using k D flip-flops and a ROM with i + k inputs (2^{i+k} words) and j + k outputs.
Now, let us derive the contents of the ROM. Table 3-2 gives the truth table for the sequential circuit, which implements the state table of Figure 3-7 with the “don’t cares” replaced by 0s, and using a straight binary state assignment.
| Q_{1} | Q_{2} | Q_{3} | X | Q^{+}_{1} | Q^{+}_{2} | Q^{+}_{3} | Z |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Assuming that Q_{1}, Q_{2}, Q_{3}, and X are connected to the address lines in that order, with X connected to the LSB, the contents of the ROM to implement this sequential machine are 3, 4, 6, 8, 9, 8, A, B, B, C, 0, 1, 1, 0, 0, and 0 (in hexadecimal representation). The hexadecimal (hex) representation is a concise and convenient way to represent the outputs. The output Z will come from the LSB of the data lines. The next-state information will be available from the three MSBs of the ROM data lines.
