Unit- 3

Combinational Logic Circuits

Dr. V S M Srinivasavarma,
Assistant Professor,
Computer Science and Engineering,
Shiv Nadar University Chennai.
Combinational Logic Circuit
• Steps to design a combinational digital circuit:
• From the problem statement derive the truth table
• From the truth table derive the unsimplified logic expression
• Simplify the logic expression
• From the simplified expression draw the logic circuit
 Half Adder-Subtractor
• A combinational circuit that performs the addition of two bits is called a half adder.
• The truth table for the half adder is listed below:

S: Sum
C: Carry

S = x’y + xy’
C = xy
Implementation of Half-Adder
 Half -Subtractor
• A combinational circuit that performs the subtraction of two bits is called a half
subtractor.
• The truth table for the half adder is listed below:

X Y D B
0 0 0 0
0 1 1 1 D: Difference
1 0 1 0 B: Borrow
1 1 0 0

S = x’y + xy’
C = xy
Implementation of Half-Subtractor
 Full- Adder
• A combinational circuit that performs the addition of two bits along with a carry is
called as a full adder.
 Full- Adder
Minimized Expressions for SUM and CARRY
• Sum = 𝐴ҧ𝐵𝐶
ത + 𝐴Bҧ 𝐶ҧ + A 𝐵ത 𝐶ҧ +ABC = A ⊕ B ⊕ C
ҧ
• Carry = 𝐴BC ത + AB𝐶ҧ + ABC = AB + BC + CA
+ A𝐵C
 Full- Adder Implementation using 2-HAs
• Full-adder can also implemented with two half adders and one OR gate.
S = z ⊕ (x ⊕ y)
= z’(xy’ + x’y) + z(xy’ + x’y)’
= xy’z’ + x’yz’ + xyz + x’y’z

C = z(xy’ + x’y) + xy = xy’z + x’yz + xy

Full- Adder Implementation using 2-HAs
Binary Adders
• Half-Adders can add only two bits at a time. Will it be sufficient to perform real
additions .? Refer to the example below….

1 1 1 1 1 1 carries
1 1 1 1 0 1
+ 1 0 1 1 1
------------------
1 0 1 0 1 0 0
• Addition in binary goes like: Add two bits at position ‘i’ corresponding to the two
numbers.
• Take the Sum and in case of a carry forward it to the next position i.e. ‘i+1’. Now,
at ‘i+1’th position, 3-bits need to be added.
• Hence, an half-adder alone cannot be used for addition purpose and Full-Adder is
needed.
Binary Adders
• Again for an n-bit addition, n-full adders are needed. Refer to the Example.
Binary Adders- Carry Propagation
• The adder shown is also called as a ripple carry adder because the carry is rippling
from Left to Right.

• However, in this method, the propagation delay increases significantly as the sum
output in the last FA or (n)th FA has to wait for the carry from (n-1)th FA and this
goes on….

• A close assumption is that, the logical depth of carry computation in each FA is 2

gate levels.

• Then for an n-bit RCA, there are 2n gate levels for the carry to propagate from
input to output.
Binary Adders- Carry Propagation
• Alternative: Pre-compute all the carries priorly instead on depending on the
previous stage carry.

• Popularly referred to as “Carry look-Ahead”-based Adders

• The working of carry look ahead adder is based on the principle-

• The carry-in of any stage full adder is independent of the carry bits
generated during intermediate stages.

• The carry-in of any stage full adder depends only on the following two
parameters-
• Bits being added in the previous stages
• Carry-in provided in the beginning
Carry Computation – CLA Adder
C1 = C0 (A0 ⊕ B0) + A0B0
C2 = C1 (A1 ⊕ B1) + A1B1
C3 = C2 (A2 ⊕ B2) + A2B2
C4 = C3 (A3 ⊕ B3) + A3B3
For simplicity, Let-
• Gi = AiBi where G is called carry generator
• Pi = Ai ⊕ Bi where P is called carry propagator

Then, re-writing the above equations, we have-

• C1 = C0P0 + G0 ………….. (1)
• C2 = C1P1 + G1 ………….. (2)
• C3 = C2P2 + G2 ………….. (3)
• C4 = C3P3 + G3 ………….. (4)
Carry Computation – CLA Adder
Now,
• Clearly, C1, C2 and C3 are intermediate carry bits.
• So, let’s remove C1, C2 and C3 from RHS of every equation.
• Substituting (1) in (2), we get C2 in terms of C0.
• Then, substituting (2) in (3), we get C3 in terms of C0 and so on.

Finally, we have the following equations-

• C1 = C0P0 + G0
• C2 = C0P0P1 + G0P1 + G1
• C3 = C0P0P1P2 + G0P1P2 + G1P2 + G2
• C4 =C0P0P1P2P3 + G0P1P2P3 + G1P2P3 + G2P3 + G3
•
 CLA Adder Implementation
• These equations show that the carry-in of any stage full adder depends only on-
• Bits being added in the previous stages
• Carry bit which was provided in the beginning

x3 y3 x2 y2 x1 y1 x0 y0
xi yi

c3 c2 c1
B Cell B Cell B Cell B Cell c0

ci s3 s2 s1 s0
G3 P3 G2 P2 G1 P1 G0 P0
B Cell
c4
Carry-lookahead logic
Gi Pi si

Bit Stage Cell G 0I P0I

4-bit carry-lookahead adder
CLA Adder- Summary
• Delay time of n-bit CLAA = XOR + (AND + OR) + XOR

Advantages:
• It generates the carry-in for each full adder simultaneously.
• It reduces the propagation delay.

Disadvantages:
• It involves complex hardware and hence, costlier.
• It gets more complicated as the number of bits increases
• Fan-In of the gates available in the Chip Design resource library decided the
actual logical depth of the design
N-bit Adders- N is 16, 32, 64, ….
xn yn x1 y1 x0 y0

cn cn-1
Full Adder ... Full Adder c1 Full Adder
ci
(FA) (FA) (FA)

sn-1 s1 s0
Most Significant bit Least Significant bit
(MSB) Position (LSB) Position
An n-bit ripple carry adder- Naïve implementation

x2n-1 y2n-1 xn yn Xn-1 yn-1 x0 y0

xkn-1 ykn-1 ...
... ...
c1 Full Adder
ckn Full Adder Full Adder c0
... (FA) (FA)
(FA)
... ...
... s0
s2n-1 sn sn-1
skn-1 s(k-1)n
Cascade of k n-bit adders
 16-bit CLA using 4-bit CLAs
x15-12 y15-12 x11-8 y11-8 x7-4 y7-4 x3-0 y3-0

c12 c8 c4
B Cell B Cell B Cell B Cell c0
Note: Cascading is the
most preferred way for
implementing large s15-12 s11-8 s7-4 s3-0
G3 I I
adders in real-time P3I G2 P2I G1 I
P1I G0I P0I

Carry-lookahead logic

G0II P0II

c16 = G3I + P3I G2I + P3I P2I G1I + P3I P2I P1I G0I + P3I P2I P1I P0I c0
Binary Adder/Subtractor
M = 1→subtractor; M = 0→adder, The design is based on 2’s Complement number system.
Recall, 2’s complement num. sys. is the preferred choice in real-computing applications
Overflow
Find the rationale behind the Overflow logic and get +2 marks reward in CIA-II
 Overflow on signed and unsigned

• Overflow is a problem in digital computers because the number of bits that hold the
number is finite and a result that contains n+1 bits cannot be accommodated.
• When two unsigned numbers are added, an overflow is detected from the end carry
out of the MSB position.

• When two signed numbers are added, the sign bit is treated as part of the number
and the end carry does not indicate an overflow.

• An overflow cann’t occur after an addition if one number is positive and the other is
negative.

• An overflow may occur if the two numbers added are both positive or both negative.
 Binary multiplier
• Usually there are more bits in the partial products and it is necessary to use full
adders to produce the sum of the partial products
 4-bit by 3-bit binary multiplier
• For J multiplier bits and K
multiplicand bits we need (J X K)
AND gates and (J − 1) K-bit
adders to produce a product of J+K
bits.

• K=4 and J=3, we need 12 AND

gates and two 4-bit adders.

• This model is called as an Array

Multiplier
 Magnitude comparator
• The equality relation of each pair
of bits can be expressed logically
with an exclusive-NOR function as:

A = A3A2A1A0; B = B3B2B1B0

xi=AiBi+Ai’Bi’ for i = 0, 1, 2, 3

(A = B) = x3x2x1x0
 Magnitude comparator
• We inspect the relative magnitudes of pairs of
MSB. If equal, we compare the next lower
significant pair of digits until a pair of unequal
digits is reached.

• If the corresponding digit of A is 1 and that of B is

0, we conclude that A>B.

(A>B)= A3B’3+x3A2B’2+x3x2A1B’1+x3x2x1A0B’0

(A<B)= A’3B3+x3A’2B2+x3x2A’1B1+x3x2x1A’0B0
 Decoders
• The decoder is called n-to-m-line decoder, where m ≤ 2n .

• the decoder is also used in conjunction with other code converters such as a BCD-
to-seven_segment decoder.

• 3-to-8 line decoder: For each possible input combination, there are seven outputs
that are equal to 0 and only one that is equal to 1.
Implementation and truth table
Inputs Outputs

X Y Z D1 D2 D3 D4 D5 D6 D7 D8

0 0 0 1 0 0 0 0 0 0 0

0 0 1 0 1 0 0 0 0 0 0

0 1 0 0 0 1 0 0 0 0 0

0 1 1 0 0 0 1 0 0 0 0

1 0 0 0 0 0 0 1 0 0 0

1 0 1 0 0 0 0 0 1 0 0

1 1 0 0 0 0 0 0 0 1 0

1 1 1 0 0 0 0 0 0 0 1
Decoder with enable input
• Some decoders are constructed with NAND gates, it becomes more economical to
generate the decoder minterms in their complemented form.

• As indicated by the truth table , only one output can be equal to 0 at any given
time, all other outputs are equal to 1.
4-to-16 decoder using 3-to-8 Decoder
Full Adder using Decoder
S(x, y, z) = ∑(1, 2, 4, 7)
C(x, y, z) = ∑(3, 5, 6, 7)
Encoders
• An encoder is the inverse operation of a decoder.
• We can derive the Boolean functions from the table below:
z = D 1 + D 3 + D 5 + D7
y = D 2 + D3 + D 6 + D 7
x = D 4 + D5 + D 6 + D 7
Priority Encoders
• If two inputs are active simultaneously, the output produces an undefined
combination. We can establish an input priority to ensure that only one input is
encoded.
• Another ambiguity in the octal-to-binary encoder is that an output with all 0’s
is generated when all the inputs are 0; the output is the same as when D0 is
equal to 1.
• The discrepancy tables on Table 4-7 and Table 4-8 can resolve aforesaid
condition by providing one more output to indicate that at least one input is
equal to 1.
Priority Encoders
V=0→no valid inputs
V=1→valid inputs
X’s in output columns represent
don’t-care conditions
X’s in the input columns are
useful for representing a truth
table in condensed form.
4-bit Priority Encoder

x = D2 + D3
y = D3 + D1D’2
V = D0 + D1 + D2 + D3
Multiplexers
S = 0, Y = I0 Truth Table → S Y Y = S’I0 + SI1
S = 1, Y = I1 0 I0
1 I1
4-to-1 Line Multiplexer
Quadruple 2-to-1 Line Multiplexer
• Multiplexer circuits can be combined with common selection inputs to
provide multiple-bit selection logic. Compare with Fig4-24.
Multiplexers
• They are also referred to as Universal Logic Circuits.
• Any combinational logic functionality can be implemented using a multiplexer
• We need a mux with n-1 select lines for implementing n-variable function
F(x, y, z) = (1,2,6,7)
Multiplexers
• F(A, B, C, D) = (1, 3, 4, 11, 12, 13, 14, 15)
De-Multiplexer
• A decoder with an enable input is referred to as a
decoder/demultiplexer.
• The truth table of demultiplexer is the same with decoder.
• Practice: Design a gate level logic circuit of a 1:4 and 1:8 de-
multiplexer A B
Truth Table

Select Lines Outputs

A B D0 D1 D2 D3
D0
0 0 E 0 0 0
Demultiplexer D1 0 1 0 E 0 0
E
D2 1 0 0 0 E 0
D3 1 1 0 0 0 E
Thank You