Instruction encoding: opcode space, register fields, expanding opcodes

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• After CMP a, b, which flags show signed a < b? from Lesson 1.1.3
• Accumulator code for X = A × B + C × D: how many instructions? from Lesson 1.1.2
• 24-bit instruction, 45 opcodes, two registers out of 32: unsigned immediate maximum? from Lesson 1.1.1

1 · The Hook

🎣

Give every instruction the same opcode width and you waste bits: a HALT needs no operands, but still carries empty operand fields. Expanding opcodes let instructions with fewer operands use longer opcodes, so the same 16 bits encode many more instructions. GATE turns this into a counting puzzle.

2 · Predict First

🤔

A 12-bit instruction has a 4-bit opcode and two 4-bit address fields. 13 two-address instructions use 13 of the 16 opcode patterns. One-address instructions need only one 4-bit address field, so they can use the leftover patterns plus 4 extra opcode bits. How many one-address instructions can there be at most?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

3 unused patterns × 2⁴ extensions = 48 one-address instructions.

Fixed opcode width

With a k-bit opcode in every instruction, at most 2ᵏ instructions exist, whatever their operands.

Expanding opcodes

Instructions with fewer operand bits get longer opcodes. The opcode of a short-operand class starts with a pattern that the long-operand class left unused (an escape pattern).

Counting with encodings. An instruction word of w bits has 2ʷ encodings (bit patterns). An instruction whose operand fields take f bits uses 2ᶠ encodings (one for every operand value). So:

• Start with 2ʷ.
• Subtract count × 2ᶠ for each class already placed.
• The maximum number of instructions in the next class = remaining ÷ 2^(its operand bits).

The classic example

16-bit instructions, 4-bit address fields:

• 3-address (12 operand bits): 15 instructions use 15 × 2¹² encodings, opcodes 0000–1110.
• 2-address (8 operand bits): opcodes 1111 0000 – 1111 1110: 15 instructions.
• 1-address (4 operand bits): 1111 1111 0000 – 1111 1111 1110: 15 instructions.
• 0-address: 1111 1111 1111 0000 – 1111 1111 1111 1111: 16 instructions.

Total 61 instructions, where a fixed 4-bit opcode would allow only 16.

Check by encodings: 2¹⁶ − 15·2¹² − 15·2⁸ − 15·2⁴ = 65,536 − 61,440 − 3,840 − 240 = 16 → 16 zero-address instructions. ✓

Why the order matters

Classes are carved from the most operand bits to the fewest. A class that is defined later can only use what earlier classes left. Questions always list the counts for the earlier classes and ask for the maximum of the last one.

4 · Visual

16-bit word, 4-bit address fields

 3-addr: [op 0000..1110][  A  ][  B  ][  C  ]      15 x 2^12 encodings
 2-addr: [1111][op 0000..1110][  A  ][  B  ]       15 x 2^8
 1-addr: [1111][1111][op 0000..1110][  A  ]        15 x 2^4
 0-addr: [1111][1111][1111][op 0000..1111]         16 x 1

5 · Worked Examples

Example 1 Easy

A machine uses a fixed 7-bit opcode. How many instructions at most?

Solution

2⁷ = 128.

Example 2 Medium

16-bit instructions, 6-bit address fields. Two-address instructions use 12 operand bits. If there are 10 two-address instructions, what is the maximum number of one-address instructions?

Solution

Opcode for two-address: 16 − 12 = 4 bits → 16 patterns; 6 unused. Each gives 2⁶ one-address encodings: 6 × 64 = 384.

Example 3 GATE

16-bit instructions, 64 registers (6-bit fields). There are 10 two-register instructions and 300 one-register instructions. How many zero-operand instructions can there be at most?

Solution

2¹⁶ − 10 × 2¹² − 300 × 2⁶ = 65,536 − 40,960 − 19,200 = 5,376.

6 · GATE Traps

⚠️

• Each instruction consumes 2^(operand bits) encodings, not 1.
• Divide the remaining encodings by 2^(operand bits of the next class).
• Carve from most operand bits to fewest; the last class gets the leftovers.
• Two register types (say 4-bit integer and 6-bit floating-point fields) give different field widths; add them per class.

7 · Memory Hook

🧠

"Encodings, not opcodes." Count bit patterns: 2ʷ total, each instruction eats 2^(its operand bits).

8 · Connect the Dots

Chapter 1.1 is complete: fields, operand counts, instruction types and encoding. Chapter 1.2 opens the operand fields: the many ways an operand field can lead to the data, called addressing modes.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markOne-address count

16-bit instructions with 6-bit address fields. Two-address instructions use a 4-bit opcode. There are 14 two-address instructions. Maximum number of one-address instructions?

Numerical answer: ________

Q2NAT2 marksUnsigned immediate

A machine has 24-bit instructions and 32 registers. It supports 45 instructions, each with two register operands and an unsigned immediate. What is the maximum immediate value?

Numerical answer: ________

Q3NAT2 marksMixed register files

2-byte instructions. 16 integer registers (4-bit fields) and 64 floating-point registers (6-bit fields). Type 1: 4 instructions with three integer registers. Type 2: 8 instructions with one floating-point and one integer register. Type 3: instructions with one floating-point register. Maximum number of type-3 instructions?

Numerical answer: ________

Q4MCQ1 markPurpose

The main benefit of expanding opcodes is that they:

• (A) make every instruction the same length
• (B) remove the need for an instruction decoder
• (C) make the clock faster
• (D) let instructions with fewer operands use longer opcodes, increasing the number of instructions

Q5NAT1 markUnused bits

A 32-bit instruction has an 8-bit opcode and three register fields; the machine has 128 registers. How many bits are left unused?

Numerical answer: ________

10 · Rule Card

• Fixed k-bit opcode: ≤ 2ᵏ instructions.
• Expanding: total encodings 2ʷ; a class with f operand bits uses count × 2ᶠ.
• Next class max = (2ʷ − Σ count·2ᶠ) ÷ 2^(f_next). Carve from most operand bits to fewest.
• Classic 16-bit / 4-bit fields: 15 + 15 + 15 + 16 = 61 instructions.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

fixed-width opcodeexpanding opcodeescape patternencoding count 2ʷencodings per instruction 2ᶠ

12 · Answer Vault