09-01-2014, 12:57 PM
Combinational Logic Design
Combinational Logic.pdf (Size: 172.44 KB / Downloads: 230)
INTRODUCTION
The foundations for the design of digital logic circuits were established in the
preceding chapters. The elements of Boolean algebra (two-element “switching
algebra”) and how the operations in Boolean algebra can be represented
schematically by means of gates (primitive devices) were presented in Chapter
2. How switching expressions can be manipulated and represented in different
ways was the subject of Chapter 3, which also presented various ways of imple-
menting such representations in a variety of circuits using primitive gates.
With all of the tools for the purpose now in hand, we will be concerned in
this chapter with the design of more complex logic circuits. Circuits in which all
outputs at any given time depend only on the inputs at that time are called com-
binational logic circuits. The design procedures will be illustrated with impor-
tant classes of circuits that are now universal in digital systems.
The approach taken is to examine the tasks that a combinational logic cir-
cuit is intented to perform and then identify one or more circuits that can per-
form the task. One circuit may have some specific advantages over others, but
it may also have certain deficiencies. Often one factor can be improved, but
only at the expense of others. Some important factors are speed of operation,
complexity or cost of hardware, power dissipation, and availability in prefabri-
cated units. We will take up a number of different operations that are useful in
different contexts and show how appropriate circuits can be designed to carry
out these operations.
Full Adder
An alternative approach for the addition of two n-bit numbers is to use a sep-
arate circuit for each corresponding pair of bits. Such a circuit would accept the
2 bits to be added, together with the carry resulting from adding the less signif-
icant bits. It would yield as outputs the 1-bit sum and the 1-bit carry out to the
more significant bit. Such a circuit is called a full adder. A schematic diagram is
shown in Figure 1b. The 2 bits to be added are xi and yi , and the carry in is Ci.
The outputs are the sum Si and the carry out Ci+1. The truth table for the full
adder and the logic maps for the two outputs are shown in Figure 2.
Ripple-Carry Adder
The problem of adding two multidigit binary numbers has the following form.
Two n-bit binary numbers are available, with all digits being presented in par-
allel. The addition is performed by using a full adder to add each correspond-
ing pair of digits, one from each number. The full adders are connected in
tandem so that the carry out from one stage becomes the carry into the next
stage, as illustrated for the case of four-digit numbers in Figure 4. Thus, the
carry ripples through each stage. For binary addition, the carry into the first
(least significant) stage is 0. The last carry out (the overflow carry) becomes the
most significant bit of the (n + 1)-bit sum.
Carry-Lookahead Adder
In contemplating the addition of two n-digit binary numbers, we were appalled
by the thought of a single combinational circuit with all those inputs. So we con-
sidered the repeated use of a simpler circuit, a full adder, with the least possi-
ble number of inputs. But what is gained in circuit simplicity with this approach
is lost in speed. Since the speed is limited by the delay in the carry function,
some of the lost speed might be regained if we could design a circuit—just for
the carry—with more inputs than 2 but not as many as 2n. Suppose that several
full-adder stages are treated as a unit. The inputs to the unit are the carry into
the unit as well as the input digits to all the full adders in that unit. Then per-
haps the carry out could be obtained faster than the ripple carry through the
same number of full adders.
Two’s-Complement Adder and Subtractor
Recall from Chapter 1 that when the addition of 2 two’s complement binary
numbers produces a final carry, it can be ignored. However, it is necessary to
detect the overflow that can occur when the result of the addition is out of
range.3 In Chapter 1 it was concluded that an arithmetic overflow could be de-
tected if the carry in and carry out of the most significant bit position are dif-
ferent. Thus, the overflow can be detected with one additional Exclusive-OR
gate. The two’s complement adder is not much different from the binary adder
for unsigned numbers.
What about subtraction? We already suggested that subtraction should be
carried out by complementing the subtrahend and adding. So the task is to de-
sign a circuit whose output is the two’s complement of the input, and use its
output as one input to an adder. Such a circuit can be designed easily, but why
should a system contain some hardware dedicated to addition and other hard-
ware dedicated to subtraction? If the only difference between these two circuits
is a circuit that computes the two’s complement, then why not design a circuit
where either addition or subtraction can be selected with one additional input?
When this additional input is, say, 0 the circuit performs addition, and when the
input is 1 the circuit performs subtraction. It sounds easy; a representation of
the circuit can be derived using the techniques of Chapter 3, but an elegant so-
lution exists that we describe next.