Interview Traps: Gray Code, Encoders, Priority Encoders, and Decoders
Explain why Gray code protects rotary encoders from misreads, why an ordinary encoder breaks with multiple active inputs, why priority encoders exist to fix that, and why decoders need exactly 2^n outputs — with the underlying mechanism, not just the vocabulary.
This cluster tests whether a candidate understands encoders and decoders as circuits with specific failure modes, not just as 'the thing that turns lines into binary and back.' Interviewers often chain these four questions together (Gray code -> encoder ambiguity -> priority encoder -> decoder fan-out) because each answer sets up the next, so a shaky answer on one tends to cascade into shaky answers on the rest.
Why is Gray code useful in rotary encoders?
A rotary encoder reports its angular position as a multi-bit code read by sensors (optical or mechanical) as the shaft turns. If that code were ordinary binary, moving between adjacent positions can require multiple bits to change at once — for example going from 011 to 100 flips all three bits. Because the physical sensors can never switch at *exactly* the same instant, there's a brief window during the transition where the sensors have only partially updated, and the encoder can momentarily output any combination of old and new bit values — including codes that don't correspond to either the old or the new position at all (e.g., a transient 111 or 000 while going from 011 to 100).
Gray code eliminates this failure mode by construction: consecutive positions in the sequence always differ in exactly one bit. So even if the single changing sensor is slightly out of sync with the others (there are no 'others' changing, since only one bit ever changes at a time), the momentary reading during a transition can only ever be the old position or the new position — never a third, invalid value. This is a direct, physical application of the same Hamming-distance-1 property that makes K-map adjacency work.
The trap answer is 'Gray code is simpler to decode,' which is actually backwards — Gray code requires *extra* conversion logic (a small XOR chain) to translate back into ordinary binary before arithmetic can be done on it. The real reason to use it is glitch/misread immunity during the physical transition between positions, at the cost of that extra conversion step, not decoding simplicity.
Why can an encoder fail when multiple inputs are active?
A basic (non-priority) encoder assumes exactly one input line is asserted at any given time, and its output logic is built by simply OR-ing together the input lines that should set each output bit for that single active input's binary code. It has no mechanism to detect or arbitrate between multiple simultaneously active inputs — it just blindly combines whatever inputs happen to be high.
When two or more inputs are active at once, the OR-based output logic combines contributions meant for different single-input codes, and the result is the binary code that happens to fall out of the OR operation — which typically doesn't correspond to *either* active input, and is functionally meaningless. For example, with an 8-to-3 encoder, if input lines 1 and 2 are both active simultaneously, the OR-combined output might read out as binary 3 — a line that was never actually asserted at all.
The trap is answering 'it just gives the wrong output bit,' without explaining *why* it's structurally guaranteed to be wrong: it's not a probabilistic glitch, it's a deterministic consequence of the encoder's fixed OR-combination logic having no way to represent 'lines 1 and 2 are both active' as a distinct, correct output — the encoder was never designed to disambiguate simultaneous requests in the first place.
Why is a priority encoder needed?
A priority encoder solves exactly the ambiguity above by defining an explicit precedence order among the inputs: when multiple inputs are asserted simultaneously, it outputs the code corresponding to the highest-priority active input and simply ignores all lower-priority inputs that happen to also be active, regardless of how many there are. This makes the circuit's behavior fully deterministic under any combination of simultaneously active inputs, not just the single-active-input case a basic encoder assumes.
Priority encoders typically also add a 'valid' or 'group signal' (GS) output that indicates whether *any* input is active at all, which is necessary because the all-zero output code is otherwise ambiguous between 'input 0 is active' and 'no input is active' — a detail interviewers often probe for specifically.
The classic real-world motivation is an interrupt controller: multiple peripheral devices can request the CPU's attention at the same instant, and the system needs a deterministic, sensible rule (e.g., the highest-priority device wins, others wait) rather than garbage output from an ambiguous OR-combination. The trap answer 'it's faster than a regular encoder' misses the point entirely — priority encoders aren't about speed, they're about resolving a correctness/ambiguity problem that a basic encoder has no way to handle.
Why does a decoder require 2^n outputs for n inputs?
A decoder's job is the inverse of an encoder's: it takes an n-bit binary input code and activates exactly one, uniquely corresponding output line (a one-hot output) for each possible input combination. Since n binary input bits can take exactly 2^n distinct combinations, and each one must map to its own dedicated, uniquely activated output line for the decoding to be unambiguous and complete, the decoder needs exactly 2^n output lines — one per possible input code, no more and no fewer.
If you used fewer than 2^n outputs, at least two different input codes would have to share the same output line, which destroys the one-to-one mapping (you could no longer tell which input code produced a given active output) — that's a fundamentally different, lossy circuit, not a decoder. If you added extra outputs beyond 2^n, they would correspond to input codes that can never actually occur, since there are no more than 2^n possible n-bit patterns to decode in the first place.
The trap answer 'more outputs give more functionality' misunderstands the requirement as a design choice rather than a mathematical necessity: 2^n is the exact count of distinct n-bit codes that exist, so it is the exact count of dedicated output lines an exhaustive, unambiguous one-hot decoder must have — not a rule of thumb, but a direct consequence of counting binary combinations.
Encoder ambiguity vs. priority resolution
The group signal (GS) / 'enable output' on a priority encoder is what disambiguates 'input 0 is active' (code 00, GS=1) from 'no input is active' (code 00, GS=0) — both would otherwise look identical. A decoder's output count is fixed at 2^n by the input bit count n: a 2-to-4 decoder has exactly 4 outputs, a 3-to-8 decoder has exactly 8, and so on — there is no intermediate option.
Basic 4-to-2 encoder (assumes only ONE input active):
Y1 = I3 + I2
Y0 = I3 + I1
If only I2=1: Y1Y0 = 10 (binary 2) -- correct
If I1=1 AND I2=1 simultaneously: Y1Y0 = 11 (binary 3) -- WRONG, neither input was '3'
Priority encoder (I3 has highest priority):
Y1 = I3 + I2.I3'
Y0 = I3 + I1.I2'.I3'
GS = I3 + I2 + I1 + I0 -- 'valid' output: is ANY input active?
If I1=1 AND I2=1 simultaneously: I2 wins (higher priority) -> Y1Y0 = 10 (binary 2), GS = 1Code Examples
This is the concrete mechanism behind 'encoders fail with multiple active inputs': the OR-based output logic silently combines bits meant for different single-input codes, producing a code that was never actually asserted by any single input. A priority encoder would instead deterministically report I2 (assuming I2 has higher priority than I1) and ignore I1.
Y2Y1Y0 = 011 (decimal 3) even though only inputs I1 and I2 were active -- neither corresponds to code 3
Common mistake: Assuming a basic encoder 'does its best' and gives a reasonable approximate answer when multiple inputs are active — it doesn't approximate anything; the OR-combination is a deterministic but meaningless result with no relationship to either active input.
8-to-3 basic (non-priority) encoder, inputs I0..I7, output Y2Y1Y0:
Y2 = I4+I5+I6+I7
Y1 = I2+I3+I6+I7
Y0 = I1+I3+I5+I7
Suppose I1=1 and I2=1 simultaneously (all other inputs 0):
Y2 = 0
Y1 = I2 = 1
Y0 = I1 = 1
=> Y2Y1Y0 = 011 = binary 3
But neither I1 alone nor I2 alone encodes to 3 -- I1 alone gives 001, I2 alone gives 010.
The output 011 is a phantom code that does not represent either active input.Decoder one-hot output requirement
Every one of the 2^n possible input codes needs its own uniquely activated output line for the decoding to remain unambiguous.
3-to-8 decoder: 3 input bits -> 2^3 = 8 output lines, exactly one HIGH at a time
A2 A1 A0 | Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7
--------------------------------------
0 0 0 | 1 0 0 0 0 0 0 0
0 0 1 | 0 1 0 0 0 0 0 0
0 1 0 | 0 0 1 0 0 0 0 0
...
1 1 1 | 0 0 0 0 0 0 0 1
8 possible input codes (2^3) => 8 dedicated output lines, one-to-one, no sharingWhy this matters beyond the interview
Gray-code position encoding is used in real rotary and linear encoders (and in FIFO pointer comparisons across clock domains) precisely because single-bit-transition codes tolerate physical/timing skew without producing invalid intermediate readings. Priority encoders are the literal building block of interrupt controllers (deciding which of several simultaneous hardware interrupt requests the CPU services first) and of keyboard scan-code logic (deciding which key wins when several are pressed at once). Decoders with exactly 2^n outputs are the basis of memory address decoding (a CPU's address bus of n lines selects exactly one of 2^n memory chip-select or row lines) — the same one-hot, no-sharing requirement discussed above.
A basic encoder with multiple active inputs just outputs 'one of' the active inputs' codes, close enough for most purposes.
A basic encoder's OR-based logic combines bits from all active inputs simultaneously, which typically produces a code that matches NEITHER active input — it is not an approximation of either input, it is a distinct, meaningless value. Only a priority encoder deterministically selects one specific input's code when multiple lines are active.
This is the crux of why priority encoders exist in real hardware: without explicit priority logic, simultaneous requests don't degrade gracefully, they produce silently wrong results.
Why does a rotary position encoder typically use Gray code instead of plain binary code for its output? A. Gray code is easier for downstream logic to decode directly into binary arithmetic B. Because consecutive positions differ in exactly one bit, so timing skew between sensors during a transition can only ever produce the old or new valid code, never an invalid intermediate one C. Gray code uses fewer bits than binary for the same range of positions D. Gray code is required by international rotary-encoder manufacturing standards
B. Because consecutive positions differ in exactly one bit, so timing skew between sensors during a transition can only ever produce the old or new valid code, never an invalid intermediate one — Because only one bit changes between adjacent Gray-code positions, even imperfectly synchronized sensors can only read the old value or the new value during a transition, never a spurious third code. Binary encoding can change multiple bits at once, so slightly-out-of-sync sensors can momentarily output a completely invalid intermediate code. Gray code actually needs extra conversion logic (not less) before it can be used arithmetically.
A basic (non-priority) encoder has two input lines active simultaneously. What happens to its output? A. It correctly reports the higher-numbered active input B. It outputs a code determined by OR-ing the contributions of both active inputs, which typically matches neither input's individual code C. It outputs all zeros as an error signal D. It alternates rapidly between the two inputs' codes
B. It outputs a code determined by OR-ing the contributions of both active inputs, which typically matches neither input's individual code — A basic encoder's output logic is a fixed OR-combination of whichever input lines happen to be active, built assuming only one is ever active at a time. With two active simultaneously, the combined output is a deterministic but typically meaningless code that doesn't correspond to either individual active input — this is precisely the ambiguity a priority encoder is designed to resolve.
What specifically does a priority encoder add over a basic encoder to make its behavior well-defined under multiple simultaneous inputs? A. A faster clock speed to sample inputs more often B. An explicit precedence rule that selects the highest-priority active input's code and ignores lower-priority active inputs, typically plus a valid/group-signal output C. A larger number of output bits to represent every possible combination of active inputs D. A built-in delay that waits until only one input is active before producing output
B. An explicit precedence rule that selects the highest-priority active input's code and ignores lower-priority active inputs, typically plus a valid/group-signal output — A priority encoder assigns a fixed ranking among its inputs and, whenever multiple inputs are asserted, deterministically outputs the code of the single highest-priority one, ignoring the rest. It typically also adds a group-signal (GS) output to distinguish 'input 0 is active' from 'no input is active,' both of which otherwise produce the same all-zero code.
Why must an n-input decoder have exactly 2^n outputs, no more and no fewer? A. It's a convention chosen for symmetry, not a strict requirement B. Because n binary input bits produce exactly 2^n distinct codes, and each one needs its own uniquely activated output line for a complete, unambiguous one-hot mapping C. Because 2^n is always an even number, which simplifies the layout D. Because decoders are built from n cascaded 2-output stages
B. Because n binary input bits produce exactly 2^n distinct codes, and each one needs its own uniquely activated output line for a complete, unambiguous one-hot mapping — A decoder must activate exactly one output per distinct input code. Since n bits produce exactly 2^n distinct combinations, exactly 2^n dedicated output lines are required: fewer would force two different codes to share an output (destroying the one-to-one mapping), and more would correspond to input codes that can never occur.
A system uses a basic (non-priority) 4-to-2 encoder (Y1=IRQ2+IRQ3, Y0=IRQ1+IRQ3) to read four interrupt request lines, IRQ0-IRQ3. During testing, IRQ1 and IRQ2 both go active at the same moment and the encoder outputs binary 3 — the code for 'IRQ3 active' — even though IRQ3 was never asserted. Explain why this happened and what single design change would fix it while preserving deterministic behavior.
With IRQ1=1 and IRQ2=1 (IRQ3=0): Y1=IRQ2+IRQ3=1+0=1, and Y0=IRQ1+IRQ3=1+0=1, so Y1Y0=11 (binary 3) — the code for IRQ3, a line that was never asserted at all. This is the deterministic-but-meaningless OR-combination failure mode: the logic was only designed assuming one input is active at a time, so it silently produces a phantom code when two inputs happen to combine their bit contributions into another valid-looking code. The fix is to replace the basic encoder with a priority encoder that assigns a fixed precedence (e.g., IRQ3 > IRQ2 > IRQ1 > IRQ0) and gates lower-priority inputs off whenever a higher-priority input is active, guaranteeing the output always reflects one specific, real, active input rather than an arbitrary OR-combination.
Substitute IRQ1=1, IRQ2=1, IRQ3=0 into Y1=IRQ2+IRQ3 and Y0=IRQ1+IRQ3 and see what Y1Y0 evaluates to; then think about what priority encoders add that basic encoders lack.