FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. x, No x, x 2018, pp. x ENERGY-EFFICIENT CRYPTOGRAPHIC PRIMITIVES Elena Dubrova∗ Royal Institute of Technology (KTH), Stockholm, Sweden Abstract: Our society greatly depends on services and applications provided by mobile communication networks. As billions of people and devices become connected, it becomes increasingly important to guarantee security of interac- tions of all players. In this talk we address several aspects of this important, many-folded problem. First, we show how to design cryptographic primitives which can assure integrity and confidentiality of transmitted messages while satisfying resource constrains of low-end low-cost wireless devices such as sen- sors or RFID tags. Second, we describe countermeasures which can enhance the resistance of hardware implementing cryptographic algorithms to hardware Trojans. Keywords: Security, lightweight cryptography, cryptographic primitive, en- cryption, message authentication, hardware Trojan. 1 Introduction Today minimal or no security is typically provided to low-end low-cost wire- less devices such as sensors or RFID tags in the conventional belief that the information they gather is of little concern to attackers. However, case studies have shown that a compromised sensor can be used as a stepping stone to mount an attack on a wireless network. For example, in the attack Manuscript received x x, x Corresponding author: Elena Dubrova Royal Institute of Technology (KTH), Stockholm, Sweden (e-mail: dubrova@kth.se) ∗An earlier version of this paper was presented as an invited address at the Reed-Muller 2017 Workshop, Novi Sad, Serbia, May 24-25, 2017. 1 FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. xx, No x, xxxx, pp. xxx - xxx ENUMERATION AND CODING METHODS FOR A CLASS OF PERMUTATIONS AND REVERSIBLE LOGICAL GATES Costas Karanikas1 and Nikolaos Atreas2 1 School of Informatics, Aristotle University of Thessaloniki, Greece 2 School of Electrical and Computer Engineering, Faculty of Engineering, Aristotle University of Thessaloniki, Greece 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. 1 Introduction Let m ≥ 2 be a natural number and P(m) be the group of permutations of the set {1, ..., m}. In this work we introduce a variety of shuffling methods. More precisely, each shuffling method is a bijective map of a set onto itself, i.e. different inputs yield different outputs and the number of inputs and outputs are equal. Manuscript received xx, xxxx Corresponding author: Nikolaos Atreas School of Electrical and Computer Engineering, Faculty of Engineering, Aristotle Univer- sity of Thessaloniki, Greece (e-mail: natreas@ece.auth.gr) An earlier version of this paper was presented as an invited address at the Reed-Muller 2017 Workshop, Novi Sad, Serbia, May 24-25, 2017 1 2 N. ATREAS AND C. KARANIKAS Our main theorem 2 in section 3 or its ”binary” version (see theorem 3 in section 4), states that any pair (ρ, s) of permutations in P(m) determines a bijective map Tρ,s : {0, 1, ...., 2m − 1} → {0, 1, ...., 2m − 1}. Since every non negative integer n ∈ {0, 1, ...., 2m − 1} can be expressed either as an m-bit binary array en = ( ε0(n), ε1(n), ..., εm−1(n) ) , εj ∈ {0, 1}, or by its dyadic expansion n = m∑ j=1 εj(n)2 j−1, the above map Tρ,s can be considered as a reversible map on the set of all m-bit binary arrays. In a different terminology, we can say that in theorem 3 we introduce reversible logic gates, i.e bijective maps on the set of m-bit binary arrays, (see [1]). An example of a reversible gate is the NOT gate, whereas the AND, OR, XOR gates are irreversible (not reversible), because they map 4 = 22 input states into 2 = 21 output states, so information is lost in the merging of paths. A second target of this work is to enumerate and code permutations in P(m) of large length (note that the cardinality of the set P(m) is m!). Therefore, a reversible map Tρ,s associated with the pair (ρ, s) can be coded either by the pair (ρ, s) or by an enumeration of P(m)×P(m) as in section 2. This coding method is associated with a particular class of sparse boolean invertible matrices introduced in [2] (see also [3–6]). Notice that sparse matrices are very useful for fast processing/transmission of data and they have been effectively used in [6] for detecting specific characteristics on finite data. The paper is organized in the following sections: In section 2 we introduce our main tool, the invertible map P(m) → S(m) (see (2) and (3)) and in Proposition 1, we see that this map induces the lexicographic order of the enumeration of P(m). Moreover we consider the cartesian product R(m) = P(1)×P(2)× ...×P(m) of permutations to show in theorem 1 that each fixed element of R(m) provides an enumeration of P(m). In section 3 we define a class of sparse m×m boolean invertible matrices Zm identified by a pair (ρ, s) ∈ P(m)×S(m) and we use this class of matrices FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 31, No 2, June 2018, pp. 241 - 255 https://doi.org/10.2298/FUEE1802241K Costas Karanikas1, Nikolaos Atreas2 Received October 22, 2017; received in revised form January 24, 2018 Corresponding author: Nikolaos Atreas School of Electrical and Computer Engineering, Dpt of Telecommunications, Faculty of Engineering, Aristotle University of Thessaloniki, 54124, Thessaloniki, Greece (E-mail: natreas@auth.gr) *An earlier version of this paper was presented as an invited address at the Reed-Muller 2017 Workshop, Novi Sad, Serbia, May 24-25, 2017 FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 28, No 4, December 2015, pp. 507 - 525 DOI: 10.2298/FUEE1504507S HORIZONTAL CURRENT BIPOLAR TRANSISTOR (HCBT) – A LOW-COST, HIGH-PERFORMANCE FLEXIBLE BICMOS TECHNOLOGY FOR RF COMMUNICATION APPLICATIONS Tomislav Suligoj1, Marko Koričić1, Josip Žilak1, Hidenori Mochizuki2, So-ichi Morita2, Katsumi Shinomura2, Hisaya Imai2 1University of Zagreb, Faculty of Electrical Engineering and Computing, Department of Electronics, Micro- and Nano-electronics Laboratory, Croatia 2Asahi Kasei Microdevices Co. 5-4960, Nobeoka, Miyazaki, 882-0031, Japan Abstract. In an overview of Horizontal Current Bipolar Transistor (HCBT) technology, the state-of-the-art integrated silicon bipolar transistors are described which exhibit fT and fmax of 51 GHz and 61 GHz and fTBVCEO product of 173 GHzV that are among the highest-performance implanted-base, silicon bipolar transistors. HBCT is integrated with CMOS in a considerably lower-cost fabrication sequence as compared to standard vertical-current bipolar transistors with only 2 or 3 additional masks and fewer process steps. Due to its specific structure, the charge sharing effect can be employed to increase BVCEO without sacrificing fT and fmax. Moreover, the electric field can be engineered just by manipulating the lithography masks achieving the high-voltage HCBTs with breakdowns up to 36 V integrated in the same process flow with high-speed devices, i.e. at zero additional costs. Double-balanced active mixer circuit is designed and fabricated in HCBT technology. The maximum IIP3 of 17.7 dBm at mixer current of 9.2 mA and conversion gain of -5 dB are achieved. Key words: BiCMOS technology, Bipolar transistors, Horizontal Current Bipolar Transistor, Radio frequency integrated circuits, Mixer, High-voltage bipolar transistors. 1. INTRODUCTION In the highly competitive wireless communication markets, the RF circuits and systems are fabricated in the technologies that are very cost-sensitive. In order to minimize the fabrication costs, the sub-10 GHz applications can be processed by using the high-volume silicon technologies. It has been identified that the optimum solution might Received March 9, 2015 Corresponding author: Tomislav Suligoj University of Zagreb, Faculty of Electrical Engineering and Computing, Department of Electronics, Micro- and Nano-electronics Laboratory, Croatia (e-mail: tom@zemris.fer.hr) ENUMERATION AND CODING METHODS FOR A CLASS OF PERMUTATIONS AND REVERSIBLE LOGICAL GATES* 1School of Informatics, Aristotle University of Thessaloniki, Greece 2School of Electrical and Computer Engineering, Faculty of Engineering, Aristotle University of Thessaloniki, Greece 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. Key words: Permutations, Reversible Logical Gates. 2 N. ATREAS AND C. KARANIKAS Our main theorem 2 in section 3 or its ”binary” version (see theorem 3 in section 4), states that any pair (ρ, s) of permutations in P(m) determines a bijective map Tρ,s : {0, 1, ...., 2m − 1} → {0, 1, ...., 2m − 1}. Since every non negative integer n ∈ {0, 1, ...., 2m − 1} can be expressed either as an m-bit binary array en = ( ε0(n), ε1(n), ..., εm−1(n) ) , εj ∈ {0, 1}, or by its dyadic expansion n = m∑ j=1 εj(n)2 j−1, the above map Tρ,s can be considered as a reversible map on the set of all m-bit binary arrays. In a different terminology, we can say that in theorem 3 we introduce reversible logic gates, i.e bijective maps on the set of m-bit binary arrays, (see [1]). An example of a reversible gate is the NOT gate, whereas the AND, OR, XOR gates are irreversible (not reversible), because they map 4 = 22 input states into 2 = 21 output states, so information is lost in the merging of paths. A second target of this work is to enumerate and code permutations in P(m) of large length (note that the cardinality of the set P(m) is m!). Therefore, a reversible map Tρ,s associated with the pair (ρ, s) can be coded either by the pair (ρ, s) or by an enumeration of P(m)×P(m) as in section 2. This coding method is associated with a particular class of sparse boolean invertible matrices introduced in [2] (see also [3–6]). Notice that sparse matrices are very useful for fast processing/transmission of data and they have been effectively used in [6] for detecting specific characteristics on finite data. The paper is organized in the following sections: In section 2 we introduce our main tool, the invertible map P(m) → S(m) (see (2) and (3)) and in Proposition 1, we see that this map induces the lexicographic order of the enumeration of P(m). Moreover we consider the cartesian product R(m) = P(1)×P(2)× ...×P(m) of permutations to show in theorem 1 that each fixed element of R(m) provides an enumeration of P(m). In section 3 we define a class of sparse m×m boolean invertible matrices Zm identified by a pair (ρ, s) ∈ P(m)×S(m) and we use this class of matrices Enumeration and Coding Permutations and Reversible Logical Circuits 3 to produce a class of non-linear bijection maps Tq,ρ,s : {0, ..., qm − 1} → {0, ..., qm − 1}, see our main theorem 2. In section 4 we show that any triple (ρ, s, τ) of permutations in P(m) provides a variety of maps from {0, ..., 2m − 1} onto {0, ..., 2m − 1} and we see that several reversible logic gates can be determined by this triple. Finally, in section 5 we apply theorems 1 and 2, to see with an example that for any pair (ρ, s) ∈ P(m) × S(m) and any fixed r ∈ R(2m) we shuffle the elements of the set {0, ..., 2m −1} and we discus the random permutation generation problem. 2 Enumeration methods for P(m) Let m ≥ 2 be a natural number. First we review the lexicographical order of the set S(m) = { s = (s1, ..., sm) : si ∈ {1, 2, ..., i} } . (1) Obviously, the map U : S(m) → {0, ..., m! − 1} : U(s) = m! m∑ i=1 si − 1 i! (2) is a bijection and the elements si ∈ {1, ..., i} can be thought of digits of the number U(s) with respect to the factorial number system. Inversely, for any n ∈ {0, ..., m! − 1}, its digits si(n), i = 1, ..., m are computed by the formula si(n) = Mod ([n i! m! ] , i ) + 1 describing the inverse map U−1. Here, [x] is the floor of x. From now on we say that U provides the lexicographical order of S(m). Using the lexicographical order of S(m) we may obtain an enumeration of the group of permutations P(m) of the set {1, ..., m} as well. In fact, let us define the map Q : P(m) → S(m) : Q(ρ) = s = (s1, ..., sm), (3) where each element si ∈ S(m) is defined by using the following iteration scheme: 242 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 243 2 N. ATREAS AND C. KARANIKAS Our main theorem 2 in section 3 or its ”binary” version (see theorem 3 in section 4), states that any pair (ρ, s) of permutations in P(m) determines a bijective map Tρ,s : {0, 1, ...., 2m − 1} → {0, 1, ...., 2m − 1}. Since every non negative integer n ∈ {0, 1, ...., 2m − 1} can be expressed either as an m-bit binary array en = ( ε0(n), ε1(n), ..., εm−1(n) ) , εj ∈ {0, 1}, or by its dyadic expansion n = m∑ j=1 εj(n)2 j−1, the above map Tρ,s can be considered as a reversible map on the set of all m-bit binary arrays. In a different terminology, we can say that in theorem 3 we introduce reversible logic gates, i.e bijective maps on the set of m-bit binary arrays, (see [1]). An example of a reversible gate is the NOT gate, whereas the AND, OR, XOR gates are irreversible (not reversible), because they map 4 = 22 input states into 2 = 21 output states, so information is lost in the merging of paths. A second target of this work is to enumerate and code permutations in P(m) of large length (note that the cardinality of the set P(m) is m!). Therefore, a reversible map Tρ,s associated with the pair (ρ, s) can be coded either by the pair (ρ, s) or by an enumeration of P(m)×P(m) as in section 2. This coding method is associated with a particular class of sparse boolean invertible matrices introduced in [2] (see also [3–6]). Notice that sparse matrices are very useful for fast processing/transmission of data and they have been effectively used in [6] for detecting specific characteristics on finite data. The paper is organized in the following sections: In section 2 we introduce our main tool, the invertible map P(m) → S(m) (see (2) and (3)) and in Proposition 1, we see that this map induces the lexicographic order of the enumeration of P(m). Moreover we consider the cartesian product R(m) = P(1)×P(2)× ...×P(m) of permutations to show in theorem 1 that each fixed element of R(m) provides an enumeration of P(m). In section 3 we define a class of sparse m×m boolean invertible matrices Zm identified by a pair (ρ, s) ∈ P(m)×S(m) and we use this class of matrices Enumeration and Coding Permutations and Reversible Logical Circuits 3 to produce a class of non-linear bijection maps Tq,ρ,s : {0, ..., qm − 1} → {0, ..., qm − 1}, see our main theorem 2. In section 4 we show that any triple (ρ, s, τ) of permutations in P(m) provides a variety of maps from {0, ..., 2m − 1} onto {0, ..., 2m − 1} and we see that several reversible logic gates can be determined by this triple. Finally, in section 5 we apply theorems 1 and 2, to see with an example that for any pair (ρ, s) ∈ P(m) × S(m) and any fixed r ∈ R(2m) we shuffle the elements of the set {0, ..., 2m −1} and we discus the random permutation generation problem. 2 Enumeration methods for P(m) Let m ≥ 2 be a natural number. First we review the lexicographical order of the set S(m) = { s = (s1, ..., sm) : si ∈ {1, 2, ..., i} } . (1) Obviously, the map U : S(m) → {0, ..., m! − 1} : U(s) = m! m∑ i=1 si − 1 i! (2) is a bijection and the elements si ∈ {1, ..., i} can be thought of digits of the number U(s) with respect to the factorial number system. Inversely, for any n ∈ {0, ..., m! − 1}, its digits si(n), i = 1, ..., m are computed by the formula si(n) = Mod ([n i! m! ] , i ) + 1 describing the inverse map U−1. Here, [x] is the floor of x. From now on we say that U provides the lexicographical order of S(m). Using the lexicographical order of S(m) we may obtain an enumeration of the group of permutations P(m) of the set {1, ..., m} as well. In fact, let us define the map Q : P(m) → S(m) : Q(ρ) = s = (s1, ..., sm), (3) where each element si ∈ S(m) is defined by using the following iteration scheme: Enumeration and Coding Permutations and Reversible Logical Circuits 3 to produce a class of non-linear bijection maps Tq,ρ,s : {0, ..., qm − 1} → {0, ..., qm − 1}, see our main theorem 2. In section 4 we show that any triple (ρ, s, τ) of permutations in P(m) provides a variety of maps from {0, ..., 2m − 1} onto {0, ..., 2m − 1} and we see that several reversible logic gates can be determined by this triple. Finally, in section 5 we apply theorems 1 and 2, to see with an example that for any pair (ρ, s) ∈ P(m) × S(m) and any fixed r ∈ R(2m) we shuffle the elements of the set {0, ..., 2m −1} and we discus the random permutation generation problem. 2 Enumeration methods for P(m) Let m ≥ 2 be a natural number. First we review the lexicographical order of the set S(m) = { s = (s1, ..., sm) : si ∈ {1, 2, ..., i} } . (1) Obviously, the map U : S(m) → {0, ..., m! − 1} : U(s) = m! m∑ i=1 si − 1 i! (2) is a bijection and the elements si ∈ {1, ..., i} can be thought of digits of the number U(s) with respect to the factorial number system. Inversely, for any n ∈ {0, ..., m! − 1}, its digits si(n), i = 1, ..., m are computed by the formula si(n) = Mod ([n i! m! ] , i ) + 1 describing the inverse map U−1. Here, [x] is the floor of x. From now on we say that U provides the lexicographical order of S(m). Using the lexicographical order of S(m) we may obtain an enumeration of the group of permutations P(m) of the set {1, ..., m} as well. In fact, let us define the map Q : P(m) → S(m) : Q(ρ) = s = (s1, ..., sm), (3) where each element si ∈ S(m) is defined by using the following iteration scheme: 4 N. ATREAS AND C. KARANIKAS For the above selection of m and the initial permutation ρ in (3), we store the position of the biggest element in ρ, i.e. we define sm = ρ −1(m) and at the same time we delete this element ρ(sm) = m from ρ and so we form a new permutation ρ(m−1) ∈ P(m − 1) by ρ(m−1)(j) = { ρ(j) if j < sm ρ(j + 1) if j ≥ sm , j = 1, ..., m − 1. Then we follow the previous step for the permutation ρ(m−1), i.e. we store the position of its biggest element by defining sm−1 = ρ −1 (m−1)(m − 1) and at the same time we delete the element m − 1 from ρ(m−1) and we form a new permutation ρ(m−2) ∈ P(m − 2) by ρ(m−2)(j) = { ρ(m−1)(j) if j < sm−1 ρ(m−1)(j + 1) if j ≥ sm−1 , j = 1, ..., m − 2. We continue in the same spirit until S is completely determined. Example 1 Let ρ = (2, 3, 4, 1). In order to determine the set S = {s1, s2, s3, s4} in (3) we are based on the above iteration scheme and so we proceed in the following way: (i) Define s4 = ρ−1(4) = 3 and ρ(3) = (2, 3, 1). (ii) Define s3 = ρ−1(3)(3) = 2 and ρ(2) = (2, 1). (iii) Define s2 = ρ−1(2)(2) = 1 and ρ(1) = (1). (iv) Define s1 = ρ−1(1)(1) = 1 and ρ(4) = ∅. Now we have the following: Proposition 1 [2] Let U and Q be two maps as in (2) and (3) respectively. Then Q is a bijection and so the composition map UQ : P(m) → {0, ..., m! − 1} provides an enumeration of P(m). 242 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 243 4 N. ATREAS AND C. KARANIKAS For the above selection of m and the initial permutation ρ in (3), we store the position of the biggest element in ρ, i.e. we define sm = ρ −1(m) and at the same time we delete this element ρ(sm) = m from ρ and so we form a new permutation ρ(m−1) ∈ P(m − 1) by ρ(m−1)(j) = { ρ(j) if j < sm ρ(j + 1) if j ≥ sm , j = 1, ..., m − 1. Then we follow the previous step for the permutation ρ(m−1), i.e. we store the position of its biggest element by defining sm−1 = ρ −1 (m−1)(m − 1) and at the same time we delete the element m − 1 from ρ(m−1) and we form a new permutation ρ(m−2) ∈ P(m − 2) by ρ(m−2)(j) = { ρ(m−1)(j) if j < sm−1 ρ(m−1)(j + 1) if j ≥ sm−1 , j = 1, ..., m − 2. We continue in the same spirit until S is completely determined. Example 1 Let ρ = (2, 3, 4, 1). In order to determine the set S = {s1, s2, s3, s4} in (3) we are based on the above iteration scheme and so we proceed in the following way: (i) Define s4 = ρ−1(4) = 3 and ρ(3) = (2, 3, 1). (ii) Define s3 = ρ−1(3)(3) = 2 and ρ(2) = (2, 1). (iii) Define s2 = ρ−1(2)(2) = 1 and ρ(1) = (1). (iv) Define s1 = ρ−1(1)(1) = 1 and ρ(4) = ∅. Now we have the following: Proposition 1 [2] Let U and Q be two maps as in (2) and (3) respectively. Then Q is a bijection and so the composition map UQ : P(m) → {0, ..., m! − 1} provides an enumeration of P(m). 244 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 245 4 N. ATREAS AND C. KARANIKAS For the above selection of m and the initial permutation ρ in (3), we store the position of the biggest element in ρ, i.e. we define sm = ρ −1(m) and at the same time we delete this element ρ(sm) = m from ρ and so we form a new permutation ρ(m−1) ∈ P(m − 1) by ρ(m−1)(j) = { ρ(j) if j < sm ρ(j + 1) if j ≥ sm , j = 1, ..., m − 1. Then we follow the previous step for the permutation ρ(m−1), i.e. we store the position of its biggest element by defining sm−1 = ρ −1 (m−1)(m − 1) and at the same time we delete the element m − 1 from ρ(m−1) and we form a new permutation ρ(m−2) ∈ P(m − 2) by ρ(m−2)(j) = { ρ(m−1)(j) if j < sm−1 ρ(m−1)(j + 1) if j ≥ sm−1 , j = 1, ..., m − 2. We continue in the same spirit until S is completely determined. Example 1 Let ρ = (2, 3, 4, 1). In order to determine the set S = {s1, s2, s3, s4} in (3) we are based on the above iteration scheme and so we proceed in the following way: (i) Define s4 = ρ−1(4) = 3 and ρ(3) = (2, 3, 1). (ii) Define s3 = ρ−1(3)(3) = 2 and ρ(2) = (2, 1). (iii) Define s2 = ρ−1(2)(2) = 1 and ρ(1) = (1). (iv) Define s1 = ρ−1(1)(1) = 1 and ρ(4) = ∅. Now we have the following: Proposition 1 [2] Let U and Q be two maps as in (2) and (3) respectively. Then Q is a bijection and so the composition map UQ : P(m) → {0, ..., m! − 1} provides an enumeration of P(m). Enumeration and Coding Permutations and Reversible Logical Circuits 5 Example 2 For m = 4, we demonstrate the enumeration of the elements of P(4) derived from Proposition (1) and the lexicographical order of the elements of S(4) derived from (2). P(4) = {(4, 3, 2, 1), (3, 4, 2, 1), (3, 2, 4, 1), (3, 2, 1, 4), (4, 2, 3, 1), (2, 4, 3, 1), (2, 3, 4, 1), (2, 3, 1, 4), (4, 2, 1, 3), (2, 4, 1, 3), (2, 1, 4, 3), (2, 1, 3, 4), (4, 3, 1, 2), (3, 4, 1, 2), (3, 1, 4, 2), (3, 1, 2, 4), (4, 1, 3, 2), (1, 4, 3, 2), (1, 3, 4, 2), (1, 3, 2, 4), (4, 1, 2, 3), (1, 4, 2, 3), (1, 2, 4, 3), (1, 2, 3, 4)}. S(4) = {(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3), (1, 1, 1, 4), (1, 1, 2, 1), (1, 1, 2, 2), (1, 1, 2, 3), (1, 1, 2, 4), (1, 1, 3, 1), (1, 1, 3, 2), (1, 1, 3, 3), (1, 1, 3, 4), (1, 2, 1, 1), (1, 2, 1, 2), (1, 2, 1, 3), (1, 2, 1, 4), (1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 3), (1, 2, 2, 4), (1, 2, 3, 1), (1, 2, 3, 2), (1, 2, 3, 3), (1, 2, 3, 4)}. For instance, the permutation ρ = (4, 3, 2, 1) is uniquely associated with the set Q(ρ) = (1, 1, 1, 1) (apply example 1) and then UQ(ρ) = 0 by (2). In the same spirit, the permutation ρ = (3, 4, 2, 1) is uniquely asso- ciated with the set Q(ρ) = (1, 1, 1, 2) (apply example 1) and then UQ(ρ) = 1 by (2). Remark 1 The set S(m) in (1) seems to be similar with a Lehmer code [7], but our approach seems to be more efficient for the purpose of obtaining a great variety of enumerating methods for P(m), see theorem (1) below. We notice that the Lehmer code of a permutation ρ = (ρ1, ....ρm) is a sequence of natural numbers (L1, ..., Lm) such that Li is the number of all elements ρ1, ..., ρi−1 which are less than ρi, i = 1, ..., m. 244 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 245 6 N. ATREAS AND C. KARANIKAS We may obtain various enumerations of the elements of S(m) (and hence P(m) as well). Indeed, let us fix any element r = (r1, r2, ..., rm) ∈ R(m) = P(1) × P(2) × ... × P(m), (4) where ri = (ri,1, ...ri,i) ∈ P(i), i = 1, ..., m. Then we have: Theorem 1 Let S(m) be defined in (1) and r be a fixed element of R(m) as in (4). For any s ∈ S(m) we define Wr,m(s) = (r1,s1, r2,s2, ..., rm,sm) Then the map Wr,m is onto S(m). Proof: Let us fix an element r ∈ R(m). Since ri,si ≤ i (due to the fact that ri ∈ P(i)), we deduce that Wr,m(s) ∈ S(m). Also, the fact that ri,j ≤ i for any j = 1, ..., i implies that Wr,m is onto S(m), because any element si of s = (s1, ..., sm) can be written by si = ri,a(i) for some index a(i) ≤ i and so by defining a = {a(i) : i = 1, ..., m} we have Wr,m(a) = s. Let U be as in (2) and Wr,m be as in theorem 1. It is easy to see that the map UWr,mU −1 : {0, ..., m! − 1} → {0, ..., m! − 1} provides a method for shuffling the set {0, ..., m! − 1}. By altering the se- lection of r ∈ R(m) in (4) we obtain a different shuffling. Finally, it is clear that the class of mappings { QWr,mU −1 : r ∈ R(m) } provides a great variety of enumeration/shuffling methods for the set of permutations P(m). Example 3 For m = 4 and r = {(1), (2, 1), (2, 1, 3), (4, 2, 1, 3)}, then by using theorem 1, the lexicographical order of S(4) (see example 2) is shuffled to: {(1, 2, 2, 4), (1, 2, 2, 2), (1, 2, 2, 1), (1, 2, 2, 3), (1, 2, 1, 4), (1, 2, 1, 2), (1, 2, 1, 1), (1, 2, 1, 3), (1, 2, 3, 4), (1, 2, 3, 2), (1, 2, 3, 1), (1, 2, 3, 3), (1, 1, 2, 4), (1, 1, 2, 2), (1, 1, 2, 1), (1, 1, 2, 3), (1, 1, 1, 4), (1, 1, 1, 2), (1, 1, 1, 1), (1, 1, 1, 3), (1, 1, 3, 4), (1, 1, 3, 2), (1, 1, 3, 1), (1, 1, 3, 3)}. 246 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 247 6 N. ATREAS AND C. KARANIKAS We may obtain various enumerations of the elements of S(m) (and hence P(m) as well). Indeed, let us fix any element r = (r1, r2, ..., rm) ∈ R(m) = P(1) × P(2) × ... × P(m), (4) where ri = (ri,1, ...ri,i) ∈ P(i), i = 1, ..., m. Then we have: Theorem 1 Let S(m) be defined in (1) and r be a fixed element of R(m) as in (4). For any s ∈ S(m) we define Wr,m(s) = (r1,s1, r2,s2, ..., rm,sm) Then the map Wr,m is onto S(m). Proof: Let us fix an element r ∈ R(m). Since ri,si ≤ i (due to the fact that ri ∈ P(i)), we deduce that Wr,m(s) ∈ S(m). Also, the fact that ri,j ≤ i for any j = 1, ..., i implies that Wr,m is onto S(m), because any element si of s = (s1, ..., sm) can be written by si = ri,a(i) for some index a(i) ≤ i and so by defining a = {a(i) : i = 1, ..., m} we have Wr,m(a) = s. Let U be as in (2) and Wr,m be as in theorem 1. It is easy to see that the map UWr,mU −1 : {0, ..., m! − 1} → {0, ..., m! − 1} provides a method for shuffling the set {0, ..., m! − 1}. By altering the se- lection of r ∈ R(m) in (4) we obtain a different shuffling. Finally, it is clear that the class of mappings { QWr,mU −1 : r ∈ R(m) } provides a great variety of enumeration/shuffling methods for the set of permutations P(m). Example 3 For m = 4 and r = {(1), (2, 1), (2, 1, 3), (4, 2, 1, 3)}, then by using theorem 1, the lexicographical order of S(4) (see example 2) is shuffled to: {(1, 2, 2, 4), (1, 2, 2, 2), (1, 2, 2, 1), (1, 2, 2, 3), (1, 2, 1, 4), (1, 2, 1, 2), (1, 2, 1, 1), (1, 2, 1, 3), (1, 2, 3, 4), (1, 2, 3, 2), (1, 2, 3, 1), (1, 2, 3, 3), (1, 1, 2, 4), (1, 1, 2, 2), (1, 1, 2, 1), (1, 1, 2, 3), (1, 1, 1, 4), (1, 1, 1, 2), (1, 1, 1, 1), (1, 1, 1, 3), (1, 1, 3, 4), (1, 1, 3, 2), (1, 1, 3, 1), (1, 1, 3, 3)}. Enumeration and Coding Permutations and Reversible Logical Circuits 7 If Q is defined in (3), then by using the composition map Q−1Wr,4U −1 we obtain the following enumeration of the set P(4): {(1, 2, 3, 4), (1, 4, 2, 3), (4, 1, 2, 3), (1, 2, 4, 3), (2, 3, 1, 4), (2, 4, 3, 1), (4, 2, 3, 1), (2, 3, 4, 1), (3, 2, 1, 4), (3, 4, 2, 1), (4, 3, 2, 1), (3, 2, 4, 1), (2, 1, 3, 4), (2, 4, 1, 3), (4, 2, 1, 3), (2, 1, 4, 3), (1, 3, 2, 4), (1, 4, 3, 2), (4, 1, 3, 2), (1, 3, 4, 2), (3, 1, 2, 4), (3, 4, 1, 2), (4, 3, 1, 2), (3, 1, 4, 2)}. 3 A class of boolean matrices coded by permutations and a class of bijection maps Before we introduce a class of bijection maps on {0, 1, ..., qm −1} for any pair of natural numbers m, q ≥ 2, we present as in [2] a class of sparse boolean matrices and their properties. Definition 1 For any natural number m ≥ 2 we define by Zm the class of all m × m boolean matrices whose row vectors Zi satisfy Zi ⊙ Zj = cij Zmax{i,j} : cij ∈ {0, 1}, i, j = 1, ..., m, where ⊙ is the usual Hadamard product operation. Then the following result is straightforward: Lemma 1 [2] Let A be an m × m boolean matrix and let 1 ≤ i < j ≤ m. Then A ∈ Zm if and only if supp{Aj} ⊂ supp{Ai} or supp{Ai}∩supp{Aj} = ∅. Here, supp{Aj} denotes the set of all non zero entries of the row Aj. In [2] we proved the following: Proposition 2 Let P(m) and S(m) be defined in section 2. Then every matrix in the class Zm is uniquely identified by a pair (ρ, s) ∈ P(m)×S(m). Using the above observations we may easily construct elements in the above class of Zm matrices. Indeed, let us fix a pair (ρ, s) ∈ P(m) × S(m) which determines a matrix Z ∈ Zm in a unique way. From the pair (ρ, s) we may construct Z in the following manner: 246 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 247 8 N. ATREAS AND C. KARANIKAS (i) First, we use ρ to permute the rows of the identity matrix Im and so we construct an m × m permutation matrix, say Z1. (ii) Starting with the above matrix Z1, we construct a sequence {Zi}mi=2 of m × m matrices iteratively, by using s ∈ S(m). In the ith step of this iteration, a matrix Zi is constructed from the matrix Zi−1 based on the following rule: (a) If si = i, define Zi = Zi−1. (a) If si < i, define Zi by replacing only the si-row of Zi−1 with the sum of the i-row and si-row of Zi−1. (iii) Execute step (ii) for any i = 2, ..., m. Then Z = Zm is a matrix in the class Zm. Example 4 Let m = 5, ρ = (4, 1, 2, 5, 3) and s = (1, 1, 3, 1, 3). Then the element Z ∈ Z5 associated with the above pair (ρ, s) is the following Z =   1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0   . It is remarkable that any matrix Z in the class Zm (which depends only on a pair (ρ, s)) is invertible and the entries of inverse matrix Z−1 are immediately computed by the above pair (ρ, s): Z−1i,j =    1 i = ρ(j) −1, i = ρ(s(j)) and s(j) < j 0 otherwise , i, j = 1, ..., m. (5) Example 5 If Z ∈ Z5 is as in example (4), then the inverse matrix of Z is calculated directly from (5): Z−1 =   0 1 0 0 0 0 0 1 0 −1 0 0 0 0 1 1 −1 0 −1 0 0 0 0 1 0   . 248 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 249 8 N. ATREAS AND C. KARANIKAS (i) First, we use ρ to permute the rows of the identity matrix Im and so we construct an m × m permutation matrix, say Z1. (ii) Starting with the above matrix Z1, we construct a sequence {Zi}mi=2 of m × m matrices iteratively, by using s ∈ S(m). In the ith step of this iteration, a matrix Zi is constructed from the matrix Zi−1 based on the following rule: (a) If si = i, define Zi = Zi−1. (a) If si < i, define Zi by replacing only the si-row of Zi−1 with the sum of the i-row and si-row of Zi−1. (iii) Execute step (ii) for any i = 2, ..., m. Then Z = Zm is a matrix in the class Zm. Example 4 Let m = 5, ρ = (4, 1, 2, 5, 3) and s = (1, 1, 3, 1, 3). Then the element Z ∈ Z5 associated with the above pair (ρ, s) is the following Z =   1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0   . It is remarkable that any matrix Z in the class Zm (which depends only on a pair (ρ, s)) is invertible and the entries of inverse matrix Z−1 are immediately computed by the above pair (ρ, s): Z−1i,j =    1 i = ρ(j) −1, i = ρ(s(j)) and s(j) < j 0 otherwise , i, j = 1, ..., m. (5) Example 5 If Z ∈ Z5 is as in example (4), then the inverse matrix of Z is calculated directly from (5): Z−1 =   0 1 0 0 0 0 0 1 0 −1 0 0 0 0 1 1 −1 0 −1 0 0 0 0 1 0   . Enumeration and Coding Permutations and Reversible Logical Circuits 9 We consider now a matrix Z−1 as above corresponding to a pair ρ = (ρ1, ..., ρm) ∈ P(m) and s = (s1, ..., sm) ∈ S(m). We shall use Z−1 to define a new shuffling method. By elementary calculations, for any real row vector e = (e1, ..., em) we obtain ( eZ−1 ) i = eρi − ( 1 − δi,si ) eρsi , i = 1, ..., m. (6) Here, δi,j denotes the usual Kronecker’s delta symbol. Inspired from (6) we have: Theorem 2 Let m, q ≥ 2 be natural numbers, ρ = (ρ1, ..., ρm) ∈ P(m) and s = (s1, ..., sm) ∈ S(m). We define the set E(q)m = {en = (en,1, ..., en,m) : n = 0, ..., q m − 1}, where en is the sequence of digits of n ∈ {0, ..., qm − 1} with respect to its q-adic expansion n = m∑ i=1 en,iq i−1. Then the map Tq,ρ,s : E (q) m → E (q) m such that for any i = 1, ..., m Tq,ρ,s ( en ) i = Mod ( en,ρi − ( 1 − δi,si ) en,ρsi , q ) is a bijection. Proof: For any natural numbers m, q ≥ 2 we fix a pair (ρ, s) ∈ P(m)×S(m) and we consider the above operator Tq,ρ,s. From now on we write T = Tq,ρ,s for simplicity. let T(ek) and T(en) be two sequences for some pair (k, n) ∈ {0, ..., qm −1}2. Notice that the elements of ek and en belong in {0, ..., q−1} by definition. Assume that T(ek) = T(en) ⇒ T(ek)i = T(en)i, ∀i = 1, ..., m. (7) If i = 1 in (7), then by recalling the definition of S(m) in (1) we have s1 = 1, so T(ek)1 = T(en)1 ⇒ Mod ( ek,ρ1, q ) = Mod ( en,ρ1, q ) . 248 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 249 10 N. ATREAS AND C. KARANIKAS Hence ek,ρ1 = en,ρ1. If i = 2, then s2 ∈ {0, 1}. For s2 = 2 we immediately obtain ek,ρ2 = en,ρ2. For s2 = 1 we have T(ek)2 = T(en)2 ⇒ Mod ( ek,ρ2 − ek,ρs2 , q ) = Mod ( en,ρ2 − en,ρs2 , q ) ⇒ Mod ( ek,ρ2 − en,ρ1, q ) = Mod ( en,ρ2 − en,ρ1, q ) , where the last equality was derived from the fact that ek,ρ1 = en,ρ1 as we showed above. Hence, either ek,ρ2 − en,ρ1 = en,ρ2 − en,ρ1 ⇒ ek,ρ2 = en,ρ2 or q − (ek,ρ2 − en,ρ1) = q − (en,ρ2 − en,ρ1) ⇒ ek,ρ2 = en,ρ2. Therefore, in any case we obtain ek,ρ2 = en,ρ2. We proceed in the same manner for the remaining values i = 3, ..., m obtain- ing ek,ρi = en,ρi, ∀i = 1, ..., m. Since ρ is a permutation, necessarily ek,i = en,i, ∀i = 1, ..., m and the proof is complete. It is clear that the above operator Tq,ρ,s provides a code for shuffling the elements of the set {0, ..., qm − 1}. Example 6 Let q = 3, ρ = (2, 1), s = (1, 2) and E (3) 2 = {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}. Then by the above definition of Tq,ρ,s we obtain (0, 0) → (0, 0), (0, 1) → (1, 0), (0, 2) → (2, 0), (1, 0) → (0, 1), (1, 1) → (1, 1), (1, 2) → (2, 1), (2, 0) → (0, 2), (2, 1) → (1, 2) and (2, 2) → (2, 2) or Tq,ρ,s : {0, 1, 2, 3, 4, 5, 6, 7, 8} → {0, 3, 6, 1, 4, 7, 2, 5, 8}. 250 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 251 10 N. ATREAS AND C. KARANIKAS Hence ek,ρ1 = en,ρ1. If i = 2, then s2 ∈ {0, 1}. For s2 = 2 we immediately obtain ek,ρ2 = en,ρ2. For s2 = 1 we have T(ek)2 = T(en)2 ⇒ Mod ( ek,ρ2 − ek,ρs2 , q ) = Mod ( en,ρ2 − en,ρs2 , q ) ⇒ Mod ( ek,ρ2 − en,ρ1, q ) = Mod ( en,ρ2 − en,ρ1, q ) , where the last equality was derived from the fact that ek,ρ1 = en,ρ1 as we showed above. Hence, either ek,ρ2 − en,ρ1 = en,ρ2 − en,ρ1 ⇒ ek,ρ2 = en,ρ2 or q − (ek,ρ2 − en,ρ1) = q − (en,ρ2 − en,ρ1) ⇒ ek,ρ2 = en,ρ2. Therefore, in any case we obtain ek,ρ2 = en,ρ2. We proceed in the same manner for the remaining values i = 3, ..., m obtain- ing ek,ρi = en,ρi, ∀i = 1, ..., m. Since ρ is a permutation, necessarily ek,i = en,i, ∀i = 1, ..., m and the proof is complete. It is clear that the above operator Tq,ρ,s provides a code for shuffling the elements of the set {0, ..., qm − 1}. Example 6 Let q = 3, ρ = (2, 1), s = (1, 2) and E (3) 2 = {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}. Then by the above definition of Tq,ρ,s we obtain (0, 0) → (0, 0), (0, 1) → (1, 0), (0, 2) → (2, 0), (1, 0) → (0, 1), (1, 1) → (1, 1), (1, 2) → (2, 1), (2, 0) → (0, 2), (2, 1) → (1, 2) and (2, 2) → (2, 2) or Tq,ρ,s : {0, 1, 2, 3, 4, 5, 6, 7, 8} → {0, 3, 6, 1, 4, 7, 2, 5, 8}. Enumeration and Coding Permutations and Reversible Logical Circuits 11 4 On reversible gates In this section we see that several of the well known reversible gates can be obtained by the bijection maps of theorem 2. First, we modify theorem 2 as follows: Theorem 3 For any natural number m, let (ρ, s) ∈ P(m) × S(m) be as in theorem 2 and Em = {en := (en,1, ..., en,m) : n = {0, ..., 2m − 1}} be the set of all m-bit arrays. Then: (i) The map Tρ,σ : Em → Em such that for any j = 1, ..., m we have Tρ,s(en)j = ∣∣en,ρj − (1 − δj,s(j))en,ρs(j) ∣∣ is a bijection. (ii) For any permutation τ ∈ P(m) we denote by Lτ (en) = (en,τ(1), ..., en,τ(m)) the element of Em obtained from shuffling en by the permutation τ. Then Lτ Tρ,σ : Em → Em is a bijection too. Proof: (i). It is a direct consequence of theorem 2 for q = 2. (ii) It is immediate. Example 7 The Feynman Gate. It is a 2-bit reversible map such that (0, 0) → (0, 0), (0, 1) → (0, 1), (1, 0) → (1, 1) and (1, 1) → (1, 0). According to theorem 3, this gate corresponds to the map Tρ,σ, where ρ = (1, 2) and σ = (1, 1). 250 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 251 12 N. ATREAS AND C. KARANIKAS In a different notation this gate can be uniquely described by a matrix in the class Z2 associated with the above pair (ρ, s) ∈ P(2) × S(2) (see definition 1 or example 4) Zρ,s = ( 1 1 0 1 ) . Also, in a different notation this gate can be described by the following 4 × 4 matrix (by concatenating the corresponding inputs and outputs)   0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0   . Example 8 The Double Feynman Gate. It is a reversible map on the 3 bit binary arrays so that (0, 0, 0) → (0, 0, 0), (1, 0, 0) → (1, 1, 1), (0, 1, 0) → (0, 1, 0), (1, 1, 0) → (1, 0, 1), (0, 0, 1) → (0, 0, 1), (1, 0, 1) → (1, 1, 0), (0, 1, 1) → (0, 1, 1) and (1, 1, 1) → (1, 0, 0). According to theorem 3, this gate corresponds to the map Tρ,σ, where ρ = (1, 2, 3) and σ = (1, 1, 1). In a different notation, this gate can be uniquely described by a matrix in the class Z3 associated with the above pair (ρ, s) ∈ P(3) × S(3) (see the above definition 1 or example 4) Zρ,s =   1 1 1 0 1 0 0 0 1   . Also, in a different notation this gate can be described by the following 8 × 6 matrix (by concatenating the corresponding inputs and outputs)   0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0   . 252 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 253 12 N. ATREAS AND C. KARANIKAS In a different notation this gate can be uniquely described by a matrix in the class Z2 associated with the above pair (ρ, s) ∈ P(2) × S(2) (see definition 1 or example 4) Zρ,s = ( 1 1 0 1 ) . Also, in a different notation this gate can be described by the following 4 × 4 matrix (by concatenating the corresponding inputs and outputs)   0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0   . Example 8 The Double Feynman Gate. It is a reversible map on the 3 bit binary arrays so that (0, 0, 0) → (0, 0, 0), (1, 0, 0) → (1, 1, 1), (0, 1, 0) → (0, 1, 0), (1, 1, 0) → (1, 0, 1), (0, 0, 1) → (0, 0, 1), (1, 0, 1) → (1, 1, 0), (0, 1, 1) → (0, 1, 1) and (1, 1, 1) → (1, 0, 0). According to theorem 3, this gate corresponds to the map Tρ,σ, where ρ = (1, 2, 3) and σ = (1, 1, 1). In a different notation, this gate can be uniquely described by a matrix in the class Z3 associated with the above pair (ρ, s) ∈ P(3) × S(3) (see the above definition 1 or example 4) Zρ,s =   1 1 1 0 1 0 0 0 1   . Also, in a different notation this gate can be described by the following 8 × 6 matrix (by concatenating the corresponding inputs and outputs)   0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0   . Enumeration and Coding Permutations and Reversible Logical Circuits 13 Fig. 1: The set of points {( n, T2,ρ,s(n) ) : n ∈ I8 } for the selection of the pair (ρ, s) as in example 9. Recall that the map T2,ρ,s is a bijection on the set I8 providing a shuffling method for I8. We mention here that the 2-bit Swap gate can be also implemented by the map Tρ,s by selecting ρ = (2, 1) and s = (1, 2). However, the 3-bit Toffoli and Fredkin gates cannot be implemented via Tρ,s. 5 Coding pseudorandom permutations We apply theorem 2 to give by an example a method to code a pseudo- random permutation in P(2m). For any (ρ, s) ∈ P(m) × S(m) and a fixed random permutation r ∈ R(2m) we shuffle the image of T2,ρ,s by the compo- sition map Wr,2T2,ρ,s for some particular selection of r ∈ R(28) (see theorem 1) and we obtain a pseudo-random permutation coded by a triple (ρ, s, r). Example 9 Let ρ = (5, 7, 6, 3, 4, 8, 1, 2) and s = (1, 1, 1, 4, 5, 2, 7, 3). Figure 1 shows how the bijective map T2,ρ,s of theorem 2 shuffles the elements of the set I8 = {0, ..., 28 − 1}. In figure 2 we use a fixed element r ∈ R(28) (see theorem 1) and we shuffle the set I8 by means of the composition operator Wr,2T2ρ,s. In this case, the graph appears to be more ”randomly” distributed than the graph of figure 1. In conclusion, we demonstrated a variety of new enumeration/shuffling methods for the group of permutations. We also proposed a class of bi- jections for sets of natural numbers based on efficient coding methods for 252 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 253 14 N. ATREAS AND C. KARANIKAS Fig. 2: The set of points { (n, Wr,2T2,ρ,s(n)) : n ∈ I8 } for some r ∈ R(28) and (ρ, s) as in example 9. sparse boolean matrices. We also discussed possible connections of the shuf- fling problem with the random permutation generation problem. According to [8, 9], any permutation in P(m) can be almost uniformly randomly dis- tributed using mlog(m)/2. This observation may be important for establish- ing a connection between our shuffling method and the random permutation generation problem in future.We believe that this direction is very promising. References [1] 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. [2] 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. [3] ——, “Multiscale haar unitary matrices with the corresponding riesz products and a characterization of cantor-type languages,” J. Fourier Anal. Appl., vol. 13, no. 2, pp. 197–210, 2007. [4] ——, “Haar-type orthonormal systems, data presentation as riesz products and a recognition on symbolic sequences,” Contemporary Math., vol. 451, pp. 1–9, 2008. [5] ——, “Discrete type riesz products,” in Walsh and Dyadic Analysis, 2008, pp. 137–143. 254 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 255 14 N. ATREAS AND C. KARANIKAS Fig. 2: The set of points { (n, Wr,2T2,ρ,s(n)) : n ∈ I8 } for some r ∈ R(28) and (ρ, s) as in example 9. sparse boolean matrices. We also discussed possible connections of the shuf- fling problem with the random permutation generation problem. According to [8, 9], any permutation in P(m) can be almost uniformly randomly dis- tributed using mlog(m)/2. This observation may be important for establish- ing a connection between our shuffling method and the random permutation generation problem in future.We believe that this direction is very promising. References [1] 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. [2] 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. [3] ——, “Multiscale haar unitary matrices with the corresponding riesz products and a characterization of cantor-type languages,” J. Fourier Anal. Appl., vol. 13, no. 2, pp. 197–210, 2007. [4] ——, “Haar-type orthonormal systems, data presentation as riesz products and a recognition on symbolic sequences,” Contemporary Math., vol. 451, pp. 1–9, 2008. [5] ——, “Discrete type riesz products,” in Walsh and Dyadic Analysis, 2008, pp. 137–143. Enumeration and Coding Permutations and Reversible Logical Circuits 15 [6] N. Atreas, C. Karanikas, and P. Polychronidou, “A class of sparse unimodu- lar matrices generating multiresolution and sampling analysis for data of any length,” SIAM J. Matrix Anal. Appl.,, vol. 30, no. 1, pp. 312–323, 2008. [7] D. H. Lehmer, “Teaching combinatorial tricks to a computer,” in Proc. Symbos. Appl. Math. Combinatorial Analysis, vol. 10, 1960, pp. 179–193. [8] 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. [9] P. Diaconis and M. Shahshahani, “Generating a random permutation with ran- dom transposition,” Z. Wahr. verw. Gebeite, vol. 57, no. 2, pp. 159–17, 1981. 254 C. KARANIKAS, N. ATREAS Enumeration and Coding Permutations and Reversible Logical Circuits 255