- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Ancilla-free reversible logic synthesis using symbolic...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Ancilla-free reversible logic synthesis using symbolic methods Soeken, Mathias
Description
Due to the properties of reversibility, optimum synthesis with respect to the number of lines is a difficult task. For an irreversible Boolean function it is coNP-hard to find an optimum embedding, i.e., a reversible function with the minimum number of additional lines. Synthesis algorithms exists that obtain from an optimum embedding ancilla-free reversible circuits which have as many circuit lines as variables in the reversible function. However, so far all implementations for such synthesis algorithms require exponential time and space since they operate on the truth table representation of the function. In the talk, alternative implementations of the algorithms based on symbolic methods are presented that allow to run the algorithm in less space and time for some functions. It is shown that high quality synthesis results for large circuits can be obtained using these implementations.
Item Metadata
Title |
Ancilla-free reversible logic synthesis using symbolic methods
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2016-04-18T15:52
|
Description |
Due to the properties of reversibility, optimum synthesis with respect to the number of lines is a difficult task. For an irreversible Boolean function it is coNP-hard to find an optimum embedding, i.e., a reversible function with the minimum number of additional lines. Synthesis algorithms exists that obtain from an optimum embedding ancilla-free reversible circuits which have as many circuit lines as variables in the reversible function. However, so far all implementations for such synthesis algorithms require exponential time and space since they operate on the truth table representation of the function. In the talk, alternative implementations of the algorithms based on symbolic methods are presented that allow to run the algorithm in less space and time for some functions. It is shown that high quality synthesis results for large circuits can be obtained using these implementations.
|
Extent |
34 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: École polytechnique fédérale de Lausanne
|
Series | |
Date Available |
2016-10-18
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0319173
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Postdoctoral
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International