COMP 273 Winter 2012 4 - combinational logic 2 Jan.

19, 2012

Last class we discussed gates and circuits and how they could be used to compute the values
of logical expressions, formed by NOT, AND, OR and other operators. Such circuits are called
combinational logic circuits or combinational digital circuits. We will look at several more useful
examples today.

Arithmetic Circuits
How would we implement addition using these gates? Recall the algorithm from Lecture 1 for
adding two n-bit numbers, A and B :

Cn−1 Cn−2 . . . C2 C1 C0
An−1 An−2 . . . A2 A1 A0
+ Bn−1 Bn−2 . . . B2 B1 B0
———————————
Sn−1 Sn−2 . . . S2 S1 S0

The Ci are the carry bits, and Si are the sum bits. Note that C0 = 0 because there is no way to
carry in. (It will be clear later why we are defining this bit.) Also recall that we allow A and B to
be negative, namely we represent these numbers using twos complement.
The rightmost bit (or least significant bit) S0 of the sum is relatively simple to determine using
logical expressions and combinational circuits, as is the carry out bit C 1 .
A0 B0 S0 C1
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Thus,
S0 = A0 ⊕ B0
C1 = A0 · B0
The circuit that implements these is called a half adder. It has two inputs and two outputs. You
should be able to draw this circuit yourself.
The values of the other sum and carry bits are given as follows:
Ck Ak Bk Sk Ck+1
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

1
COMP 273 Winter 2012 4 - combinational logic 2 Jan. 19, 2012

which we can represent using sum-of-products circuits as defined by these expressions:

Sk = Ak · Bk · Ck + Ak · Bk · Ck + Ak · Bk · Ck + Ak · Bk · Ck

Ck+1 = Ak · Bk · Ck + Ak · Bk · Ck + Ak · Bk · Ck + +Ak · Bk · Ck
The box with the ’+’ below contains the combinational circuitry for implementing the truth table
above. Note that we have used a full adder for the least significant bit (LSB) and set C0 to 0.

A0 S0
+
B0

C1

A1
+ S1
B1

C2

A2 S2
+
B2

C3

A3 S3
+
B3

C4

etc

This circuit is called a ripple adder. To compute Sn−1 you need to allow the carries to ripple
through from bits 0 up to bit n − 1. This suggests that for large n (say 32 bits for A and B each),
you would have to allow a long delay. Later this lecture, we will discuss how this delay can be
avoided. For now, we turn to other useful combinational circuits.

Encoders
An encoder is a combinational logical circuit whose outputs specify which of a set of possible inputs
or groups of inputs has occured. The term encoder is used somewhat loosely. (There is no generally
agreed upon formal definition of an encoder that I am aware of.) Let’s look at a few examples.
A common example is a set of m input wires, such that exactly one of them has the value 1.
For example, consider a keyboard with 5 buttons and suppose that the mechanics of these buttons
are such that one and only one of these buttons is pressed down. (You may have seen something
like this on a children’s toy.) Such an encoder might be constructed using the truth table:

2
COMP 273 Winter 2012 4 - combinational logic 2 Jan. 19, 2012

A B C D E Y1 Y2 Y3
0 0 0 0 1 0 0 1
0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 1
0 1 0 0 0 1 0 0
1 0 0 0 0 1 0 1

Notice that if none of the button is pressed, or if multiple buttons is pressed (because you push
hard and break the mechanism), then the above truth table does not specify what the value of the
output variables Yi is. But this is not a problem, as long as the design is such that only one can
be pressed (1) at any time. Also note that if we use a sum-of-products representation of the above
encoder, then (because this uniquely specifies a circuit) we do know what the output would be for
any of the 25 inputs.
Suppose we allow for multiple buttons to be pressed and we want to explicitly say (in the truth
table) what the output of the circuit will be for each possible input. One way to do it is shown
below. Consider the following truth table and recall that X means “don’t care”. If no buttons are
pressed, the output is 000. If two or more buttons are pressed, then the output is the same as if
only the rightmost of these buttons was pressed.
A B C D E Y1 Y2 Y3 interpretation
0 0 0 0 0 0 0 0 none of the buttons is pressed
X X X X 1 0 0 1 E is pressed (and maybe A,B,C,D)
X X X 1 0 0 1 0 D and not E (but maybe A,B,C)
X X 1 0 0 0 1 1 C and neither E nor D (but maybe A,B)
X 1 0 0 0 1 0 0 etc
1 0 0 0 0 1 0 1 etc
For example, written as a sum-of-products, we would have

Y1 = (A · B · C · D · E) + (B · C · D · E)
Y2 = (D · E) + (C · D · E)
Y3 = E + (C · D · E) + (A · B · C · D · E)

A second example of an encoder that you should be familiar with is an output device (an LCD)
that displays a single digit from {0, 1, ..., 8, 9}. Each digit is defined by “turning on” a subset of the
line segments L1 , · · · , L7 . For example, when all seven of the line segments are on, the output digit
represents “8”, whereas when all lines except L2 are turned on, the output digit represents “0”. In
Exercises 2, you will write out the truth table for such an encoder.
L1

L4 L6
L2

ten buttons L5 L7
L3

3
COMP 273 Winter 2012 4 - combinational logic 2 Jan. 19, 2012

Decoders
A decoder is the opposite of an encoder. It takes a code (a binary number) as input, and turns on
one of several output wires (or some other event, i.e. subset of the output wires). For example,
here is a truth table for a 1-to-2 decoder:
A Y1 Y2
0 1 0
1 0 1

Here is the truth table for a “2-to-4 decoder”:

A B Y1 Y2 Y3 Y4
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1

You should be able to draw the circuit for these two examples.

Multiplexor (or selector)

One common way that decoders are used is to select from a set of possible input variables. The
circuit that does a selection is called a multiplexor. A multiplexor takes n inputs and chooses among
them. It is like a switch on a railroad. n different wires (tracks) arrive at a junction and the value
on one of the wires (the train on one of the tracks) is allowed through. A multiplexor is also called
a selector.
A multiplexor requires two types of inputs. The first carries the data (the trains) that can go
potentially through the circuit. The second carries a code saying which of the data goes through.
The simplest example of a multiplexor has two input wires that carry a bit of data – call these
A and B – and a selector input wire – call it S – that says which of A and B to select. It is called
a 1-bit multiplexor. (We saw this example last lecture.) The three circuits shown below show this
“one bit multiplexor” at three levels of increasing abstraction, from left to right.
Suppose instead we had four different inputs (A, B, C, D) and we wanted to select from them.
Then we would use a “two bit multiplexor” circuit, also shown below. The circuit on the right hides
the underlying circuitry of the one on the left.
Sometime the inputs A, B, C, D are not single bits themselves, but may have many bits, e.g. we
might be selecting one of four integers. In this case we might use the same notation show in the two
bit multiplexor figure, and if we wanted to explicitly show that the inputs had a certain number
(say 16) of bits, we would label the wires as such (by putting a little slash in each wire and writing
16. We will see examples later in the course and the notation will be come natural to you.

4
COMP 273 Winter 2012 4 - combinational logic 2 Jan. 19, 2012

One bit multiplexor

A
Y A 0
M
1
U Y
B B X

A
Y S
B
S
decoder

S
Two bit multiplexor

A
A 3 M
Y B 2
C 1 U Y
B D 0 X

C
S

D
4 M
U Y
decoder X
2

S S

Fast adder (“carry select”)

Let’s look at a few examples of how multiplexors can be useful. Recall the ripple adder discussed at
the beginning of the lecture. We can reduce the long delays for the carries to propagate, using the
following trick. Assume n is an even number. Divide the bits into low order bits (0, 1, . . . , n/2 − 1)
and high order bits (n/2, . . . , n − 1). Build one circuit to compute the sum for the low bits. Build
two circuits to compute the sum for the high order bits. Set the carry in bit for the LSB in the
lower order bit circuit to 0. Set the carry in bits for the LSB in the two high order circuits to 0 and
1, respectively. In the figure below, the “+” box is a 16 bit adder, rather than a one bit adder. (I
drew a slightly different looking figure in the lectures.)
The main idea here is that we don’t need to wait for the worse case in which the carries are
passed through the entire circuit (e.g. adding A = 011111 · · · 111 and B = 0000 · · · 0001. Instead,

5
COMP 273 Winter 2012 4 - combinational logic 2 Jan. 19, 2012

once the carries pass through the first n/2 full adders and the circuits stabilize, we know which of
the upper order sums we want. We just select it. Thus we have almost cut the computation time
in half. I write “almost” because we also have to do the selection, which takes time.
Note that we could repeat this idea, and speed up the computation of the n/2 bit additions, by
decomposing into additions of n/4 bits, and so on. Indeed it can be shown that the addition of two
n bit numbers can be done in O(log n) time, rather than O(n) times which is what the ripple adder
does. (Details omitted, since I just want to give you the idea.)
0

S7,S6, ..., S0
+
carry out bit
0

A15,A14,... A8
+ M
U S15,S14,..., S8
B15,B14,...,B8 X

Subtraction
Suppose we wanted to build a circuit for performing subtraction.
An−1 An−2 . . . A2 A1 A0
– Bn−1 Bn−2 . . . B2 B1 B0
———————————-
To perform A − B, we compute A + (−B). This requires us to negate B and then send the result
through the adder.
To negate a number that is represented in twos complement, we invert each of the bits and then
add 1 (Lecture 1). To do this with a combinational circuit is easy. We can use circuit similar to the
adder except that the B bits need to be inverted. To add one, we can set the carry in bit C0 to 1.
See Below. Binvert is the variable that specifies whether we are doing addition (0) or subtraction
(1). Note that we can use this variable both to select the B versus B, and for the C0 .

Arithmetic Logic Unit (ALU)

We can make the circuit even more powerful (and complicated) by also computing the operations
AND and OR for each of the bits. In the figure, a dotted square indicates the adder part of
the circuit only. The entire local circuit computes four different operations, namely, addition and
subtraction, AND, OR. Moreover, if we want to select from the operators, then we need yet another
a multiplexor. Notice that Binvert and Operation are related to each other. If the operation specifies
subtraction then Binvert should also be set to 1. Otherwise it should be set to 0.
A circuit such as this is called an arithmetic logic unit or ALU. Every computer has (at least)
one.

6
COMP 273 Winter 2012 4 - combinational logic 2 Jan. 19, 2012

Binvert Binvert
Operation
Ci (add, sub, and, or)

A0 Ai
M
+ M +
U Bi U M
B0 X
X U
X

A1
M
+
B1 U
X

A2 +
M
B2 U
X Op

A3 A
M
+
B3 U ALU
X

ETC
B