 Logic circuits for digital systems may be Combinational or

Sequential.
 A combinational circuit consists of input variables, logic gates,
and output variables.
 Output of a Combinational Circuit at a given instance and for
particular inputs depends only on the present inputs provided
to the circuit at that particular time and has no relation with
the previous outputs of the circuit.
 Block Diagram of Combinational Circuit

Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur 1

 Step 1: Analyse the problem statement to identify the no.
of Inputs and Outputs
 Step 2: After getting number of I/Ps and O/Ps, Name
them as per functionality
 Step 3: Draw the Truth table (O/Ps against all possible
combination of I/Ps) as per the required function
 Step 4: Use K-map or any other simplification method to
get Optimized equations of all O/Ps in terms of I/Ps
 Implement or Realize the circuit as per equations

2
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
To obtain the output Boolean functions from a logic
diagram, proceed as follows:
1. Label all gate outputs that are a function of input variables with
arbitrary symbols. Determine the Boolean functions for each
gate output.
2. Label the gates that are a function of input variables and
previously labeled gates with other arbitrary symbols. Find the
Boolean functions for these gates.
3. Repeat the process outlined in step 2 until the outputs of the
circuit are obtained.
4. By repeated substitution of previously defined functions, obtain
the output Boolean functions in terms of input variables.
3
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
F2 = AB + AC + BC; T1 = A + B + C; T2 = ABC; T3 = F2’T1;
F1 = T3 + T2
F1 = T3 + T2 = F2’T1 + ABC = A’BC’ + A’B’C + AB’C’ + ABC

4
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 We can derive the truth table in Table 4-1 by using the
circuit of Fig.4-2.

5
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
Table4-2 is a Code-Conversion example, first, we can list the
relation of the BCD and Excess-3 codes in the truth table.

6
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 K-Maps
2. For each symbol of the Excess-3 code, we use 1’s to draw
the map for simplifying Boolean function.

7
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 Circuit implementation
z = D’; y = CD + C’D’ = CD + (C + D)’
x = B’C + B’D + BC’D’ = B’(C + D) + B(C + D)’
w = A + BC + BD = A + B(C + D)

8
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 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’ = x ⨁ y
C = xy
9
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 10
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 One that performs the addition of three bits(two
significant bits and a previous carry) is a Full Adder.

11
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 S = x’y’z + x’yz’ + xy’z’ + xyz
C = xy + xz + yz

12
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 13
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 Full-adder can also implemented with two half adders and one
OR gate (Carry Look-Ahead adder).
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

14
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 15
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 This is also called Ripple
Carry Adder ,because of
the construction with
full adders are connected
in cascade.

16
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 Fig.4-9 causes a unstable factor on carry bit, and produces
a longest propagation delay.
 The signal from Ci to the output carry Ci+1, propagates
through an AND and OR gates, so, for an n-bit RCA, there
are 2n gate levels for the carry to propagate from input to
output.

17
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 Because the propagation delay will affect the output signals on
different time, so the signals are given enough time to get the
precise and stable outputs.
 The most widely used technique employs the principle of carry
look-ahead to improve the speed of the algorithm.

18
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 Pi = Ai ⊕ Bi steady state value
Gi = AiBi steady state value
Output sum and carry
Si = Pi ⊕ Ci
Ci+1 = Gi + PiCi
Gi : carry generate Pi : carry propagate
C0 = input carry
C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1G0 + P1P0C0
C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0

 C3 does not have to wait for C2 and C1 to propagate.

19
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 C3 is propagated at the same time as C2 and C1.

20
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 Delay time of n-bit CLAA = XOR + (AND + OR) + XOR

21
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
M = 1 Subtractor M = 0 Adder

22
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
BCD adder can’t exceed 9 on each input digit. Maximum value
of addition of two BCD digits is 19 and K is the carry.

23
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 When the binary sum is greater than 1001 (9), we obtain a non-
valid BCD representation.

 The addition of binary 6 (0110) to the binary sum converts it to

the correct BCD representation and also produces an output
carry as required.

 To distinguish them from binary 1000 and 1001, which also

have a 1 in position Z8, we specify further that either Z4 or Z2
must have a 1.

C = K + Z8Z4 + Z8Z2
24
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 25
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 A decimal parallel
adder that adds n
decimal digits needs
n BCD adder stages.

 The output carry

from one stage must
If =1
be connected to the
input carry of the
0110
next higher-order
stage.

26
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 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.

And

27
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 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.

28
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 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

29
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 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

30
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 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.

31
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 32
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 33
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 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.

34
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 35
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 Example: Full-Adder
 In form of minterms,
Sum S(x, y, z) = ∑(1, 2, 4, 7) and C(x, y, z) = ∑(3, 5, 6, 7)

36
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 An Encoder is the Inverse operation of a Decoder.
 We can derive the Boolean functions by table 4-7
z = D1 + D3 + D5 + D7
y = D2 + D3 + D6 + D7
x = D4 + D5 + D6 + D7

37
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 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.

38
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 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.
Instead of listing all 16
minterms of four variables.

V=0no valid inputs

V=1valid inputs
39
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 x = D2 + D3
y = D3 + D1D’2
V = D0 + D1 + D2 + D3
40
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 41
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
S = 0, Y = I0 Truth Table  S Y Y = S’I0 + SI1
S = 1, Y = I1 0 I0
1 I1

42
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 43
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 Multiplexer circuits can be combined with common selection inputs
to provide multiple-bit selection logic. Compare with Fig 4-24.

I0 Y

I1

44
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
Implementation Types
 Type-0: MUX Size will be M x 1 with M=2n inputs and n select
lines (with inputs from I0 to IM having the value same as output
i.e. 0 or 1 as per the function definition).
 Type-1: MUX Size will be M x 1 with M=2(n-1) inputs and (n-1)
select lines (with Inputs from I0 to IM having the values as per
the Implementation Table.
 Type-2: MUX Size will be M x 1 with M=2(n-2) inputs and (n-2)
select lines (with Inputs from I0 to IM having the values as per
the solution obtained for each I using K-map.
 Type-3 and … : With the same above specified logic.

45
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
Exampe: F(A, B, C, D) = (1, 3, 4, 11, 12, 13, 14, 15)

46
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 47
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 48
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 49
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 50
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 51
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 52
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 53
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 54
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 55
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 A decoder with an enable input is referred to as a
decoder/demultiplexer.
 The truth table of demultiplexer is the same with
decoder. A B

D0

Demultiplexer D1
E
D2
D3

56
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 A multiplexer can be constructed with three-state gates.

57
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 58
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
 59
Bhoopesh Kumawat, Asst. Prof., JECRC Jaipur
60