CHAPTER FIVE

Combinational Logic
DIGITAL LOGIC DESIGN (EENG2041 )

By Ahmed S.
 Digital System
 The digital system consists of two types of circuits, namely
Combinational Logic Circuits and
Sequential Logic Circuits
 A combinational Logic Circuit:
Consists of logic gates, where outputs are at any instant and are determined only
by the present combination of inputs.
 A Sequential Logic Circuits
 Contain logic gates as well as memory cells.
And Their outputs depend on the present inputs as well as on the states of memory
elements.
 Combinational Logic Circuit
• A combinational logic circuit consists of input variables, logic gates, and
output variables.
• The logic gates accept signals from inputs and output signals are
generated according to the logic circuits employed in it
• Figure below shows a block diagram of a combinational logic circuit.
• There are n number of input variables coming from an electric source
and m number of output signals go to an external destination.
 Design Procedure OF Combinational Logic Circuit
 Any combinational circuit can be designed by the following steps of design procedure.
[Link] the problem.
[Link] the number of input variables and output functions.
[Link] the input and output variables with letter symbols.
[Link] the truth table which completely defines the relationship between the input variables
and output functions.
[Link] the simplified Boolean expression by using any method of minimization - algebraic
method, or Karnaugh map method.
[Link] a logic diagram for the simplified expression using logic gates.
 The output Boolean functions from the truth table are simplified by any available method, such as
algebraic manipulation, the K-map method, or the tabulation procedure.
 Design Constraints
• However, in any particular application, certain restrictions, limitations, and criteria will serve as a guide in
the process of choosing a particular algebraic expression.
• A practical design method would have to consider such constraints as
1. Minimum number of gates,
2. Minimum number of inputs to a gate,
3. Minimum propagation time of the signal through the circuit,
4. Minimum number of interconnections, and
5. Limitations of the driving capabilities of each gate.
• Since all these criteria cannot be satisfied simultaneously, and since the importance of each constraint is
dictated by the particular application, it is difficult to make a general statement as to what constitutes an
acceptable simplification.
• In most cases, the simplification begins by satisfying an elementary objective, such as producing a
simplified Boolean function in a standard form, and from that proceeds to meet any other performance
criteria.
 Design the Following Combinational Logic Circuit
• Example 1:- Design a logic circuit that has three inputs, A, B, and C, and whose output
will be HIGH only when a majority of the inputs are HIGH.
• Example 2:- Design a combinational circuit with four inputs and four outputs. The
output generates the 2's complement of the input binary number.
• Example 3:- Design a combinational circuit with three inputs, x, y, and z, and three
outputs, A, B, and C. When the binary input is 0, 1, 2, or 3, the binary output is one
greater than the input. When the binary inputs is 4, 5, 6, or 7, the binary output is one
less than the input.
• Example 4:- Design a logic circuit whose output is HIGH whenever A and B are both
HIGH as long as C and D are either both LOW or both HIGH.
• Example 5:- Develop a logic circuit with four input variables that will only produce a 1
output when exactly three input variables are 1s.
• Example 6:- Design a combinational circuit ,which convert a 4-bit binary to Gray code.
 cont…
• Example 7:- Design a combinational circuit ,which convert a 4-bit Gray
code to binary.
• Example 8:- Design a combinational circuit ,which convert BCD-to-Seven-
Segment decoder
 Universal Logic Gates (NAND)
 NAND gates are sometimes called universal gates because they can be
used to produce the other basic Boolean functions.
 NAND Implementation
 The NAND gate is said to be a universal gate because any digital system can
be implemented with it.
 To facilitate the conversion to NAND logic, it is convenient to use the two
alternate graphic symbols shown in Figure below.

FIGURE. Two graphic symbols for a NAND gate

 The AND-invert graphic symbol consists of an AND graphic symbol followed

by a small circle.
 The invert-OR graphic symbol consists of an OR graphic symbol that is
preceded by small circles in all the inputs.
 Either symbol can be used to represent a NAND gate.
 cont…
To obtain a multilevel NAND diagram from a Boolean expression, proceed
as follows:
a) From the given Boolean expression, draw the logic diagram with AND,
OR, and inverter gates. Assume that both the normal and complement
inputs are available.
b) Convert all AND gates to NAND gates with AND-invert graphic symbols.
c) Convert all OR gates to NAND gates with invert-OR graphic symbols.
d) Check all small circles in the diagram. For every small circle that is not
compensated by another small circle along the same line, insert an
inverter (one-input NAND gate) or complement the input variable.
In general, the number of NAND gates required to implement a Boolean
expression is equal to the number of AND-OR gates except for an
occasional inverter.
 cont…
 Example: implement using only NAND gates.
a) F = A + (B’ + C)(D’ + BE’)
b) F = (CD + E)(A + B’)
c) F = BC’ + A(B + CD)
d) F = (AB' + CD')E + BC(A + B)
e) F = w(x + y + z) + xy;
 Universal Logic Gates (nor gate)
 NOR gates are also universal gates and can form all of the basic gates.
 nor Implementation
• The two graphic symbols for the NOR gate are shown in Fig. below.

• The OR-invert symbol defines the NOR operation as an OR followed

by a complement.
• The invert-AND symbol complements each input and then performs
an AND operation.
• The two symbols designate the same NOR operation and are logically
identical because of DeMorgan's theorem.
 cont…
 The procedure for implementing a Boolean function with NOR gates is similar to the
procedure outlined in the previous section for NAND gates.
a) Draw the AND-OR logic diagram from the given algebraic expression Assume that both
the normal and complement inputs are available.
b) Convert all OR gates to NOR gates with OR-invert graphic symbols.
c) Convert all AND gates to NOR gates with invert-AND graphic symbols.
d) Any small circle that is not compensated by another small circle along the same line
needs an inverter or the complementation of the input variable.
 cont…
Example:
Implement the following Boolean function using only NOR gates.
a) F = (AB + E)(C + D)
b) F = A + (B’ + C)(D’ + BE’)
c) F = (CD + E)(A + B’)
d) F = [(C + D)B' + A](B + C')
e) F = (AB' + CD')E + BC(A + B)
f) F = w(x + y + z) + xy;
 Half Adder
 Basic rules of binary addition are performed by a half adder, which has
two binary inputs (A & B) and two binary outputs (Cout and Sum)
 The inputs and outputs can be summarized on a truth table.
 The S(sum) represents the least significant bit of the sum.
 The Cout represents the most significant bit of the sum.
 The Boolean functions for the two output from the truth table:
S = A’B + AB’ = A⊕B
Cout = AB Inputs Outputs
A Bout C S
 The logic symbol and equivalent circuit are: 0 0
0 1
0 0
0 1
1 0 0 1
1 1 1 0
 Full Adder
• Full Adder has three binary inputs (A, B, and Carry in) and two binary
outputs (Carry out and Sum).
• Symbol

• The truth table summarizes the operation.

• The Boolean functions for the two output from the truth table:
Sum = A’B’C + A’BC’ + AB’C’ + ABC
Cout = A’BC + AB’C + ABC’ + ABC
 cont…
• Using x-OR,
S = A⊕ B⊕C and Cout = AB + C(A⊕ B)
• A full-adder can be constructed from two half adders as shown:
 Parallel Adder
• Full adders are combined into parallel adders that can add binary
numbers with multiple bits.
• It consists of full-adders connected in a chain, with the output carry
from each full-adder connected to the input carry of the next full-adder
in the chain.
• An n-bit parallel adder requires n full-adders. A 4-bit adder is shown as
below.
 cont…

• Example:
a) What are the sum outputs when 111 and 101 are added by the 3-bit parallel
adder?
b) What are the sum outputs when 1110 and 1011 are added by the 4-bit
parallel adder?
 Decoder
• A decoder is a combinational circuit that converts binary information from
n input lines to a maximum of 2n unique output lines.
• If the n-bit decoded information has unused or don't-care combinations,
the decoder output will have fewer than 2n output.
• The decoders presented here are called n-to-2n-line decoders,
• Their purpose is to generate the 2n (or fewer) minterms of n input
variables.
• The name decoder is also used in conjunction with some code converters
such as a BCD-to-seven segment decoder.
• Only one output can be active (high) at any times.
 cont…
3x8 Decoder

a) Block diagram

b) Truth table
 cont…
3x8 Decoder
 Decoder With Enable Input
• Normally every commercially available decoder ICs have a special input other
than normal working input variables called ENABLE.
• The use of this ENABLE input is that when activated the complete IC comes to
the working condition for its normal functioning.
• If ENABLE input is deactivated the IC goes to sleep mode, the normal
functioning is suspended, and all the outputs become logic 0 irrespective of
normal input variables conditions.
• Its function is build higher decoder from lower decoders.

Figure: 2-to-4 decoder with enable input E.

 cont…
• Example:- Construct a 3-to-8 line decoder with the use of a 2-to-4 line decoder.

• Example:- Construct a 4-to-16 line decoder with the use of a 2-to-4 line
decoder.
• Example:- Construct a 5-to-32 line decoder with the use of a 3-to-8 line
decoder.
 Encoder
• An encoder is a digital circuit that performs the inverse operation of a decoder.
An encoder has 2n (or fewer) input lines and n output lines.
The output lines generate the binary code corresponding to the input value.
It is assumed that only one input has a value of 1 at any given time; otherwise the
circuit has no meaning.
 cont…
• 8x3 Encoder:
• The encoder can be implemented with OR gates whose inputs are determined directly
from the truth table.
 cont…
• These conditions can be expressed by the following output Boolean
functions:

• Logic circuit from the above Boolean function will be:

 cont…
• Example: Show how the decimal-to-BCD encoder converts the decimal
number 3 into a BCD 0011.
• Solution: The top two OR gates have ones as indicated with the red lines.
Thus the output is 0111.
 Multiplexer
• Multiplexer is also called data selectors.
• A digital multiplexer is a combinational circuit that selects binary
information from one of the 2n input channels and transmits to a
single output line.
• The selection of the particular input channel is controlled by a set of
select inputs.
• It select binary information from one of many input lines and direct it
to a single output line
• 2n input lines needs n selection lines and one output line
 cont…
• 2-to-1-line multiplexer:
 cont…
• 4x1-line Multiplexer:
• A 4x1 Multiplexer has four data inputs I3, I2, I1 & I0, two selection lines s1 and s0 and one output
Y.
• The block diagram of 4x1 Multiplexer is shown in the following figure.

Fig. : block diagram of

4x1 Mux.
 cont…
• A logic circuit, for 4x1 multiplexer will be:

Fig. : Logic circuit of 4x1 Mux.

 Multiplexer with enable inputs
• As in decoders, multiplexer ICs may have an enable input to control the
operation of the unit.
• When the enable input is in a given binary state, the outputs are disabled,
and when it is in the other state (the enable state), the circuit functions as a
normal multiplexer.
• The enable input (sometimes called strobe) can be used to expand two or
more multiplexer ICs to a digital multiplexer with a larger number of inputs.
 cont…
• Example:- Construct a 8-to-1 multiplexer with the use of a 4-to-1 line
multiplexer and external gate.

• Example:- Construct a 16-to-1 multiplexer with the use of only a 4-to-

1 line multiplexer.
 De-Multiplexer
• A de-multiplexer is a circuit that receives information from a single line and
directs it to one of 2n possible output lines.
• The selection of a specific output is controlled by the bit combination of n
elected lines.
• The term “demultiplex” means one into many.