GATE CS 1992 Q01-vi — Machine Instructions and Addressing Modes

We can solve this problem using two methods: the State-Space Method (most efficient) and the Expanding Opcode Method.

Method 1: State-Space Method

An $11$-bit instruction format provides a total of $2^{11} = 2048$ distinct states (combinations).

• Two-address instructions: Each instruction has two $4$-bit address fields.
  States consumed per instruction = $2^4 \times 2^4 = 256$.
  States consumed by $5$ two-address instructions = $5 \times 256 = 1280$ states.
• One-address instructions: Each instruction has one $4$-bit address field.
  States consumed per instruction = $2^4 = 16$.
  States consumed by $32$ one-address instructions = $32 \times 16 = 512$ states.
• Zero-address instructions: Each instruction has zero address fields.
  States consumed per instruction = $2^0 = 1$.
  Let $N$ be the number of zero-address instructions. States consumed = $N \times 1 = N$ states.

Equating the total states consumed to the total available states:

Method 2: Expanding Opcode Method

1. Two-address instructions:
   • Opcode size = $11 - (4 + 4) = 3$ bits.
   • Total possible opcodes = $2^3 = 8$.
   • Opcodes used = $5$.
   • Unused opcodes left for expansion = $8 - 5 = 3$.
2. One-address instructions:
   • Opcode size = $11 - 4 = 7$ bits.
   • By expanding the $3$ unused opcodes with the $4$-bit address field, we get: $3 \times 2^4 = 48$ possible opcodes.
   • Opcodes used = $32$.
   • Unused opcodes left for expansion = $48 - 32 = 16$.
3. Zero-address instructions:
   • Opcode size = $11$ bits.
   • By expanding the $16$ unused opcodes with the remaining $4$-bit address field, we get: $16 \times 2^4 = 256$ possible opcodes.

Thus, the computer can support a maximum of 256 zero-address instructions.