GATE 2020 CS Q.44: solution and answer

GATE 2020 · CSQ.44 · 2 marks · NAT

A processor has 64 registers and uses 16-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name, and a 4-bit immediate value. Each R-type instruction contains an opcode and two register names. If there are 8 distinct I-type opcodes, then the maximum number of distinct R-type opcodes is ____.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The maximum number of distinct R-type opcodes is 14.

Official answer: 14Source: Official answer key, GATE 2020 CS (IIT Delhi)

Register field width: with 64 registers, a register name needs $lo g_{2} 64 = 6$ bits.
I-type opcode length: an I-type instruction packs an opcode, one register name, and a 4-bit immediate into 16 bits, so the opcode field is $16 - 6 - 4 = 6$ bits long.
R-type opcode length: an R-type instruction packs an opcode and two register names into 16 bits, so the opcode field is $16 - 6 - 6 = 4$ bits long.
Since I-type and R-type opcodes are read from the same leading bits of a 16-bit word, no R-type opcode (4 bits) may be a bit-prefix of any I-type opcode (6 bits), and vice versa — the full set of opcodes must be a prefix-free (instantaneous) code, exactly as in Huffman coding.
Model all possible opcode bit-strings as leaves of a binary tree of depth 6 (the longest opcode length): there are $2^{6} = 64$ leaf slots in total.
Each of the 8 chosen I-type opcodes is a full-length (6-bit) codeword, so it occupies exactly 1 leaf slot each: $8 \times 1 = 8$ slots used.
Each R-type opcode is only 4 bits long, so to keep the code prefix-free it must reserve every one of its length-6 extensions: $2^{6 - 4} = 4$ leaf slots per R-type opcode.
Leaf slots left after removing the I-type opcodes: $64 - 8 = 56$ .
Maximum number of distinct R-type opcodes: $56/4 = 14$ (this is the same bound as Kraft's inequality $8 \cdot 2^{- 6} + n \cdot 2^{- 4} \leq 1 \Rightarrow n \leq 14$ ).

KEY IDEA

Because opcodes of two different bit-lengths share one fixed-width instruction word, the decoder must be able to tell them apart just by reading bits left to right — the set of all opcodes must form a prefix-free (instantaneous) code, exactly as in Huffman/variable-length coding. Kraft's inequality $\sum 2^{- ℓ_{i}} \leq 1$ (equivalently, counting reserved leaf slots in a binary code-tree) then bounds how many short codewords can coexist with the given long ones.

WATCH OUT FOR

Treating the R-type opcode field size (4 bits) as directly giving $2^{4} = 16$ possible R-type opcodes, ignoring that some of those 4-bit patterns must be excluded because they would otherwise be indistinguishable, as prefixes, from the 6-bit I-type opcodes sharing the same instruction word.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 11 Instructions & addressing questions, with notes

GATE 2020 CS Q.44: solution and answer

Answer and solution

More Instructions & addressing questions