03Wiring and combinational circuits

1. Selecting and joining bits is wiring

An 8-bit bus is eight wires under one name, and some of those wires can be named on their own. Bit 7 of x is a 1-bit signal, the top wire; bits 7 to 4 of x are a 4-bit signal, the top four wires. With these fixed bit positions, no logic operation is needed: the same connections carry a second label. Selecting a position that changes with an input is different; it needs selection logic.

Joining goes the other way. Put the four wires of a above the four wires of b and the result is an 8-bit bus with a in bits 7 to 4 and b in bits 3 to 0. With a = 1011 and b = 0010 it reads 10110010. Reordering, such as writing the bits of x backwards, is wiring too: the same wires in a different order. Each language has its own notation for these; the idea does not change.

2. A multiplexer chooses one of its inputs

A multiplexer, or MUX, has data inputs, a select input and one output; the select says which data input reaches the output. The smallest MUX has data inputs a and b and a 1-bit sel: y is a when sel = 0 and b when sel = 1. In gates, y = (NOT sel AND a) OR (sel AND b); the select forces one AND term to 0 and the other passes its data bit through.

Set a = 1 and b = 0, then press sel back and forth. y follows whichever input sel points at.

k select bits address 2^k inputs; a MUX between buses is this circuit once per bit, sharing sel. It is the hardware form of "if sel then b else a": both inputs are present all the time, and the MUX only decides which one is seen.

3. A decoder turns a number into a position

A decoder takes an n-bit number and has 2^n outputs numbered 0 to 2^n − 1. Exactly one output is 1, the one whose number equals the input; a pattern with a single 1 is called one-hot. The decoder below reads a1 a0 as a number, a1 being the more significant bit, and drives y3 to y0: input 10, which is two, makes y2 1. Each output is one AND of the inputs or their inversions: y2 = a1 AND NOT a0.

Press a1 and a0 through all four values and watch the single 1 move. Unlike a MUX, which selects a data input, this decoder converts an input code into one-hot output enables. Routing a separate data input to one of several outputs is the job of a demultiplexer.

4. An adder is XOR for the sum and a majority for the carry

1 + 1 is 10, two, which needs two bits, so the half adder has two outputs: sum = a XOR b, 1 when exactly one input is 1, and carry = a AND b, 1 only for 1 + 1.

Every position above the lowest also receives the carry from below, so it needs a full adder with inputs a, b and cin. sum = a XOR b XOR cin is 1 when an odd number of inputs are 1; cout is 1 when two or more are 1, the majority from the previous unit. Together, cout sum is the count of 1s among the inputs: with all three inputs 1 the count is three, 11, so cout = 1 and sum = 1. Confirm it, then try the rows with two 1s.

5. Fixed bit connections need no selection logic

Selecting fixed positions, joining and reordering bits are wiring operations: they do not themselves require logic gates. Physical wires still occupy routing resources and have delay. A MUX, a decoder and an adder generally require logic between the inputs and the output, and the output is what they compute. In code each may be one short line; the difference is in what gets built.

Caution. Choosing between two distinct buses with a changing select bit needs a MUX, because the connection depends on sel. The comparison here assumes general inputs; synthesis can remove logic when its inputs are identical or constants.

6. Variation: a 4-bit ripple adder

Four full adders in a row add two 4-bit numbers. Stage i adds bit i of a, bit i of b and the cout of stage i − 1; stage 0 gets a cin of 0, and the cout of stage 3 is a fifth result bit. Here is 5 + 6, which is 0101 + 0110.

sum read from stage 3 down is 1011, which is 11, with a final cout of 0. Now work 9 + 8, which is 1001 + 1000, through the same four rows on paper.

7. Summary

• Selecting fixed bit positions, joining and reordering bits need no logic operation.
• A MUX chooses one of 2^k inputs with k select bits; a decoder turns an n-bit number into one 1 among 2^n outputs; a full adder adds three bits, sum their XOR and cout their majority.
• Wiring uses physical routing resources; data-dependent selection and arithmetic generally need logic as well.

The next chapter asks what an adder's result means when the carry does not fit, and how one pattern reads as positive or negative.