La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

An Algorithm for Generating Generic BDDs Un algorithme pour générer des BDD génériques

Tetsushi KATAYAMA, Hiroyuki OCHI, Takao TSUDA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Les diagrammes de décision binaire (BDD) sont une représentation graphique des fonctions booléennes. En particulier, les BDD ordonnés (OBDD) sont utiles dans de nombreuses situations, car ils fournissent une représentation canonique et sont manipulés efficacement. Des packages BDD qui génèrent automatiquement des OBDD ont été développés et sont désormais largement utilisés dans le domaine de la conception logique, notamment la vérification formelle et la synthèse logique. La synthèse de circuits à transistors passe-bas est l'une des applications réussies de tels packages BDD. Les circuits à transistors passants sont générés à partir de BDD en mappant chaque nœud sur un sélecteur composé de deux ou quatre transistors passants. Si les circuits sont générés à partir de BDD plus petits, les circuits générés comportent un plus petit nombre de transistors et permettent ainsi d'économiser de la surface sur la puce et de la consommation d'énergie. Dans cet article, des BDD plus génériques qui n'ont aucune restriction dans l'ordre des variables et le nombre d'apparences variables sur leurs chemins sont appelés BDD génériques (GBDD), et un algorithme de génération de GBDD est proposé à des fins de synthèse de circuits à transistors passe-bas. L'algorithme proposé se compose de deux étapes. Lors de la première étape, des arbres d'analyse (PT) pour des formules booléennes données sont générés, où un PT est une représentation arborescente orientée de formules booléennes et se compose de nœuds littéraux et de nœuds d'opération. Dans cette étape, notre algorithme tente de réduire le nombre de nœuds littéraux des PT. Lors de la deuxième étape, un GBDD est généré pour les PT à l'aide de la méthode de concaténation, où la méthode de concaténation génère un GBDD en connectant les GBDD verticalement. Dans cette étape, notre algorithme tente de partager des sous-graphes isomorphes. Lors d'expériences sur des circuits de référence ISCAS'89 et MCNC, notre programme a généré avec succès 32 GBDD sur 680 fonctions à sortie unique et 4 GBDD sur 49 fonctions multi-sorties dont les tailles sont inférieures à celles des OBDD. La taille du GBDD est réduite de 23.1 % dans le meilleur des cas par rapport à l'OBDD.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.12 pp.2505-2512
Date de publication
2000/12/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Catégories
Synthèse logique

Auteurs

Mots-clés

Table des matières