Combinational circuits: decoder, mux, full adder, PLA

On the previous page you saw gates. On this page you will learn four building blocks made from them that are found in every processor: the decoder, the multiplexer, the full adder and the PLA. All of them are combinational circuits: the output depends only on the current inputs, and nothing is remembered. Circuits that remember (latch, register) are the topic of week 4.

On the midterm these structures bring short-answer questions: “if the input is 101, which output is 1?”, “how many selects does a 32-to-1 mux need?”, “the output of a full adder for 1+1+0?”, “write the carries of a 4-bit adder”. You will see all of them in the LC-3 too: register selection is done with a decoder, the ALU input with a mux, and addition with an adder.

Decoder

A decoder with $n$ inputs has $2^n$ outputs. It reads the input as a binary number and sets the output with that number to 1 and all the rest to 0.

2-to-4 decoder
A1 A0 | D0 D1 D2 D3
 0  0 |  1  0  0  0
 0  1 |  0  1  0  0
 1  0 |  0  0  1  0
 1  1 |  0  0  0  1

D0 = A1'A0'   D1 = A1'A0   D2 = A1A0'   D3 = A1A0

Each output is an AND gate and produces exactly one minterm. Therefore:

TIP · Decoder + OR = any function. If the minterm list of a function is $\Sigma m(1, 2, 4, 7)$, connect the D1, D2, D4, D7 outputs of a 3-to-8 decoder to an OR gate. Done.

Where is it used? To decode the opcode of an instruction (which instruction?), to decode an address in memory (which row?), to choose which register to write in a register file.

Multiplexer (mux)

A mux chooses one of $2^n$ data inputs and passes it to the output. $n$ select lines decide which one passes.

The equation of a 2-to-1 mux:

$Y = S'A + SB$

A 4-to-1 mux is a 2-to-4 decoder with four AND gates and an OR gate: the decoder decodes the select, and the chosen AND gate passes its own data input.

4-to-1 mux, I0..I3 = 1, 0, 0, 1
S1 S0 = 11 → I3 → output 1
S1 S0 = 01 → I1 → output 0

Building a function with a mux

You can build a function of $n+1$ variables with a $2^n$-to-1 mux. Connect the first $n$ variables to the select. Split the table into groups of two rows according to these variables. In each group F, in terms of the last variable (C), is one of these four things: 0, 1, C, C’.

Example: $F(A,B,C) = \Sigma m(0, 3, 4, 5)$, select = AB.

Adders

Half adder

It adds two bits: $S = A \oplus B$, $C = AB$. It cannot take an incoming carry, so it is useful only at the rightmost bit.

Full adder

It adds three bits: A, B and the $C_{in}$ coming from the right. It has two outputs: the right bit of the sum, S, and the $C_{out}$ going to the left.

Do not memorize the table, just add the three bits: 1+1+1 = 3 = 11 → Cout = 1, S = 1. The equations:

$S = A \oplus B \oplus C_{in} \qquad C_{out} = AB + AC_{in} + BC_{in}$

S is 1 when the number of 1s is odd (odd parity). Cout is 1 when at least two inputs are 1 (majority).

Ripple-carry adder

To add two $n$-bit numbers, $n$ full adders are placed side by side. The $C_{out}$ of each is connected to the $C_{in}$ of the one on its left. The $C_{in}$ of the rightmost is 0. The carry moves from right to left, “rippling” along.

Worked example: 0111 + 0101

carry in:   1 1 1 0
            0 1 1 1    (7)
          + 0 1 0 1    (5)
          ---------
            1 1 0 0    (12), Cout = 0

bit0: 1+1+0 = 10 → S=0, c=1
bit1: 1+0+1 = 10 → S=0, c=1
bit2: 1+1+1 = 11 → S=1, c=1
bit3: 0+0+1 = 01 → S=1, c=0

This adder is the same circuit for unsigned and 2’s complement. In 2’s complement, because 0111 + 0101 = 1100 (two positives → negative), there is overflow; this is the hardware counterpart of the rule from week 2. For subtraction, every bit of B is NOTed and the rightmost $C_{in}$ is made 1: $A + B' + 1 = A - B$.

PLA (programmable logic array)

A PLA is a ready-made piece of hardware for the idea “build every function as SOP”. It has two layers:

1. AND array: produces product terms from the inputs and their complements.
2. OR array: connects the desired terms to the OR gate of each output.

The connections are “programmed”: which AND gate goes to which OR is chosen. A term can be shared by several outputs.

Example: $F_1 = \Sigma m(0, 3)$, $F_2 = \Sigma m(3, 5, 6)$. The distinct minterms needed are 0, 3, 5, 6. 4 gates are enough in the AND array; the gate of m3 is connected to both OR gates.

A full PLA with 3 inputs produces at most 8 distinct minterms. With $n$ inputs, $2^n$.

Combinational versus sequential

Common mistakes