Optimisation logique

L'optimisation logique est un processus de recherche d'une représentation équivalente du circuit logique spécifié sous une ou plusieurs contraintes spécifiées. Ce processus fait partie d'une synthèse logique appliquée à l'électronique numérique et à la conception de circuits intégrés .

En général, le circuit est limité à une surface de puce minimale respectant un délai de réponse prédéfini. L'objectif de l'optimisation logique d'un circuit donné est d'obtenir le plus petit circuit logique qui évalue les mêmes valeurs que celui d'origine. Habituellement, le circuit plus petit avec la même fonction est moins cher, prend moins de place, consomme moins d'énergie , a une latence plus courte et minimise les risques de diaphonie inattendue , le risque de traitement du signal retardé et d'autres problèmes présents au niveau nanométrique des structures métalliques sur un circuit intégré .

En termes d' algèbre booléenne , l'optimisation d'une expression booléenne complexe est un processus consistant à trouver une expression booléenne plus simple, qui, après évaluation, produirait finalement les mêmes résultats que l'original.

Le problème d'un circuit complexe (c'est-à-dire comportant de nombreux éléments, comme des portes logiques ) est que chaque élément occupe de l'espace physique et coûte du temps et de l'argent à produire. La minimisation des circuits peut être une forme d'optimisation logique utilisée pour réduire la zone de logique complexe dans les circuits intégrés .

Avec l'avènement de la synthèse logique , l'un des plus grands défis auxquels a été confrontée l'industrie de l'automatisation de la conception électronique (EDA) était de trouver la représentation de circuit la plus simple de la description de conception donnée. Alors que l'optimisation logique à deux niveaux existait depuis longtemps sous la forme de l' algorithme Quine-McCluskey , suivi plus tard par le minimiseur logique heuristique Espresso , l'amélioration rapide des densités de puces et l'adoption généralisée des langages de description matérielle pour la description des circuits ont formalisé le domaine de l'optimisation logique tel qu'il existe aujourd'hui, y compris Logic Friday (interface graphique), Minilog et ESPRESSO-IISOJS (logique à valeurs multiples).

Les méthodes de simplification des circuits logiques sont également applicables à la minimisation des expressions booléennes.

Aujourd’hui, l’optimisation logique est divisée en différentes catégories :

Basé sur la représentation du circuit

Optimisation logique à deux niveaux

Optimisation logique multi-niveaux

Basé sur les caractéristiques du circuit

Optimisation logique séquentielle

Optimisation logique combinatoire

En fonction du type d'exécution

Méthodes d'optimisation graphique

Méthodes d'optimisation tabulaire

Méthodes d'optimisation algébrique

Les méthodes graphiques représentent la fonction logique requise par un diagramme représentant les variables logiques et la valeur de la fonction. En manipulant ou en inspectant un diagramme, de nombreux calculs fastidieux peuvent être éliminés. Les méthodes de minimisation graphique pour la logique à deux niveaux comprennent :

• Diagramme d'Euler (ou cercle eulérien ) (1768) par Leonhard P. Euler (1707–1783)
• Diagramme de Venn (1880) par John Venn (1834-1923)
• Carte de Karnaugh (1953) par Maurice Karnaugh

Les mêmes méthodes de minimisation (simplification) d’expression booléenne répertoriées ci-dessous peuvent être appliquées à l’optimisation du circuit.

Dans le cas où la fonction booléenne est spécifiée par un circuit (c'est-à-dire que nous voulons trouver un circuit équivalent de taille minimale possible), le problème de minimisation de circuit non borné a longtemps été conjecturé comme étant -complet en complexité temporelle , un résultat finalement prouvé en 2008, mais il existe des heuristiques efficaces telles que les cartes de Karnaugh et l' algorithme de Quine-McCluskey qui facilitent le processus.

Les méthodes de minimisation des fonctions booléennes incluent :

• Algorithme de Quine-McCluskey
• Méthode de Petrick

Les méthodes qui trouvent des représentations de circuits optimales de fonctions booléennes sont souvent appelées synthèse exacte dans la littérature. En raison de la complexité des calculs, la synthèse exacte n'est réalisable que pour les petites fonctions booléennes. Les approches récentes associent le problème d'optimisation à un problème de satisfaction booléenne . Cela permet de trouver des représentations de circuits optimales à l'aide d'un solveur SAT .

Une méthode heuristique utilise des règles établies qui résolvent un sous-ensemble pratique et utile d'un ensemble beaucoup plus vaste de problèmes possibles. La méthode heuristique peut ne pas produire la solution optimale théoriquement, mais si elle est utile, elle fournira la plupart des optimisations souhaitées avec un minimum d'effort. Un exemple de système informatique qui utilise des méthodes heuristiques pour l'optimisation logique est le minimiseur logique heuristique Espresso .

Alors qu'une représentation de circuit à deux niveaux fait strictement référence à la vue aplatie du circuit en termes de SOP ( somme de produits ) — ce qui est plus applicable à une implémentation PLA de la conception — une représentation à plusieurs niveaux est une vue plus générique du circuit en termes de SOP, POS ( produit de sommes ) arbitrairement connectés, forme factorisée, etc. Les algorithmes d'optimisation logique fonctionnent généralement soit sur la représentation structurelle (SOP, forme factorisée) soit sur la représentation fonctionnelle ( diagrammes de décision binaires , diagrammes de décision algébriques ) du circuit. Sous la forme somme de produits (SOP), les portes ET forment la plus petite unité et sont cousues ensemble à l'aide de OU, tandis que sous la forme produit de sommes (POS), c'est l'opposé. La forme POS nécessite des parenthèses pour regrouper les termes OU sous les portes ET, car OU a une priorité inférieure à ET. Les formes SOP et POS se traduisent parfaitement dans la logique du circuit.

Si nous avons deux fonctions F ₁ et F ₂ :

La représentation à 2 niveaux ci-dessus prend six termes de produit et 24 transistors dans CMOS Rep.

Une représentation fonctionnellement équivalente à plusieurs niveaux peut être :

P = B + C .

F ₁ = AP + AD .

F ₂ = A'P + A'E .

Bien que le nombre de niveaux soit ici de 3, le nombre total de termes de produits et de littéraux est réduit en raison du partage du terme B + C.

De même, on distingue les circuits combinatoires et les circuits séquentiels . Les circuits combinatoires produisent leurs sorties uniquement à partir des entrées actuelles. Ils peuvent être représentés par des relations booléennes . Quelques exemples sont les encodeurs de priorité , les décodeurs binaires , les multiplexeurs , les démultiplexeurs .

Les circuits séquentiels produisent leur sortie en fonction des entrées actuelles et passées, en fonction d'un signal d'horloge pour distinguer les entrées précédentes des entrées actuelles. Ils peuvent être représentés par des machines à états finis. Les bascules et les compteurs en sont quelques exemples .

Bien qu'il existe de nombreuses façons de minimiser un circuit, cet exemple minimise (ou simplifie) une fonction booléenne. La fonction booléenne exécutée par le circuit est directement liée à l'expression algébrique à partir de laquelle la fonction est implémentée. Considérons le circuit utilisé pour représenter . Il est évident que deux négations, deux conjonctions et une disjonction sont utilisées dans cette instruction. Cela signifie que pour construire le circuit, il faudrait deux inverseurs , deux portes ET et une porte OU .

Le circuit peut être simplifié (minimisé) en appliquant les lois de l'algèbre booléenne ou en utilisant l'intuition. Puisque l'exemple indique que est vrai lorsque est faux et inversement, on peut conclure que cela signifie simplement . En termes de portes logiques, l'inégalité signifie simplement une porte XOR (ou exclusif). Par conséquent, . Alors les deux circuits présentés ci-dessous sont équivalents, comme on peut le vérifier à l'aide d'une table de vérité :