ENUMERATION AND CODING METHODS FOR A CLASS OF PERMUTATIONS AND REVERSIBLE LOGICAL GATES

Costas Karanikas, Nikolaos Atreas

DOI Number
10.2298/FUEE1802241K
First page
241
Last page
255

Abstract


We introduce a great variety of coding methods for boolean sparse invertible matrices and we use these methods to create a variety of bijections on the permutation group P(m) of the set {1,2,...,m}. Also, we propose methods for coding, enumerating and shuffling the set{0,...,2m−1}, i.e. the set of all m-bit binary arrays. Moreover we show that several well known reversible logic gates/circuits (on m-bit binary arrays) can be coded by sparse matrices.

Keywords

Permutations, Reversible Logical Gates.

Full Text:

PDF

References


K.N. Patel, J.P. Hayes, and I.L. Markov, “Fault testing for reversible circuits,” in IEEE VLSI Test Symposium, Napa Valley, California, 2003, pp. 410–417.

N. Atreas and C. Karanikas, “Boolean invertible matrices identified from two permutations and their corresponding haar-type matrices,” Linear Algebra Appl., vol. 435, no. 1, pp. 95–105, 2011.

N. Atreas and C. Karanikas, “Multiscale haar unitary matrices with the corresponding riesz products andacharacterizationofcantor-typelanguages,”J.FourierAnal.Appl.,vol.13, no. 2, pp. 197–210, 2007.

N. Atreas and C. Karanikas, “Haar-type orthonormal systems, data presentation as riesz products and a recognition on symbolic sequences,” Contemporary Math., vol. 451, pp. 1–9, 2008.

N. Atreas and C. Karanikas, “Discrete type riesz products,” in Walsh and Dyadic Analysis, 2008, pp. 137–143.

N. Atreas, C. Karanikas, and P. Polychronidou, “A class of sparse unimodular matrices generating multiresolution and sampling analysis for data of any length,” SIAM J. Matrix Anal. Appl.,, vol. 30, no. 1, pp. 312–323, 2008.

D. H. Lehmer, “Teaching combinatorial tricks to a computer,” in Proc. Symbos. Appl. Math. Combinatorial Analysis, vol. 10, 1960, pp. 179–193.

P. Diaconis, G. Graham, and S. P. Holmes, “Statistical problems involving permutations with restricted positions,” in Lecture Notes. Monograph Series, vol. 36, 2001, pp. 195–202.

P. Diaconis and M. Shahshahani, “Generating a random permutation with random transposition,” Z. Wahr. verw. Gebeite, vol. 57, no. 2, pp. 159–17, 1981.


Refbacks

  • There are currently no refbacks.


ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626