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

We are given a processor with 16 general purpose registers and a fixed 2-byte (16-bit) instruction format, where opcodes can have variable length as long as the encoding stays uniquely decodable.

Step 1: Bits needed to address a register.
Since there are 16 registers, each register operand needs \(\log_2 16 = 4\) bits.

Step 2: Bits consumed by operands of each instruction type.

M-type: 2 register operands + 6-bit immediate = \(2 \times 4 + 6 = 14\) bits.
So the opcode field for M-type = \(16 - 14 = 2\) bits.

R-type: 3 register operands = \(3 \times 4 = 12\) bits.
So the opcode field for R-type = \(16 - 12 = 4\) bits.

C-type: 1 register operand + 6-bit offset = \(4 + 6 = 10\) bits.
So the opcode field for C-type = \(16 - 10 = 6\) bits.

Step 3: Why the opcodes must be prefix-free.
Since the total instruction is always exactly 16 bits but the opcode length differs by type (2, 4, or 6 bits), the decoder identifies the instruction type purely by reading the opcode bits one at a time. This is only possible if no valid opcode is a bit-prefix of another valid opcode of a different length -- exactly like a Huffman / prefix code tree.

Step 4: Build the prefix-code tree level by level.
At the 2-bit level there are \(2^2 = 4\) possible codes. M-type uses 2 of them, leaving 2 codes unused at this level. These 2 unused 2-bit codes are the only ones that can be extended further (used codes cannot be extended, or they would no longer be prefix-free).

Step 5: Expand to the 4-bit level.
Each unused 2-bit code can be extended by 2 more bits, giving \(2^2 = 4\) children each. So the 2 unused 2-bit codes give \(2 \times 4 = 8\) available 4-bit codes. R-type uses 7 of these 8, leaving exactly 1 unused 4-bit code.

Step 6: Expand to the 6-bit level.
That single unused 4-bit code can be extended by 2 more bits, giving \(2^2 = 4\) children at the 6-bit level. These 4 codes are exactly the opcode space available for C-type instructions.

Step 7: Conclusion.
The maximum number of unique C-type opcodes possible is \(\boxed{4}\), which corresponds to option (B).