Year 2017, Volume 4 , Issue 3, Pages 261 - 269 2017-09-15

On the equivalence of cyclic and quasi-cyclic codes over finite fields

Kenza GUENDA [1] , T. Aaron GULLİVER [2]


This paper studies the equivalence problem for cyclic codes of length $p^r$ and quasi-cyclic codes of length $p^rl$. In particular, we generalize the results of Huffman, Job, and Pless (J. Combin. Theory. A, 62, 183--215, 1993), who considered the special case $p^2$. This is achieved by explicitly giving the permutations by which two cyclic codes of prime power length are equivalent. This allows us to obtain an algorithm which solves the problem of equivalency for cyclic codes of length $p^r$ in polynomial time. Further, we characterize the set by which two quasi-cyclic codes of length $p^rl$ can be equivalent, and prove that the affine group is one of its subsets.
Cyclic code, Quasi-cyclic code, Equivalence, Automorphism, Permutation
  • [1] B. Alspach, T. D. Parson, Isomorphism of circulant graphs and digraphs, Discrete Math. 25(2) (1979) 97–108.
  • [2] L. Babai, P. Codenotti, J. A. Groshow, Y. Qiao, Code equivalence and group isomorphism, in Proc. ACM-SIAM Symp. on Discr. Algorithms, San Francisco, CA, (2011) 1395–1408.
  • [3] N. Brand, Polynomial isomorphisms of combinatorial objects, Graphs Combin. 7(1) (1991) 7–14.
  • [4] K. Guenda, T. A. Gulliver, On the permutation groups of cyclic codes, J. Algebraic Combin. 38(1) (2013) 197–208.
  • [5] M. Hall, Jr., The Theory of Groups, MacMillan, New York, 1970.
  • [6] W. C. Huffman, V. Job, V. Pless, Multipliers and generalized multipliers of cyclic objects and cyclic codes, J. Combin. Theory Ser. A 62(2) (1993) 183–215.
  • [7] S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes III: Generator theory, IEEE Trans. Inform. Theory 51(7) (2005) 2692–2700.
  • [8] R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report 42-44, (1978) 114–116.
  • [9] A. Otmani, J.–P. Tillich, L. Dallot, Cryptanalysis of a McEliece cryptosystem based on quasi-cyclic LDPC codes, in Proc. Conf. on Symbolic Computation and Crypt., Beijing, China, (2008) 69–81.
  • [10] P. P. Palfy, Isomorphism problem for relational structures with a cyclic automorphism, European J. Combin. 8(1) (1987) 35–43.
  • [11] N. Sendrier, Finding the permutation between equivalent linear codes: The support splitting algorithm, IEEE Trans. Inform. Theory 46(4) (2000) 1193–1203.
  • [12] N. Sendrier, D.E. Simos, How easy is code equivalence over $F_q$?, in Proc. Int. Workshop on Coding Theory and Crypt., Bergen, Norway, 2013.
  • [13] N. Sendrier, D. E. Simos, The hardness of code equivalence over $F_q$ and its application to codebased cryptography, in P. Gaborit (Ed.), Post-Quantum Cryptography, Springer Lecture Notes in Computer Science 7932, Limoges, France (2013) 203–216.
Subjects Engineering
Journal Section Articles
Authors

Orcid: 0000-0002-1482-7565
Author: Kenza GUENDA

Orcid: 0000-0001-9919-0323
Author: T. Aaron GULLİVER

Dates

Publication Date : September 15, 2017

Bibtex @research article { jacodesmath327375, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2017}, volume = {4}, pages = {261 - 269}, doi = {10.13069/jacodesmath.327375}, title = {On the equivalence of cyclic and quasi-cyclic codes over finite fields}, key = {cite}, author = {Guenda, Kenza and Gulli̇ver, T. Aaron} }
APA Guenda, K , Gulli̇ver, T . (2017). On the equivalence of cyclic and quasi-cyclic codes over finite fields . Journal of Algebra Combinatorics Discrete Structures and Applications , 4 (3) , 261-269 . DOI: 10.13069/jacodesmath.327375
MLA Guenda, K , Gulli̇ver, T . "On the equivalence of cyclic and quasi-cyclic codes over finite fields" . Journal of Algebra Combinatorics Discrete Structures and Applications 4 (2017 ): 261-269 <https://dergipark.org.tr/en/pub/jacodesmath/issue/30328/327375>
Chicago Guenda, K , Gulli̇ver, T . "On the equivalence of cyclic and quasi-cyclic codes over finite fields". Journal of Algebra Combinatorics Discrete Structures and Applications 4 (2017 ): 261-269
RIS TY - JOUR T1 - On the equivalence of cyclic and quasi-cyclic codes over finite fields AU - Kenza Guenda , T. Aaron Gulli̇ver Y1 - 2017 PY - 2017 N1 - doi: 10.13069/jacodesmath.327375 DO - 10.13069/jacodesmath.327375 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 261 EP - 269 VL - 4 IS - 3 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.327375 UR - https://doi.org/10.13069/jacodesmath.327375 Y2 - 2017 ER -
EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications On the equivalence of cyclic and quasi-cyclic codes over finite fields %A Kenza Guenda , T. Aaron Gulli̇ver %T On the equivalence of cyclic and quasi-cyclic codes over finite fields %D 2017 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 4 %N 3 %R doi: 10.13069/jacodesmath.327375 %U 10.13069/jacodesmath.327375
ISNAD Guenda, Kenza , Gulli̇ver, T. Aaron . "On the equivalence of cyclic and quasi-cyclic codes over finite fields". Journal of Algebra Combinatorics Discrete Structures and Applications 4 / 3 (September 2017): 261-269 . https://doi.org/10.13069/jacodesmath.327375
AMA Guenda K , Gulli̇ver T . On the equivalence of cyclic and quasi-cyclic codes over finite fields. Journal of Algebra Combinatorics Discrete Structures and Applications. 2017; 4(3): 261-269.
Vancouver Guenda K , Gulli̇ver T . On the equivalence of cyclic and quasi-cyclic codes over finite fields. Journal of Algebra Combinatorics Discrete Structures and Applications. 2017; 4(3): 261-269.