« back

Only available in German

---

Kolloquium | Besuch und Kolloquium "Minimization Techniques for Reversible Logic Synthesis"

05.12.2005 | ab 15 Uhr | SFG (Raum 2060)

Gerhard Dueck | University of New Brunswick, Kanada

Gerhard Dueck aus Kanada wird in der Woche vom 5.-9.12. zu Besuch sein. Am Montag (5.12.) wird er ab 15 Uhr einen Vortrag über "Minimization Techniques for Reversible Logic Synthesis" halten.

Abstract

Reversible logic is an emerging research area. Interest in reversible logic is sparked by its applications in quantum computing, low-power CMOS, nanotechnology, and optical computing. Synthesis of reversible circuits differs significantly from synthesis using traditional irreversible gates. Two restrictions are added for reversible networks, namely fan-outs and back-feeds are not allowed. Thus, the only possible structure for a reversible network is a cascade of reversible gates. Toffoli gates are the most frequently used and best investigated. The Toffoli gate inverts a single bit if the Boolean AND of a set of control lines is true. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. In this talk I will addresses the above synthesis idea. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half the gates in a template, then a transformation reducing the gate count can be applied. I will describe an efficient method to find all identity circuits (the basis for a template) with a reasonable number of gates. I will conclude the talk by describing some open problems and offer hints on how to tackle them.Reversible Logic Synthesis" halten.

»Gerhard Dueck was born in Montevideo, Uruguay. He received the Ph.D. degree in Computer Science form the University of Manitoba, Winnipeg, Manitoba, Canada, in 1988. He is currently Professor and Assistant Dean in the Faculty of Computer Science at the University of New Brunswick. His research interests include reversible logic, Reed Muller expansions, multiple-valued logic, and digital design.