Recent progress on weight distributions of cyclic codes over finite fields

Abstract

Cyclic codes are an interesting type of linear codes and have wide applications in communication and storage systems due to their efficient encoding and decoding algorithms. In coding theory it is often desirable to know the weight distribution of a cyclic code to estimate the error correcting capability and error probability. In this paper, we present the recent progress on the weight distributions of cyclic codes over finite fields, which had been determined by exponential sums. The cyclic codes with few weights which are very useful are discussed and their existence conditions are listed. Furthermore, we discuss the more general case of constacyclic codes and give some equivalences to characterize their weight distributions.

Keywords

• Linear codes, Weight distribution, Cyclic codes, Finite fields, Gauss periods, Gauss sums, Exponential sums,Quadratic forms

References

1. N. Aydin, I. Siap, D. K. Ray-Chaudhuri, The structure of 1-generator quasi-twisted codes and new
2. linear codes, Designs Codes Cryptogr. 24, 313-326, 2001.
3. A. Batoul, K. Guenda, T. A. Gulliver, On self-dual cyclic codes over finite chain rings, Designs
4. Codes Cryptogr. 70, 347-358, 2014.
5. E. R. Berlekamp, Negacyclic Codes for the Lee Metric, Proceedings of the Conference on Combi
6. natorial Mathematics and Its Applications, Chapel Hill, N.C., University of North Carolina Press, 298-316, 1968.
7. E. R. Berlekamp, Algebraic Coding Theory, revised 1984 edition, Aegean Park Press, 1984.
8. S. D. Berman, Semisimple cyclic and Abelian codes. II, Kibernetika (Kiev) 3 (1967), 21-30 (Russian).

9. English translation: Cybernetics 3, 17-23,1967.
10. B. C. Berndt, R. J. Evans, K. S. Williams, Gauss and Jacobi Sums, Wiley-Interscience Publication, 1998.
11. C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon limit error-correcting coding and
12. decoding: Turbo-codes, 1993.
13. A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. A. Kohnert, A. Wassermann, Error Correcting
14. Linear Codes: Classification by Isometry and Applications, Springer, Berlin, 2006.
15. N. Boston and G. McGuire, The weight distribution of cyclic codes with two zeros and zeta functions,
16. J. Symbolic Comput., 45(7), 723-733, 2010.
17. A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs, Berlin, Germany: Springer- Verlag, 18, 1989, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)].
18. A. R. Calderbank and J. M. Goethals, Three-weight codes and association schemes, Philips J. Res., 39, 143-152, 1984.
19. R. Calderbank and W. M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18,
20. A. Canteaut, P. Charpin, and H. Dobbertin, Weight divisibility of cyclic codes, highly nonlinear functions on F2mand crosscorrelation of maximum-length sequences, SIAM J. Discrete Math., 13(1), 105-138, 2000.
21. C. Carlet, P. Charpin, and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr. 15(2), 125-156, 1998.
22. C. Carlet and C. Ding, Highly nonlinear mappings, J. Complexity, 20(2), 205-244, 2004.
23. G. Castagnoli, J. L. Massey, P. A. Schoeller and N. von Seemann, On repeated-root cyclic codes, IEEE Trans. Inform. Theory 37, 337-342, 1991.
24. P. Charpin, Open problems on cyclic codes, in Handbook of Coding Theory, Part 1: Algebraic Coding, V. S. Pless, W. C. Huffman, and R. A. Brualdi, Eds. Amsterdam, The Netherlands: Elsevier, ch. 11, 1998.
25. P. Charpin, Cyclic codes with few weights and Niho exponents, J. Combin. Theory Ser. A, 108, 247-259, 2004.
26. B. Chen, Y. Fan, L. Lin, H. Liu, Constacyclic codes over finite fields, Finite Fields Appl. 18, 1217- 1231, 2012.
27. B. Chen, H. Q. Dinh, H. Liu, Repeated-root constacyclic codes of length psand their duals, Discrete Appl. Math. 177, 60-70, 2014.
28. R. S. Coulter and R. W. Matthews, Planar functions and planes of Lenz- Barlotti class II, Des., Codes, Cryptogr., 10, 167-184, 1997.
29. P. Delsarte, On subfield subcodes of modified Reed-Solomon codes, IEEE Trans. Inform. Theory, 21(5), 575-576, 1975.
30. P. Dembowski and T. G. Ostrom, Planes of order n with collineation groups of order n2, Math. Z., 193, 239-258, 1968.
31. C. Ding, The weight distribution of some irreducible cyclic codes, IEEE Trans. Inf. Theory, 55(3), 955-960, 2009.
32. C. Ding, Y. Gao, and Z. Zhou, Five families of three-weight ternary cyclic codes and their duals, IEEE Trans. Inform. Theory, 59(12), 7940-7946, Dec. 2013.
33. C. Ding, Y. Liu, C. Ma, and L. Zeng, The weight distributions of the duals of cyclic codes with two zeros, IEEE Trans. Inform. Theory, 57(12), 8000-8006, 2011.
34. C. Ding and J. Yang, Hamming weights in irreducible cyclic codes, Discrete Math., 313(4), 434-446, Feb. 2013.
35. H. Q. Dinh, S. R. López-Permouth, Cyclic and negacyclic codes over finite chain rings, IEEE Trans. Inform. Theory, 50, 1728-1744, 2004.
36. H. Q. Dinh, On the linear ordering of some classes of negacyclic and cyclic codes and their distance distributions, Finite Fields Appl. 14 , 22-40, 2008.
37. H. Q. Dinh, Constacylic codes of length psover Fpm+ uFpm, Journal of Algebra, 324, 940-950, 2010.
38. H. Q. Dinh, Repeated-root constacyclic codes of length 2ps, Finite Fields Appl. 18, 133-143, 2012.
39. H. Q. Dinh, Structure of repeated-root constacyclic codes of length 3psand their duals, Discrete Math. 313, 983-991, 2013.
40. G. Falkner, B. Kowol, W. Heise, E. Zehendner, On the existence of cyclic optimal codes, Atti Sem. Mat. Fis. Univ. Modena 28, 326-341, 1979.
41. K. Feng and J. Luo, Value distributions of exponential sums from perfect nonlinear functions and their applications, IEEE Trans. Inform. Theory, 53(9), 3035-3041, Sep. 2007.
42. K. Feng and J. Luo, Weight distribution of some reducible cyclic codes, Finite Fields Appl., 14, 390-409, 2008.
43. T. Feng, On cyclic codes of length 22− 1 with two zeros whose dual codes have three weights, Des.
44. r− 1 with two zeros whose dual codes have three weights, Des.
45. Codes Cryptogr., 62, 253-258, 2012.
46. T. Feng and K. Momihara, Evaluation of the weight distribution of a class of cyclic codes based on index 2 Gauss sums, IEEE Trans. Inform. Theory, 59(9), 5980-5984, Sep. 2013.
47. T. Helleseth, Some results about the cross-correlation function between two maximal linear sequences, Discrete Math., 16(3), 209-232, 1976.
48. T. Helleseth, Some two-weight codes with composite parity-check polynomials, IEEE Trans. Inform. Theory, 22, 631-632, 1976.
49. T. Helleseth, A note on the cross-correlation function between two binary maximal length linear sequences, Discrete Math., 23(3), 301-307, 1978.
50. T. Helleseth, J. Lahtonen, and P. Rosendahl, On Niho type cross-correlation functions of m- sequences, Finite Fields Appl., 13, 305-317, 2007.
51. G. Hughes, Constacyclic codes, cocycles and a u + v | u − v construction, IEEE Trans. Inform. Theory 46, 674-680, 2000.
52. I. James, Claude Elwood Shannon, 30 April 1916 - 24 February 2001, Biographical Memoirs of Fellows of the Royal Society, 55, 257-265, 2009.
53. T. Kasami, The weight enumerators for several classes of subcodes of the 2nd order binary reed-muller codes, Inf. Control, 18(4), 369-394, 1971.
54. R. G. Kelsch, D. H. Green, Nonbinary negacyclic code which exceeds Berlekamp’s (p − 1)/2 bound, Elec. Letters 7, 664-665, 1971.
55. C. Li and Q. Yue, Weight distribution of two classes of cyclic codes with respect to two distinct order elements, IEEE Trans. Inform. Theory, 60(1), 296-303, Jan. 2014.
56. C. Li, Q. Yue, and F. Li, Weight distributions of cyclic codes with respect to pairwise coprime order elements, Finite Fields Appl., 28, 94-114, 2014.
57. C. Li, Q. Yue, and F. Li, Hamming weights of the duals of cyclic codes with two zeros, IEEE Trans. Inform. Theory, 60(7), 3895-3902, Jul. 2014.
58. C. Li and Q. Yue, Weight distributions of a class of cyclic codes from Fl-conjugates, submitted.
59. C. Li, N. Li, T. Helleseth, and C. Ding, The weight distributions of several classes of cyclic codes from APN monomials, IEEE Trans. on Inform. Theory, 60(8), 4710-4721, Aug. 2014.
60. N. Li, T. Helleseth, A. Kholosha, and X. Tang, On the Walsh transform of a class of functions from Niho exponents, IEEE Trans. Inform. Theory, 59(7), 4662-4667, Jul. 2013.
61. S. Li, T. Feng, and G. Ge, On the weight distribution of cyclic codes with Niho exponents, IEEE Trans. Inform. Theory, 60(7), 3903-3912, Jul. 2014.
62. S. Li, S. Hu, T. Feng, and G. Ge, The weight distribution of a class of cyclic codes related to Hermitian forms graphs, IEEE Trans. on Inform. Theory, 59(5), 3064-3067, May 2013.
63. R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley Publishing Inc., 1983.
64. J. Luo and K. Feng, On the weight distribution of two classes of cyclic codes, IEEE Trans. Inform. Theory, 54(12), 5332-5344, Dec. 2008.
65. X. Liu and Y. Luo, The weight distributions of some cyclic codes with three or four nonzeros over F3, Des. Codes Cryptogr., 73(3), 747-768, 2013.
66. Y. Liu, H. Yan, and C. Liu, A class of six-weight cyclic codes and their weight distribution, Des. Codes Cryptogr., Doi: 10.1007/s10623-014-9984-y, 2014.
67. J. Luo and K. Feng, Cyclic codes and sequences from generalized Coulter-Matthews function, IEEE Trans. Inform. Theory, 54(12), 5345-5353, Dec. 2008.
68. J. Luo, Y. Tang, and H. Wang, Cyclic codes and sequences: the generalized Kasami case, IEEE Trans. Inform. Theory, 56(5), 2130-2142, May 2010.
69. C. Ma, L. Zeng, Y. Liu, D. Feng, and C. Ding, The weight enumerator of a class of cyclic codes, IEEE Trans. Inform. Theory, 57(1), 397-402, Jan. 2011.
70. J. L. Massey, D. J. Costello, and J. Justesen, Polynomial weights and code constructions, IEEE Trans. Information Theory 19, 101-110, 1973.
71. G. McGuire, On three weights in cyclic codes with two zeros, Finite Fields Appl., 10, 97-104, 2004.
72. M. Moisio and K. Ranto, Kloosterman sum identities and low-weight codewords in a cyclic code with two zeros, Finite Fields Appl. 13, 922-935, 2007.
73. G. Myerson, Period polynomials and Gauss sums for finite fields, Acta Arith., 39, 251-264, 1981.
74. Y. Niho, Multivalued cross-correlation functions between two maximal linear recursive sequence, Ph.D. dissertation, Univ. Southern Calif., Los Angeles, 1970.
75. V. Pless, Power moment identities on weight distributions in error-correcting codes, Inf. Contr., 6, 147-152, 1962.
76. E. Prange, Cyclic error-correcting codes in two symbols, TN-57-103, September 1957.
77. E. Prange, Some cyclic error-correcting codes with simple decoding algorithms, TN-58-156, April 1958.
78. E. Prange, The use of coset equivalence in the analysis and decoding of group codes, TN-59-164, 1959.
79. E. Prange, An algorithm for factoring xn− 1 over a finite field, TN-59-175, October 1959.
80. E. Prange, The use of information sets in decoding cyclic codes, IEEE Trans. Inform. Theory 8,
81. R. M. Roth and G. Seroussi, On cyclic MDS codes of length q over F(q), IEEE Trans. Inform. Theory 32, 284-285, 1986.
82. B. Schmidt and C. White, All two-weight irreducible cyclic codes, Finite Fields Appl., 8, 1-17, 2002.
83. R. Schoof, Families of curves and weight distribution of codes, Bull. Amer. Math. Soc., 32(2), 171-183, 1995.
84. C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 , 379-423, 623-656, 1948. Reprinted in: A mathematical theory of communication, (Eds. C.E. Shannon and W. Weaver), Univ. of Illinois Press, Urbana, IL, 1963.
85. D. Stanton, Three addition theorems for some q-Krawtchouk polynomials, Geom. Dedicata, 10(1-4), 403-425, 1981.
86. J. H. van Lint, Repeated-root cyclic codes, IEEE Trans. Inform. Theory 37, 343-345, 1991.
87. G. Vega, Two-weight classes cyclic codes constructed as the direct sum of two one-weight cyclic codes, Finite Fields Appl., 14, 785-797, 2008.
88. G. Vega, The weight distribution of an extended class of reducible cyclic codes, IEEE Trans. Inform. Theory, 58(7), 4862-4869, Jul. 2012.
89. G. Vega and L. B. Morales, A general description for the weight distribution of some reducible cyclic codes, IEEE Trans. Inform. Theory, 59(9), 5994-6001, Sep. 2013.
90. G. Vega and J. Wolfmann, New classes of 2-weight cyclic codes, Des. Codes Cryptogr., 42, 327-344, 2007.
91. B. Wang, C. Tang, Y. Qi, Y. Yang, and M. Xu, The weight distributions of cyclic codes and elliptic curves, IEEE Trans. Inform. Theory, 58(12), 7253-7259, Dec. 2012.
92. J. Wolfmann, Negacyclic and cyclic codes over Z, IEEE Trans. Inform. Theory 45, 2527-2532, 1999.
93. J. Wolfmann, Are 2-weight projective cyclic codes irreducible?, IEEE Trans. Inform. Theory, 51(2), 733-737, Feb. 2005.
94. J. Wolfmann, Projective two-weight irreducible cyclic and constacyclic codes, Finite Fields Appl., 14, 351-360, 2008.
95. M. Xiong, The weight distributions of a class of cyclic codes, Finite Fields Appl., 18, 933-945, 2012.
96. M. Xiong, The weight distributions of a class of cyclic codes II, Des. Codes Cryptogr., 72(3), 511-528, 2012.
97. M. Xiong, The weight distributions of a class of cyclic codes III, Finite Fields Appl., 21, 84-96, 2013.
98. J. Yang, L. Xia, Complete solving of explicit evaluation of Gauss sums in the index 2 case, Sci. China Math., 53(9), 2525-2542, 2010.
99. J. Yang, M. Xiong, C. Ding, and J. Luo, Weight distribution of a class of cyclic codes with arbitrary number of zeros, IEEE Trans. Inform. Theory, 59(9), 5985-5993, Sep. 2013.
100. J. Yuan, C. Carlet, and C. Ding, The weight distribution of a class of linear codes from perfect nonlinear functions, IEEE Trans. Inform. Theory, 52(2), 712-717, Feb. 2006.
101. X. Zeng, L. Hu, W. Jiang, Q. Yue, and X. Cao, The weight distribution of a class of p-ary cyclic codes, Finite Fields Appl., 16, 56-73, 2010.
102. T. Zhang, S. Li, T. Feng, and G. Ge, Some new results on the cross correlation of m-sequences, IEEE Trans. Inform. Theory, 60(5), 3062-3068, May 2014.
103. D. Zheng, X. Wang, X. Zeng, and L. Hu, The weight distribution of a family of p-ary cyclic codes, Des. Codes Cryptogr., Doi: 10.1007/s10623-013-9908-2, 2013.
104. D. Zheng, X. Wang, X. Zeng, and L. Hu, The weight distributions of two classes of p-ary cyclic codes, Finite Fields Appl., 29, 202-224, 2014.
105. Z. Zhou and C. Ding, A class of three-weight cyclic codes, Finite Fields Appli., 25, 79-93, Jan. 2014.
106. Z. Zhou and C. Ding, Seven classes of three-weight cyclic codes, IEEE Trans. Commun., 61(10), 4120-4126, Oct. 2013.
107. Z. Zhou, C. Ding, J. Luo, and A. Zhang, A family of five-weight cyclic codes and their weight enumerators, IEEE Trans. Inform. Theory, 59(10), 6674-6682, Oct. 2013.
108. Z. Zhou, A. Zhang, C. Ding, and M. Xiong, The weight enumerator of three families of cyclic codes, IEEE Trans. Inform. Theory, 59(9), 6002-6009, Sep. 2013.