Microinstruction formats: horizontal vs vertical, field encoding, control-memory size

0 · Recall Warm-up

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

• CM words for 64 instructions × 6 steps + 4 fetch steps? from Lesson 3.2.1
• Why is microprogrammed control usually slower? from Lesson 3.2.1
• How many bits name one of N things? from Lesson 0.2.1

1 · The Hook

🎣

A horizontal microinstruction spends one bit per signal, but in any one step most signals are 0, and some can never be 1 together (only one register drives the bus, the ALU does one function at a time). Encoding those groups shrinks the word dramatically. GATE's favourite control-unit question computes the encoded width.

2 · Predict First

🤔

Eight register-output signals (R0out … R7out) can never be 1 at the same time. Instead of 8 bits, how few bits can say which one (if any) is active?

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

3 · Core Concept

💡

Predict First — the answer

9 possibilities (8 signals or none) → ⌈log₂ 9⌉ = 4 bits. (Without a "none" case, 3 bits would do.)

Horizontal microinstructions

One bit per control signal. Width = number of signals.

• Maximum parallelism: any combination of signals in one step.
• No decoding delay.
• Wide words: large control memory.

Vertical (encoded) microinstructions

Group signals that are mutually exclusive (never active together) into fields; store a number in each field and decode it.

• A field for k mutually exclusive signals needs ⌈log₂(k + 1)⌉ bits: k codes for the signals plus one code for "none".
• If a group always has exactly one active signal, ⌈log₂ k⌉ bits suffice; questions say so when they intend it.
• Width = Σ over fields.
• Narrower words, but decoders add delay and only one signal per field per step.

Extreme vertical: one field encodes the entire micro-operation: ⌈log₂(number of distinct control words or micro-operations)⌉ bits, at most one micro-operation per microinstruction.

Worked example

Signals grouped into mutually exclusive sets of sizes 3, 7, 12, 2, plus 5 independent signals:

• Horizontal: 3 + 7 + 12 + 2 + 5 = 29 bits.
• Vertical: ⌈log₂ 4⌉ + ⌈log₂ 8⌉ + ⌈log₂ 13⌉ + ⌈log₂ 3⌉ + 5 = 2 + 3 + 4 + 2 + 5 = 16 bits.

Fields of a full microinstruction

Horizontal vs vertical

4 · Visual

Horizontal (29 bits):  |A1 A2 A3|B1 ... B7|C1 ...... C12|D1 D2|E1 E2 E3 E4 E5|
                        3 bits   7 bits     12 bits      2     5 independent

Vertical (16 bits):    | A: 2 | B: 3 | C: 4 | D: 2 | E1 E2 E3 E4 E5 |
                          |      |      |      |
                       decoder per field: 2->4, 3->8, 4->16, 2->4  (code 0 = none)

5 · Worked Examples

Example 1 Easy

A datapath has 75 control signals. Width of a horizontal microinstruction (control part only)?

Solution

75 bits.

Example 2 Medium

Signals fall into mutually exclusive groups of sizes 4, 6, 8 and 15 (each group may also be idle). Vertical control-field width?

Solution

⌈log₂ 5⌉ + ⌈log₂ 7⌉ + ⌈log₂ 9⌉ + ⌈log₂ 16⌉ = 3 + 3 + 4 + 4 = 14 bits.

Example 3 GATE

A machine has 100 instructions; each execute microroutine averages 8 microinstructions; fetch takes 4. There are 48 control signals in 6 mutually exclusive groups of 8 (idle allowed). Compare control-memory sizes for horizontal and vertical (control fields only).

Solution

Words = 4 + 800 = 804. Horizontal: 804 × 48 = 38,592 bits. Vertical: each group ⌈log₂ 9⌉ = 4 bits → 24 bits; 804 × 24 = 19,296 bits.

6 · GATE Traps

⚠️

• Add 1 for the "none" code unless the question says one signal is always active.
• Only mutually exclusive signals may share a field.
• Use the ceiling: 12 signals + none = 13 codes → 4 bits.
• Vertical saves memory but costs decoding time and parallelism.

7 · Memory Hook

🧠

"Horizontal = a bit per signal; vertical = a code per group, plus one for none."

8 · Connect the Dots

Lesson 3.2.1 stored control words; this lesson compressed them. Next: the fields that decide which microinstruction comes next (condition select, next address), the classic GATE width calculation, and the final comparison of hardwired and microprogrammed control.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markVertical field

A field encodes 10 mutually exclusive signals, and the field may also be idle. Bits needed?

Numerical answer: ________

Q2NAT2 marksVertical width

Control signals form mutually exclusive groups of 2, 5, 9 and 14 (each may be idle), plus 6 independent signals. Vertical control-field width?

Numerical answer: ________

Q3MCQ1 markTrade-off

Compared with horizontal microinstructions, vertical microinstructions:

• (A) are narrower but need decoding, which slows them
• (B) allow more signals to be active at once
• (C) are wider and faster
• (D) need no control memory

Q4NAT2 marksCM saving

A CM holds 512 microinstructions. Horizontal control fields would be 64 bits; vertical encoding reduces them to 22 bits. How many bits of control memory are saved?

Numerical answer: ________

Q5NAT1 markAlways-active group

A group of 16 mutually exclusive signals always has exactly one active signal. Bits to encode it?

Numerical answer: ________

10 · Rule Card

• Horizontal: width = number of signals; fast; parallel; big CM.
• Vertical: field of k mutually exclusive signals = ⌈log₂(k+1)⌉ bits (⌈log₂ k⌉ if one is always active).
• Width = Σ fields (+ independent signals) (+ condition select + next address).
• CM bits = words × width.

11 · Concept Ledger

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

horizontal microinstructionvertical (encoded) microinstructionmutually exclusive signal groupfield decoder"none" codeextreme vertical encoding

12 · Answer Vault