2,Combinational Logic Circuits.pdf

Combinational ckt

1. COMBINATIONAL LOGIC CIRCUITS COMBINATIONAL LOGIC CIRCUITS
Introduction ‰
Until
now we studied the operation of the entire
basic
logic
gate, and we used Boolean alge
bra to describe and analyze

circuits that were made up of
combinations of logic gates.
‰
These Circuits can be classified
as combinational logic circuits
becau
se,
at any time, the logic level at the
output
depends
on
the combination of logic l
evels present at the inputs.
‰
A
combinational circuit has no me
mory characteristic, so its
output depends on the curre
nt value of its input.
‰
We will study the simplification
of logic circuits by usin
g
Boolean algebra theorems & a mapping technique.
‰
In addition, we will study
simple
techniques for designing logic
circuits to satisfy a gi
ven set of requirements.
‰
Any Boolean expression can be expressed
¾
In
a
stand
a
rd
or
canonical
or
expanded Sum (OR) Of
Produ
cts
(AND)-SOP form-or
¾
In a
standard
or
canonical
or
expanded Product
(AND) Of

S
u
ms (OR)-POS form.

2. SumSum
--
ofof
--
Products Form (Minterms) Products Form (Minterms)
‰
The methods
of
logic-
circuit
simplification and design that we
will
study
require logic expression to be in a sum-
of-
p
roducts
form (
SOPSOP
).
‰
Some examples of this form are:
‰
Each of this sum-
of-
p
roduct expression consists of
two
or
more AND terms (products) that are ORed together.
‰
Each AND term consists of one
or
more
variables
appearing
in
either complemented or Uncomplemented form.
‰
Note that in a sum-
of-
p
roducts
expression; one
inversion
sign
can not cover more than one variable in a term.
‰
Example : we can not have
C
B
A
ABC
+
D
D
C
C
B
A
AB
+
+
+
GH
EF
D
C
B
A
+
+
+
1. 2. 3.
T
RS
or
ABC

3. Product Product
--
ofof
--
Sums (Maxterms Sums (Maxterms
))
‰
There is another general form for logic expressions that is sometimes used in logic-
circuit design.
‰
It is called the Product-
o
f-
sums form (
POSPOS
), and it
consists of two or more OR terms (sums) that are ANDed together.
‰
Each OR term contains one or more variables in complemented or Uncompleme
nted form. Here are some
product-
o
f-
sums expressions;
‰
The methods of circuit simplification and design, which we will be using, are based on
the sum-
of-
p
roducts form, so
we will not be doing much with the products-
of-
s
um form.
‰
It
will, however, occur from
time to time in some logic
circuits, which have a particular structure.
)
C
A
(
)
C
B
A
(
+
+
+
F
)
D
C
(
)
B
A
(
+
+
1. 2.

4. CONVERSION FROM SOP to POS CONVERSION FROM SOP to POS
and vice and vice
--
versa versa
‰
A standard SOP form can always be converted to a standard POS
form, by treating missing minterms of the
SOP form as the maxterms of the POS form.
‰
Similarly, a standard POS form can always be converted to a standard SOP form, by treating the missing maxterms of the POS form
as the minterms of the
corresponding SOP form.

5. EXPANSION OF A BOOLEAN EXPRESSION TO SOP FORM EXPANSION OF A BOOLEAN EXPRESSION TO SOP FORM ‰
The
following steps are follo
wed for the expansion of a
Boolean expression in SOP form in standard SOP form: 1.
Write down all the terms.
2.
If one or more variables are missing
in
any term, expand that term by
multiplying it with the sum of each
one of the missing variable and its
complement
3.
Drop out the redundant terms
‰
Also,
the
given
expression can be directly written in terms of
its minterms by using the following procedure: 1.
Write down all the terms.
2.
Put Xs in terms where variables must
be inserted to form a minterm.
3.
Replace the non-complemented variab
les by 1s and the complemented
variables by 0s, and use all combinations
of Xs in terms of 0s and
1s
to
generate minterms.
4.
Drop out all the redundant terms.

6. Example#1 Expand to minterms and maxterms Solution ‰
The given expression is a two-variable function.
‰
In the first term , the va
riable B is missing; so, multiply
it by .
‰
In the second term , the variable A is mi
ssing; so, multiply by
.
‰
Therefore,
‰
The minterm m
3
is missing in the SOP form
.
‰
Therefore, the maxterm M
3
will be present in the POS form.
‰
Hence the POS form is M
3
i.e.
.
B
A
+
B
B
+
B
)
A
(A
+

)
A
(A
B
)
B
(B
A
B
A
+
+
+
=
+A
B
A
+
B
A
B
A
B
A
B
A
+
+
+
=
B
A
B
A
B
A
+
+
=
10

00

01
+
+
=
2
0
1
m
m
m

+
+
=
∑
=
m(0,1,2)

7. ‰
2
nd
method
∑
=
+
+
=
+
+
=
+
+
+
=
+
=
+
=
+
m(0,1,2)

m
m
m


10

01

00


10

00

01

00


X0
0X

B
X
X
A
B
A
2
1
0

8. Exercise 9
Expand to minterms and maxterms
ABC
C
B
A
+
+

9. EXPANSION OF A BOOLEAN EXPRESSION TO POS FORM EXPANSION OF A BOOLEAN EXPRESSION TO POS FORM ‰
The expansion of a Boolean expression to
the
standard
POS form is conducted as follows
:
1.
If one or more variables are missing
in
any sum term, expand that term by
adding the products of each of the missing term and its complement.
2.
Drop out the redundant terms.
‰
The given expression can also
be written in terms of
maxterms by using the following procedure
:
1.
Put Xs in terms wherever variables must be inserted to form a maxterm.
2.
Replace the complemented variables
by 1 s and the non-complemented
variables by Os and use all combinations
of Xs in terms of Os and 1 s to
generate maxterms.
3.
Drop out the redundant terms.

10. Example#2 Expand
to maxterms and minterms
Solution ‰
The given expression is a two-
variable function in the POS
form.
‰
The variable B is missing In the firs
t term A. so, add to
it.
‰
The second term contains all the va
riables. So leave it as it is.
‰
The variable A is missing in the thir
d term B. So, add to
it.
‰
Therefore,
or ‰
The maxterm M
3
is missing in the POS form. So, the SOP
form will contain only the minterm m
3
i.e. AB
A)B
B
A(
+
B
B
A
A
)
A
A)(B
(B
A
A
B
B
)
B
B)(A
(A
B
B
A
A
+
+
=
+
=
+
+
=
+
=

B)
A
B)(
)(A
B
)(A
B
B)(A
(A
A)B
B
A(
+
+
+
+
+
=
+
B)
A
)(
B
B)(A
(A
+
+
+
=
(10)
(01)
(00)
=
2
1
0
M
M
M

⋅
⋅
=
∏
=
M(0,1,2)

11. ‰
2
nd
method
∏
=
+
⋅
=
=
→
=
→
+
⋅
=
=
→
M(0,1,2)
)B
B
A(ATherefore,
M
M
(00)(10)
X0
B
M

(01)
)
B
(A
M
M
(00)(01)
OX
A
2
0
1
1
0

12. Exercise 9
Expand
to maxterms and minterms
)
C
B
)(A
C
A
A(
+
+
+
)
C
B
A
)(
C
B
A
(
)
C
B
A
)(
C
B
A
(
)
C
C
B
A
)(
C
C
B
A
(
C
C
)
B
A
)(
B
A
(
C
C
B
B
A
A
+
+
+
+
+
+
+
+
+
=
+
+
+
+
=
+
+
+
=
+
+
=
)
B
C
A
)(
B
C
A
(
B
B
C
A
C
A
+
+
+
+
=
+
+
=
+

13. SIMPLIFYING LOGIC CIRCUITS SIMPLIFYING LOGIC CIRCUITS
Why simplification? Why simplification?
‰
Once
the
expressio
n
for a logic circuit ha
s been
obtained,
we
may be able to
r
e
d
u
c
e
i
t
t
o
a
s
im
p
le
r

form
containing
fewer
terms of fewer variables in
one or m
o
re terms.
‰
The new expression can then be used
to
implement
a circuit that is equivalent
to the original cir
c
uit
but that contains fewer gates and connections.
‰
To illustrate, the circuit of
fig
(a)
can
be simplified
to produce the circuit of fig (b).
‰
Since bo
th circuits perform the
sa
me
logic,
it
sho
u
ld be obvio
u
s tha
t
the
simplest
circuit
is
more
desira
ble
beca
use
it
contains fewer ga
tes a
n
d will
therefore be smaller and chea
per
tha
n

the
original.
‰
Furthermore,
the circuit relia
bility will improve
because there are
f
e
wer inter
c
onnections that
can
be potential circuit faults
. In
subsequent sections
we will study two methods
for simplifying
logic
circuits:
¾
One method will utilize
the
Boolean
algebra
theorems (
Algebraic Method Algebraic Method
) and
¾
The other method will utilize Karnaugh

mapping
(K-map Method)
(
)
(
)
B
A

C

B
A
Y
⋅
⋅
⋅
+
=
C)
(B
A
⋅
+
C
B
⋅
(a) unsimplified circuit
A
B
A
Y
⋅
=
(b) Simplified circuit

14. ALGEBRAIC SIMPLIFICATION ALGEBRAIC SIMPLIFICATION
‰
The Boolean algebra theorems that we studied
earlier
can
be
used
t
o
help
us
simplify the expression for logic circuit.
‰
Unfortunately, it is not always obvious which theorems should be
applied in
order to produce the simplest result.
‰
Furthermore, there is no easy way to tell whether the simplified
e
xpression is
in its simplest form or whether it could have been simplified further.
‰
Thus,
algebraic simplification
often becomes
a process of trial and error a process of trial and error
. With
experience, however, one can become
adept at obtaining reasonably good
results.
‰
The examples that follow will illustrate
many of the ways in which the Boolean
theorems can be applied in trying to simplify an expression.
‰
You should notice that these examples contain two essential steps;
1.
The original expression is put in to the sum-
of-
p
roducts
form
by
repeated
application of De Morgan’s theorems and multiplication of terms.
2.
Once it is in this form the product terms are checked for common
factors, and
factoring is performed wherever possible.
Hopefully, the factoring results in
the elimination of one or more terms.

15. Example # 1 Example # 1 Simplify the expression 9
It is usually a good idea to break down all large inverter signs
using De
Morgan’s theorems and then multiply out all terms
9
With the expression now in sum-of-prod
ucts form, we should look for common
factors.
∴
The first and third terms above have AC in common, which can be
factored out:
)
C
A
(
B
A
ABC
Z
+
=
)
C
A
(
B
A
ABC
Z
+
+
=
C)
(A
B
A
ABC
+
+
=
C
B
A
A
B
A
ABC
+
+
=
C
B
A
B
A
ABC
+
+
=
[multiply out] [theorem (19)]
[cancel double inversions]
[A.A=A]
]
1
B
B
[
=
+
B
A
)
B
AC(B
Z
+
+
=
B
A
AC(1)
Z
+
=
[factor out A]
)
B
A(C
Z
+
=
B
A
AC
Z
+
=

16. Example # 2 Example # 2 9
Simplify the expr
ession
So
lution
:
9
We will look at two
different ways to
arrive at the same result.
Method 1 Method 1
::
9
The
first two ter
m
s have the product AB
in common.
Thus, 9
We can fac
t
or
the variable A fr
om both
terms
9
Invoking theorem
(15)
,
Method 2
:
9
The first two terms have AB in common.
9
The first and the
last
te
r
m
s ha
ve AC
in

common.
9
How do we know whet
her to factor
AB
from
the first two terms or AC from the
two-end terms?
9
Actually
we can do both by using the ABC
term twice.
9
In other words, we can
rewrite
the

ex
press
ion as

9
The extra term ABC is valid and
will
not
change
the value of t
he expression, Since
ABC +A
BC = A
B
C [Theorem(7)]
9
This is the same result as method 1.
9
In
fa
ct, the
same
te
rm can

be
u
s
ed
mo
re
than twice if necessary.
C
B
A
C
AB
ABC
Z
+
+
=
C
B
A
)
C
AB(C
Z
+
+
=
C
B
A
AB(1)
+
=
C
B
A
AB
+
=
C)
B
A(B
Z
+
=
C)
A(B
Z
+
=
ABC
C
B
A
C
AB
ABC
Z
+
+
+
=
B)
B
AC(
C
AB(C
Z
+
+
+
=
)
1
AC
1
AB
⋅
+
⋅
=
C)
A(B
+
=

17. Design procedures of combinational logic circuit using algebraic method
STEP 1 :
Set up the truth table
STEP 2
:
Write the AND term for each case where the output is a 1
STEP 3
:
Write the SOP expression for the output
STEP 4
:
Simplify the output expression
STEP 5
:
Implement the circuit for the final expression

18. Example #1
.
Design a logic circuit that has
three inputs, A, B and C whose
output will be high only when a majority of the inputs are high.
Solution:
Step 1 :
Set up the truth table
BC
A
C
B
A
C
AB ABC
A
B
C
X
00
00
00
10
01
00
01
11
10
0
0
10
11
11
01
11
11
STEP 2

19. Step 3 Step 3
.
Write the Sum Write the Sum
--
ofof
--
products expression for the output. products expression for the output.
Step 4.
ABC
C
AB
C
B
A
BC
A
X
+
+
+
=
Step 4.
Simplify the output expression. Simplify the output expression.
99
This expression can be simplified in several ways. This expression can be simplified in several ways.
99
Perhaps
the
quickest
way is to r
ealize that the last term ABC tw
Perhaps
the
quickest
way is to r
ealize that the last term ABC tw
o o
variables in common with each of the other terms. variables in common with each of the other terms.
99
Factoring the appropriate
pairs of terms ,
we have
Factoring the appropriate
pairs of terms ,
we have
99
Since each term in the parenth
esis is equal to 1, we have
ABC
C
AB
ABC
C
B
A
ABC
BC
A
X
+
+
+
+
+
=
C)
C
AB(
B)
B
AC(
A)
A
BC(
X
+
+
+
+
+
=
Since each term in the parenth
esis is equal to 1, we have
AB
AC
BC
X
+
+
=

20. Step 5. Step 5.
Implement the circuit for the final expression. Implement the circuit for the final expression.
99
The The
X=
AB +
BC +
AC
X=
AB +
BC +
AC
expression is implemented in fig. below. expression is implemented in fig. below.
99
Since the expression
is in
SOP,
the circuit consists of a group
Since the expression
is in
SOP,
the circuit consists of a group
of of
AND gates working into a
s
i
ngle OR gate.
AND gates working into a
s
i
ngle OR gate.
ABAB
BCBC ACAC
X =
AB+ BC +
AC
X =
AB+ BC +
AC

21. Example # 2 Example # 2
:
9
refer to fig (a), where four l
ogic-signal lines A, B, C, D are
being used to
represent a 4-bit binary number with A as
the MSB and D as the LSB. The
binary inputs are fed to a
logic circuit
that produces a HIGH output only when the
binary number is greater than 0110
2
= 6
10
.
9
Design this circuit

Fig.(a)

22. TRUTH TABLE
ABC
D
Z
8
1
0
0
0
9
1
0
0
1
1
0
1
0
1
0
1
1
1
0
1
1
1
2
1
1
0
0
1
3
1
1
0
1
1
4
1
1
1
0
1
5
1
1
1
1
ABC
D
Z
0
0
0
0
0
1
0
0
0
1
2
0
0
1
0
3
0
0
1
1
4
0
1
0
0
5
0
1
0
1
6
0
1
1
0
7
0
1
1
1

23. STEP:2 STEP:2
ABC
D
Z
8
1000
1
9
1001
1
10
1010
1
11
1011
1
12
1100
1
13
1101
1
14
1110
1
15
11
1
1
1
ABC
D
Z
0
0000
0
1
0001
0
2
0010
0
3
0011
0
4
0100
0
5
0101
0
6
0110
0
7
0111
1
D
C
B
A
D
C
B
A
D
C
B
A
CD
B
A
D
C
AB
D
C
AB
D
ABC ABCD
BCD
A

24. Step 3 Step 3
.
SOP expression SOP expression
ABCD
D
ABC
D
C
AB
D
C
AB
CD
B
A
D
C
B
A
D
C
B
A
D
C
B
A
BCD
+
+
+
+
+
+
+
+
=
A

Z
Step:4 Step:4
Simplification Simplification
ABCD
D
ABC
D
C
AB
D
C
AB
CD
B
A
D
C
B
A
D
C
B
A
D
C
B
A
BCD
+
+
+
+
+
+
+
+
=
A

Z
)
D
D
(
ABC
)
D
D
(
C
AB
)
D
D
(
C
B
A
)
D
D
(
C
B
A
BCD
A
Z
+
+
+
+
+
+
+
+
=
ABC
C
AB
C
B
A
C
B
A
BCD
A
+
+
+
+
=
)
C
C
(
AB
)
C
C
(
B
A
BCD
A
+
+
+
+
=
AB
B
A
BCD
A
+
+
=
)
B
B
(
A
BCD
A

+
+
=
A
BCD
A
+
=
A
BCD

Z
+
=

25. AOI LOGIC CIRCUIT AOI LOGIC CIRCUIT
(for example # 1) (for example # 1)

27. NANDNAND
NANDNAND
NANDNAND
NANDNAND

28. NAND/NAND LOGIC CIRCUIT NAND/NAND LOGIC CIRCUIT
AB BC AC
AC
BC
AB
X
⋅
⋅
=

29. AOI LOGIC CIRCUIT AOI LOGIC CIRCUIT
(for example # 2) (for example # 2)

30. 99
We can streamline the process of converting a sum We can streamline the process of converting a sum
--
ofof
--
products c
i
rcuit from AND/OR to NAND gates as fo
llows:
products c
i
rcuit from AND/OR to NAND gates as fo
llows:
1.1.
Replace each AND gate, OR gate,
and Inverter by
a single
Replace each AND gate, OR gate,
and Inverter by
a single
NAND g
a
te
.
NAND g
a
te
.
2.2.
Use
a
NAND g
a
te
t
o
in
v
e
rt
a
n
y
s
i
n
g
l
e

v
a
r
i
a
b
l
e

t
h
a
t
is
fe
e
d
ing

Use
a
NAND g
a
te
t
o
in
v
e
rt
a
n
y
s
i
n
g
l
e

v
a
r
i
a
b
l
e

t
h
a
t
is
fe
e
d
ing

the final OR gate. the final OR gate.
AOI LOGIC CIRCUIT AOI LOGIC CIRCUIT
NAND/
NAND LOGIC CIRCUIT
NAND/
NAND LOGIC CIRCUIT
BCD
A
Y
⋅
=
BCD
A

31. BCD
A
X
+
=
???