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:

Convert every instruction type's opcode length into how many 16-bit code points it uses, 2 raised to (16 minus opcode bits) per opcode, then see how many C-type-sized slots remain once the M-type and R-type opcodes have claimed their share.

Answer 1

The Correct Option is B

Step 1: Understanding the Question.
The processor has a fixed instruction length of 2 bytes, that is 16 bits, but the opcode field itself is allowed to be a different size for each instruction type, which is called variable-sized or expanding opcode encoding. We must work out how many bits each instruction type spends on its opcode, then figure out how the total 16-bit code space gets shared between M-type, R-type, and C-type instructions so we can find the maximum number of C-type opcodes left over.

Step 2: Find the register field size.
There are 16 general purpose registers, so each register operand needs
\[ \log_2 16 = 4 \text{ bits} \]

Step 3: Find the opcode size for each instruction type.
M-type has 2 register operands and a 6-bit immediate, using \(2\times4+6=14\) bits for operands, leaving
\[ 16-14=2 \text{ bits for the opcode} \]
R-type has 3 register operands, using \(3\times4=12\) bits, leaving
\[ 16-12=4 \text{ bits for the opcode} \]
C-type has 1 register operand and a 6-bit offset, using \(4+6=10\) bits, leaving
\[ 16-10=6 \text{ bits for the opcode} \]

Step 4: Set up the shared code space.
Since C-type instructions use the widest opcode field, 6 bits, treat the total opcode space at that resolution as the budget: there are \(2^6=64\) distinct 6-bit patterns in total. Every M-type or R-type opcode, being shorter, actually blocks off a whole group of these 6-bit patterns, all the ones that start with it, not just a single one.

Step 5: Work out how much budget each M-type opcode uses.
An M-type opcode is only 2 bits long. Any 6-bit pattern that begins with that same 2-bit prefix cannot be used as a C-type or R-type opcode, since it would be indistinguishable from the M-type one during decoding. The number of 6-bit patterns sharing a given 2-bit prefix is
\[ 2^{6-2}=2^4=16 \]
With 2 unique M-type opcodes, the total budget used is
\[ 2\times16=32 \]

Step 6: Work out how much budget each R-type opcode uses.
An R-type opcode is 4 bits long, so each one blocks off
\[ 2^{6-4}=2^2=4 \]
6-bit patterns. With 7 unique R-type opcodes, the total budget used is
\[ 7\times4=28 \]

Step 7: Find what is left for C-type.
The total budget available is 64. M-type and R-type together use
\[ 32+28=60 \]
So the remaining budget for C-type opcodes, each of which uses exactly 1 unit at this 6-bit resolution, is
\[ 64-60=4 \]

Step 8: Final conclusion.
The maximum number of unique opcodes possible for C-type instructions is
\[ \boxed{4} \]