In this section, examples are used to illustrate how to implement a logic circuit from a Boolean expression or a truth table. Minimization of a logic circuit using the methods covered in Chapter 4 is also a logic circuit.

From a Boolean Expression to a Logic Circuit

Let's examine the following Boolean expression

X = AB + CDE

A brief inspection shows that this expression is composed of two terms, AB and CDE, with a domain of five variables. The first term is formed by ANDing A with B , and the second term is formed by ANDing C, D, and E. The two terms are then ORed to form the output X. These operations are indicated in the structure of the expression as follows:



Note that in this particular expression, the AND operations forming the two individual terms, AB and CDE, must be performed before the terms can be ORed.

To implement this Boolean expression, a 2-input AND gate is required to form the term AB, and a 3-input AND gate is needed to form the term CDE. A 2-input OR gate is then required to combine the two AND terms.

As another example, let's implement the following expression:


A breakdown of this expression shows that the terms A, B, and CD+EFare ANDed. The term CD+EFis formed by first ANDing C andDand ANDing E and F, and then ORing these two terms. This structure is indicated in relation to the expression as follow:

Before the expression can be formed, you must have the termCD+EF; but before you can get this term , you must have the terms CDand EF; but before you can get the termCD, you must haveD. So, as you can see, the logic operations must be done in the proper order.

The logic gates required to implementX=AB(CD+EF)

are as follows:

1.One inverter to form D

2.Two 2-input AND gates to form CD,and EF

3.One 2-input OR gate to formCD +EF

4.One 3-input AND gate to form X

The logic circuit for this expression is shown in Figure 3-1(a). Notice that there is a maximum of three gates and an inverter between an input and output in this circuit (from input D to output). Often the total propagation delay time through a logic circuit is a major consideration. Propagation delays are additive, so the more gates or inverters betweeninput and output, the greater the propagation delay time.

FIGURE 3-1Logic circuits for X=AB(CD+EF)=ABCXD+ABEF




Unless an intermediate term, such as CD+EFin Figure 3-1(a), is required as an output for some other purpose, it is usually best to reduce a circuit to its SOP form. The expression is converted to SOP as follows, and the resulting circuit is shown in Figure 3-1(b).


From a Truth Table to a Logic Circuit

If you begin with a truth table instead of an expression, you can write the SOP expression from the truth table and then implement the logic circuit. Table specifies a logic function.

The Boolean SOP expression obtained from the truth table by ORing the product terms for which X = 1 (the blue rows) is


The first term in the expression is formed by ANDing the three variables A, B, and C. The second term is formed by ANDing the three variablesA,B, and C.

The logic gates required to implement this expression are as follows: three invert-ers to form theA, B, and Cvariables; two 3-input AND gates to form the terms ABC and AB C; and one 2-input OR gate to form the final output function,.ABC+AB C

The implementation of this logic function is illustrated in Figure 3-3


Logic circuit forX = ABC+AB C



3.2 .1The Full-Adder

As you saw , a single full-adder is capable of adding two 1-bit numbers and an input carry. To add binary numbers with more than one bit, additional full-adders must be used. When one binary number is added to another, each column generates a sum bit and a 1 or 0 carry bit to the next column to the left, as illustrated here with 2-bit numbers.

To add two binary numbers, a full-adder is required for each bit in the numbers. So for 2-bit numbers, two adders are needed; for 4-bit numbers, four adders are used and so on. The carry output of each adder is connected to the carry input of the next higher-order adder , as shown in Figure 3-4 for a 2-bit adder. Notice that either a half-adder can be used for the least significant position or the carry input of a full-adder can be made 0 (grounded)because there is no carry input to the least significant bit position.


Block diagram of a basic 2-bit parallel adder using two full-adders.

In Figure 3-4 the least significant bits (LSB) of the two numbers are represented by A1and B1. The next higher-order bits are represented by A2and B2. The three sum bits are Σ1,Σ2 and Σ3. Notice that the output carry from the left-most full-adder becomes the most significant bit (MSB) in the sum, Σ3.


Determine the sum generated by the 3-bit parallel adder in Figure 3-5 and show the intermediate carries when the binary numbers 101 and 011 are being added.


SolutionThe LSBs of the two numbers are added in the right-most full-adder.The sum bits and the intermediate carries are indicated in blue in Figure3-5

The full-adder accepts two input bits and an input carry and generates a sum output and an output carry.


Logic symbol for a full-adder





Full-adder truth table

Full-Adder LogicThe full-adder must add the two input bits and the input carry. From the half-adder you know that the sum of the input bits A and B is the exclusive-OR of those two variables, AB. For the input carry (Cin) to be added to the input bits, it must be exclusive-OR with A B, yielding the equation for the sum output of the full-adder.

Σ=( AB)Cin


This means that to implement the full-adder sum function, two 2-input exclusive-OR gates can be used. The first must generate the term A B, and the second has as its inputs the output of the first XOR gate and the input carry, as illustrated in Figure 6-4(a).

The output carry is a 1 when both inputs to the first XOR gate are 1s or when both inputs to the second XOR gate are 1s. You can verify this fact by studying Table 3-1. The output carry of the full-adder is therefore produced by the inputs A ANDed with B and AB ANDedwith Cin.



(a) Logic required to form the sum of three bits


(b) Complete logic circuit for a full-adder (each half-adder is enclosed by a shadedarea)


These two terms are ORed, as expressed in Equation . This function is implemented and combined with the sum logic to form a complete full-a circuit.

There are two half-adders, connected as shown in the block diagram of Figure 3-8(a), with their output carries ORed. The logic symbol shown in Figure 3-8(b) will normally be used to represent the full-adder.

Figure 3-8 (a) Arrangement of two half-adders to form a full-adder

(b) Full-adder logic symbol




The basic function of a comparator is to compare the magnitudes of two binary quanti-ties to determine the relationship of those quantities. In its simplest form, a comparator circuit determines whether two numbers are equal.


As you learned , the exclusive-OR gate can be used as a basic comparator be-cause its output is a 1 if the two input bits are not equal and a 0 if the input bits are equal. Figure 3-9 shows the exclusive-OR gate as a 2-bit comparator.

Figure 3-9

In order to compare binary numbers containing two bits each, an additional exclu-sive-OR gate is necessary. The two least significant bits (LSBs) of the two numbers are compared by gate G1and the two most significant bits (MSBs) are compared by gate G2, as shown in Figure 6-16. If the two numbers are equal, their corresponding bits are the same, and the output of each exclusive-OR gate is a 0. If the corresponding sets of bits are not equal, a 1 occurs on that exclusive-OR gate output.

In order to produce a single output indicating an equality or inequality of two num-bers, two inverters and an AND gate can be used, as shown in Figure 3-10. The output of each exclusive-OR gate is inverted and applied to the AND gate input. When the two input bits for each exclusive-OR are equal, the corresponding bits of the numbers are equal, pro-ducing a 1 on both inputs to the AND gate and thus a 1 on the output. When the two num-bers are not equal, one or both sets of corresponding bits are unequal, and a 0 appears on at least one input to the AND gate to produce a 0 on its output. Thus, the output of the AND gate indicates equality (1) or inequality (0) of the two numbers.

General format: Binary number A→ A1A0 Binary number B→B1B0


Logic diagram for equality comparison of two 2-bit numbers.


Example 3-1 illustrates this operation for two specific cases. The exclusive-OR gate and inverter are replaced by an exclusive-NOR symbol. Recall that in the system application for Chapter 3, you used this basic type of circuit to compare two 8-bit numbers.

As you know , the basic comparator can be expanded to any number of bits. The AND gate sets the condition that all corresponding bits of the two number must be equal if the two numbers themselves are equal.


In addition to the equality output, many integrated circuit comparators provide additional outputs that indicate which of the two binary numbers being compared is the larger. That is, there is an output that indicates when number A is greater than number B (A > B) and an output that indicates when number A is less than number B (A < B), as shown in the logic symbol for a 4-bit comparator in Figure 3-11.

Figure 3-11 Logic symbol for 4-bit comparator with inequality indication.


To determine an inequality of binary numbers A and B, you first examine the high-est-order bit in each number. The following conditions are possible:

1.If A3= 1 and B3= 0, number A is greater than number B.

2.If A3= 0 and B3= 1, number/I is less than number B.

3.If A3= B3, then you must examine the next lower bit position for an inequality.

These three operations are valid for each bit position in the numbers. The general procedure used in a comparator is to check for an inequality in a bit position, starting with the highest order bits (MSBs). When such an inequality is found, the relationship of the two numbers is established, and any other inequalities in lower-order bit positions must be ignored because it is possible for an opposite indication to occur; the highest-order indica-tion must take precedence.

An MSI 4-Bit Magnitude Comparator

The 74HC85 is an MSI comparator that is also available in other IC families. The pin dia-gram and logic symbol are shown in Figure 3-12. Notice that this device has all the inputs and outputs of the generalized comparator previously discussed and, in addition, has three cascading inputs: A < B,A =B,A> B. These inputs allow several comparators to be cas-caded for comparison of any number of bits greater than four. To expand the comparator, the A < B, A = B, and A > B outputs of the lower-order comparator are connected to the corresponding cascading inputs of the next higher-order comparator. The lowest-order comparator must have a HIGH on the A = B input and LOWson the A < B and A > B inputs.


Pin diagram and logic symbol for the 74HC8S 4-bit magnitude comparator (pin numbers are inparentheses).



Use 74HC85 comparators to compare the magnitudes of two 8-bit numbers. Show the comparators with proper interconnections.

SolutionTwo 74HC85s are required to compare two 8-bit numbers. They are connected as shown in Figure 3-13, in a cascaded arrangement.


An 8-bit magnitude comparator using two 74HC85s.

Related ProblemExpand the circuit in Figure 3-13 to a 16-bit comparator.




3.3.1 The basic function of decoder

The basic function of a decoder is to detect the presence of a specified combination of bits (code) on its inputs and to indicate the presence of that code by a specified output level. In its general form, a decoder has n input lines to handle n bits and from one to output lines to indicate the presence of one or more n-bit combinations. In this sec-tion, several decoders are introduced. The basic principles can be extended to other types of decoders.

The Basic Binary Decoder

Suppose you need to determine when a binary 1001 occurs on the inputs of a digital circuit. An AND gate can be used as the basic decoding element because it produces a HIGH out-put only when all of its inputs are HIGH. Therefore, you must make sure that all of the in-puts to the AND gate are HIGH when the binary number 1001 occurs; this can be done by inverting the two middle bits (the 0s), as shown in Figure 3-14.


Decoding logic for the binary code 1001 with an active-HIGH output.

The logic equation for the decoder of Figure 3-14(a) is developed as illustrated in Figure 3-14(b). You should verify that the output is 0 except when A0 = 1, A1 = 0, A2 = 0, and A3 = 1 are applied to the inputs. A0 is the LSB and A3 is the MSB. In the represen-tation of a binary number or other weighted code in this book, the LSB is the right-most bit in a horizontal arrangement and the topmost bit in a vertical arrangement, unless specified otherwise.

If a NAND gate is used in place of the AND gate in Figure 3-14, a LOW output will indicate the presence of the proper binary code, which is 1001 in this case.


Determine the logic required to decode the binary number 1011 by producing a HIGH level on the output.

SolutionThe decoding function can be formed by complementing only the variables that appear as 0 in the desired binary number, as follows:

X=A3A2A1A0        (1011)

This function can be implemented by connecting the true (uncomplemented) variables| A0, A 1, and A3 directly to the inputs of an AND gate, and inverting the variable A2 before applying it to the AND gate input. The decoding logic is shown in Figure 3-15.


Decoding logic for producing a HIGH output

when 1011 is on the inputs.

Related ProblemDevelop the logic required to detect the binary code 10010 and produce an active-LOW output.



The Half-Adder

Recall the basic rules for binary addition .

0 + 0= 0

0+ 1=1

1 + 0=1

1+ 1 = 10

The operations are performed by a logic circuit called a half-adder.

The half-adder accepts two binary digits on its inputs and produces two binary digits on its outputs, a sum bit and a carry bit

A half-adder is represented by the logic symbol in Figure 3-16.


Logic symbol for a hay-adder.

Half-Adder LogicFrom the logical operation of the half-adder as stated in Table 3-2,expressions can be derived for the sum and the output carry as functions of the inputs. Notice that the output carry (Cout) is a 1 only when both A and B are 1s; therefore, Coutcan be expressed as the AND of the input variables.


Now observe that the sum output (Σ) is a 1 only if the input variables, A and B, are not equal. The sum can therefore be expressed as the exclusive-OR of the input variables.



Half-odder truth table.





















Σ= sum

Cout= output carry

A and B = input variables (operands)

From Equations, the logic implementation required for the half-adder function can be developed. The output carry is produced with an AND gate with A and B on the inputs, and the sum output is generated with an exclusive-OR gate, as shown in Figure 3-17.


Half-adder logic diagram.


3.3.2The Basic Binary Decoder

Suppose you need to determine when a binary 1001 occurs on the inputs of a digital circuit. An AND gate can be used as the basic decoding element because it produces a HIGH out-put only when all of its inputs are HIGH. Therefore, you must make sure that all of the in-puts to the AND gate are HIGH when the binary number 1001 occurs; this can be done by inverting the two middle bits (the 0s), as shown in Figure3-18 .

Figure3-18 Decoding logic for the binary code 1001 with an active-HIGH output.


1) For the given Input and Output relations, make a truth table .
2) Write product boolean for each '1' and then OR .
3)  Apply rules of simplification .

Example 3-4   
















   Truth Table for input and output

                          Figure  3-19

Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8