Combinational Logic Circuits

What makes a circuit combinational

A combinational circuit is one whose output at any instant is a function of the inputs present at that same instant, and nothing else. There is no memory anywhere in it: feed it the same inputs twice, in any order, separated by any amount of time, and it gives the same output both times. This is the property every gate from the earlier lessons already has, and it stays true of anything built purely by wiring gates together without feedback. The opposite case, where a circuit's output also depends on what happened before, is sequential logic, and it is the subject of the next lesson.

Designing a combinational circuit from a specification is mostly the two previous lessons applied in sequence: write the truth table from the word problem, read off a canonical SOP or POS expression, then simplify it with a Karnaugh map before drawing the gates. Analysing an existing circuit runs the same steps backward, tracing the gates to recover an expression and then a truth table. This lesson works through the specific combinational building blocks that appear everywhere in real designs, starting with the one every ALU needs first.

The half adder

A half adder adds two single bits, A and B, and produces a sum bit and a carry bit. Let us write its truth table directly: 0+0=00, 0+1=01, 1+0=01, 1+1=10 (that last row is binary 2, a sum of 0 with a carry of 1). Reading Sum and Carry off as separate functions of A and B gives two very familiar expressions – Sum = A ⊕ B and Carry = AB – which is exactly the XOR and AND truth tables from the gates lesson. A half adder is nothing more than one XOR gate and one AND gate, sharing the same two inputs.

The full adder

A half adder has no way to accept a carry coming in from a less significant bit, which makes it useless on its own for anything wider than one bit. A full adder fixes this by taking three inputs – A, B and a carry-in C_in – and producing a sum bit and a carry-out. The standard way to build one reuses two half adders rather than deriving new gate-level equations from scratch: the first half adder adds A and B, the second adds that partial sum to C_in, and an OR gate combines the two half adders' carry outputs, since at most one of them can be 1 at a time for any given input combination.

Chaining n full adders, with each stage's C_out wired into the next stage's C_in, builds an n-bit ripple-carry adder – the same addition worked by hand in the first lesson, now as hardware. Its one real weakness is named by its own description: a carry can only ripple from bit 0 up to bit n−1 one stage at a time, so the worst-case delay through the whole adder grows with the number of bits. The eighth lesson in this path, on fast adders, exists specifically to remove that growing delay.

Multiplexers

A multiplexer, or mux, is a data selector: it has several data inputs, a set of select lines, and one output, and it routes exactly one of the data inputs through to the output based on the binary value present on the select lines. A 2-to-1 mux has one select line and two data inputs (Y = S′·D0 + S·D1); a 4-to-1 mux needs two select lines to choose among four inputs, and in general a 2ⁿ-to-1 mux needs n select lines.

A mux is worth more attention than its simple description suggests, because any Boolean function can be implemented directly on a large enough multiplexer by wiring the function's own truth table onto the data inputs – each data input is simply the output value for one row. This is a useful trick for implementing a function in a technology library that is rich in muxes but short on arbitrary gates, and it is also how a multiplexer earns its very common second job as a clock or reset selector in real designs.

Demultiplexers, decoders and encoders

A demultiplexer is the mirror image of a mux: one data input, several outputs, and select lines that choose which single output the input is routed to, with every other output held at a fixed inactive value. A decoder is closely related but drops the data input entirely – it has n inputs and up to 2ⁿ outputs, and for every input combination it asserts exactly one output, which is why a decoder is sometimes described as a demultiplexer whose data input is tied permanently to 1.

Decoders appear throughout real designs wherever one of several resources has to be selected by an address – choosing one row of a memory array out of many, for example, is nothing more than a large decoder driven by the address bits.

An encoder does the opposite job to a decoder: it takes 2ⁿ inputs, of which exactly one is expected to be active, and produces the n-bit binary code of which input that was. A plain encoder assumes exactly one input is active and gives an undefined result if two are active at once, which is rarely acceptable in a real system. A priority encoder removes that assumption: when more than one input is active, it outputs the code of whichever active input has the highest priority, typically the one with the largest index, and it adds a valid-output signal so the rest of the circuit can tell "no input is active" apart from "input 0 is active."

Magnitude comparators

A magnitude comparator takes two multi-bit numbers, A and B, and reports whether A is less than, equal to, or greater than B. The equality output is the simplest of the three to build directly from earlier material: two numbers are equal exactly when every corresponding pair of bits matches, and XNOR already reports "these two bits match" for a single pair, so A = B is the AND of one XNOR per bit position. The less-than and greater-than outputs are built by comparing bits from the most significant position down, the same way long division compares digits from the left: the first position where A and B differ decides the whole result, and any lower-order bits no longer matter once that decision is made.