JUCS - Journal of Universal Computer Science 5(5): 307-321, doi: 10.3217/jucs-005-05-0307
Group Theoretical Aspects of Reversible Logic Gates
expand article infoLeo Storme, Alexis De Vos§, Gerald Jacobs|
‡ Vakgroep zuivere wiskunde en computeralgebra, Universiteit Gent, Gent, Belgium§ Imec v.z.w., Universiteit Gent, Gent, Belgium| Vakgroep wiskundige natuurkunde en sterrenkunde, Universiteit Gent, Gent, Belgium
Open Access
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
reversible computing, group theory, permutations