Linear sifting of decision diagrams and its application in synthesis
Identifieur interne : 002005 ( Main/Exploration ); précédent : 002004; suivant : 002006Linear sifting of decision diagrams and its application in synthesis
Auteurs : Christoph Meinel [Allemagne] ; F. Somenzi ; T. TheobaldSource :
- IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems [ 0278-0070 ] ; 2000.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
We propose a new algorithm, called linear sifting, for the optimization of decision diagrams that combines the efficiency of sifting and the power of linear transformations. The new algorithm is applicable to large examples, and in many cases leads to substantially more compact diagrams when compared to simple variable reordering. We also show in what sense linear transformations complement variable reordering and how the technique can be applied to verification issues. Going a step further, we discuss a synthesis scenario where-due to the complexity of the target function-it is inevitable to decompose the function in a preprocessing step. By using linear sifting it is possible to extract a linear filter and, hence, to achieve the necessary decomposition. Using this method we were able to synthesize functions with standard tools which fail otherwise.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000F28
- to stream PascalFrancis, to step Curation: 000041
- to stream PascalFrancis, to step Checkpoint: 000C89
- to stream Main, to step Merge: 002335
- to stream Main, to step Curation: 002005
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Linear sifting of decision diagrams and its application in synthesis</title><author><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Univ Trier</s1><s2>Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>Trier</wicri:noRegion><wicri:noRegion>Univ Trier</wicri:noRegion><wicri:noRegion>Univ Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Somenzi, F" sort="Somenzi, F" uniqKey="Somenzi F" first="F." last="Somenzi">F. Somenzi</name></author><author><name sortKey="Theobald, T" sort="Theobald, T" uniqKey="Theobald T" first="T." last="Theobald">T. Theobald</name></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">00-0342583</idno><date when="2000">2000</date><idno type="stanalyst">PASCAL 00-0342583 EI</idno><idno type="RBID">Pascal:00-0342583</idno><idno type="wicri:Area/PascalFrancis/Corpus">000F28</idno><idno type="wicri:Area/PascalFrancis/Curation">000041</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000C89</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000C89</idno><idno type="wicri:doubleKey">0278-0070:2000:Meinel C:linear:sifting:of</idno><idno type="wicri:Area/Main/Merge">002335</idno><idno type="wicri:Area/Main/Curation">002005</idno><idno type="wicri:Area/Main/Exploration">002005</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Linear sifting of decision diagrams and its application in synthesis</title><author><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Univ Trier</s1><s2>Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>Trier</wicri:noRegion><wicri:noRegion>Univ Trier</wicri:noRegion><wicri:noRegion>Univ Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Somenzi, F" sort="Somenzi, F" uniqKey="Somenzi F" first="F." last="Somenzi">F. Somenzi</name></author><author><name sortKey="Theobald, T" sort="Theobald, T" uniqKey="Theobald T" first="T." last="Theobald">T. Theobald</name></author></analytic><series><title level="j" type="main">IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</title><title level="j" type="abbreviated">IEEE Trans Comput Aided Des Integr Circuits Syst</title><idno type="ISSN">0278-0070</idno><imprint><date when="2000">2000</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</title><title level="j" type="abbreviated">IEEE Trans Comput Aided Des Integr Circuits Syst</title><idno type="ISSN">0278-0070</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Binary decision diagrams</term><term>Boolean functions</term><term>Combinatorial circuits</term><term>Data structures</term><term>Decision diagrams</term><term>Experiments</term><term>Linear sifting</term><term>Linear transformations</term><term>Mathematical transformations</term><term>Matrix algebra</term><term>Optimization</term><term>Spectrum analysis</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Expérience</term><term>Optimisation</term><term>Algorithme</term><term>Transformation mathématique</term><term>Fonction booléenne</term><term>Algèbre matricielle</term><term>Analyse spectre</term><term>Circuit combinatoire</term><term>Structure donnée</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We propose a new algorithm, called linear sifting, for the optimization of decision diagrams that combines the efficiency of sifting and the power of linear transformations. The new algorithm is applicable to large examples, and in many cases leads to substantially more compact diagrams when compared to simple variable reordering. We also show in what sense linear transformations complement variable reordering and how the technique can be applied to verification issues. Going a step further, we discuss a synthesis scenario where-due to the complexity of the target function-it is inevitable to decompose the function in a preprocessing step. By using linear sifting it is possible to extract a linear filter and, hence, to achieve the necessary decomposition. Using this method we were able to synthesize functions with standard tools which fail otherwise.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><noCountry><name sortKey="Somenzi, F" sort="Somenzi, F" uniqKey="Somenzi F" first="F." last="Somenzi">F. Somenzi</name><name sortKey="Theobald, T" sort="Theobald, T" uniqKey="Theobald T" first="T." last="Theobald">T. Theobald</name></noCountry><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002005 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002005 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= Pascal:00-0342583
|texte= Linear sifting of decision diagrams and its application in synthesis
}}
| This area was generated with Dilib version V0.6.31. |  |