Exercises — Encoders and priority encoders

WHAT: many lines in (8 buttons), one number out (3 bits). That is compression position → number, which is exactly the encoder direction. A decoder goes the other way ($n$ → $2^n$). Answer: an 8-to-3 encoder — $8=2^3$ inputs, $3$ outputs. Check: ${\log }_{2}8=3$ output wires. ✅

Use the equations. $Y_0=I_1+I_3=0+1=1$. $Y_1=I_2+I_3=0+1=1$. Answer: $Y_1{Y}_0=11_2=3$. That is index 3 — correct, because $I_3$ is the active line. ✅

WHY this rule: $Y_2$ is the "value-4" column of the 3-bit index. It must be 1 exactly when the index $j$ has its bit-2 set, i.e. $j\in \{4,5,6,7\}$. Look at the figure: the indices whose bit-2 is 1 are grouped on the right.

Answer: $Y_2=I_4+I_5+I_6+I_7$. (For completeness: $Y_1=I_2+I_3+I_6+I_7$, $Y_0=I_1+I_3+I_5+I_7$.)

$V=I_0+I_1+I_2+I_3=0+0+1+0=1$ (something is on). $Y_1=I_2+I_3=1+0=1$. $Y_0=I_3+I_1\overline{I_2}=0+(0)(\overline{1})=0+0=0$. Answer: $Y_1{Y}_0=10_2=2$, $V=1$. Correct index. ✅

WHAT: two inputs on — the priority rule ("highest index wins") must pick $I_3$. $V=0+0+0+1=1$. $Y_1=I_2+I_3=0+1=1$. $Y_0=I_3+I_1\overline{I_2}=1+(0)(1)=1$. Answer: $Y_1{Y}_0=11=3$, $V=1$. $I_3$ (highest) wins, $I_0$ is ignored. ✅

WHY it can be ambiguous: the plain encoder OR-s bits from whichever inputs are on; it has no way to know only one is on. Try $I_1=1$ and $I_2=1$: $Y_0=I_1+I_3=1$, $Y_1=I_2+I_3=1\Rightarrow 11$. So $\{I_1,I_2\}$ and $\{I_3\}$ both give $11$. Answer: active $I_1,I_2$ also yields $11$. The output $11$ therefore does not uniquely mean "$I_3$." A plain encoder is only trustworthy when the one-hot guarantee holds. ✅

WHAT happens: the output is the bitwise OR of the two indices, not either index itself. With $I_0(=00_2)$ and $I_1(=01_2)$ active: $Y_0=I_1+I_3=1$, $Y_1=I_2+I_3=0\Rightarrow 01=1$. Here it accidentally equals index 1. But take $I_1(01)$ and $I_2(10)$: OR $=11=3$, which is neither. General reason: ${\text{index}}_a\text{ OR }{\text{index}}_b$ equals ${\text{index}}_a$ or ${\text{index}}_b$ only when one index's set bits are a subset of the other's. Otherwise you get a third code. Answer: the merged output is the bitwise OR of the two indices; it matches a real input only in the special subset case, so in general it is garbage — which is exactly why priority encoders exist. ✅

WHY: a suppression term is only needed when a higher-priority input wants that output bit cleared while a lower one wants it set.

• Indices whose bit-1 is set: $\{2,3\}$. The only higher input above 2 is 3 — and index 3 also wants $Y_1=1$. No conflict, so $Y_1=I_2+I_3$ suffices.
• Indices whose bit-0 is set: $\{1,3\}$. Between them sits index 2, which wants $Y_0=0$. Since $2>1$, active $I_2$ must override $I_1$. Hence $I_1\overline{I_2}$. Answer: $Y_1$ is conflict-free (its two claimants 2 and 3 agree, and the higher one wins anyway); $Y_0$ has a higher input (2) that disagrees with a lower one (1), forcing the $\overline{I_2}$ guard. ✅

Step 1 — which indices set bit-2? $\{4,5,6,7\}$. Step 2 — any higher index disagree? The highest indices are exactly the ones in this set, and every index above 3 wants $Y_2=1$; anything below 4 wants $Y_2=0$ but they are all lower priority, so if any of $\mathrm{4..7}$ is on it wins. WHY no suppression: a suppression term guards against a higher input wanting the bit cleared. No index $\ge 4$ ever wants $Y_2=0$. So a plain OR works. $Y_2=I_4+I_5+I_6+I_7$ $V=I_0+I_1+I_2+I_3+I_4+I_5+I_6+I_7$ Answer: $Y_2=I_4+I_5+I_6+I_7$, no suppression needed; $V$ = OR of all 8. ✅

Reasoning per claimant (highest priority wins; a lower claimant is only allowed to speak if no higher-priority input is active):

• $I_7,I_6$ set bit-1 and are the top of the pile → unconditional.
• $I_3$ wants $Y_1=1$, but only if nothing above index 3 is on. Above 3 are $I_4,I_5,I_6,I_7$. So $I_3$ needs guard $\overline{I_4}\overline{I_5}\overline{I_6}\overline{I_7}$.
• $I_2$ likewise: guard against $I_3$? No — $I_3$ also sets bit-1, so it agrees; but $I_4,I_5$ want bit-1 = 0 and outrank $I_2$. Guard against $I_4,I_5,I_6,I_7$: $\overline{I_4}\overline{I_5}\overline{I_6}\overline{I_7}$.

Both $I_2$ and $I_3$ share the same guard $G=\overline{I_4}\overline{I_5}\overline{I_6}\overline{I_7}$. $Y_1=I_6+I_7+(I_2+I_3)\overline{I_4}\overline{I_5}\overline{I_6}\overline{I_7}$ Since $I_6,I_7$ appear standalone, the $\overline{I_6}\overline{I_7}$ inside the guard is redundant for correctness of the value (when $I_6$ or $I_7$ is on, the standalone term already forces $Y_1=1$), but keeping it makes the intent explicit. A minimised form (via Karnaugh maps / Boolean algebra simplification): $Y_1=I_6+I_7+(I_2+I_3)\overline{I_4}\overline{I_5}$ Answer: $Y_1=I_6+I_7+(I_2+I_3)\overline{I_4}\overline{I_5}$. ✅

Idea (this is exactly how real interrupt controllers cascade):

• High block handles $I_4..I_7$ → gives $Y_1^H,Y_0^H,V^H$.
• Low block handles $I_0..I_3$ → gives $Y_1^L,Y_0^L,V^L$.
• $V^H=1$ means "something in the top half is active" → that is the new bit-2: $Y_2=V^H$
• Choose the lower two bits from the high block if $V^H$, else the low block (a 2:1 select on each bit): $Y_1=V^H{Y}_1^H+\overline{V^H}{Y}_1^L,Y_0=V^H{Y}_0^H+\overline{V^H}{Y}_0^L$
• Overall valid: $V=V^H+V^L$.

Answer: the high block's $V^H$ is the new MSB; two 2:1 muxes (steered by $V^H$) pick the low two bits, and $V=V^H+V^L$. This cascades priority: any top-half request outranks the whole bottom half — precisely the "big boss wins" rule scaled up. ✅

WHY $EN$: real chips (e.g. cascaded interrupt logic) need a way to switch a block off so a higher block can take over — this is the "enable-in" pin. Multiply every output by $EN$ so that $EN=0$ zeroes everything: $Y_1=EN(I_2+I_3)$ $Y_0=EN(I_3+I_1\overline{I_2})$ $V=EN(I_0+I_1+I_2+I_3)$

Verify $EN=1,I_1=1,I_2=1$: $Y_1=1\cdot (1+0)=1$. $Y_0=1\cdot (0+1\cdot \overline{1})=1\cdot (0+0)=0$. $V=1\cdot (0+1+1+0)=1$. Output $10=2$, $V=1$ — highest active input $I_2$ wins. ✅

Verify $EN=0,I_3=1$: Every term is $0\cdot (\dots )=0$: $Y_1=Y_0=V=0$. Chip silent even though $I_3$ is on. ✅ Answer: the three enable-gated equations above; both test cases behave correctly.

Case no input ($I_0=I_1=I_2=I_3=0$): $V=0$. The $Y$ bits are treated as don't-care because $V=0$ commands "ignore the number." Case $I_0$ active only: $V=I_0+\cdots =1$; $Y_1=I_2+I_3=0$, $Y_0=I_3+I_1\overline{I_2}=0$ → code $00$, but now $V=1$. So the two situations differ in the $V$ bit ($0$ vs $1$), which is the deciding signal — the $00$ code is only meaningful when $V=1$. Why plain fails: a plain encoder has no $V$; both situations produce $Y_1{Y}_0=00$ and are indistinguishable. Answer: $V$ separates them ($0$ = empty, $1$ = "$I_0$"); the plain encoder, lacking $V$, cannot. ✅

Simplify using absorption $X+XY=X$ (from Boolean algebra simplification): The term $I_1{I}_3$ contains $I_3$ as a factor, and $I_3$ is already a standalone term, so $I_3+I_1{I}_3=I_3$. The extra term vanishes: $Y_0=I_3+I_1\overline{I_2}+I_1{I}_3=I_3+I_1\overline{I_2}.$ Answer: yes it is logically correct, but redundant; by absorption it reduces to the standard $Y_0=I_3+I_1\overline{I_2}$. The wasted $I_1{I}_3$ AND-gate can be deleted. ✅

L1 recognise the box · L2 plug into the equations · L3 diagnose why plain encoders lie · L4 scale up (8-input, cascade two 4-blocks) · L5 add enable, prove correctness, minimise. The single thread: priority + the valid bit $V$ turn an ambiguous OR-gate into a trustworthy address generator.