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

[3]

C. Berrou, A. Glavieux and P. Thitimajshima, Near Shannon limit error-correcting coding and decoding: turbo codes,, in, (1993), 1064.   Google Scholar

[4]

J. Boutros and G. Zemor, On quasi-cyclic interleavers for parallel turbo codes,, IEEE Trans. Inform. Theory, 52 (2006), 1732.  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.  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.  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.  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.  doi: 10.1117/12.591043.  Google Scholar

[9]

C. J. Colbourn and J. H. Dinitz, "Handbook of Combinatorial Designs,'' 2nd edition,, Chapman & Hall/CRC, (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, (2003), 555.   Google Scholar

[11]

C. Corrada and I. Rubio, Algebraic construction of interleavers using permutation monomials,, in, (2004), 911.   Google Scholar

[12]

S. Crozier, New high-spread high-distance interleavers for turbo codes,, in, (2000), 3.   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.   Google Scholar

[14]

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

[15]

S. A. Eldin, N. Shalaby and F. Al-Thukair, Construction of Skolem sequences,, Int. J. Comp. Math., 70 (1998), 333.  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.  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.   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.  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, (2003).   Google Scholar

[21]

V. Linek and Z. Jiang, Hooked $k$-extended Skolem sequences,, Discrete Math., 196 (1999), 229.  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, (2004), 254.   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, (2008), 229.   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.  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, (2010), 22.   Google Scholar

[28]

A. Sakzad and M.-R. Sadeghi, On cycle-free lattices with high rate label codes,, Adv. Math. Commun., 4 (2010), 441.  doi: 10.3934/amc.2010.4.441.  Google Scholar

[29]

A. Sakzad, M-R. Sadeghi and D. Panario, Construction of turbo lattices,, in, (2010), 14.   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.  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.  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.  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.  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.  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.  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.   Google Scholar

[3]

C. Berrou, A. Glavieux and P. Thitimajshima, Near Shannon limit error-correcting coding and decoding: turbo codes,, in, (1993), 1064.   Google Scholar

[4]

J. Boutros and G. Zemor, On quasi-cyclic interleavers for parallel turbo codes,, IEEE Trans. Inform. Theory, 52 (2006), 1732.  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.  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.  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.  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.  doi: 10.1117/12.591043.  Google Scholar

[9]

C. J. Colbourn and J. H. Dinitz, "Handbook of Combinatorial Designs,'' 2nd edition,, Chapman & Hall/CRC, (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, (2003), 555.   Google Scholar

[11]

C. Corrada and I. Rubio, Algebraic construction of interleavers using permutation monomials,, in, (2004), 911.   Google Scholar

[12]

S. Crozier, New high-spread high-distance interleavers for turbo codes,, in, (2000), 3.   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.   Google Scholar

[14]

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

[15]

S. A. Eldin, N. Shalaby and F. Al-Thukair, Construction of Skolem sequences,, Int. J. Comp. Math., 70 (1998), 333.  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.  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.   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.  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, (2003).   Google Scholar

[21]

V. Linek and Z. Jiang, Hooked $k$-extended Skolem sequences,, Discrete Math., 196 (1999), 229.  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, (2004), 254.   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, (2008), 229.   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.  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, (2010), 22.   Google Scholar

[28]

A. Sakzad and M.-R. Sadeghi, On cycle-free lattices with high rate label codes,, Adv. Math. Commun., 4 (2010), 441.  doi: 10.3934/amc.2010.4.441.  Google Scholar

[29]

A. Sakzad, M-R. Sadeghi and D. Panario, Construction of turbo lattices,, in, (2010), 14.   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.  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.  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.  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.  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.  doi: 10.1109/JPROC.2007.897975.  Google Scholar

[1]

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
[2]

Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020121
[3]

Wenjun Liu, Yukun Xiao, Xiaoqing Yue. Classification of finite irreducible conformal modules over Lie conformal algebra $ \mathcal{W}(a, b, r) $. Electronic Research Archive, , () : -. doi: 10.3934/era.2020123
[4]

Jianfeng Huang, Haihua Liang. Limit cycles of planar system defined by the sum of two quasi-homogeneous vector fields. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 861-873. doi: 10.3934/dcdsb.2020145
[5]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069
[6]

Andreas Koutsogiannis. Multiple ergodic averages for tempered functions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1177-1205. doi: 10.3934/dcds.2020314
[7]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[8]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[9]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098
[10]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006
[11]

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378
[12]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178
[13]

Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020122
[14]

Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095
[15]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117
[16]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[17]

Tahir Aliyev Azeroğlu, Bülent Nafi Örnek, Timur Düzenli. Some results on the behaviour of transfer functions at the right half plane. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020106
[18]

Meenakshi Rana, Shruti Sharma. Combinatorics of some fifth and sixth order mock theta functions. Electronic Research Archive, 2021, 29 (1) : 1803-1818. doi: 10.3934/era.2020092
[19]

Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331
[20]

Kalikinkar Mandal, Guang Gong. On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences