Created it, 06/09/09
Update it, 06/09/17
N° Visitors
2. 3. - MATRIC METHOD OF HUFFMAN
We know that the table of Karnaugh does not make it possible to solve a sequential problem directly. Indeed, it can exist for each combination of the variables of entry only one value for the exit, i.e. a value by elementary box of the table.
It is thus advisable to seek a representation which allows the introduction of one or several variables secondary as considering previously.
2. 3. 1. SEQUENCE
One calls sequence a buckled succession of stable states separated by transitory states.
Figure 19 represents an example of sequence.
2. 3. 2. - RESOLUTION OF A PROBLEM BY THE MATRIC METHOD
To illustrate this method, still let us take again the same example.
a) Analyze
One lays out of two variables of entry m and a.
These two variables make it possible to obtain 22 = 4 combinations.
Like starting point, one is useful oneself of a table with four columns corresponding to the combinations of the entries which one arranges according to the considered binary code. In a fifth column, one will register the binary value of the output. The table is represented figure 20.
Let us take again the operation of the assembly and define the number of stable states :
Initial state
a = 0, m = 0 with L = 0
Action on m
a = 0, m = 1 from where L = 1
m is slackened
a = 0, m = 0 and L always with 1
Action on a
a = 1, m = 0 and L = 0
Simultaneous action on a and m a
= 1, m = 1 one chose to privilege the stop : L
= 0
b) Construction of the primitive matrix of the states.
One calls primitive matrix of the states a table of the model of figure 20 in which there is a line by stable state as represented figure 21.
One positions each stable state in the box for which the variables m and a are with the values having involved this stable state.
Example :
For a
= 0, m = 0
stable state ,
L = 0
a
= 0, m = 1
stable state ,
L = 1
a
= 0, m = 0
stable state ,
L = 1
a
= 1, m = 0
stable state ,
L = 0
a
= 1, m = 1
stable state ,
L = 0
It is now necessary to position the transitory states.
The transitory states are located at the intersection of the line on which figure the initial state stable and of the column in which figure the following stable state.
Figure 22 shows these transitory states.
We know that it is impossible that two variables commutate simultaneously. To materialize this on the primitive matrix, it is advisable to hatch to eliminate them, all the boxes for which on the same line two variables change compared to the combination of the variables which caused the stable state included in this line.
We obtain thus the table of figure 23.
In our example : for the
stable state
a = 0, m = 0, it is necessary to hatch
the box where a = 1, m = 1
for the stable state
a = 0, m = 1, it is necessary to hatch
the box where a = 1, m = 0
for the stable state a
= 0, m = 0, it is necessary to hatch the box where a
= 1, m = 1
for the stable state
a = 1, m = 0, it is necessary to
hatch the box where a = 0, m = 1
for the stable state
a = 1, m = 1, it is necessary to
hatch the box where a = 0, m = 0
It is now necessary to examine the remaining boxes.
Line 1 :
Put 10 (a = 1, m = 0)
If one supports on a
whereas L is extinct, one evolves to a
situation similar at the stable state
(a = 1, m = 0, L = 0), one thus writes 3
in the box what shows that one passes by the transitory state 3.
Line 2 :
Put 11 (a = 1, m = 1)
If one supports on a
whereas m was not slackened, one thus
goes towards the extinction of the lamp towards the stable state
(a = 1, m = 1, L = 0). One registers 4
in the box.
Line 3 :
Put 01 (a = 0, m = 1)
If one supports on walk
whereas the lamp is already lit, this does not have an effect and one goes
towards the stable state
(a = 0, m = 1, L = 1), one thus writes 1
in the box.
Line 4 :
Put 00 (a = 0, m = 0)
One slackens a
and the lamp remains extinct, one thus goes towards the stable state
(a = 0, m = 0, L = 0), one writes 0
in the box.
Line 5 :
1) Put 01 (a = 0, m = 1)
One slackens a
whereas a and m
were actuated and that L was extinct. The
lamp is re-ignited because one returns in a stable state
(a = 0, m = 1, L = 1), one thus writes 1
in the box.
2) Put 10 (a = 1, m = 0)
One slackens the button walks
whereas L is extinct, one thus returns
towards the stable state
(a = 1, m = 0, L = 0), one thus writes 3
in the box.
One thus obtains the supplemented primitive matrix of figure 24.
c) Research of the contracted matrix
It is desirable to bring back the primitive matrix of the states to a matrix contracted in order to decrease the number of additional lines, those introducing of new excitations and new complementary variables or transfers.
Rules of contraction or fusion :
It is possible to vertically contract the primitive matrix
of the states by superimposing two lines if they present the same states.
One can amalgamate two lines in only one when there are a stable state or a of
the same transient number located in the same column or a stable or transitory
state with a hatched box located in the same column, indeed, the hatched box
indicates that, for technological reasons, this case cannot occur and is thus
indifferent.
The outputs do not intervene in the possible superpositions.
Study of the possibilities for line 1 :
Let us compare line 1 with line
2 : they are not superposable bus for a = 0 and m =
0, one has the state
on the first line and 2 over the
second.
Let us compare line 1 with line
3 : they are not superposable because one has
on the first line and 2 on the third
for a = 0 and m = 0.
Let us compare
line 1 with line 4 : these two lines are superposable because one a
corresponds to 0, to 1 corresponds an impossibility, to an impossibility
corresponds 4, to 3 corresponds .
Let us compare line 1 with line 5 : these two lines are superposable.
For line 2, the possible combinations are :
Lines 2 and 3 superposable.
Lines 2 and 4 nonsuperposable.
Line 2 and 5 superposable.
For line 3, the possible combinations are :
Lines 3 and 4 nonsuperposable
Lines 3 and 5 superposable
For line 4, the possible combinations are :
Lines 4 and 5 superposable
d) Polygon of fusion
Let us distribute on a circle by counting in the direction of the needles of a watch the five points materializing the five lines of the primitive matrix of the states : we obtain figure 25.
Let us connect together all the superposable lines as represented figure 26.
e) Interpretation of the polygon of fusion
We obtain two triangles of tops 1-5-4 and tops 2-5-3.
Regulate :
We can amalgamate for example 2-3-5 n tops connected to each other but each top should appear only in one grouping so that in our case, one can carry out the groupings :
1-4-5 and 2-3 or 2-3-5 and 1-4
We will prefer 1-4-5 and 2-3 bus inside each grouping the state of the exits is identical.
This will facilitate later on the groupings in the ultimate table of Karnaugh, but it is especially not obligatory and not always possible.
f) Stamp contracted or table of fusion.
Let us superimpose lines 1-4-5 represented figure 27.
Figure 28 shows lines 1-4-5 after contraction.
Figure 28 shows us that the stable states override the transients with fusion.
Figure 29 represents lines 2-3 of the primitive matrix before fusion.
Figure 30 represents lines 2-3 after fusion.
We can reconstitute a matrix known as contracted by means of the lines 1-4-5 and 2-3. Figure 31 represents this contracted matrix.
We see on figure 31 that the contracted matrix includes/understands two lines, which means that the complementary variables or transfers are one only which one calls x.
For a matrix of 21 = 2 lines, there is 1 complementary variable, for 22 = 4 lines, one has 2 complementary variables and for 2n lines, one has n variable.
If the matrix includes / understands 20 = 1 line, the examined system can be summarized with a combinative system (no complementary variable).
g) Establishment of the table of Karnaugh bringing back the problem to a combinative problem.
Let us draw up the table of Karnaugh of the exit by deferring the binary values of the exit for the stable states considered in the contracted matrix.
One will seek the state L for a stable state given in the primitive matrix of the states (figure 21).
For
L = 0
For
L = 1
For
L = 1
For
L = 0
For
L = 0
We obtain figure 32.
There remain three boxes to be filled for the transitory states.
We will defer the logical state of the exit (1 or 0) for the stable state to which the transitory state considered evolves.
The transitory state 1
evolves to the stable state
for which L = 1
The transitory state 4
evolves to the stable state
for which L = 0
The transitory state 3
evolves to the stable state
for which L = 0
Let us defer these values in the matrix of figure 32.
We obtain the table of Karnaugh of figure 33.
From this table of Karnaugh, the problem is become again a combinative problem.
We can carry out the groupings as we learned how to do it. They are represented figure 34.
We obtain the following equation of L :
L = 
m
+ x
That is to say L = (m
+ x)
One finds well the equation obtained by the preceding methods.
We thus have 2 methods to solve a sequential problem :
Method of the phases generalized
Matric method of HUFFMAN
We will prefer the method of Huffman who is more abstract but at the same time more systematic and surer. However, the method of the phases generalized has the advantage of allowing a visualization of the possible risks of operation and their eliminations easier. One can thus only recommend the use of the method of the phases like checking of a diagram obtained by the method of Huffman in order to seek possible risks.
Let us examine now the bistable trigger circuits.
Click
here for the following lesson or in the synopsis envisaged to this end. |
High
of page |
 Preceding
page |
Following
page |
