Question

Instead of using four state bits to implement the finite-state machine in Figure D.3.1, use nine state bits, each of which is a 1 only if the finite-state machine is in that particular state (e.g., S1 is 1 in state 1. S2 is 1 in state 2, etc.). Redraw the PLA (Figure D.3.9).

Short answer

The finite-state machine consists of finite states and transactions from one state to another state. Each state in finite state machine has a different name. In Figure D.3.1 of the textbook, each state in the finite-state machine is labelled using 4 state bits.

As there are total 10 states in the finite-state machine, 4 bits are sufficient to write the name of the state in binary. The four bits are represented as (S3, S2, S1, S0). The value 1001 means machine is in state 9 because the decimal equivalent of 1001 is 9.

Step-by-step solution

Define finite-state machine

The finite-state machine consists of finite states and transactions from one state to another state. Each state in finite state machine has a different name. In Figure D.3.1 of the textbook, each state in the finite-state machine is labelled using 4 state bits.

As there are total 10 states in the finite-state machine, 4 bits are sufficient to write the name of the state in binary. The four bits are represented as (S3, S2, S1, S0). The value 1001 means machine is in state 9 because the decimal equivalent of 1001 is 9.

Use 9 state bits to represent the states of the finite-state machine

The finite-state machine has 10 states (0-9). The particular bit of the 9-bit state is one if and only if that machine is in that state. Every state will be written in the following format:

(S9 S8 S7 S6 S5 S4 S3 S2 S1 S0)

For example, if the machine is in state 1, the S1 bit of 9 state bits is set to 1, rest will be 0. If the machine is in state 5, the S5 bit of the 9 state bits is set to 1, rest will be zero.

Define PLA

PLA is short for Programmable Logic Array. These are the logic devices. The combinational circuits are implemented using the PLAs. PLA consist of a set of AND gates followed by the OR gates. These provide control over data path and can also be used as counter or decoders.

Draw PLA using 9 state bits

The PLA will consist 9 state bits from S0 to S9. If the machine is in particular state, the corresponding operation for that particular state are highlighted in the PLA using black dot. For example, If the state is S0, the operations PCWrite, MemRead, ALUSrc80 are selected. Similarly, for the rest of the states, the corresponding operations are performed. The PLA for 9 state bit is shown below: