American Institute of Mathematical Sciences

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

Cycle structure of permutation functions over finite fields and their applications

Amin Sakzad 1, , Mohammad-Reza Sadeghi 1, and  Daniel Panario 2,

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.
Keywords: Interleavers and permutation functions over finite fields..
Mathematics Subject Classification: Primary: 12E20, 12E05, 94B60; Secondary: 94A05, 94A24, 94B1.
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.  Google Scholar

[2]

C. Baker, A. Bonato and P. Kergin, Skolem arrays and Skolem labellings of ladder graphs, Ars Combin., 63 (2002), 97-107.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[12]

S. Crozier, New high-spread high-distance interleavers for turbo codes, in "Proc. 20th Biennial Symp. Communications,'' (2000), 3-7. Google Scholar

[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. Google Scholar

[14]

A. R. Eckler, The construction of missile guidance codes resistant to random interference, Bell System Tech. J., 39 (1960), 973-994.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

R. Lidl and G. L. Mullen, Cycle structure of Dickson permutation polynomials, Math. J. Okayama Univ., 33 (1991), 1-11.  Google Scholar

[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.  Google Scholar

[19]

R. Lidl and H. Niederreiter, "Finite Fields,'' Cambridge Univ. Press, 1997.  Google Scholar

[20]

S. Lin and D. J. Costello, "Error Control Coding Fundamentals and Application,'' 2nd edition, Pearson Prentice Hall, New Jersey, 2003. Google Scholar

[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.  Google Scholar

[22]

B. Moision and M. Klimesh, Some observations on permutation polynomials,, JPL, ().   Google Scholar

[23]

L. Rédei, Uber eindeuting umkehrbare polynome in endlichen kopern,, Acta Sci. Math., 11 (): 1946.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2]

C. Baker, A. Bonato and P. Kergin, Skolem arrays and Skolem labellings of ladder graphs, Ars Combin., 63 (2002), 97-107.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[12]

S. Crozier, New high-spread high-distance interleavers for turbo codes, in "Proc. 20th Biennial Symp. Communications,'' (2000), 3-7. Google Scholar

[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. Google Scholar

[14]

A. R. Eckler, The construction of missile guidance codes resistant to random interference, Bell System Tech. J., 39 (1960), 973-994.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

R. Lidl and G. L. Mullen, Cycle structure of Dickson permutation polynomials, Math. J. Okayama Univ., 33 (1991), 1-11.  Google Scholar

[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.  Google Scholar

[19]

R. Lidl and H. Niederreiter, "Finite Fields,'' Cambridge Univ. Press, 1997.  Google Scholar

[20]

S. Lin and D. J. Costello, "Error Control Coding Fundamentals and Application,'' 2nd edition, Pearson Prentice Hall, New Jersey, 2003. Google Scholar

[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.  Google Scholar

[22]

B. Moision and M. Klimesh, Some observations on permutation polynomials,, JPL, ().   Google Scholar

[23]

L. Rédei, Uber eindeuting umkehrbare polynome in endlichen kopern,, Acta Sci. Math., 11 (): 1946.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Nian Li, Qiaoyu Hu. A conjecture on permutation trinomials over finite fields of characteristic two. Advances in Mathematics of Communications, 2019, 13 (3) : 505-512. doi: 10.3934/amc.2019031
[2]

Lei Lei, Wenli Ren, Cuiling Fan. The differential spectrum of a class of power functions over finite fields. Advances in Mathematics of Communications, 2021, 15 (3) : 525-537. doi: 10.3934/amc.2020080
[3]

Stefania Fanali, Massimo Giulietti, Irene Platoni. On maximal curves over finite fields of small order. Advances in Mathematics of Communications, 2012, 6 (1) : 107-120. doi: 10.3934/amc.2012.6.107
[4]

Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459
[5]

Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203-227. doi: 10.3934/amc.2012.6.203
[6]

Francis N. Castro, Carlos Corrada-Bravo, Natalia Pacheco-Tallaj, Ivelisse Rubio. Explicit formulas for monomial involutions over finite fields. Advances in Mathematics of Communications, 2017, 11 (2) : 301-306. doi: 10.3934/amc.2017022
[7]

Fatma-Zohra Benahmed, Kenza Guenda, Aicha Batoul, Thomas Aaron Gulliver. Some new constructions of isodual and LCD codes over finite fields. Advances in Mathematics of Communications, 2019, 13 (2) : 281-296. doi: 10.3934/amc.2019019
[8]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[9]

Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101
[10]

Liren Lin, Hongwei Liu, Bocong Chen. Existence conditions for self-orthogonal negacyclic codes over finite fields. Advances in Mathematics of Communications, 2015, 9 (1) : 1-7. doi: 10.3934/amc.2015.9.1
[11]

László Mérai, Igor E. Shparlinski. Unlikely intersections over finite fields: Polynomial orbits in small subgroups. Discrete & Continuous Dynamical Systems, 2020, 40 (2) : 1065-1073. doi: 10.3934/dcds.2020070
[12]

Uwe Helmke, Jens Jordan, Julia Lieb. Probability estimates for reachability of linear systems defined over finite fields. Advances in Mathematics of Communications, 2016, 10 (1) : 63-78. doi: 10.3934/amc.2016.10.63
[13]

David Grant, Mahesh K. Varanasi. Duality theory for space-time codes over finite fields. Advances in Mathematics of Communications, 2008, 2 (1) : 35-54. doi: 10.3934/amc.2008.2.35
[14]

Nguyen Thi Bach Kim. Finite algorithm for minimizing the product of two linear functions over a polyhedron. Journal of Industrial & Management Optimization, 2007, 3 (3) : 481-487. doi: 10.3934/jimo.2007.3.481
[15]

Amita Sahni, Poonam Trama Sehgal. Enumeration of self-dual and self-orthogonal negacyclic codes over finite fields. Advances in Mathematics of Communications, 2015, 9 (4) : 437-447. doi: 10.3934/amc.2015.9.437
[16]

David Grant, Mahesh K. Varanasi. The equivalence of space-time codes and codes defined over finite fields and Galois rings. Advances in Mathematics of Communications, 2008, 2 (2) : 131-145. doi: 10.3934/amc.2008.2.131
[17]

Marko Budišić, Stefan Siegmund, Doan Thai Son, Igor Mezić. Mesochronic classification of trajectories in incompressible 3D vector fields over finite times. Discrete & Continuous Dynamical Systems - S, 2016, 9 (4) : 923-958. doi: 10.3934/dcdss.2016035
[18]

Ekkasit Sangwisut, Somphong Jitman, Patanee Udomkavanich. Constacyclic and quasi-twisted Hermitian self-dual codes over finite fields. Advances in Mathematics of Communications, 2017, 11 (3) : 595-613. doi: 10.3934/amc.2017045
[19]

Josep M. Miret, Jordi Pujolàs, Anna Rio. Explicit 2-power torsion of genus 2 curves over finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 155-168. doi: 10.3934/amc.2010.4.155
[20]

Michael Braun, Michael Kiermaier, Reinhard Laue. New 2-designs over finite fields from derived and residual designs. Advances in Mathematics of Communications, 2019, 13 (1) : 165-170. doi: 10.3934/amc.2019010

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (101)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences