UnivTrevesV1, PascalFrancis, Corpus, bibRecord, 000F28

Linear sifting of decision diagrams and its application in synthesis

Identifieur interne : 000F28 ( PascalFrancis/Corpus ); précédent : 000F27; suivant : 000F29

Linear sifting of decision diagrams and its application in synthesis

Auteurs : C. Meinel ; F. Somenzi ; T. Theobald

Source :

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems [ 0278-0070 ] ; 2000.

RBID : Pascal:00-0342583

Descripteurs français

Pascal (Inist)
- Expérience, Optimisation, Algorithme, Transformation mathématique, Fonction booléenne, Algèbre matricielle, Analyse spectre, Circuit combinatoire, Structure donnée.

English descriptors

KwdEn :
- Algorithms, Binary decision diagrams, Boolean functions, Combinatorial circuits, Data structures, Decision diagrams, Experiments, Linear sifting, Linear transformations, Mathematical transformations, Matrix algebra, Optimization, Spectrum analysis.

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.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0278-0070`
A03		`1`		`@0 IEEE Trans Comput Aided Des Integr Circuits Syst`
A05				`@2 19`
A06				`@2 5`
A08	`01`	`1`	`ENG`	`@1 Linear sifting of decision diagrams and its application in synthesis`
A11	`01`	`1`		`@1 MEINEL (C.)`
A11	`02`	`1`		`@1 SOMENZI (F.)`
A11	`03`	`1`		`@1 THEOBALD (T.)`
A14	`01`			`@1 Univ Trier @2 Trier @3 DEU @Z 1 aut.`
A20				`@1 521-533`
A21				`@1 2000`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 222 X`
A44				`@0 A100`
A45				`@0 36 Refs.`
A47	`01`	`1`		`@0 00-0342583`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems`
A66	`01`			`@0 USA`
C01	`01`		`ENG`	@0 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.
C02	`01`	`X`		`@0 001D02B07B`
C02	`02`	`X`		`@0 001D01A`
C02	`03`	`X`		`@0 001A02B`
C02	`04`	`X`		`@0 001D02A`
C02	`05`	`X`		`@0 001A02D`
C02	`06`	`X`		`@0 001D02A04`
C03	`01`	`1`	`ENG`	`@0 Decision diagrams @4 INC`
C03	`02`	`1`	`ENG`	`@0 Linear sifting @4 INC`
C03	`03`	`1`	`ENG`	`@0 Linear transformations @4 INC`
C03	`04`	`1`	`ENG`	`@0 Binary decision diagrams @4 INC`
C03	`05`	`1`	`FRE`	`@0 Expérience`
C03	`05`	`1`	`ENG`	`@0 Experiments`
C03	`06`	`1`	`FRE`	`@0 Optimisation`
C03	`06`	`1`	`ENG`	`@0 Optimization`
C03	`07`	`1`	`FRE`	`@0 Algorithme`
C03	`07`	`1`	`ENG`	`@0 Algorithms`
C03	`08`	`1`	`FRE`	`@0 Transformation mathématique`
C03	`08`	`1`	`ENG`	`@0 Mathematical transformations`
C03	`09`	`1`	`FRE`	`@0 Fonction booléenne`
C03	`09`	`1`	`ENG`	`@0 Boolean functions`
C03	`10`	`1`	`FRE`	`@0 Algèbre matricielle`
C03	`10`	`1`	`ENG`	`@0 Matrix algebra`
C03	`11`	`1`	`FRE`	`@0 Analyse spectre`
C03	`11`	`1`	`ENG`	`@0 Spectrum analysis`
C03	`12`	`1`	`FRE`	`@0 Circuit combinatoire`
C03	`12`	`1`	`ENG`	`@0 Combinatorial circuits`
C03	`13`	`1`	`FRE`	`@0 Structure donnée @3 P`
C03	`13`	`1`	`ENG`	`@0 Data structures @3 P`
N21				`@1 234`

Format Inist (serveur)

NO :	PASCAL 00-0342583 EI
ET :	Linear sifting of decision diagrams and its application in synthesis
AU :	MEINEL (C.); SOMENZI (F.); THEOBALD (T.)
AF :	Univ Trier/Trier/Allemagne (1 aut.)
DT :	Publication en série; Niveau analytique
SO :	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems; ISSN 0278-0070; Etats-Unis; Da. 2000; Vol. 19; No. 5; Pp. 521-533; Bibl. 36 Refs.
LA :	Anglais
EA :	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.
CC :	001D02B07B; 001D01A; 001A02B; 001D02A; 001A02D; 001D02A04
FD :	Expérience; Optimisation; Algorithme; Transformation mathématique; Fonction booléenne; Algèbre matricielle; Analyse spectre; Circuit combinatoire; Structure donnée
ED :	Decision diagrams; Linear sifting; Linear transformations; Binary decision diagrams; Experiments; Optimization; Algorithms; Mathematical transformations; Boolean functions; Matrix algebra; Spectrum analysis; Combinatorial circuits; Data structures
LO :	INIST-222 X
ID :	00-0342583

Links to Exploration step

Pascal:00-0342583

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">C. Meinel</name>
<affiliation><inist:fA14 i1="01"><s1>Univ Trier</s1>
<s2>Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</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>
</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">C. Meinel</name>
<affiliation><inist:fA14 i1="01"><s1>Univ Trier</s1>
<s2>Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</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>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0278-0070</s0>
</fA01>
<fA03 i2="1"><s0>IEEE Trans Comput Aided Des Integr Circuits Syst</s0>
</fA03>
<fA05><s2>19</s2>
</fA05>
<fA06><s2>5</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>Linear sifting of decision diagrams and its application in synthesis</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>MEINEL (C.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>SOMENZI (F.)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>THEOBALD (T.)</s1>
</fA11>
<fA14 i1="01"><s1>Univ Trier</s1>
<s2>Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA20><s1>521-533</s1>
</fA20>
<fA21><s1>2000</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>222 X</s2>
</fA43>
<fA44><s0>A100</s0>
</fA44>
<fA45><s0>36 Refs.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>00-0342583</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</s0>
</fA64>
<fA66 i1="01"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>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.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02B07B</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001D01A</s0>
</fC02>
<fC02 i1="03" i2="X"><s0>001A02B</s0>
</fC02>
<fC02 i1="04" i2="X"><s0>001D02A</s0>
</fC02>
<fC02 i1="05" i2="X"><s0>001A02D</s0>
</fC02>
<fC02 i1="06" i2="X"><s0>001D02A04</s0>
</fC02>
<fC03 i1="01" i2="1" l="ENG"><s0>Decision diagrams</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="02" i2="1" l="ENG"><s0>Linear sifting</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="03" i2="1" l="ENG"><s0>Linear transformations</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="04" i2="1" l="ENG"><s0>Binary decision diagrams</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="05" i2="1" l="FRE"><s0>Expérience</s0>
</fC03>
<fC03 i1="05" i2="1" l="ENG"><s0>Experiments</s0>
</fC03>
<fC03 i1="06" i2="1" l="FRE"><s0>Optimisation</s0>
</fC03>
<fC03 i1="06" i2="1" l="ENG"><s0>Optimization</s0>
</fC03>
<fC03 i1="07" i2="1" l="FRE"><s0>Algorithme</s0>
</fC03>
<fC03 i1="07" i2="1" l="ENG"><s0>Algorithms</s0>
</fC03>
<fC03 i1="08" i2="1" l="FRE"><s0>Transformation mathématique</s0>
</fC03>
<fC03 i1="08" i2="1" l="ENG"><s0>Mathematical transformations</s0>
</fC03>
<fC03 i1="09" i2="1" l="FRE"><s0>Fonction booléenne</s0>
</fC03>
<fC03 i1="09" i2="1" l="ENG"><s0>Boolean functions</s0>
</fC03>
<fC03 i1="10" i2="1" l="FRE"><s0>Algèbre matricielle</s0>
</fC03>
<fC03 i1="10" i2="1" l="ENG"><s0>Matrix algebra</s0>
</fC03>
<fC03 i1="11" i2="1" l="FRE"><s0>Analyse spectre</s0>
</fC03>
<fC03 i1="11" i2="1" l="ENG"><s0>Spectrum analysis</s0>
</fC03>
<fC03 i1="12" i2="1" l="FRE"><s0>Circuit combinatoire</s0>
</fC03>
<fC03 i1="12" i2="1" l="ENG"><s0>Combinatorial circuits</s0>
</fC03>
<fC03 i1="13" i2="1" l="FRE"><s0>Structure donnée</s0>
<s3>P</s3>
</fC03>
<fC03 i1="13" i2="1" l="ENG"><s0>Data structures</s0>
<s3>P</s3>
</fC03>
<fN21><s1>234</s1>
</fN21>
</pA>
</standard>
<server><NO>PASCAL 00-0342583 EI</NO>
<ET>Linear sifting of decision diagrams and its application in synthesis</ET>
<AU>MEINEL (C.); SOMENZI (F.); THEOBALD (T.)</AU>
<AF>Univ Trier/Trier/Allemagne (1 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems; ISSN 0278-0070; Etats-Unis; Da. 2000; Vol. 19; No. 5; Pp. 521-533; Bibl. 36 Refs.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001D02B07B; 001D01A; 001A02B; 001D02A; 001A02D; 001D02A04</CC>
<FD>Expérience; Optimisation; Algorithme; Transformation mathématique; Fonction booléenne; Algèbre matricielle; Analyse spectre; Circuit combinatoire; Structure donnée</FD>
<ED>Decision diagrams; Linear sifting; Linear transformations; Binary decision diagrams; Experiments; Optimization; Algorithms; Mathematical transformations; Boolean functions; Matrix algebra; Spectrum analysis; Combinatorial circuits; Data structures</ED>
<LO>INIST-222 X</LO>
<ID>00-0342583</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000F28 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000F28 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    PascalFrancis
   |étape=   Corpus
   |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.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

Linear sifting of decision diagrams and its application in synthesis

Linear sifting of decision diagrams and its application in synthesis

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri