CHAPTER-5

COMBINATIONAL LOGIC
CIRCUIT
BY: Hayleyesus Girma (MSC)

WOLAITA SODO UNIVERSITY

Digital logic design by Hayleyesus G.

5. Analysis and Synthesis of a Combinational logic circuit

• The digital system consists of two types of circuits, namely
➢ Combinational circuits and
➢ Sequential circuits
• A combinational circuit consists of logic gates, where outputs are at any instant and are
determined only by the present combination of inputs.
• Sequential circuits contain logic gates as well as memory cells.
• Their outputs depend on the present inputs and also on the states of memory elements.
• A combinational 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.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.

DESIGN PROCEDURE
• Any combinational circuit can be designed by the following steps of design
procedure.
1. The problem is stated.
2. Identify the input variables and output functions.
3. The input and output variables are assigned letter symbols.
4. The truth table is prepared that completely defines the relationship
between the input variables and output functions.
5. The simplified Boolean expression is obtained by any method of
minimization—algebraic method, Karnaugh map method, or tabulation
method.
6. A logic diagram is realized from 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 map method, or the tabulation
procedure.
• Usually, there will be a variety of simplified expressions from which to choose.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.

CONT…..
• 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
• Minimum number of gates,
• Minimum number of inputs to a gate,
• Minimum propagation time of the signal through the circuit,
• Minimum number of interconnections, and
• 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.
• 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.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.

CONT….
▪ 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
▪ Example 7: Design a combinational circuit , which convert a 4-bit Gray to binary
▪ Example 8: Design a combinational circuit ,which convert BCD-to-Seven-Segment decoder

▪ Example 9:The main stairway in a block of flats has three switches for controlling the
lights. Switch A is located at the top of the stairs, switch B is located halfway up the stairs
and switch C is positioned at the bottom of the stairs. Design a logic network to control
the lights on the staircase.
▪ Example 10: Design a circuit to enable a chemical additive to be introduced into the fluid through
another inlet only when the temperature is not too cold or too hot and the fluid is above the
high- level sensor.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.

THE UNIVERSAL PROPERTY OF NAND AND NOR GATES

The NAND Gate as a Universal Logic Element
• The NAND gate is a universal gate because it can be used to produce the NOT, the
AND, the OR, and the NOR functions.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.

The NOR Gate as a Universal Logic Element

• Like the NAND gate, the NOR gate can be used to produce the NOT, AND. OR and
NAND functions.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.

COMBINATIONAL LOGIC USING NAND AND NOR GATES

a) 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.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.

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.
▪ 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;

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.

b) 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.
• 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.
WOLAITA SODO UNIVERSITY.
Digital logic design by Hayleyesus G.
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;
▪ Convert the logic diagram the following to a multiple-level NAND and NOR circuit

WOLAITA SODO UNIVERSITY.

 Design of combinational logic circuits
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.
▪ The Sout 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 = x’y+ xy’ = x⊕y
▪ C = xy
Digital logic design by Hayleyesus G.
b) The Full-Adder
▪ The full-adder accepts two input bits and an input carry and generates a sum output and an
output carry.
▪ The basic difference between a full-adder and a half-adder is that the full-adder accepts an input
carry.
▪ The Boolean functions for the two out put from the truth table:
▪ Using x-OR, S = x’y’z + x’yz’ + xy’z’ + xyz = x⊕y⊕z
C = x’yz + xy’z + xyz’ + xyz = xy + z(x ⊕y)
Implementation of Full Adder with Two Half
Adders and an OR Gate

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
c) Half-Subtractor
▪ A half-subtractor is a combinational circuit that subtracts two bits and produces their difference.
It also has an output to specify if a 1 has been borrowed.
▪ The Boolean functions for the two outputs of the
half-subtractor are derived directly from the truth table:
▪ D = x'y + xy' = x⊕y
▪ B = x’y

d) Full-Subtractor
▪ A full-subtractor is a combinational circuit that performs a subtraction between two bits, taking
into account that a 1 may have been borrowed by a lower significant stage.
▪ This circuit has three inputs and two outputs.
▪ Exercise:- design the full-subtractor combinational logic ckt.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
e) Binary Parallel Adder
▪ A binary parallel adder is a digital circuit that produces the arithmetic sum of two binary numbers
in parallel.
▪ 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.
▪ Figure below shows the interconnection of four full-adder (FA) circuits to provide a
4-bit binary parallel adder.
▪ An n-bit parallel adder requires n full-adders.

▪ 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?

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
g) Binary Adder-Subtractor
▪ The subtraction of binary numbers can be done most conveniently by means of complements, as
discussed before.
▪ Remember that the subtraction A - B can be done by taking the 2's complement of B and adding it
to A.
▪ The 2's complement can be obtained by taking the 1 's complement and adding one to the least
significant pair of bits.
▪ The addition and subtraction operations can be combined into one circuit with one common
binary adder.
▪ This is done by including an exclusive-OR gate with each full adder.
▪ A 4-bit adder-subtractor circuit is shown in Figure below.
▪ The mode input M controls the operation.
▪ When M = 0, the circuit is an adder, and when
M = 1, the circuit becomes a subtractor.
▪ Each exclusive-OR gate receives input M and
one of the inputs of B.
▪ When M = 0, we have B ⊕ 0= B
▪ When M = 1, we have B ⊕ 1= B’ and C1=1.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
h) MAGNITUDE COMPARATOR
▪ The comparison of two numbers is an operation that determines if one number is greater than,
less than, or equal to the other number.
▪ A magnitude comparator is a combinational circuit that compares two numbers, A and B, and
determines their relative magnitudes.
▪ The outcome of the comparison is specified by three binary variables that indicate whether A > B,
A = B, or A < B.
▪ Algorithm
▪ A = A3A2A1A0 ; B = B3B2B1B0
▪ A=B if A3=B3, A2=B2, A1=B1and A1=B1
▪ equality: xi= AiBi + Ai'Bi'
▪ (A=B) = x3x2x1x0
▪ If the corresponding digit of A is 1 and that of B is 0, we conclude that A > B.
▪ If the corresponding digit of A is 0 and that of B is 1, we have that A < B.
▪ (A>B) = A3B3‘ + x3A2B2‘ + x3x2A1B1‘ + x3x2x1 A0B0'
▪ (A<B) = A3'B3 + x3A2'B2 + x3x2A1'B1 + x3x2x1 A0'B0
▪ Implementation
▪ xi = (AiBi‘ + Ai'Bi)'

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
h) MAGNITUDE COMPARATOR

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
i) DECODERS
▪ 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-m-line decoders, where m <= 2n.
▪ 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.

a) Truth table
b) Block diagram
WOLAITA SODO UNIVERSITY.
Digital logic design by Hayleyesus G.
Combinational Logic Implementation using decoder
▪ A decoder provides the 2n minterm of n input variables. Since any Boolean function can be
expressed in sum of minterms canonical form, one can use a decoder to generate the minterms
and an external OR gate to form the sum.
▪ In this way, any combinational circuit with n inputs and m outputs can be implemented with an n-
to-2n- line decoder and m OR gates.
▪ The procedure for implementing a combinational circuit by means of a decoder and OR gates
requires that the Boolean functions for the circuit be expressed in sum of minterms.
▪ Example:-Implement a full-adder circuit with a decoder and two OR gates.
▪ From the truth table of the full-adder, we obtain the functions for this combinational circuit in the
sum of minterms:
S(x, y, z) = ∑(1, 2, 4, 7)
C(x, y, z) = ∑(3, 5, 6, 7)
Example: A combinational circuit is defined by the
following three Boolean functions.
Design the circuit with a decoder and external gates.
F1 = x'y'z' + XZ
F2 = xy'z' + x'y
F3 = x'y'z + xy
WOLAITA SODO UNIVERSITY.
Digital logic design by Hayleyesus G.
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.

E A B D0 D1 D2 D3

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

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
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.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
j) Encoders
▪ 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.
▪ The encoder can be implemented with OR gates whose inputs are determined
directly from the truth table.
▪ These conditions can be expressed by the following output Boolean functions:

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
MULTIPLEXERS OR 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.
▪ That is why the multiplxers are also called data selectors.
▪ The selection of the particular input channel is controlled by a set of select inputs.
▪ Select binary information from one of many input lines and direct it to a single output
line
▪ 2n input lines, n selection lines and one output line
▪ e.g.: 2-to-1-line multiplexer

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
Cont….
▪ Example: a logic circuit, for 4x1 multiplexer

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
Cont….
▪ 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.
▪ 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.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
Demultiplexer
▪ A demultiplexer 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.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
PARITY GEINERATOR AND CHECKER
▪ Whenever information is transmitted from one device (the transmitter) to another device (the receiver),
there is a possibility that errors can occur such that the receiver does not receive the identical information
that was sent by the transmitter.
▪ One of the simplest and most widely used schemes for error detection is the parity method.
▪ Parity Bit:- A parity bit is an extra bit that is attached to a code group that is being transferred from one
location to another.
▪ The parity bit is made either 0 or 1, depending on the number of bits that are contained in the code group.
Two different methods are used.
✓ The even-parity method, and
✓ The odd-parity method.
▪ In the even-parity method, the value of the parity bit is chosen so that the total number of 1s in the code
group (including the parity bit) is an even number.

▪ In the odd-parity method, the value of the parity bit is chosen so that the total number of 1s in the code
group (including the parity bit) is an odd number.

WOLAITA SODO UNIVERSITY.

Digital logic design by Hayleyesus G.
Cont…
▪ A parity generator is a combination logic system to generate the parity bit at the transmitting
side.
▪ Parity Checker:- The message bits with the parity bit are transmitted to their destination, where
they are applied to a parity checker circuit.
▪ The circuit that checks the parity at the receiver side is called the parity checker.
▪ The parity checker circuit produces a check bit and is very similar to the parity generator circuit.
▪ If the check bit is 1, then it is assumed that the received data is incorrect. The check bit will be 0 if
the received data is correct.

WOLAITA SODO UNIVERSITY.