• Previous Article
    On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity
  • AMC Home
  • This Issue
  • Next Article
    A note on the order bound on the minimum distance of AG codes and acute semigroups
May  2008, 2(2): 183-200. doi: 10.3934/amc.2008.2.183

Young subgroups for reversible computers

1. 

Imec v.z.w. and Vakgroep elektronika en informatiesystemen, Universiteit Gent, Sint Pietersnieuwstraat 41, B - 9000 Gent, Belgium

2. 

Vakgroep elektronika en informatiesystemen, Universiteit Gent, Sint Pietersnieuwstraat 41, B - 9000 Gent, Belgium

Received  November 2007 Revised  February 2008 Published  April 2008

We consider the symmetric group $S_n$ in the special case where $n$ is composite: $n = pq$ (both $p$ and $q$ being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of $S$ pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup $S_p^q$, whereas the second one is an element of the dual Young subgroup $S_q^p$. This leads to synthesis methods for arbitrary reversible logic circuits of logic width $w$. These circuits form a group isomorphic to $S$2w. A particularly efficient synthesis is found by choosing $p=2$ and thus $q=2$w−1. The approach illustrates a direct link between combinatorics, group theory, and reversible computing.
Citation: Alexis De Vos, Yvan Van Rentergem. Young subgroups for reversible computers. Advances in Mathematics of Communications, 2008, 2 (2) : 183-200. doi: 10.3934/amc.2008.2.183
[1]

João Marcos do Ó, Bruno Ribeiro, Bernhard Ruf. Hamiltonian elliptic systems in dimension two with arbitrary and double exponential growth conditions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 277-296. doi: 10.3934/dcds.2020138

[2]

Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020449

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (148)
  • HTML views (0)
  • Cited by (21)

Other articles
by authors

[Back to Top]