DIGITAL ELECTRONICS

Combinational Blocks

Every combinational building block in one place: multiplexers and demultiplexers, encoders and priority encoders, decoders and address decoding, and the arithmetic circuits from half adder through carry-lookahead. Each with a live explorer and the propagation-delay cost that decides which one you use.

Reviewed 2026-08-224,545 words

Multiplexers: Selecting One of Many, and Building Anything

A multiplexer routes one of several inputs to a single output under the control of select lines - n select lines choose among 2^n inputs. That is its stated job and its smaller one. Its more interesting property is that a multiplexer is a universal logic element: with the inputs tied to constants or to a variable, a 2^n-to-1 mux implements any function of n or even n+1 variables, which is exactly how an FPGA's lookup table works.

How it is built

The basic cell is 2-to-1: Y = (A AND NOT S) OR (B AND S). Larger multiplexers are trees of these, so a 16-to-1 is four levels deep and its delay is four gate delays rather than one.
In CMOS a multiplexer is often built from transmission gates rather than from AND-OR logic, which is smaller and faster because the signal passes through rather than being regenerated.
Feeding the data inputs with constants turns the mux into a function generator. A 4-to-1 with its selects driven by two variables and its inputs set to 0 and 1 implements any two-variable function - which is a lookup table.
Extending that, an FPGA's LUT is a small multiplexer whose data inputs come from configuration memory. Programming the device is writing the truth table into that memory, and the mux does the rest.
A multiplexer must not glitch when the select changes, because the two data paths have different delays. In a synchronous design the output is registered, which makes the glitch harmless; in an asynchronous one it is not.
Bus multiplexing at scale is done with tri-state drivers rather than multiplexers, because a mux for many wide sources becomes enormous. Both approaches solve the same problem with opposite costs.

Design procedure

Size the multiplexer from the number of sources, remembering the tree depth is log2 of that count and contributes directly to the critical path.
Decide whether the select is timing-critical. A select arriving late is worse than data arriving late, because it must propagate through every level of the tree.
Register the output if the select can change asynchronously, so the transient while paths settle is never observed.
For function generation, write the truth table and read the data inputs straight off it - that mapping is mechanical and needs no algebra.
For wide buses with many sources, compare a multiplexer tree against tri-state drivers on area and on the timing of enable signals.
Check the default case in any behavioural description. An unspecified select value in RTL infers a latch, which is almost never what was wanted.

Key terms

Select lines: n of them choose among 2^n inputs.
Transmission gate: A pass structure of two complementary transistors. How a CMOS mux is usually built.
Lookup table (LUT): A mux whose data inputs are configuration bits. The FPGA's basic logic element.
Tree depth: log2 of the input count. Each level adds delay.
Universal element: A 2^n-to-1 mux implements any function of n+1 variables.
Glitch on select: A transient while the two paths settle. Harmless if the output is registered.

Worked example

An FPGA's four-input LUT is a 16-to-1 multiplexer with sixteen configuration bits as data and the four logic inputs as selects. Any function of four variables - every one of the 65,536 of them - is implemented by writing its truth table into those bits. No gates are synthesised at all in the usual sense; the tools compute a truth table and store it. Understanding that a LUT is just a multiplexer explains why FPGA logic is counted in LUTs rather than gates, and why a four-input function and a much simpler two-input one cost exactly the same.

Common pitfalls

Demultiplexers: One Source, Many Destinations

A demultiplexer is a multiplexer run backwards: one input is routed to one of 2^n outputs under n select lines, with the unselected outputs driven to an inactive level. The pairing matters more than either device alone, because a mux and a demux together are how one shared resource - a bus, a converter, a serial link - serves many endpoints. Structurally a demultiplexer is a decoder with an enable, which is why the two are frequently the same part.

How it is built

Each output is the AND of the data input with the decoded select for that position. Only one decoded line is active at a time, so only one output follows the data and the rest sit at their inactive value.
A decoder is a demultiplexer whose data input is tied active. That equivalence is why datasheets label the same silicon both ways, and why the enable pin on a decoder is the demultiplexer's data input.
The inactive level matters. Outputs held low suit active-high loads; outputs held high suit active-low ones such as chip selects, and a demultiplexer used for chip selects is almost always the active-low variety.
Only one output may be active at once, which is exactly what makes it safe for chip selects on a shared bus - the structure enforces mutual exclusion rather than relying on firmware to.
For a shared analog resource the same idea uses analog switches rather than gates, which is what an analog multiplexer in front of an ADC is doing - and there the on-resistance and charge injection matter, unlike in a logic demux.
Address decoding in a memory map is a demultiplexer: the upper address bits select which device's chip select asserts, and the lower bits go to the device.

Design procedure

Decide the inactive level from the loads. Chip selects are almost always active low, so the demultiplexer's idle output should be high.
Check the enable behaviour: with the enable inactive, every output should be inactive, which is what makes a clean 'select nothing' state possible.
For address decoding, work out how many upper bits are needed and confirm the decode is unique - two devices responding to overlapping ranges is a bus contention.
Add glitch protection on chip selects if the select lines can change while enabled, since a transient decode can briefly assert the wrong device.
For analog multiplexing, budget the on-resistance against the settling requirement and remember charge injection when the channel changes.
Verify the unselected outputs stay inactive under every select value, including the ones the design never intends to produce.

Key terms

Demultiplexer: One input to one of 2^n outputs, chosen by n select lines.
Decoder: A demultiplexer with the data input tied active. Same structure.
Enable: Forces every output inactive. The demux's data input, seen another way.
Active low: Inactive level is high. Standard for chip selects.
Mutual exclusion: Only one output active at a time, enforced structurally.
Address decoding: Upper address bits selecting which device responds.

Worked example

A microcontroller with one SPI bus and eight peripherals can use eight GPIOs for chip selects, or three GPIOs into a 3-to-8 decoder. The decoder is not merely a pin saving: because only one output can be low at a time, it is structurally impossible for firmware to select two devices at once - a bug that on eight separate GPIOs is one wrong line of code away and produces bus contention that can damage drivers. The saving is five pins; the real benefit is that a whole class of fault stops existing.

Common pitfalls

Encoders and Priority: Turning Many Lines Into a Number

An encoder is the inverse of a decoder: given 2^n input lines of which one is active, it outputs the n-bit number of that line. The plain version is almost useless, because it assumes exactly one input is active and produces nonsense otherwise. The priority encoder is the one that gets used - it outputs the index of the highest-numbered active input and ignores the rest, which is precisely what an interrupt controller needs.

How it is built

A plain encoder ORs together the inputs whose index has a 1 in each bit position. It cannot distinguish 'no input active' from 'input zero active', because both give an output of zero.
A valid output solves that: it asserts when any input is active, so zero-with-valid and zero-without-valid are distinguishable. Without it, an encoder has an ambiguity that firmware cannot resolve.
A priority encoder resolves multiple simultaneous inputs by a fixed rule - highest index wins. That turns an invalid condition into a defined one, which is why it is the version that appears in real hardware.
Interrupt controllers are priority encoders with extra state. The highest-priority pending interrupt is encoded into a vector number, and the rest stay pending rather than being lost.
The delay grows with the input count, because deciding the highest active input is inherently a chain. Wide priority encoders are built as trees to keep that logarithmic rather than linear.
Leading-zero count, used in floating-point normalisation, is a priority encoder by another name: it reports the position of the highest set bit, which is exactly the same operation.

Design procedure

Use a priority encoder rather than a plain one unless the inputs are genuinely mutually exclusive by construction, which they rarely are.
Include and check the valid output. Without it, no active input and input zero active are indistinguishable.
Decide the priority direction deliberately and document it. Highest-index-wins and lowest-index-wins are both common, and assuming the wrong one produces a system that works until two events coincide.
For interrupt use, confirm that lower-priority requests remain pending rather than being discarded when a higher one is serviced.
For wide inputs, use a tree structure so the delay grows with log of the width rather than linearly.
Test with several inputs active simultaneously, which is the case the plain encoder gets wrong and the one that occurs in practice.

Key terms

Encoder: 2^n lines to an n-bit index. Assumes exactly one is active.
Priority encoder: Resolves multiple active inputs by a fixed rule, usually highest index.
Valid output: Distinguishes 'no input' from 'input zero'. Not optional.
Vector number: The encoded index an interrupt controller hands the processor.
Leading-zero count: The same operation, used for floating-point normalisation.
Tree structure: Keeps priority resolution logarithmic in the input count.

Worked example

Eight interrupt sources feed a priority encoder whose three-bit output indexes a vector table. Sources 2 and 5 assert at the same instant: the encoder reports 5, the processor vectors to that handler, and source 2 stays pending so it is serviced next. A plain encoder given the same inputs would OR 2 and 5 together and output 7 - vectoring to a handler for an interrupt that never occurred, while both real ones are lost. That failure needs two simultaneous interrupts to appear, which is exactly the condition testing is least likely to produce.

Common pitfalls

Decoders: One Number In, One Line Out

A decoder takes an n-bit number and asserts exactly one of 2^n outputs. It is the mechanism behind address decoding, memory word-line selection, instruction decoding and chip selects - anywhere a number has to become a physical selection. Its defining property is that exactly one output is active, which makes it structurally safe for anything that must be mutually exclusive.

How it is built

Each output is an AND of the address bits in true or complemented form, one unique combination per output. A 3-to-8 decoder is eight three-input ANDs with the inverters shared.
An enable input forces all outputs inactive, which provides a defined 'nothing selected' state and allows decoders to be cascaded into larger ones.
Cascading is how large decoders are built: the upper address bits enable one of several smaller decoders, each decoding the lower bits. A 6-to-64 is eight 3-to-8s enabled by another 3-to-8.
In a memory array the decoder drives the word lines, and it is physically enormous - one output per row. Its delay is a significant part of the memory's access time, which is why large memories are divided into banks.
Address decoding in a system maps regions rather than single addresses: the upper bits select the device and the lower bits pass through, so one decoder output covers a whole range.
Partial decoding ignores some upper bits to save logic, with the consequence that a device appears repeatedly at multiple addresses - aliasing that is harmless if documented and confusing if not.

Design procedure

Draw the memory map with explicit ranges before writing any decode logic, and check for gaps and overlaps.
Decide whether to decode fully or partially. Partial decoding is cheaper and creates address aliases that must be documented.
Use the enable input to guarantee a defined state at reset, before the address lines are driven.
For cascaded decoders, confirm the enable chain leaves exactly one leaf active for every address in range and none for addresses outside it.
Check the decode timing against the bus cycle: the chip select must be valid for the whole access, including the setup before the strobe.
Verify that no two outputs can assert simultaneously, which is the property the whole structure exists to provide.

Key terms

n-to-2^n decoder: One output active per input value.
Enable: Forces all outputs inactive, giving a defined 'nothing selected' state.
Cascading: Building a large decoder from small ones via the enable chain.
Word line: The decoder output that selects a row in a memory array.
Partial decoding: Ignoring upper bits to save logic, producing address aliases.
Address aliasing: The same device appearing at several addresses, from partial decoding.
Memory map: The assignment of address ranges to devices. Draw it before the logic.

Worked example

An 8-bit system with 64 kB of address space places RAM at 0x0000-0x7FFF, ROM at 0x8000-0xBFFF and peripherals at 0xC000-0xFFFF. Decoding only A15 and A14 gives four 16 kB regions and needs a 2-to-4 decoder - four gates. Full decoding of the peripheral region into eight 2 kB slots needs three more address bits and a second decoder enabled by the first. The peripheral at 0xC000 then also appears at 0xC800 and every 2 kB above it if those bits are not decoded, which is harmless when documented and a mystery when not.

Common pitfalls

Arithmetic Circuits: Where the Carry Chain Sets the Speed

Binary addition is built from a full adder - two operand bits and a carry in, producing a sum bit and a carry out - and everything else follows. Subtraction is addition of the two's complement, multiplication is repeated shifted addition, and comparison is subtraction with only the flags kept. The interesting engineering is not the arithmetic but the carry: it must propagate from the least significant bit to the most, and how quickly that happens determines the whole unit's speed.

How it is built

A full adder's sum is the three-input XOR and its carry out is the majority function of the three inputs. Both are small; the problem is that the carry out of one stage is the carry in of the next.
A ripple-carry adder chains n full adders, so the worst-case delay is n carry delays. It is the smallest adder and the slowest, and its delay grows linearly with width.
Carry-lookahead computes each stage's carry directly from the operands using generate and propagate signals, so the delay grows with the logarithm of the width rather than linearly - at a substantial cost in gates.
Generate means a stage produces a carry regardless of the carry in, which is A AND B. Propagate means it passes an incoming carry through, which is A XOR B. Every fast adder is built from these two.
Two's complement makes subtraction free: negate the subtrahend by inverting and adding one, and the same adder does both operations. The carry in to the least significant bit supplies that added one.
Overflow in two's complement is detected by the carry into the sign bit differing from the carry out of it - not by the carry out alone, which is the unsigned condition and a common confusion.

Design procedure

Choose the adder structure from the width and the timing budget. Below about eight bits a ripple carry is usually fine; above that the carry chain dominates.
For a synchronous design, check the adder's delay against the clock period including setup time, since the adder is very often the critical path.
Use two's complement throughout and let one adder do both addition and subtraction, rather than building separate units.
Compute both carry-out and overflow, and be explicit about which one the design uses - unsigned code needs the first and signed code the second.
For multiplication, decide between an iterative shift-and-add - small and slow - and an array or tree multiplier, which is large and completes in one cycle.
Test the boundaries specifically: the largest positive, the most negative, and the transitions across zero, which is where sign handling fails.

Key terms

Full adder: Two bits plus carry in, giving sum and carry out.
Ripple carry: Chained full adders. Delay grows linearly with width.
Carry-lookahead: Carries computed directly from the operands. Logarithmic delay, more gates.
Generate (G): A AND B - this stage makes a carry regardless of the input carry.
Propagate (P): A XOR B - this stage passes an incoming carry through.
Two's complement: Negation by inversion plus one. Makes one adder do subtraction too.
Overflow: Carry into the sign bit differs from carry out of it. Not the same as carry-out.

Worked example

A 32-bit ripple-carry adder with a 100 ps carry delay per stage takes 3.2 ns worst case, which caps the clock at about 300 MHz before anything else is considered. A carry-lookahead adder of the same width resolves in about five levels - roughly 500 ps - and runs comfortably past 1 GHz, at perhaps three times the gate count. That is the trade in one comparison, and it is why the adder is the first thing examined when a design misses timing.

Common pitfalls

Multiplexers and demultiplexers: selection as a primitive

A multiplexer selects one of several inputs and routes it to a single output, chosen by a binary select code. A demultiplexer does the reverse, routing one input to one of several outputs. They are the most reused blocks in digital design, and the reason is broader than data routing: a multiplexer with its inputs tied to constants is a lookup table, which means any Boolean function of n variables can be implemented by one 2^n-to-1 multiplexer with no other logic.

How it is built

A 2^n-to-1 multiplexer takes 2^n data inputs and n select lines, and passes the selected input through.
Internally it is an AND-OR structure: each input is gated by a decoded select term, and the results are ORed.
A demultiplexer is a decoder with the data line acting as an enable; all non-selected outputs take an inactive value.
Cascading small multiplexers builds larger ones: two 4-to-1 feeding a 2-to-1 gives an 8-to-1 at the cost of one extra level.
Propagation delay is set by the number of levels, so a tree of narrow multiplexers is slower than one wide one where the library allows.

Design procedure

Use a multiplexer wherever the design has an if/else on a data path; it is the direct hardware equivalent.
To implement an arbitrary function, wire the select lines to the variables and the data inputs to the truth table column.
Halve the multiplexer size by connecting one variable to the data inputs as itself or its complement, rather than to a select line.
For demultiplexers, define what the unselected outputs do - held, zeroed, or high-impedance - because it is a real design decision.
Check the enable behaviour, which is what makes cascading work and is where most cascade bugs live.

Key terms

Select lines: The binary code choosing which input is routed. n lines select among 2^n inputs.
Enable: An input that forces the whole block inactive, used to build larger blocks from smaller ones.
Mux-based logic: Implementing an arbitrary function by wiring a truth table to a multiplexer's data inputs.
Bus multiplexing: Selecting between whole multi-bit buses, using one multiplexer per bit with shared select lines.
One-hot: A demultiplexer output encoding where exactly one line is active at a time.

Worked example

A multiplexer as a universal function generator:

  Y = A'B'C + A'BC' + AB'C' + ABC     (three variables)

  An 8-to-1 mux with A,B,C on the select lines and the truth table
  column on the data inputs implements this with NO other gates:

    ABC : 000 001 010 011 100 101 110 111
    D   :  0   1   1   0   1   0   0   1

  And the halving trick, using a 4-to-1 instead:

    select on A,B; for each pair of rows express Y in terms of C

    AB=00 -> Y = C        D0 = C
    AB=01 -> Y = C'       D1 = C'
    AB=10 -> Y = C'       D2 = C'
    AB=11 -> Y = C        D3 = C

  Half the multiplexer, one inverter. This scales: an n-variable
  function needs only a 2^(n-1)-to-1 mux.

Common pitfalls

Encoders, priority encoders, and decoders

A decoder turns an n-bit code into one of 2^n active outputs; an encoder does the reverse, turning an active input into its binary index. The plain encoder has a flaw that makes it nearly useless in practice - it produces a meaningless result if two inputs are active at once - which is why the priority encoder, which resolves ties by a fixed ordering, is the one actually used. Interrupt controllers are built from it.

How it is built

An n-to-2^n decoder asserts exactly one output for each input code, and is the same structure a demultiplexer uses.
Address decoding is the dominant use: the high bits of an address select which peripheral or memory bank responds.
A plain 2^n-to-n encoder assumes exactly one input is active; two active inputs produce the OR of their codes, which is a valid-looking wrong answer.
A priority encoder resolves multiple active inputs by returning the index of the highest-priority one, and adds a valid output distinguishing 'no input' from 'input zero'.
The valid output is not optional: without it, all-inputs-inactive and input-0-active produce the same code.

Design procedure

Use a decoder with an enable for address decoding, and check that unmapped addresses assert nothing rather than aliasing.
Never use a plain encoder where two inputs can be simultaneously active; use a priority encoder even if you believe they cannot.
Always wire the valid output, and treat an invalid code as an error rather than as index zero.
Define the priority order explicitly in the design, since it becomes the system's interrupt or arbitration policy.
Watch decoder delay in address paths, since it sits directly in the critical path to memory.

Key terms

Address decoding: Using the high address bits to select which device responds to a bus transaction.
Priority encoder: An encoder that returns the highest-priority active input, tolerating multiple assertions.
Valid output: The flag distinguishing 'no input active' from 'input zero active'. Both give code 0 without it.
Aliasing: Two addresses selecting the same device because the decode ignores some bits. Usually a bug, sometimes deliberate.
One-hot decoding: The output form of a decoder: exactly one line active.

Worked example

Why the plain encoder is a trap, and what the valid bit is for:

  plain 4-to-2 encoder, inputs I3..I0

    I = 0100  ->  Y = 10   correct, input 2
    I = 0010  ->  Y = 01   correct, input 1
    I = 0110  ->  Y = 11   WRONG - the OR of 10 and 01, meaning
                           input 3, which is not active at all

  priority encoder, highest index wins

    I = 0110  ->  Y = 10, valid = 1     input 2, correctly
    I = 0000  ->  Y = 00, valid = 0     nothing active
    I = 0001  ->  Y = 00, valid = 1     input 0 active

  The last two rows produce the same Y. Only the valid bit tells
  them apart, which is why an interrupt controller that ignores it
  services a spurious interrupt 0 whenever nothing is pending.

Common pitfalls

Arithmetic circuits: from half adder to carry-lookahead

Binary addition is the one place in combinational design where the obvious implementation has a serious and well-understood performance problem. A ripple-carry adder is trivially correct and its delay grows linearly with width, because each bit must wait for the carry from the bit below. Every faster adder is a way of computing the carries without waiting for them to propagate, and that trade - area and complexity against delay - is the classic example of the design space.

How it is built

A half adder sums two bits producing sum and carry: sum is XOR, carry is AND.
A full adder sums two bits and a carry-in, producing sum and carry-out, and is built from two half adders and an OR.
A ripple-carry adder chains n full adders; its worst-case delay is n carry propagations, so a 32-bit add is 32 gate delays deep.
Carry-lookahead computes generate (G = A·B) and propagate (P = A xor B) per bit, then derives all carries in parallel from them.
Subtraction reuses the adder: A - B is A + NOT B + 1, which is why two's complement is the representation hardware uses.

Design procedure

Use ripple-carry for narrow widths or non-critical paths; its simplicity is worth more than its delay below about eight bits.
Use carry-lookahead or a carry-select structure once the adder sits in a critical path.
Build subtraction from the adder by inverting the subtrahend and forcing carry-in high, rather than as separate logic.
Detect signed overflow by comparing the carry into the sign bit with the carry out of it; they differ exactly when it overflowed.
Remember that unsigned overflow is the carry-out and signed overflow is that XOR - they are different conditions from the same adder.

Key terms

Half adder: Two inputs, sum and carry out. No carry in.
Full adder: Three inputs including carry in. The cell a multi-bit adder is built from.
Generate / propagate: G = A·B, this bit creates a carry; P = A xor B, this bit passes one through. The basis of lookahead.
Ripple delay: The linear worst case: the carry must cross every bit position in turn.
Overflow: Unsigned: carry out of the top bit. Signed: carry in and carry out of the sign bit differ.

Worked example

Where the delay goes, and how lookahead removes it:

  ripple-carry, 8 bits
    C1 needs C0, C2 needs C1, ... C8 needs C7
    worst case = 8 carry delays in series
    32-bit: 32 deep, and that is the critical path of the whole ALU

  carry-lookahead
    Gi = Ai · Bi          this bit generates a carry
    Pi = Ai xor Bi        this bit propagates one

    C1 = G0 + P0·C0
    C2 = G1 + P1·G0 + P1·P0·C0
    C3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0

    Every carry is a two-level function of the inputs, so all of
    them settle in the same two gate delays regardless of width -
    at the cost of gates that grow quadratically, which is why real
    designs block it into 4-bit groups and cascade those.

And the two overflows, from the same adder:

  0111_1111 + 0000_0001 = 1000_0000
    carry out = 0        -> no UNSIGNED overflow (127 + 1 = 128, fine)
    carry into sign = 1, out of sign = 0
                         -> SIGNED overflow (127 + 1 gave -128)

Combinational Blocks

Multiplexers: Selecting One of Many, and Building Anything

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Demultiplexers: One Source, Many Destinations

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Encoders and Priority: Turning Many Lines Into a Number

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Decoders: One Number In, One Line Out

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Arithmetic Circuits: Where the Carry Chain Sets the Speed

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Multiplexers and demultiplexers: selection as a primitive

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Encoders, priority encoders, and decoders

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Arithmetic circuits: from half adder to carry-lookahead

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

More in Digital Electronics