Tableau de Karnaugh -> algo ?

Bonsoir tout le monde !
Je cherche, plus par curiosité qu'autre chose, à trouver les équations logiques issues du Tableau de Karnaugh, mais bien sûr, par un algo :P .
En fait, j'ai du mal à voir comment faire, mais les logiciels de synthèse logique le font (ils vont même loin, car ils trouvent le meilleur compromis).

Avez-vous des pistes à me proposer ?
Le nom d'un algo qui fait ça ?
Voire l'algo lui-même...
Ou encore des documents expliquant comment ça se fait ?

Merci d'avance de vos réponses :) !

Voit la méthode de Quine-Mac Cluskey. Elle est simple à appréhender et donne les solutions possibles à la table de K

Merci, je vais regarder ça :) .

Bon, alors, j'ai regardé en détails l'algorithme en question.
Il semble assez peu utilisé...
Ceci dit, il m'a fait me poser plein de questions, ce qui est plutôt bien :) .
Comment un outil de synthèse logique réussi-t-il à passer du code (vhdl ou verilog en général) à des équations logiques ?
En fait, si j'arrive pas exploiter du code vhdl pour sortir l'ensemble des combinaisons, je pense pouvoir simplifier ensuite l'équation. Mais sur des systèmes assez complexes, je ne vois pas !
Sur des systèmes synchrones, je suis bloqué !
Bref, c'est pas simple tout ça...
Si des concepteurs ou utilisateurs avertis pouvaient m'éclairer, ne serait-ce qu'au niveau des méthodes utilisées dans les logiciels de synthèse logique, je serais déjà plus avancé !

Merci d'avance pour vos réponses !

Citation:

---

Envoyé par progman

Ceci dit, il m'a fait me poser plein de questions, ce qui est plutôt bien :) .
Comment un outil de synthèse logique réussi-t-il à passer du code (vhdl ou verilog en général) à des équations logiques ?

---

Il y a d'abord une phase d'analyse lexicale et grammaticale semblable à tout compilateur. Ensuite, si on parle de synthèse RTL comme j'en ai l'impression, on identifie facilement les registres (les structures syntaxiques reconnues pour ça sont très stylisées). Pour extraire les blocs combinatoires, on applique une technique dite de simulation symbolique, ce qui permet d'avoir en fin de processus les équations des sorties en fonction des entrées.

Par exemple pour:

Code:

---

1 2 3 4 5 6 7 8

t1 := i1 or i2; t2 := i2; if i3 then t2 := t2 and i4; t3 := i2; else t3 := i1; end if;

---

Le résultat de la simulation symbolique après les deux premières lignes est simple:

Code:

---

1 2	t1 := i1 or i2; t2 := i2;

---

A la fin de la branche then du if, c'est simple aussi:

Code:

---

1 2 3

t1 := i1 or i2; t2 := i2 and i4; t3 := i2;

---

A la fin de la branche else du if, on a donc:

Code:

---

1 2 3

t1 := i1 or i2; t2 := i2; t3 := i1;

---

Il faut combiner les deux branches sachant que la condition est i3, donc on a

Code:

---

1 2 3

t1 := ((i1 or i2) and i3) or ((i1 or i2) and not i3); t2 := ((i2 and i4) and i3) or (i2 and not i3); t3 := (i2 and i3) or (i1 and not i3);

---

Ces équations sont transformées en équations booléennes (bien que mon exemple ne le montre pas, elles peuvent avoir des opérations sur les entiers) et ensuite optimisées. On utilise en effet rarement quelque chose comme Quine-Mac Cluskey qui donne des formes normales, celles-ci étant inimplémentables quand on a un peu beaucoup de variables. On décompose donc en plus de niveaux pour tenir compte des fanin des portes et aussi de la taille de la mémoire. Ensuite on mappe (on transforme les équations en circuits en tenant compte des cellules dans la bibliothèque employée) et enfin on fait des transformations pour respecter les contraintes (par exemple on peut demander qu'une sortie soit disponible plus tot que les autres, ou qu'une entrée arrive plus tard, il faut aussi tenir compte des temps de setup et hold des circuits). Enfin on place les cellules et on recommence de l'optimisation pour ternir compte de l'influence du placement et du routage.(Ou plus exactement, maintenant on fait tout en même temps: optimiser et placer).

Note que cela fait quand même cinq ou six ans que je ne travaille plus sur la synthèse (analyse->équations logiques) et que je n'ai jamais travaillé sur l'optimisation en dehors de celle faite en synthèse.

Pour le moment, je ne cherche pas à optimiser !
Si je peux déjà faire de la synthèse logique simple, je serais déjà content...
Je n'ai pas l'ambition d'un logiciel complet de synthèse + placement/routage...
En fait, j'avoue que ceci :

Citation:

---

Envoyé par Jean-Marc.Bourguet

Si on parle de synthèse RTL comme j'en ai l'impression, on identifie facilement les registres (les structures syntaxiques reconnues pour ça sont très stylisées). Pour extraire les blocs combinatoires, on applique une technique dite de simulation symbolique, ce qui permet d'avoir en fin de processus les équations des sorties en fonction des entrées.

---

Est déjà complexe !
Oui, je parle de synthèse RTL ;) .
Je vais voir tout ça !
Merci !

Citation:

---

Envoyé par progman

En fait, j'avoue que ceci :

Citation:

---

Envoyé par Jean-Marc.Bourguet

Si on parle de synthèse RTL comme j'en ai l'impression, on identifie facilement les registres (les structures syntaxiques reconnues pour ça sont très stylisées). Pour extraire les blocs combinatoires, on applique une technique dite de simulation symbolique, ce qui permet d'avoir en fin de processus les équations des sorties en fonction des entrées.

---

Est déjà complexe !

---

Si tu as des questions, n'hésite pas. Mais étant donné que je ne suis pas sûr de m'habituer à ce genre de forums, si je ne réponds pas ici -- pour ce genre de questions, il faut un peu de temps devant soi pour répondre, ne soit donc pas trop pressé -- repose ta question sur fr.comp.algorithmes ou par email.