Group Theoretical Aspects of Reversible Logic Gates

Leo Storme (Vakgroep zuivere wiskunde en computeralgebra, Universiteit Gent, Belguim)

Alexis De Vos (Imec v.z.w., Universiteit Gent, Belgium)

Gerald Jacobs (Vakgroep wiskundige natuurkunde en sterrenkunde, Universiteit Gent, Belgium)

Abstract: Logic gates with three input bits and three output bits have a privileged position within fundamental computer science: they are a sufficient building block for constructing arbitrary reversible boolean networks and therefore are the key to reversible digital computers. Such computers can, in principle, operate without heat production. As there exist as many as 8! = 40,320 different 3-bit reversible truth tables, the question arises as to which ones to choose as building blocks. Because these gates form a group with respect to the operation "cascading" , we can apply group theoretical tools, in order to make such a choice.

Keywords: group theory, permutations, reversible computing

Categories: B.6.1