Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

CHAPTER 12
COMBINATIONAL LOGIC
Decisions generated by combinational logic involve only the inputs, which constitute
information supplied in the form of statements
...
In the latter case, one has first to assign a binary variable
(symbol) to each of the binary quantities involved, and then obtain a logical
description of the problem in a mathematical language
...
1

Truth Table

The simplest way to describe the problem in a mathematical form is to list the values
of each (binary) output variable corresponding to all the possible combinations of the
(binary) input variables
...
Let us
illustrate this method by the example of a Half-adder, used to add two 1-bit numbers
A and B to generate a (1-bit) SUM and a (1-bit) CARRY as the output
...
1
...

Table 12
...
1
...

It is easy to see that the statement for any combinational logic can be expressed in a
similar manner in terms of three basic operations:
(a) OR – for expressing a condition which is satisfied when any one or more of
the given conditions are satisfied
...

(c) NOT – for expressing a condition which is satisfied if a given condition is not
satisfied
...
2

Basic Postulates of Boolean Algebra

An algebra suitable for expressing problems of combinational logic in a compact
form as well as for convenient manipulation of such logic statements was suggested
by Shannon in 1938, following the original structure proposed by George Boole
(1815-1864), a logician, who had developed an algebra for handling problems of
symbolic logic
...

The basic postulates of Boolean algebra are as follows
...
’ are defined on
Boolean variables so that,
(a)

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 and 1+1 = 1;

(b)

0 + 0 = 0, 0
...
0 = 1 and 1
...


It is obvious that each of these operations is commutative as well as
associative i
...

A+B = B+A, A
...
A
...
(B
...
B
...
e
...
(B+C) = (A
...
C) and A+(B
...
(A+C)
...


The two identities given below follow directly from these postulates:
__

__

A + A = 1 and A
...


(12
...
1)

2

A
0
0
0
0
1
1
1
1

B
0
0
1
1
0
0
1
1

C
0
1
0
1
0
1
0
1

Y
0
1
1
1
1
1
1
1

Y = A+B+C
(a) OR (shown with 3 inputs)

A
0
0
1
1

B
0
1
0
1

Y
0
0
0
1

Y=A⋅B
(b) AND (shown with 2 inputs)

A
0
1

Y
1
0
__

Y=A
(c ) NOT (complementation)

Fig
...
2
...
’ and complementation respectively
...
12
...
1
...
3

De Morgan’s Theorem:

It follows from the logic statement for the OR function that a function
Y=A+B+C+…
has a value ‘0’ only if all the variables A,B, C, … are ‘0’; i
...
one can also express Y
in the following equivalent form:
__

__ __ __

Y = A
...
C
...
3
...
3
...
The equivalences expressed by Eqns
...
3
...
3 2 can be symbolically represented as shown in Fig
...
3
...
Thus an
alternative way of stating De Morgan’s theorem is that “Positive-Logic AND” is
equivalent to “Negative-Logic OR” and vice-versa
...
4

Boolean Expressions

Boolean expressions can be obtained for any combinational logic performing a
prescribed function by the following procedure:
(1)

For each output variable, construct a truth table giving the different values of
the output in question for different combinations of the inputs
...


4

5

Let us illustrate this procedure by considering the design of a 1-bit Full Adder
...
The truth tables for these
outputs for the eight possible combinations of the values that the inputs A, B, C, can
take are shown in Table 12
...
1
...
4
...
Truth Table of Full Adder
A

B

C

CARRY

SUM

MINTERM

0

0

0

0

0

A ⋅B⋅C

0

0

1

0

1

A ⋅B⋅C

0

1

0

0

1

A ⋅B⋅C

0

1

1

1

0

A ⋅B⋅C

1

0

0

0

1

A ⋅B⋅C

1

0

1

1

0

A ⋅B⋅C

1

1

0

1

0

A ⋅B⋅C

1

1

1

1

1

A
...
C
...
4
...
Each such AND function is called a minterm
...
B
...
B
...
B
...
B
...
4
...
4
...
12
...
1
...
4
...
are in the Sum of Products (SOP)
form
...
Clearly, the output will be ‘0’ if an OR
combination of all such terms will be ‘0’
...
4
...

6

SUM = A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ C

Application of De Morgan’s theorem then gives
SUM = (A + B + C) ⋅ (A + B + C) ⋅ (A + B + C) ⋅ (A + B + C)

(12
...
3)

Similarly, the ‘0’ entries in the Truth Table for CARRY can be combined to obtain
the expression
CARRY = A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ C

By applying De Morgan’s theorem, one therefore obtains
CARRY = (A + B + C) ⋅ (A + B + C) ⋅ (A + B + C) ⋅ (A + B + C)

(12
...
4)

Eqns
...
4
...
4
...
An OR function of
n literals in an n-variable problem is called maxterm, just as an AND function of n
literals is called a minterm; e
...
for the Full Adder (A + B + C) is a maxterm
...
12
...
1 and 12
...
2 is a minterm, and
each sum term in Eqns
...
4
...
4
...
Such expressions constitute
the two canonical forms of Boolean expressions, and are referred to as the standard
SOP and POS forms respectively
...

A systematic method for obtaining a Boolean expression directly in the minimal sum
of products form is based on a geometric representation of the truth table called the
Karnaugh Map
...

12
...
It can be constructed for any number of input variables, though it is useful as a
design tool only up to 4 variables
...
If n is
even, one chooses m = n/2 for the sake of symmetry and convenience, while for odd
values of n, m and n−m and made to be consecutive integers
...
The configurations of 2-variable, 3-variable and 4variable K-maps are given in Fig
...
5
...


7

8

The K-map for a given Boolean function of a variables is constructed by entering ‘1’
and ‘0’s in the squares of an n-variable K-map, where the given Boolean function has
the values ‘1’ and ‘0’ respectively
...
12
...
2
...
Note that each minterm in Eqns
...
4
...
4
...
It is thus possible to write Eqns
...
4
...
4
...

Let us now see how a Boolean expression in a minimal form can be written down
directly from the K-map
...
Hence if the K-map for a given Boolean function has
‘1’ entered in any two adjacent squares, one can combine the two (n-variable)
minterms representing these two squares into a single (n-1)-variable term
...

Let us consider the CARRY output of a full-adder to illustrate this process
...
12
...
2 with the 3 sets of adjacent pairs to squares
indicated by loops
...
12
...
1,
__

__

A
...
C + A
...
C = A
...
(C + C) = A
...
B
...
B
...
C
...
C and
__

__

A
...
C + A
...
C = B
...
(A + A) = A
...
e
...
B, A
...
C) represents a pair of two squares
corresponding to two minterms differing only one of the three literals
...

CARRY = A
...
C + B
...
5
...

It is obvious from the foregoing algebraic considerations that the two extreme
columns in a 3-variable K-map have to be treated as adjacent
...

The combination of two adjacent squares to simplify the Boolean expression can
obviously be extended to the combination of two such adjacent pairs of squares,
which would then be represented by an (n-2)-variable term
...
The number
9

10

of squares which can thus be grouped together so as to be represented by a single
term is therefore a power of 2, e
...
2, 4, 8 and so on
...
Fig
...
5
...

The K-map method can also be used to obtain a Boolean expression in the minimal
product of sums form
...
e
...
12
...
2, one can write
CARRY = A ⋅ B + A ⋅ C + B ⋅ C

(12
...
2)

By virtue of De Morgan’s theorem, therefore
CARRY = (A+B) ⋅ (A+C) ⋅ (B+C)

(12
...
3)

which is in the minimal product of sums form
...
6

K-map for Incompletely Specified Functions (with Don’t Care States)

For the example considered above, the two alternative minimal expressions have the
same degree of complexity
...
This consideration
becomes really significant in the case of incompletely specified functions, which do
not involve some of the minterms at all, so that these can be chosen arbitrarily as ‘0’
or ‘1’ to assist the designer in obtaining minimal expressions
...
In such a case, one enters ‘φ’ (a
superimposition of ‘0’ and ‘1’) in each of the squares corresponding to the minterms
not to be encountered at all, and combines these so-called don’t care states either
with ‘1’s or with ‘0’s as desired to obtain the largest possible binary groups
...


(2)

Decide whether the sum of products or the product of sum form is to be
obtained, and identify the selected squares accordingly
...


(4)

Form binary groups of 2 with those of the remaining selected squares
which are not members of any larger binary group, and write down the
(n-1)-variable terms required to include all such selected squares
...


(6)

If n > 3, repeat step 3 for binary groups of 8, and obtain the necessary
(n-3)-variable terms
...


(8)

In the formation of binary groups in any of the foregoing steps, any of the
selected squares can be repeatedly included in as many groups as
necessary for forming the largest possible group
...

12
...
The
configuration of the 7-segments, their usual nomenclature and the requirement for
each of these segments to be lighted are given in Fig
...
7
...
These requirements are
directly put in the form of four K-maps, one for the segment a and one each for the
pairs of segments bc, de and fg
...
Reading the
‘1’s, including the don’t care squares wherever convenient, from these K-maps gives
Boolean expressions for the 7 outputs in the minimised SOP form, as given below
...
7
...
7
...
7
...
7
...
7
...
7
...
7
...

a = C ⋅A + C⋅A + D + B
b = B⋅A + B⋅A + C
c=C +B +A
d = C⋅B⋅A + C⋅A + C⋅B + B⋅A + D
e = C⋅A + B⋅A
f = C⋅B + C⋅A + B⋅A + D

g = C ⋅B + C ⋅B + B⋅ A + D
These expressions in the product of sums form are obtained by applying De
Morgan’s theorem
...
7
...
7
...
7
...
7
...
7
...
7
...
7
...
12
...
9,12
...
10 and 12
...
12 give identical expressions for b, c and e as Eqns
...
7
...
7
...
7
...
This is
typical of problems involving incompletely specified functions
...
8

Commercially available Gates

A combinational circuit is the circuit realisation of any combinational logic
...
A study of the available logic modules is therefore
necessary before one can proceed with the design procedure of combinational circuits
using gates
...
In
addition, combination gates like AOI (AND-OR-INVERT) gates are also available as
commercial gate “chips”
...
12
...
1
...
12
...
2
...
This uniformity in
cost is consequence of the fact that the tremendously successful mass production
technology employed by the manufacturers of semiconductor devices has or ought
the production cost of the actual semiconductor chip down to less than 1/10 of the
ultimate cost of the packaged device which depends mainly on three factors- (i) the
cost of the package itself, (ii) the volume of production, and (iii) the yield of the
product
...
To reduce the package cost, the semiconductor houses have standardised
the package for gates to a 14-pin dual –in-line plastic (DIP) package
...
As a result of this standardisation, NOT/OR/ AND/ NOR/ NAND gates are
available in the following standard chip configurations:
1
...

3
...

5
...
9

Hex inverters – a total of 6 inputs and 6 outputs per chip
...

Triple 3- input gates – a total of 9 inputs and 3 outputs per chip
...

Single 8- input gates – a total of 8 inputs and 1 output per chip
...
g
...
12
...
1 has its output Y equal to one of its four
(data) inputs I0, I1, I2 and I3 depending on whether the value of the 2-bit control
(input) BA is 00, 01, 10 or 11
...
A
...
A
...
A
...
A
...
9
...
It is obvious that a multiplexer is in fact a direct embodiment
of a truth table
...
1
...
12
...
1, indeed represent the truth table
...
Like gates,
multiplexers are also available in quad 2-input, dual 4-input and single 8-input
packages, the standard package for multiplexers being a 16-pin DIP package
...
10 Circuits Using Gates Only

Once a given problem of combinational logic has been expresses in terms of Boolean
expressions for the output variable, circuit realisations using AND gates, OR gates
and inverters follow in a straightforward fashion
...
12
...
1, which give two alternate circuit realisations of the CARRY
output of a Half-adder
...

CARRY
and

=

A
...
+ A
...
C

(12
...
1)

CARRY

=

(A+B)
...
(B+C)

(12
...
3)

One notes that each of the two circuits needs both AND and OR gates
...
Eqn
...
5
...
can be
written in the equivalent form
CARRY

=

A
...
A
...
B
...
10
...
)

Which immediately leads to the circuit realisation given in Fig
...
10
...
Circuits having such structures are called two-level NAND or
NAND-NAND realisations
...

An alternative realisation using NOR gates only results if De Morgan’s theorem is
applied to Eqn
...
5
...
10
...
)

which has the two-level NOR or NOR-NOR realisation shown in Fig
...
10
...

Like to NAND-NAND realisation, the NOR-NOR realisation is also possible for any

18

19

combinational logic problem, as the Boolean expression for any output variable can
always be obtained in a minimal product of sums form
...
12
...
e
...
A comparison of the four
circuits given in Fig
...
10
...
However, one should not generalise on the basis
of this comparison that the four alternative circuit realisations always require the
same chip count
...

12
...
12
...
Such a scheme requires a multiplexer with n-bit control i
...
a 2ninput multiplexer, for an n-variable problem
...
A more practical scheme for realising any combinational logic with
multiplexers is to generate inputs from one of the n variables, using the remaining (n1) variables as the control inputs
...
The exact procedure for generating the necessary input from the K-map(s)
pertaining to a given problem is outlined in Fig
...
11
...
The
functional dependence of the inputs I0, I1, I2 and I3 on the variable C would be
determined by the entries in the pairs of squares indicated by I0, I1, I2 and I3
respectively in the K-map
...
12
...
2
...


__

Thus if both C and C are available, a Full Adder can be realised by a dual 4-input
multiplexer, resulting in half the chip count in comparison with a realisation using 8input multiplexers
...
Fig
...
11
...
Thus if a 4-input multiplexer is used to realise a 4-variable
K-map, using A as the control of the multiplexer, the four inputs I0, I1, I2 and I3 can
be read off from these four parts in the same manner as any K-map is read, and
Boolean expressions written for these four inputs in terms of the remaining variables
C and D, This would of course require some gates besides as many multiplexers as
the number of output variables, but the total chip count would in general be lower in
this approach
...
12
...
Referring back to the K-maps given in Fig
...
7
...
and using BA as the
control, one can prepare a table of the required input functions I0 to I3 from the Kmaps of the seven segments, as given in Table 12
...
1
...
As seen from the table, there is only one nontrivial input
function D
...

Segment ‘c’ has the simplest Boolean expression, which can be realised by a 3-input
NOR gate:
c=C
...
A=C+B+A
Assuming the complements of the variables to be available, this leads to a chip count
of 4, as compared to 7 chips in a NAND-NAND realisation
...
11
...
Multiplexer input functions for BCD to 7-segment decoder

Input No

a

b

c

d

e

f

g

I0

C

0

0

C

C

0

__ __

I1

__ __

C

0

__ __

1

__ __

__ __

D
...
C

I2

C

C

C

0

0

C

0

I3

0

0

0

C

1

1

C

D
...
C

D

---