Simplification de circuit logique - expression booléenne

[invite563547f9]

Bonjour,

existe-t-il une méthode générale pour optimiser une expression booléenne dans un but pratique, c'est-à-dire réduire le nombre de portes logiques ?

Est-il possible d'étendre à n'importe quelles portes logiques ? Par exemple, si je veux créer un circuit logique avec que et le minimum possible de portes NOR ; ça m'avait frappé à quel point la porte NXOR était compacte et peu intuitive, et je me demandais comment on était arrivé à ça. J'ai aussi essayé de faire un full adder avec des NOR, et je suis arrivé à 12, mais je n'ai aucun moyen d'être sûr que c'est le minimum.

Un autre problème que j'avais eu, qui est un peu irréaliste, certes, concernait un décodeur dont on aurait tronqué certaines valeurs. L'intérêt était simplement que le jeu d'instruction ne prenait pas toutes les valeurs de la plage possible. L'autre contrainte était d'utiliser des portes AND à 2 entrées, alors que les instructions faisaient plus de 2 bits. Si on utilise toutes les instructions de 0 à 2^n - 1, la façon dont on arrange les portes logiques ne change pas le nombre nécessaire, vu que toutes les combinaisons de 2 bits apparaissent en nombres égaux. Mais dans cette situation, c'est différent, et je n'ai aucune idée de comment optimiser ça.

Merci beaucoup !
-----

[DAUDET78]

existe-t-il une méthode générale pour optimiser une expression booléenne dans un but pratique, c'est-à-dire réduire le nombre de portes logiques ?

C'était une question qui était intéressante dans les années 80 /90 . Maintenant, c'est complétement dépassé. On utilise un PAL , FPGA ou autres . Et, ce qui compte, c'est que ça tienne dedans et sans aléa de timing .

[invite563547f9]

Ce n'est pas forcément par utilité que je m'y suis intéressé, sans cela, je ne ferais plus d'électronique. C'est plutôt le défi mathématique que je n'ai pu résoudre qui m'a un peu "frustré".

Y a-t-il une solution ?

Merci beaucoup !

[invite57d3cd4f]

Bonjour,
La méthode pour simplifier une expression booléenne utilise la table de Karnaugh : https://fr.wikipedia.org/wiki/Table_de_Karnaugh
Bonne journée

[A voir en vidéo sur Futura]

[invite563547f9]

Bonjour,

les tables de Karnaugh ne sont pas suffisantes pour le deuxième exemple : elles donnent indifféremment des opérateurs n-aires avec n plus grand ou égal à deux, alors que la condition est d'avoir uniquement des opérateurs binaires.

Dans le premier exemple, je ne vois pas comment utiliser cet outil pour aboutir à la réalisation d'une porte NXOR uniquement avec des NOR.

D'une manière générale, je cherche des méthodes plus "rigoureuses" et j'aimerais bien pouvoir prouver que le résultat auquel on aboutit est bien optimal.

Une idée ? (peut-être cela a-t-il mieux sa place dans une section math)

Merci !

[Antoane]

Bonjour,

Déplacé d'électronique en mathématiques du supérieur.

Crdt.

[azizovsky]

Bonjour, il n'y a pas de porte logique qui traine quelque part dans un circuit, pour un additionneur, il y'a l' additionneur (composé de deux demi-additionneur en série accompagnés d'une logique pour calculer la retenue), additionneur parallèle à propagation de retenue, additionneur parallèle à retenue anticipée.

Optimisation des additionneurs
Les additionneurs sont au cœur des unités arithmétique et logique des processeurs. Des techniques particulièrement spécifiques sont mises en œuvre pour additionner le plus vite envisageable, le plus fréquemment en utilisant des techniques complexes de prédiction de la retenue (cf. références). Par exemple on peut détecter des blocs (série de bits consécutifs) ne générant pas de retenue, et par conséquent particulièrement rapides à additionner. On peut aussi calculer deux résultats indépendamment et en parallèle, l'un avec une retenue, l'autre sans, et ensuite choisir le bon (via un multiplexeur).

ps: je me souvient du fonctionnement de Z80 de Zilog, je n'ai jamais tombé sur un problème d'optimisation des portes logiques.

[invite563547f9]

Hein ?

Je ne cherche pas vraiment d'application en pratique réaliste, c'est juste que je m'amuse à concevoir des circuits un peu trop spécifiques et peu utiles. Je cherchais à réduire le nombre de portes logiques nécessaires, et je suis tombé sur ce problème. C'est plus une considération mathématique que pratique.

Merci beaucoup !

[Resartus]

Bonjour,
L'optimisation avec des portes NAND ou NOR n'a pas, à ma connaissance, de solution autre que la force brute, qui croit évidemment très vite avec le nombre de variables logiques à traiter. Le nombre maximum d'entrées des portes joue également un rôle très important.
Ce calcul "force brute" est un exercice de programmation plutôt ardu, qui devait faire les délices des informaticiens en son temps, mais je doute qu'on puisse encore trouver aujourd'hui ce type de programme

Aux temps (quasi préhistoriques) où ces problèmes se posaient, je crois même me souvenir qu'il existait quelques cas pathologiques où un bouclage entrée/sortie pouvait fournir une solution théoriquement optimale.

Bien évidemment, ce type de solution était inutilisable avec des circuits réels à temps de propagation fini, qui se seraient comportés en oscillateurs. D'ailleurs, un des critères additionnels généralement imposés était que le nombre d'étages soit le plus faible possible (pour réduire le temps de propagation), et que ce nombre soit le même (à +1 près) pour toutes les variables.

Une méthode opératoire à la main est de commencer à trouver une formule simplifiée (somme de produits ou produits de sommes), de la réaliser avec des portes à nombre d'entrées infinies, qui donne une solution à 1/2 étages, et de la déformer pour passer à des portes réelles avec moins d'entrées, ce qui augmente chaque parcours d'un nombre pair d'étages. Mais cette méthode n'est évidemment pas du tout optimale.

[invited3a27037]

C'est faisable puisque les logiciels de synthèse logique font ce travail. Et on peut leur imposer de n'utiliser qu'un nombre restreint de portes de la bibliothèque. Mais je ne sais précisément pas comment ils font.

[Resartus]

Rebonjour,

Après quelques recherches sur internet, j'ai trouvé ce logiciel gratuit (que je n'ai pas testé, mais qui doit répondre à la question posée ):
http://sontrak.com/
On peut choisir les types d'optimisation : partielle (rapide mais pas toujours la meilleure) ou complète, beaucoup plus lente (je suppose que cela croit comme factorielle du nombre de variables)

Et, contrairement à ce que je supposais, il existe même une suite logicielle gratuite (open source) pour faire des synthèses logiques complètes :
http://opencircuitdesign.com/qflow/welcome.html

[invite563547f9]

Bonjour,

Merci beaucoup de la réactivité !

Finalement, le résultat est bien triste, mais je m'y attendais un peu.

Mais donc, ce n'est effectivement pas un problème dépassé, si ? On conçoit toujours des circuits qui doivent être le plus rapides possible. Simplement, maintenant, on délègue ça à des algorithmes tout faits, si j'ai bien compris.

Si je veux comprendre ça, il faudrait donc que je me tourne vers ceux-ci, voire que je lise le code source des programmes cités (ce qui me paraît quasiment mort pour comprendre un algorithme).

Merci beaucoup !

[invited3a27037]

Bien sur que non ce n'est pas un problème dépassé.
Les logiciels de synthèse logique sortent des netlists les plus petites possibles qui satisfont aux contraintes données (frequence ..)

Ce qui est dépassé, c'est de faire de l'optimisation à la main, avec des tableaux de Karnaugh ou autre

[invite563547f9]

Bonjour et merci de la réponse.

Les logiciels de synthèse logique sortent des netlists les plus petites possibles qui satisfont aux contraintes données (frequence ..)

Une idée de comment ils s'y prennent ?

Merci !

[albanxiii]

Bonjour,

Et, contrairement à ce que je supposais, il existe même une suite logicielle gratuite (open source) pour faire des synthèses logiques complètes :
http://opencircuitdesign.com/qflow/welcome.html

On peut aussi mentionner Alliance