Question

Consider a processor that has 16 general purpose registers and it uses 2-byte
instruction format for all its instructions. Variable-sized opcodes are permitted.
There are three different types of instructions; M-type, R-type, and C-type. Each
M-type instruction has 2 register operands and a 6-bit immediate operand. Each R-
type instruction has 3 register operands. Each C-type instruction has a register
operand and a 6-bit offset value. If there are 2 unique M-type opcodes and 7 unique
R-type opcodes, which one of the following options gives the maximum number of
unique opcodes possible for C-type instructions?

• A. 8
• B. 4
• C. 64
• D. 16

Hint:

First find the opcode field width for each instruction type by subtracting the fixed operand bits from the 16-bit word (M-type: 2 bits, R-type: 4 bits, C-type: 6 bits). Then treat opcode allocation as a prefix-free code tree: unused codes at a shorter length can only be split into new codes at the next length by consuming 2 extra bits each (a factor of 4). Track how many short codes remain unused after M-type and R-type allocations, then expand those into the 6-bit level to count available C-type opcodes.

Answer 1

The Correct Option is B

Here is a second way to reach the same result, using a code-space budgeting argument (Kraft's inequality) instead of drawing the tree explicitly.

Step 1: Determine opcode lengths.
With 16 registers needing 4 bits each and a fixed 16-bit instruction:

M-type opcode length \(= 16 - (2 \times 4 + 6) = 2\) bits.
R-type opcode length \(= 16 - (3 \times 4) = 4\) bits.
C-type opcode length \(= 16 - (4 + 6) = 6\) bits.

Step 2: Assign a 'space fraction' to every opcode.
Think of the full set of 16-bit instruction words as one unit of code space. An opcode of length \(L\) bits, once fixed, reserves a fraction \(1/2^{L}\) of the total space (because the remaining \(16-L\) bits can be anything and still decode uniquely).

Step 3: Subtract the space already used.
M-type: 2 opcodes of length 2, each reserving \(1/2^{2} = 1/4\). Total used \(= 2 \times 1/4 = 1/2\).
R-type: 7 opcodes of length 4, each reserving \(1/2^{4} = 1/16\). Total used \(= 7/16\).
Space used so far \(= 1/2 + 7/16 = 8/16 + 7/16 = 15/16\).

Step 4: Find the leftover space.
Leftover fraction \(= 1 - 15/16 = 1/16\).

Step 5: Convert leftover space into number of C-type opcodes.
Each C-type opcode (length 6 bits) reserves \(1/2^{6} = 1/64\) of the space. So the maximum count of C-type opcodes that fit in the leftover \(1/16\) is:

\(\dfrac{1/16}{1/64} = \dfrac{64}{16} = 4\)

This confirms the maximum number of unique C-type opcodes is \(\boxed{4}\), matching option (B).