0195136047.pdf

6.1 DIGITAL BUILDING BLOCKS 281

Thus far we have shown how to find the truth table for a given combination of logic blocks.
The inverse process, that of finding an interconnection of blocks to produce a given truth table,
is known aslogic synthesis. Even though the resulting circuit is not necessarily minimal (thereby
assuming a minimum number of components), the truth table can be realized by the two standard
forms:sum of products(SOP) andproduct of sums(POS). SOP can be implemented by using
two-level (AND–OR) networks, where each product term requires an AND gate (except for a
term with a single variable) and the logic sum of these terms is obtained by using an OR gate with
inputs from the AND gates or the single variables. POS can be implemented by using two-level
(OR–AND) networks, where each term requires an OR gate (except for a term with a single
variable) and the product of these terms is obtained by using an AND gate with inputs from the
OR gates or the single variables.
Figure 6.1.8 shows four possible gates with an output of 1 only. For example, the truth table
of Figure 6.1.9(a) can be realized by the interconnection of gates shown in Figure 6.1.9(b) with
the resulting Boolean expressionF=AB ̄ +AB. The SOP or the POS method can be used to
realize any truth table, but it is not efficient and minimal; usually other realizations with fewer
blocks can be found. The realization can often be simplified by using the distributive law and the
simple theoremA+A ̄=1. For example, the expressionF=AB ̄ +ABcan be rewritten as
F=

(

A ̄+A

)
Bby means of the distributive law, and can be simplified asF=B, sinceA ̄+A=1.
Finding minimal realizations with a minimum number of components is the challenge inlogic
design.
Addition of binary numbers is so common that a binaryhalf-adderand afull-adder(FA)
have become building blocks in their own right, and are available in IC form. The representation
of the half-adder, which can add single-digit binary numbers, is shown in Figure 6.1.10(a) along
with its truth table.Nfull adders are needed to add together twoN-digit binary numbers. Figure
6.1.11 illustrates the addition of 4-digit binary numbers.

A

Output 1 only if A = 1, B = 1
(a) (b)

(c) (d)

Output 1 only if A = 1, B = 0

Output 1 only if A = 0, B = 1 Output 1 only if A = 0, B = 0

F

F

B

B

F

A

B

F

A

A

B

Figure 6.1.8Four possible gates with an output

of 1 only.

A

1st level 2nd level

F = AB + AB

B

(a)

AB

00

01

10

11

F

0

1

0

1

(b)

Figure 6.1.9SOP realization ofF=AB ̄ +AB.(a)Truth table.(b)Interconnection of gates.