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

---

Digital Circuits - Canonical & Standard Forms
We shall get four Boolean product terms by combining the two
variables x and y using the logical AND operator
...
The minimal terms are X'y', X'y, XY',
and XY
...
Standard
sum terms or Max terms are other names for these Boolean sum
words
...

The following table displays the representation of minimum
terms and maximum terms for two variables
...
In a similar manner, if the binary variable is "1," it is

shown as the variable's complement in the Max term and as the
variable itself in the Min term
...
If there are ‘n’ Boolean
variables, then there will be 2n min terms and 2n Max terms
...
If there are
‘n’ input variables, then there will be 2n possible combinations
with zeros and ones
...
So, each output
variable will have ‘1’ for some combination of input variables and
‘0’ for some other combination of input variables
...

Canonical SoP form
• Canonical PoS form
Canonical SoP form
•

It stands for Canonical Sum of Products form
...
These product terms
are only the minimum terms, then
...

To acquire the Boolean expression function that corresponds to
that output variable, first determine the minimum terms for
which the output variable is one
...
The shape of this Boolean function will be sum
of min terms
...

Example
Consider the following truth table
...
The
corresponding min terms are p’qr, pq’r, pqr’, pqr
...


Therefore, the Boolean function of output is, f = p’qr + pq’r + pqr’
+ pqr
...
We can also
represent this function in following two notations
...
In other equation, we used the symbol for
summation of those min terms
...
Each sum term in
this form includes all literals
...
As a result, the canonical PoS form is also
known as the Max terms form's product
...
Then, logically AND those Max terms
...

If there are other output variables, follow the same process for
each of them
...
Here, the
output ff is ‘0’ for four combinations of inputs
...
By doing logical AND of these four Max terms, we will get
the Boolean function of output ff
...
p+q+r′p+q+r′
...
p′+q+rp′+q+r
...
We can also represent this
function in following two notations
...
M1
...
M4f=M0
...
M2
...
In other equation, we used the symbol for
multiplication of those Max terms
...
p+q+r′p+q+r′
...
p′+q+rp′+q+r is
dual of the Boolean function, f = p’qr + pq’r + pqr’ + pqr
...
Functionally, these two forms are same
...

Standard SoP and PoS forms
We discussed two canonical forms of representing the Boolean
outputss
...
These are the simplified version of
canonical forms
...
The
main advantage of standard forms is that the number of inputs

applied to logic gates can be minimized
...

Standard SoP form
Standard SoP form means Standard Sum of Products form
...
So, the
product terms may or may not be the min terms
...

We will get Standard SoP form of output variable in two steps
...


Follow the same procedure for other output variables also, if
there is more than one output variable
...
In that case, both
canonical and standard SoP forms are same
...

f = p’qr + pq’r + pqr’ + pqr
The given Boolean function is in canonical SoP form
...

Step 1 − Use the Boolean postulate, x + x = x
...
So, we can write the last term pqr
two more times
...

⇒ f = qrp′+pp′+p + prq′+qq′+q + pqr′+rr′+r
Step 3 − Use Boolean postulate, x + x’ = 1 for simplifying the
terms present in each parenthesis
...
1 = x for simplifying above
three terms
...
Therefore, the standard
SoP form corresponding to given canonical SoP form is f = pq +
qr + pr
Standard PoS form
Standard PoS form means Standard Product of Sums form
...
So, the
sum terms may or may not be the Max terms
...

We will get Standard PoS form of output variable in two steps
...


Follow the same procedure for other output variables also, if
there is more than one output variable
...
In that case, both
canonical and standard PoS forms are same
...

f = p+q+rp+q+r
...
p+q′+rp+q′+r
...
Now, we
have to simplify this Boolean function in order to get standard
PoS form
...
x = x
...
So, we can write the first term p+q+r
two more times
...
p+q+rp+q+r
...
p+q+r′p+q+r′
...
p′+q+rp′+q+r
Step 2 − Use Distributive law, x + y
...
z = x+yx+y
...

⇒ f = p+q+rr′p+q+rr′
...
q+r+pp′q+r+pp′
Step 3 − Use Boolean postulate, x
...

⇒ f = p+q+0p+q+0
...
q+r+0q+r+0
Step 4 − Use Boolean postulate, x + 0 = x for simplifying the terms
present in each parenthesis
⇒ f = p+qp+q
...
q+rq+r
⇒ f = p+qp+q
...
p+rp+r

This is the simplified Boolean function
...
q+rq+r
...
This is the dual of the Boolean
function, f = pq + qr + pr
...


Digital Circuits - K-Map Method
In previous chapters, we have simplified the Boolean functions
using Boolean postulates and theorems
...

To overcome this difficulty, Karnaugh introduced a method for
simplification of Boolean functions in an easy way
...
It is a
graphical method, which consists of 2n cells for ‘n’ variables
...

K-Maps for 2 to 5 Variables
K-Map method is most suitable for minimizing Boolean functions
of 2 variables to 5 variables
...

2 Variable K-Map
The number of cells in 2 variable K-map is four, since the number
of variables is two
...


There is only one possibility of grouping 4 adjacent min
terms
...

3 Variable K-Map
•

The number of cells in 3 variable K-map is eight, since the
number of variables is three
...


•

•

•

There is only one possibility of grouping 8 adjacent min
terms
...

The possible combinations of grouping 2 adjacent min
terms are {(m0, m1), (m1, m3), (m3, m2), (m2, m0), (m4,
m5), (m5, m7), (m7, m6), (m6, m4), (m0, m4), (m1, m5), (m3,
m7) and (m2, m6)}
...

4 Variable K-Map
•

The number of cells in 4 variable K-map is sixteen, since the
number of variables is four
...


•

•

•

There is only one possibility of grouping 16 adjacent
min terms
...
Similarly, C1, C2, C3 and C4 represents the
min terms of first column, second column, third
column and fourth column respectively
...

If w=0, then 4 variable K-map becomes 3 variable Kmap
...
The following figure shows 5 variable KMap
...

There are two possibilities of grouping 16 adjacent min
terms
...
e
...

If v=0, then 5 variable K-map becomes 4 variable Kmap
...
Similarly, you can use exclusively the Max terms
notation
...


Similarly, if we consider the combination of inputs for which the
Boolean function is ‘0’, then we will get the Boolean function,
which is in standard product of sums form after simplifying the
K-map
...

•

•

•

•

•

Select the respective K-map based on the number of
variables present in the Boolean function
...
If the Boolean function is given as sum of
products form, then place the ones in all possible cells
of K-map for which the given product terms are valid
...
It should be powers of two
...
Highest power is equal to the number of
variables considered in K-map and least power is zero
...
It is known as prime implicant
...

Note down all the prime implicants and essential prime
implicants
...


Note 1 − If outputs are not defined for some combination of
inputs, then those output values will be represented with don’t
care symbol ‘x’
...

Note 2 − If don’t care terms also present, then place don’t cares
‘x’ in the respective cells of K-map
...
In those cases, treat the don’t care value as ‘1’
...

The given Boolean function is in sum of products form
...
So, we require 4 variable K-map
...


Here, 1s are placed in the following cells of K-map
...


•

•

The cells, which are common to the intersection of
Rows 3 & 4 and columns 3 & 4 are corresponding to the
product term, WY
...


There are no possibilities of grouping either 16 adjacent ones or
8 adjacent ones
...
After these three groupings, there is no single one
left as ungrouped
...

The 4
variable
K-map with
these
three groupings is shown in the following figure
...
All these
prime implicants are essential because of following reasons
...
Only fourth row
grouping covers those two ones
...
Only the square shape
grouping covers that one
...
Only fourth column
grouping covers those two ones
...

•

•

•

•

•

Select the respective K-map based on the number of
variables present in the Boolean function
...
If the Boolean function is given
as product of sums form, then place the zeroes in all
possible cells of K-map for which the given sum terms
are valid
...
It should be powers of two
...
Highest power is equal to the number of
variables considered in K-map and least power is zero
...

It is known as prime implicant
...

Note down all the prime implicants and essential prime
implicants
...

Note − If don’t care terms also present, then place don’t cares ‘x’
in the respective cells of K-map
...
In those cases, treat the don’t care value as ‘0’
...

The given Boolean function is in product of Max terms form
...
So, we require 3 variable K-map
...
The 3 variable K-map with
zeroes corresponding to the given Max terms is shown in the
following figure
...
There are three possibilities of grouping 2
adjacent zeroes
...
The 3 variable K-map with these
three groupings is shown in the following figure
...
All these
prime implicants are essential because one zero in each
grouping is not covered by any other groupings except with their
individual groupings
...
Y+ZY+Z
...
For more than 5 variables, it is
difficult to simplify the functions using K-Maps
...

Due to this checking and grouping of adjacent
ones mintermsminterms or
adjacent
zeros MaxtermsMaxterms will be complicated
...


Quine-McCluskey Tabular Method

In previous chapter, we discussed K-map method, which is a
convenient method for minimizing Boolean functions up to 5
variables
...

Quine-McClukey tabular method is a tabular method based on
the concept of prime implicants
...

This tabular method is useful to get the prime implicants by
repeatedly using the following Boolean identity
...
1 = x
Procedure of Quine-McCluskey Tabular Method
Follow these steps for simplifying Boolean functions using
Quine-McClukey tabular method
...
So, there will be at most ‘n+1’ groups if
there are ‘n’ Boolean variables in a Boolean function or ‘n’ bits in
the binary equivalent of min terms
...
If
there is a change in only one-bit position, then take the pair of
those two min terms
...

Step 3 − Repeat step2 with newly formed terms till we get
all prime implicants
...
It consists of set of
rows and columns
...
Place ‘1’ in the cells
corresponding to the min terms that are covered in each prime
implicant
...
If the min term is covered only by one prime implicant,
then it is essential prime implicant
...

Step 6 − Reduce the prime implicant table by removing the row
of each essential prime implicant and the columns
corresponding to the min terms that are covered in that essential
prime implicant
...
Stop this process when all min terms of given Boolean
function are over
...

The given Boolean function is in sum of min terms form
...
The given min terms are 2, 6, 8, 9,
10, 11, 14 and 15
...
The following table shows these min
terms and their equivalent binary representations
...
The
following table shows the possible merging of min terms from
adjacent groups
...
That differed bit is represented
with this symbol, ‘-‘
...
The following
table shows the possible merging of min term pairs from
adjacent groups
...
That differed bit is represented
with this symbol, ‘-‘
...
Here, these
combinations of 4 min terms are available in two rows
...
The reduced table after
removing the redundant rows is shown below
...
There are three rows in the above table
...
Therefore, the prime
implicants are YZ’, WX’ & WY
...

Min terms /
Prime
Implicants

2

6

YZ’

1

1

WX’
WY

8

9

10

11

1
1

1

14

15

1

1

1

1

1

1

1

The prime implicants are placed in row wise and min terms are
placed in column wise
...

The min terms 2 and 6 are covered only by one prime
implicant YZ’
...
This will be
part of simplified Boolean function
...
The
reduced prime implicant table is shown below
...
So, it is an essential prime implicant
...
Now, remove this prime
implicant row and the corresponding min term columns
...

Min terms /
Prime
Implicants

15

WY

1

The min term 15 is covered only by one prime implicant WY
...
This will be part of simplified
Boolean function
...
Therefore, the simplified Boolean
function is
fW,X,Y,ZW,X,Y,Z = YZ’ + WX’ + WY

---