FRANCAIS francophone2.gif ANGLAIS

 

 

Created the, 12/06/2019

 Updated the, 02/01/2020

Visiteurs N°  


Home
Back to Main Sites New Blog Novelty Search engine Your Shopping Cart For Shopping Your Member Area Bookmarks, Your Favorite Games Static Welcome Page Site in French Web Site in English
Summaries
Basic Electronics Fundamental Technology Test your Knowledge Digital Theoretical Electronics Digital Practical Electronics Digital Electronic Lexicon Data book TTL Data book CMOS TVC Troubleshooting Mathematical
Microcomputers
Theoretical of Microcomputers Test your Knowledge Practical Microcomputers Computer Glossaries
Physical
The light Field of Action Electromagnetic Radiation
Technologies
Classification of Resistances Identification of Resistances Classification of Capacitors Identification of Capacitors
Mathematical Forms
Geometry Physical 1. - Electronic 1. 2. - Electronic 1. 3. - Electrical 1. 4. - Electromagnetism
Access to all our Products
E. T. F. - Volume I - 257 Pages E. T. F. - Volume II - 451 Pages E. T. F. - Volume III - 611 Pages E. T. D. - Volume I - 610 Pages N. B. M. - Volume I - 201 Pages E. T. M. - Volume I - 554 Pages Business at Home Books 34 free pages Our E-books Geometry Software Electronic Components Software
Overview of all our Products
E. T. F. - Volume I - 257 Pages E. T. F. - Volume II - 451 Pages E. T. F. - Volume III - 611 Pages E. T. D. - Volume I - 610 Pages E. T. M. - Volume I - 554 Pages Geometry Software Electronic Components Software
Our Lessons in PDF Formats
Basic Electronics Fundamental Technology Digital Theoretical Electronics Digital Practical Electronics Theoretical of Microcomputers Mathematics
Data Processing
Troubleshooting Win98 and WinXP PC Troubleshooting Glossary HTML and Programs PHP and Programs JavaScript (in progress) Creation of several Sites
Forums
Electronic Forum and Infos Electronic Forum and Poetry
Miscellaneous and others
Form of the personal pages News XML Statistics CountUs JavaScript Editor Our Partners and Useful Links Partnership Manager Our MyCircle Partners Surveys 1st Guestbook 2nd Guestbook Site Directories




Signet : 
     Footer  


Matrix Method of Huffman and Fusion Polygon :


2. 3. - HUFFMAN MATRIX METHOD


We know that Karnaugh's chart does not directly solve a sequential problem. Indeed, for each combination of the input variables, there can only be one value for the output, that is to say one value per elementary box of the array.

It is therefore necessary to look for a representation that allows the introduction of one or more secondary variables as seen previously.

2. 3. 1. SEQUENCE

A sequence is a looped succession of stable states separated by transient states.

Figure 19 shows an example of a sequence.

Exemple_de_sequence.gif

2. 3. 2. - RESOLUTION OF A PROBLEM BY THE MATRIX METHOD

To illustrate this method, let's take the same example again.

a)  Analysis

There are two input variables «m» and «a».

These two variables make it possible to obtain 22 = 4 combinations.

As a starting point, we use a table with four columns corresponding to the combinations of entries that are arranged according to the reflected binary code. In a fifth column, enter the binary value of the output state. The table is shown in Figure 20.

Tableau_de_depart.gif

Let us take again the operation of the assembly and define the number of stable states :

Nombre_0.gif  Initial state                                       a = 0,  m = 0  with  L = 0

Nombre_1.gif  Action on m                                    a = 0,  m = 1  where  L = 1

Nombre_2.gif  m is released                                   a = 0,  m = 0  and  L  always at 1

Nombre_3.gif  Action on a                                     a = 1,  m = 0  and  L = 0

Nombre_4.gif  Simultaneous action on a and m         a = 1,  m = 1  we chose to privilege the stop : L = 0

 b)  Construction of the primitive matrix of states.

A primitive matrix of states is a table of the model of Figure 20 in which there is a stable state line as shown in Figure 21.

Each stable state is positioned in the box for which the variables «m» and «a» are at the values having caused this stable state.



Matrice_primitive_des_etats_stables.gif


Example :

For     a = 0, m = 0                stable state Nombre_0.gif, L = 0

           a = 0, m = 1                stable state Nombre_1.gif, L = 1

           a = 0, m = 0                stable state Nombre_2.gif, L = 1

           a = 1, m = 0                stable state Nombre_3.gif, L = 0

           a = 1, m = 1                stable state Nombre_4.gif, L = 0

It is now necessary to position the transient states.

The transient states are located at the intersection of the line on which the initial stable state appears and the column in which the next steady state appears.

Figure 22 shows these transient states.

Matrice_primitive_des_etats_stables_et_transitoires.gif

We know that it is impossible for two variables to switch simultaneously. To materialize this on the primitive matrix, it is necessary to hatch to eliminate them, all the boxes for which on the same line two variables change with respect to the combination of the variables which caused the stable state included in this line.

We thus obtain the table of figure 23.

In our example :    for steady state Nombre_0.gif   a = 0,  m = 0,  you have to hatch the box where a = 1,  m = 1

                              for steady state Nombre_1.gif   a = 0,  m = 1,  you have to hatch the box where a = 1, m = 0

                              for steady state Nombre_2.gif   a = 0,  m = 0,  you have to hatch the box where a = 1, m = 1

                              for steady state Nombre_3.gif   a = 1,  m = 0,  you have to hatch the box where a = 0, m = 1

                              for steady state Nombre_4.gif   a = 1,  m = 1,  you have to hatch the box where a = 0, m = 0

Matrice_primitive_des_etats.gif

It is now necessary to examine the remaining boxes.

Line 1 :

Box  10  (a = 1,  m = 0)

If we press "a" while L is off, we move to a steady-state situation Nombre_3.gif (a = 1, m = 0, L = 0), so we write 3 in the box which shows that we go through the transient state 3.

Line 2 :

Box 11  (a = 1,  m = 1)

If we press "a" while "m" has not been released, we go to the extinction of the lamp so to the steady state Nombre_4.gif (a = 1, m = 1, L = 0). We write 4 in the box.

Line 3 :

Box 01  (a = 0, m = 1)

If we press «on» while the lamp is already on, this has no effect and we go to the steady state Nombre_1.gif (a = 0, m = 1, L = 1), we write 1 in the box.

Line 4 :

Box 00  (a = 0, m = 0)

We release "a" and the lamp remains off, so we go to steady state Nombre_0.gif (a = 0, m = 0, L = 0), we write 0 in the box.

Line 5 :

1)  Box 01  (a = 0, m = 1)

We release "a" while "a" and «m» were activated and L was extinguished. The lamp comes back because we return to the stable state Nombre_1.gif (a = 0, m = 1, L = 1), so we write 1 in the box.

2)  Box 10  (a = 1, m = 0)

We release the start button while L is off, we return to the stable state Nombre_3.gif (a = 1, m = 0, L = 0), so we write 3 in the box.

The primitive matrix completed in Figure 24 is thus obtained.

Matrice_primitive_des_etats_completee.gif

c)  Finding the contracted matrix

It is desirable to reduce the original matrix of states to a contracted matrix in order to reduce the number of additional lines, which introduce new excitations and new complementary variables or transfers.

Contraction or merger rules :

     It is possible to contract the primitive matrix of states by superimposing two lines if they present vertically the same states.

     Two lines can be merged into one when there is a steady state or a transient of the same number in the same column or a stable or transient state with a hatched box in the same column, because the hatched box indicates that, for technological reasons, this case can not occur and is therefore indifferent.

     Output states do not intervene in the possible overlays.

Study of the possibilities for line 1 :

Let's compare line 1 with line 2 : they are not superimposable because for a = 0 and m = 0, we have the state Nombre_0.gif on the first line and 2 on the second.

Let's compare line 1 with line 3 : they are not superimposable because we have Nombre_0.gif on the first line and 2 on the third for a = 0 and m = 0.

Let's compare line 1 with line 4 : these two lines are superimposable because we have Nombre_0.gif corresponds to 0, to 1 corresponds an impossibility, to an impossibility corresponds 4, to 3 corresponds Nombre_3.gif.

Let's compare line 1 with line 5 : these two lines are superimposable.

For line 2, the possible combinations are :

Lines 2 and 3 stackable.

Lines 2 and 4 are not stackable.

Line 2 and 5 stackable.

For line 3, the possible combinations are :

Lines 3 and 4 non-stackable

Lines 3 and 5 stackable

For line 4, the possible combinations are :

Lines 4 and 5 stackable

d)  Fusion polygon

Let's spread on a circle by counting in a clockwise direction the five points representing the five lines of the primitive matrix of states : we get Figure 25.

Les_sommets_du_polygone_de_fusion.gif

Connect together all the stackable lines as shown in Figure 26.

Polygone_de_fusion.gif

e)  Interpretation of the fusion polygon

We get two triangles of vertices 1-5-4 and vertices 2-5-3.

Rule :

For example, we can merge 2-3-5 ... n vertices connected to each other, but each vertex must appear in only one group so that in our case we can make the groupings :

1-4-5  and  2-3  or  2-3-5  and  1-4

We will prefer 1-4-5 and 2-3 because inside each group the state of the outputs is identical.

This will later facilitate the groupings in the final table of Karnaugh, but it is not obligatory and especially not always possible.

f)  Contrasted matrix or fusion table.

Let's superimpose lines 1-4-5 shown in Figure 27.

Lignes_1_4_5_avant_contraction.gif

Figure 28 shows lines 1-4-5 after contraction.

Lignes_1_4_5_fusionnees.gif

Figure 28 shows that stable states outweigh transitions on fusion.

Figure 29 shows lines 2-3 of the primitive matrix before merging.

Lignes_2_3_avant_fusion.gif

Figure 30 shows lines 2-3 after merging.

Lignes_2_3_apres_fusion.gif

We can reconstruct a so-called contracted matrix using lines 1-4-5 and 2-3. Figure 31 shows this contracted matrix.

Matrice_contractee.gif

We see in Figure 31 that the contracted matrix comprises two lines, which means that the complementary variables or transfers are only one number that we call x.

For a matrix of 21 = 2 lines, we have 1 complementary variable, for 22 = 4 lines, we have 2 complementary variables and for 2n lines we have n variables.

If the matrix includes 20 = 1 line, the system under review can be summarized as a combinatorial system (no additional variables).

g)  Establishment of Karnaugh's chart reducing the problem to a combinatorial problem.

Let's establish Karnaugh's array of output by plotting the output binary values for the stable states considered in the contracted matrix.

We will look for the state L for a given stable state in the primitive matrix of states (Figure 21).

For Nombre_0.gif    L = 0

For Nombre_1.gif    L = 1

For Nombre_2.gif    L = 1

For Nombre_3.gif    L = 0

For Nombre_4.gif    L = 0

We get Figure 32.

There are three boxes to fill in for transition states.

We will report the logical state of the output (1 or 0) for the steady state to which the transient state considered evolves.

The transient state 1 evolves towards the stable state Nombre_1.gif for which L = 1

The transient state 4 evolves towards the stable state Nombre_4.gif for which L = 0

The transient state 3 evolves towards the stable state Nombre_3.gif for which L = 0

Let's put these values in the matrix of Figure 32.

We get the Karnaugh chart from Figure 33.

Tableau_de_Karnaugh_obtenu_a_partir_de_la_matrice_contractee.gif

From this table of Karnaugh, the problem is again a combinatorial problem.

We can achieve the groupings as we have learned to do. They are represented in figure 34.

We obtain the following equation of L :

L = A_barre1.gifm + A_barre1.gifx

Let  L = A_barre1.gif(m + x)

We find the equation obtained by the previous methods.

We have 2 methods to solve a sequential problem :

  • The generalized phase method

  • HUFFMAN's matrix method

We will prefer the Huffman method which is more abstract but more systematic and more secure. However, the generalized phase method has the advantage of allowing a visualization of the possible operating hazards and their eliminations easier. One can therefore only recommend the use of the phase method as verification of a scheme obtained by the method of Huffman to look for possible hazards.

Now let's look at Bistable Flip-Flops.








Nombre de pages vues, à partir de cette date : le 27 Décembre 2019

compteur visite blog gratuit


Mon audience Xiti



Send an email to Corporate Webmaster for any questions or comments about this Web Site.

Web Site Version : 11. 5. 12 - Web Site optimization 1280 x 1024 pixels - Faculty of Nanterre - Last modification : JANUARY 02, 2020.

This Web Site was Created on, 12 JUNE 2019 and has Remodeled, in JANUARY 2020.