EC106

Chapter 4
Combinational Logic
Nithin Chatterji
Assistant Professor
ECED, SVNIT
Prepared using:
1. Morris Mano, “Digital Logic and Computer Design.” (Pearson India, 2017)
Introduction
• Logical circuits
1. Combinational circuits 2. Sequential circuits
– Made of logical gates – Made of logical gates and
– Outputs at any time are directly memory elements (binary
determined by the present cells).
combination of i/ps. (do not – Outputs at any time are
depend on previous i/ps) determined by the present
– Performs information combination of i/ps and the
processing operation specified state of the memory elements.
by a set of Boolean functions. – State of memory elements is a
function of previous i/ps.
Recap
• Binary numbers and binary codes are used to represent discrete
quantities of information.
– Binary numbers are represented by electric voltages or some other
signals.
• Signals are manipulated in digital logic gates to preform required
function.
• Boolean algebra is used to express logic functions algebraically.
• Simplification of Boolean functions for economic gate
implementations.
• Now the knowledge gained is used to
– Formulate various systematic design and analysis procedures of
combinational circuits.
Combinational circuit
• n i/p variables
– 2n combinations of binary i/p
values possible.
– for each i/p combination there • Each i/p variable to a
is only and one o/p combinational circuit may
combination possible. have
• A combinational circuit can – One wire (either normal or
be represented by complement form)
– m Boolean functions, one for – or two wires (both normal and
each o/p variable. complement form)
– each o/p function is expressed • Flip Flops (binary cells for
in terms of n i/p variables. storage) have o/ps in both
forms.
Design Procedure
1. The problem is stated.
2. The number of available input variables and required
output variables is determined.
3. The input and output variables are assigned letter symbols.
4. The truth table that defines the required relationships
between inputs and outputs is derived.
5. The simplified Boolean function for each output is
obtained.
6. The logic diagram is drawn.
Simplified expressions
• Application specific.
• Depends on constraints such as
– Minimum number of gates.
– Minimum number of i/ps to a gate.
– Minimum propagation time of the signal through the circuit.
– Minimum number of interconnections.
– Limitations on the driving capabilities of the gate.
Adders
• Digital computers perform a variety of information-
processing tasks.
– Includes various arithmetic operations.
• Most basic arithmetic operation
– Addition of two bits
• Half-adder: Combinational circuit that performs addition
of two bits.
• Full-adder: Performs addition of three bits.
– Two half-adders can be employed to implement a full-adder.
Half-adder
Various implementations of half-adder
Full-adder
Implementation of Full-adder with 2 HA.
Subtractors
• If the minuend (1st) bit is smaller than the subtrahend
(2nd) bit
– A 1 is borrowed from the next significant position.
– Conveyed to next pair of higher bits by Borrow bit (B).
Half-subtractor
Full-subtractor
• Performs a subtraction between two bits
– Takes in to account a 1 may have been borrowed by a lower
significant stage.
– 3 i/ps and 2 o/ps.
Full-adder to Full-subtractor
Code Conversion
• A large variety of codes are available for the same discrete
elements.
– Different codes are used by different digital systems.
• Code conversion is used when connecting two such digital
systems to make them compatible.
• To convert code A to code B
– i/p is A.
– o/p generated corresponding bit combination of code B.
– Combinational circuits using logical gates is used for this
transformation.
BCD to excess-3 code
BCD to excess-3 code
z = D′
y = CD + C′D′ = CD + (C + D)′
x = B′C + B′D + BC′D′ = B′(C + D) + BC′D′
= B′(C + D) + B(C + D)′
w = A + BC + BD = A + B(C + D)
Analysis Procedure
• Reverse problem
– Starts with a logic diagram
– Culminates with a Boolean expression or truth table.

• Methods used
– Derivation of the Boolean Function by Algebraic
Manipulation
– Derivation of the Truth Table
– Block Diagram Transformation
Derivation of the Boolean Function by
Algebraic Manipulation
Derivation of the Truth Table
Block Diagram Transformation
Review
• Adders
• Subtractors
• Code convertors
• Analysis procedure