# American Institute of Mathematical Sciences

August  2012, 6(3): 347-361. doi: 10.3934/amc.2012.6.347

## Cycle structure of permutation functions over finite fields and their applications

 1 Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran, Iran 2 School of Mathematics and Statistics, Carleton University, Ottawa, Canada

Received  November 2011 Revised  May 2012 Published  August 2012

In this work we establish some new interleavers based on permutation functions. The inverses of these interleavers are known over a finite field $\mathbb F_q$. For the first time Möbius and Rédei functions are used to give new deterministic interleavers. Furthermore we employ Skolem sequences in order to find new interleavers with known cycle structure. In the case of Rédei functions an exact formula for the inverse function is derived. The cycle structure of Rédei functions is also investigated. The self-inverse and non-self-inverse versions of these permutation functions can be used to construct new interleavers.
Citation: Amin Sakzad, Mohammad-Reza Sadeghi, Daniel Panario. Cycle structure of permutation functions over finite fields and their applications. Advances in Mathematics of Communications, 2012, 6 (3) : 347-361. doi: 10.3934/amc.2012.6.347
##### References:
 [1] S. Ahmad, Cycle structure of automorphisms of finite cyclic groups, J. Comb. Theory, 6 (1969), 370-374. doi: 10.1016/S0021-9800(69)80032-3. [2] C. Baker, A. Bonato and P. Kergin, Skolem arrays and Skolem labellings of ladder graphs, Ars Combin., 63 (2002), 97-107. [3] C. Berrou, A. Glavieux and P. Thitimajshima, Near Shannon limit error-correcting coding and decoding: turbo codes, in "Proc. International Conference on Communications,'' (1993), 1064-1070. [4] J. Boutros and G. Zemor, On quasi-cyclic interleavers for parallel turbo codes, IEEE Trans. Inform. Theory, 52 (2006), 1732-1739. doi: 10.1109/TIT.2006.871061. [5] G. Caire, G. Taricco and E. Biglieri, Bit-interleaved coded modulation, IEEE Trans. Inform. Theory, 44 (1998), 927-946. doi: 10.1109/18.669123. [6] L. Carlitz, A note on permutation functions over a finite field, Duke Math. J., 29 (1962), 325-332. doi: 10.1215/S0012-7094-62-02931-9. [7] A. Cesmelioglu, W. Meidl and A. Topuzoglu, On the cycle structure of permutation polynomials, Finite Fields Appl., 14 (2008), 593-614. doi: 10.1016/j.ffa.2007.08.003. [8] M. Cheng, M. Nakashima, J. Hamkins, B. Moision and M. Barsoum, A decoder architecture for high-speed free-space laser communications, Proc. SPIE, 5712 (2005), 174-185. doi: 10.1117/12.591043. [9] C. J. Colbourn and J. H. Dinitz, "Handbook of Combinatorial Designs,'' 2nd edition, Chapman & Hall/CRC, Boca Raton, FL, 2006. doi: 10.1201/9781420010541. [10] C. Corrada and I. Rubio, Deterministic interleavers for turbo codes with random-like performance and simple implementation, in "Proc. of the 3rd Int. Symp. on Turbo Codes and Related Topics,'' (2003), 555-558. [11] C. Corrada and I. Rubio, Algebraic construction of interleavers using permutation monomials, in "Proc. of the 2004 IEEE Int. Conf. on Communications,'' (2004), 911-915. [12] S. Crozier, New high-spread high-distance interleavers for turbo codes, in "Proc. 20th Biennial Symp. Communications,'' (2000), 3-7. [13] S. Crozier and P. Guinand, Distance upper bounds and true minimum distance results for turbo-codes designed with DRP interleavers, Ann. Telecommun., 60 (2005), 10-28. [14] A. R. Eckler, The construction of missile guidance codes resistant to random interference, Bell System Tech. J., 39 (1960), 973-994. [15] S. A. Eldin, N. Shalaby and F. Al-Thukair, Construction of Skolem sequences, Int. J. Comp. Math., 70 (1998), 333-345. doi: 10.1080/00207169808804756. [16] N. Francetić and E. Mendelsohn, A survey of Skolem-type sequences and Rosa's use of them, Math. Slovaca, 59 (2009), 39-76. doi: 10.2478/s12175-008-0110-3. [17] R. Lidl and G. L. Mullen, Cycle structure of Dickson permutation polynomials, Math. J. Okayama Univ., 33 (1991), 1-11. [18] R. Lidl and G. L. Mullen, When does a polynomial over a finite field permute the elements of the field?, Amer. Math. Monthly, 100 (1993), 71-74. doi: 10.2307/2324822. [19] R. Lidl and H. Niederreiter, "Finite Fields,'' Cambridge Univ. Press, 1997. [20] S. Lin and D. J. Costello, "Error Control Coding Fundamentals and Application,'' 2nd edition, Pearson Prentice Hall, New Jersey, 2003. [21] V. Linek and Z. Jiang, Hooked $k$-extended Skolem sequences, Discrete Math., 196 (1999), 229-238. doi: 10.1016/S0012-365X(98)00202-7. [22] B. Moision and M. Klimesh, Some observations on permutation polynomials,, JPL, (). [23] L. Rédei, Uber eindeuting umkehrbare polynome in endlichen kopern,, Acta Sci. Math., 11 (): 1946. [24] I. Rubio and C. Corrada, Cyclic decomposition of permutations of finite fields obtained using monomials, in "7th Int. Conf. on Finite Fields and their Applications,'' Springer-Verlag, (2004), 254-261. [25] I. Rubio, G. L. Mullen, C. Corrada and F. Castro, Dickson permutation polynomials that decompose in cycles of the same length, in "8th Int. Conf. on Finite Fields and their Applications,'' (2008), 229-239. [26] J. Ryu and O. Y. Takeshita, On quadratic inverses for quadratic permutation polynomials over integer rings, IEEE Trans. Inform. Theory, 52 (2006), 1254-1260. doi: 10.1109/TIT.2005.864442. [27] A. Sakzad, D. Panario, M-R. Sadeghi and N. Eshghi, Self-inverse interleavers based on permutation functions for turbo codes, in "Proc. of 48th Ann. Allerton Conf. Commun. Control, and Computing,'' (2010), 22-28. [28] A. Sakzad and M.-R. Sadeghi, On cycle-free lattices with high rate label codes, Adv. Math. Commun., 4 (2010), 441-452. doi: 10.3934/amc.2010.4.441. [29] A. Sakzad, M-R. Sadeghi and D. Panario, Construction of turbo lattices, in "Proc. of 48th Ann. Allerton Conf. Commun. Control, and Computing,'' (2010), 14-21. [30] J. Sun and O. Y. Takeshita, Interleavers for turbo codes using permutation polynomials over integer rings, IEEE Trans. Inform. Theory, 51 (2005), 101-119. doi: 10.1109/TIT.2004.839478. [31] O. Y. Takeshita, Permutation polynomials interleavers: an algebraic geometric perspective, IEEE Trans. Inform. Theory, 53 (2007), 2116-2132. doi: 10.1109/TIT.2007.896870. [32] O. Y. Takeshita and D. J. Costello, New deterministic interleaver designs for turbo codes, IEEE Trans. Inform. Theory, 46 (2000), 1988-2006. doi: 10.1109/18.868474. [33] D. V. Truhachev, M. Lentmaier and K. S. Zigangirov, Some results concerning design and decoding of turbo-codes, Probl. Inform. Trans., 37 (2001), 190-205. doi: 10.1023/A:1013821922527. [34] B. Vucetic, Y. Li, L. C. Perez and F. Jiang, Recent advances in turbo code design and theory, Proc. IEEE, 95 (2007), 1323-1344. doi: 10.1109/JPROC.2007.897975.

show all references

##### References:
 [1] S. Ahmad, Cycle structure of automorphisms of finite cyclic groups, J. Comb. Theory, 6 (1969), 370-374. doi: 10.1016/S0021-9800(69)80032-3. [2] C. Baker, A. Bonato and P. Kergin, Skolem arrays and Skolem labellings of ladder graphs, Ars Combin., 63 (2002), 97-107. [3] C. Berrou, A. Glavieux and P. Thitimajshima, Near Shannon limit error-correcting coding and decoding: turbo codes, in "Proc. International Conference on Communications,'' (1993), 1064-1070. [4] J. Boutros and G. Zemor, On quasi-cyclic interleavers for parallel turbo codes, IEEE Trans. Inform. Theory, 52 (2006), 1732-1739. doi: 10.1109/TIT.2006.871061. [5] G. Caire, G. Taricco and E. Biglieri, Bit-interleaved coded modulation, IEEE Trans. Inform. Theory, 44 (1998), 927-946. doi: 10.1109/18.669123. [6] L. Carlitz, A note on permutation functions over a finite field, Duke Math. J., 29 (1962), 325-332. doi: 10.1215/S0012-7094-62-02931-9. [7] A. Cesmelioglu, W. Meidl and A. Topuzoglu, On the cycle structure of permutation polynomials, Finite Fields Appl., 14 (2008), 593-614. doi: 10.1016/j.ffa.2007.08.003. [8] M. Cheng, M. Nakashima, J. Hamkins, B. Moision and M. Barsoum, A decoder architecture for high-speed free-space laser communications, Proc. SPIE, 5712 (2005), 174-185. doi: 10.1117/12.591043. [9] C. J. Colbourn and J. H. Dinitz, "Handbook of Combinatorial Designs,'' 2nd edition, Chapman & Hall/CRC, Boca Raton, FL, 2006. doi: 10.1201/9781420010541. [10] C. Corrada and I. Rubio, Deterministic interleavers for turbo codes with random-like performance and simple implementation, in "Proc. of the 3rd Int. Symp. on Turbo Codes and Related Topics,'' (2003), 555-558. [11] C. Corrada and I. Rubio, Algebraic construction of interleavers using permutation monomials, in "Proc. of the 2004 IEEE Int. Conf. on Communications,'' (2004), 911-915. [12] S. Crozier, New high-spread high-distance interleavers for turbo codes, in "Proc. 20th Biennial Symp. Communications,'' (2000), 3-7. [13] S. Crozier and P. Guinand, Distance upper bounds and true minimum distance results for turbo-codes designed with DRP interleavers, Ann. Telecommun., 60 (2005), 10-28. [14] A. R. Eckler, The construction of missile guidance codes resistant to random interference, Bell System Tech. J., 39 (1960), 973-994. [15] S. A. Eldin, N. Shalaby and F. Al-Thukair, Construction of Skolem sequences, Int. J. Comp. Math., 70 (1998), 333-345. doi: 10.1080/00207169808804756. [16] N. Francetić and E. Mendelsohn, A survey of Skolem-type sequences and Rosa's use of them, Math. Slovaca, 59 (2009), 39-76. doi: 10.2478/s12175-008-0110-3. [17] R. Lidl and G. L. Mullen, Cycle structure of Dickson permutation polynomials, Math. J. Okayama Univ., 33 (1991), 1-11. [18] R. Lidl and G. L. Mullen, When does a polynomial over a finite field permute the elements of the field?, Amer. Math. Monthly, 100 (1993), 71-74. doi: 10.2307/2324822. [19] R. Lidl and H. Niederreiter, "Finite Fields,'' Cambridge Univ. Press, 1997. [20] S. Lin and D. J. Costello, "Error Control Coding Fundamentals and Application,'' 2nd edition, Pearson Prentice Hall, New Jersey, 2003. [21] V. Linek and Z. Jiang, Hooked $k$-extended Skolem sequences, Discrete Math., 196 (1999), 229-238. doi: 10.1016/S0012-365X(98)00202-7. [22] B. Moision and M. Klimesh, Some observations on permutation polynomials,, JPL, (). [23] L. Rédei, Uber eindeuting umkehrbare polynome in endlichen kopern,, Acta Sci. Math., 11 (): 1946. [24] I. Rubio and C. Corrada, Cyclic decomposition of permutations of finite fields obtained using monomials, in "7th Int. Conf. on Finite Fields and their Applications,'' Springer-Verlag, (2004), 254-261. [25] I. Rubio, G. L. Mullen, C. Corrada and F. Castro, Dickson permutation polynomials that decompose in cycles of the same length, in "8th Int. Conf. on Finite Fields and their Applications,'' (2008), 229-239. [26] J. Ryu and O. Y. Takeshita, On quadratic inverses for quadratic permutation polynomials over integer rings, IEEE Trans. Inform. Theory, 52 (2006), 1254-1260. doi: 10.1109/TIT.2005.864442. [27] A. Sakzad, D. Panario, M-R. Sadeghi and N. Eshghi, Self-inverse interleavers based on permutation functions for turbo codes, in "Proc. of 48th Ann. Allerton Conf. Commun. Control, and Computing,'' (2010), 22-28. [28] A. Sakzad and M.-R. Sadeghi, On cycle-free lattices with high rate label codes, Adv. Math. Commun., 4 (2010), 441-452. doi: 10.3934/amc.2010.4.441. [29] A. Sakzad, M-R. Sadeghi and D. Panario, Construction of turbo lattices, in "Proc. of 48th Ann. Allerton Conf. Commun. Control, and Computing,'' (2010), 14-21. [30] J. Sun and O. Y. Takeshita, Interleavers for turbo codes using permutation polynomials over integer rings, IEEE Trans. Inform. Theory, 51 (2005), 101-119. doi: 10.1109/TIT.2004.839478. [31] O. Y. Takeshita, Permutation polynomials interleavers: an algebraic geometric perspective, IEEE Trans. Inform. Theory, 53 (2007), 2116-2132. doi: 10.1109/TIT.2007.896870. [32] O. Y. Takeshita and D. J. Costello, New deterministic interleaver designs for turbo codes, IEEE Trans. Inform. Theory, 46 (2000), 1988-2006. doi: 10.1109/18.868474. [33] D. V. Truhachev, M. Lentmaier and K. S. Zigangirov, Some results concerning design and decoding of turbo-codes, Probl. Inform. Trans., 37 (2001), 190-205. doi: 10.1023/A:1013821922527. [34] B. Vucetic, Y. Li, L. C. Perez and F. Jiang, Recent advances in turbo code design and theory, Proc. IEEE, 95 (2007), 1323-1344. doi: 10.1109/JPROC.2007.897975.

2020 Impact Factor: 0.935