Combinational logic

Why two levels resist noise

An analogue signal carries its information in its exact shape, and that is its weakness. Every metre of cable adds a little random noise, and once noise is mixed in no circuit can tell it from signal. Amplifying a tired analogue signal amplifies the noise with it, so each leg of a long link leaves the signal permanently worse.

A digital signal gives up the shape entirely. Only two levels mean anything, logic 0 near 0 V and logic 1 near the supply voltage, and the receiver makes one crude test: is the level above the threshold or below it? Noise that would wreck an analogue waveform leaves a 1 still recognisably a 1. There is a genuine margin for error, and small noise sits inside it.

Describe the drawing

Three traces one above the other. The sent signal is a crisp eight-bit square wave; the received signal is smaller, sagging and rippling with noise, with amber dots marking the instant each bit is sampled against a dashed threshold; the regenerated signal below is a full-height square wave carrying exactly the original bits, the noise thrown away rather than amplified.

Better still, a digital signal can be regenerated. A repeater partway along the route reads each incoming pulse as 0 or 1, then issues a brand-new, full-height pulse at the nominal levels. It does not amplify the old signal; it replaces it, and the noise collected so far is discarded. While every sample still falls on the correct side of the threshold the message crosses a continent unchanged; if noise or timing error exceeds the margin before the next repeater, bits are misread, which is why repeaters are spaced to stay well inside it.

The six gates

The circuits that act on logic levels are gates. A gate's output depends only on its present inputs, so the whole behaviour fits in a truth table, one row per input combination. The simplest is NOT, one input, one output, always the opposite: input 0 gives 1, input 1 gives 0. The remaining five take two inputs, so their tables have four rows:

Three of these are worth learning as sentences. AND outputs 1 only when both inputs are 1. OR outputs 1 when at least one input is 1. EOR, exclusive-OR, outputs 1 when the inputs differ, and that last row is the one that separates it from OR. NAND and NOR are simply AND and OR with the answer inverted, drawn with a small circle on the output, and each of them alone can be wired up to build every other gate.

Combinational design is reading Boolean sentences in both directions. A specification in words becomes an expression, the expression becomes gates. The habit worth building is to write the full truth table, every input combination in binary counting order, because it brings out the cases you did not think about.

The half-adder

Binary arithmetic in one column is small enough to build by inspection. Adding bits A and B gives 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10, which is the number two, written as sum 0 carry 1. Compare the two output columns. The sum is 1 exactly when the inputs differ, and the carry is 1 exactly when both inputs are 1. Those are tables you already know.

So a half-adder is one EOR gate for the sum and one AND gate for the carry, wired to the same pair of inputs. It is the standard exam example of combinational design, a truth table recognised as a pair of known gates. Chain half-adders with provision for an incoming carry and you have the adder at the heart of every processor.