Comparison
with the method of Karnaugh |
Synthesis |
|
|
Simplification
of the functions |
||
|
Return
to the synopsis |
To
contact the author |
Low
of page |
Created it, 06/09/09
Update it, 06/09/15
N° Visitors
4. - METHOD OF QUINE-MAC CLUSKEY
Although little employed, we must nevertheless quote a method different from that of the tables from Karnaugh for simplification from the functions from several variables. It is about a method imagined by the American mathematician W.V. QUINE and reorganized by its compatriot Doctor Edwards J. Mac CLUSKEY Junior in a thesis of doctorate which he presented at M.I.T. (Massachusetts Institute off Technology) in June 1956.
4. 1. - DESCRIPTION OF THE METHOD
To examine this method, we will take an example with four variables. Let us leave the truth table of the function f (a, b, c, d) which is given on figure 54.
We can note that the function f is “true” (equal to 1) for eleven combinations of the variables a, b, c and d.
Let us give as name with each one of these combinations the decimal value which corresponds to the binary code formed by the variables a, b, c, d by considering that a is the bit of strong weight and d the bit of weak weight.
Example :
0110 = 
bc
: we will call it combination 6 since 0110
into binary is equivalent to 6 into decimal.
If we recapitulate, the function f is thus the sum of the summarized combinations figure 55 :
This list can be recapitulated in the following way :
From this list of combinations really the method of QUINE-MAC CLUSKEY starts.
The first thing to be made is to classify these combinations in a whole successive according to the number of zeros of the binary format of each combination while starting with that which counts some more.
The first unit is thus formed by the combination 0 whose binary format 0000 comprises four zeros. The second unit gathers the combinations comprising three zeros… until the fifth which is formed of the combination 15 whose binary format 1111 does not comprise a zero of the whole.
The five sets are represented figure 56.
The second phase of the method consists in comparing the terms of each whole with the terms of the unit which immediately follows in order to eliminate a variable if that is possible.
Combination 0000 of unit 1 must thus be compared with the four combinations of unit 2. Then each of the four combinations of this unit 2 will be compared with each of the three combinations of unit 3 and so on until unit 5…
When two combinations differ only from ONE VARIABLE, those cannot be associated to form of them any more but one in which the variable which differs can be eliminated.
When a variable is eliminated in such an association, one announces this fact by replacing this variable by a cross (or any other sign with your suitability).
In the example that we chose, combinations 0 and 1 can, for example, being associated since only the variable d is different :
Let us proceed thus by comparing each term of each whole with each term of the following unit and we obtain the combinations described in figure 57.
We obtain new members gathered now in four sets I, II, III and IV. Let us start again the same operation with these new sets. Figure 58 gives the new combinations obtained.
In the general principles of the method of QUINE-MAC CLUSKEY, it is advisable to continue this process until there is no more possible combination between one of these sets and the following.
In the example chosen, we arrived from there at this point. Moreover, we note in this figure that several combinations are identical. We will of course keep only the different groupings which we will call A, B, C, D, E and F (figure 58).
The function f takes the form then :
f = A + B + C + D + E + F, Is :
f = 
+
+
+ b
+ a
+ ab
NOTE :
In all the regroupings which we carried out, it could have happened that certain terms of a unit do not combine with any term of the following unit. These terms are then terms first and it is advisable not to forget them in the final equation.
Arrived at this stage, it is advisable to check if the equation obtained cannot be simplified yet. To eliminate the possible superfluous terms, let us form a grate known as “diagram of the terms first”.
This diagram represented figure 59 comprises eleven columns corresponding to the initial combinations 0, 1, 2, 4, 6, 8, 9, 12, 13, 14 and 15. It includes/understands in addition six horizontal lines corresponding to the six groupings A, B, C, D, E and F obtained after the various processes of simplification.
On each line, let us mark of a cross the combinations having been used to form the grouping considered.
For example for the grouping A which utilizes combinations 0, 1, 8 and 9, we notched on line A columns 0, 1, 8 and 9. After having made in the same way for the lines B, C, D, E and F, we note that certain columns (1, 2 and 15) comprise only one cross which we then surround of a circle. These combinations are located on the lines A, B, and F which are called “base lines”.
We note that in addition the combinations included in the lines C, D, E are found at least once in the lines A, B and F. The lines C, D and E can thus be removed and the function f is thus simplified still to become :
f = A + B + F
f =
+
+ ab
4. 2. - COMPARISON
WITH THE METHOD OF KARNAUGH
As comparison, let us carry out the same exercise by the method of the tables of KARNAUGH. Using the pointed out truth table figure 60-a, let us draw up the table of corresponding KARNAUGH (figure 60-b).
The regroupings carried out in this table (ringed of red in the figure) give the solution immediately :
f = 1 + 2 + 3
f =
+
+ ab
One finds the same result as previously.
CONCLUSIONS :
In the light of this example, solved on the one hand with the method of QUINE MAC CLUSKEY, on the other hand thanks to a table of Karnaugh, it appears that the second is definitely simpler, fast and tempting that the first. This explains why this first method is almost unemployed. We will not extend more on it.
Let us specify however with its discharge that this method of QUINE MAC CLUSKEY applies whatever the number of variables whereas the method of the tables of Karnaugh becomes complicated notably when the number of variables increase and becomes higher than 6 or 7.
5. - SYNTHESIS
In this chapter called synthesis, we will make a recall of all the important concepts necessary to the study and the realization of circuits and diagrams of combinatory logic electronics since the combinatory logic was the object of our concern in the first three theories.
Indeed, one calls combinatory logic any circuit in which the exits are an only function of the values of the entries, independently of time.
5. 1. - VARIABLE
One calls logical variable any quantity likely to take only two values 1 or 0.
5. 2. - FUNCTION
When two simple Boolean variables a and b vary in such way that to each value of "a" a well defined value of b corresponds, the quantity b is related to a.
We write b = f(a).
5. 3. - TRUTH TABLES
Figure 61 recapitulates the various basic switching functions.
With each switching function, corresponds a truth table and a logical equation. The truth table indicates the state of the exit of the function considered, according to the state of the variables of entry.
5. 4. - GRAPHIC SYMBOLS
Figure 62 gives the various charts used for the switching functions.
5. 5. - TABLES OF KARNAUGH
The number of boxes, constituting the table, is a function of the number of
variables brought into play. It was seen that a variable could take two states :
“1” or “0”.
Two variables will be able to take four combinations of states :
1 Þ “0” and “0”
2 Þ “0” and “1”
3 Þ “1” and “0”
4 Þ “1” and “1”
The number of possible combinations is given by the formula:
x = 2n with n = numbers of variables.
5. 5. 1. - TABLE OF KARNAUGH A ONLY ONE VARIABLE
Example : function YES, x = a.
The electric state of S is not a function
that of “a”. one a : x
= 21 = 2 boxes.
Figure 63 gives the table of Karnaugh of this function.
5. 5. 2. - TABLE OF KARNAUGH A TWO VARIABLES
Figure 64 in the case of gives the configuration of the table of Karnaugh two variables.
Example: S = a + b x = 22 = 4 boxes
has) Location of the two variables :
The state “1” of a variable occupies
half of the boxes,
The state “0” of a variable occupies
other half (figure 65).
b) Location of a sum of two variables :
This sum is represented by the whole of the boxes belonging to the two
variables,
The location will be done by “0” and
from the “1” which has the same
significance that in the truth tables, that is to say S
= a + b.
Figure 66 gives the truth table and the table of corresponding Karnaugh.
c) Location of a product of two variables :
This product is represented by the whole of the boxes common to both variables
as for the circles of Euler, That is to say S = a . b.
Figure 67 gives the truth table and the table of corresponding Karnaugh.
d) Location of an unspecified function with two variables:
Either S = a
+ b,
figure 68 gives the table of corresponding Karnaugh.
One locates initially the product a
then the productb.
5. 5. 3. - TABLE OF KARNAUGH A THREE VARIABLES
x = 23 = 8 boxes
Either S = a + bc, figure 69 gives the table of Karnaugh of this function.
5. 5. 4. - TABLE OF KARNAUGH A FOUR VARIABLES
x = 24 = 16 boxes
Either S = (a + b) . (c + d), the truth table and the table of Karnaugh of this function are represented figure 70.
5. 5. 5. - CASE OF MORE THAN FOUR VARIABLES
One uses several tables of Karnaugh with four variables which one superimposes. Their double number to each time one adds a new variable beyond four.
Example : 4 variables = 1 table
5 variables = 2 tables
6 variables = 4 tables
7 variables = 8 tables
One can also employ the method of Mac CLUSKEY seen previously.
5. 6. - SIMPLIFICATION OF THE FUNCTIONS
The representation of the functions on a table of Karnaugh makes it possible to detect simplifications quickly.
5. 6. 1. - RULE :
The minimal equation will be obtained as a practitioner the maximum groupings by
power of 2, (2, 4, 8 boxes), of adjacent boxes.
The expression of a grouping contains only the variables which do not change a
state (figure 71).
Another type of possible grouping :
It is necessary to regard the table of figure 72 as which can roll itself on itself to meet on the lines AB and CD or lines AC and BD
Only the surface of a torus could return this image (figure 72-b).
When the groupings are carried out, one deduces the minimal equations from them.
5. 6. 2. - EXAMPLES :
That is to say the function S = a + ab
whose figure 73 gives the table of Karnaugh
The equation deduced from the grouping is S = a, a is the only variable which in this grouping does not change a state.
To simplify the function: L =
+ a
+ b
Figure 74 gives the corresponding tables of Karnaugh.
The simplified equation is thus :
L =
+
To simplify the function : L = bd +
+ acd
+ c
+ abc
Figure 75 gives the corresponding tables of Karnaugh.
.gif)
From where the simplified equation :
L = ac + bd +
5. 7. - THEOREM OF MORGAN
1st theorem :
The
complement of a sum is equal to the product of each one of its complémentés
terms. Thus, the complement of a + b is
.
One writes :
=
.
2nd theorem :
The
complement of a product is equal to the sum of each one of its complémentés
terms. Thus, the complement of a . b is
+
One writes : 
=
+
In the following chapter, we propose two solved problems to you which will enable you into practice to put the whole of acquired knowledge.
We propose to you to finish several series of exercises whose solutions are given after each series. (On another site envisaged to this end).
End of this lesson and we will learn how to solve some problems on another page in order not to encumber this one.
|
Click
here for the following lesson or in the synopsis envisaged to this end. |
High
of page |
 Preceding
page |
Following
page |
