American Institute of Mathematical Sciences

May 2018, 12(2): 363-385. doi: 10.3934/amc.2018023

The weight distribution of quasi-quadratic residue codes

 1 Department of Mathematics, Department of Electric and Computer Engineering, University of Wisconsin-Madison, WI 53706, United States 2 Department of Mathematics, University of Wisconsin-Madison, WI 53706, United States

Received  May 2017 Published  March 2018

Fund Project: The first author is supported by Simons Foundation grant MSN179747

We investigate a family of codes called quasi-quadratic residue (QQR) codes. We are interested in these codes mainly for two reasons: Firstly, they have close relations with hyperelliptic curves and Goppa's Conjecture, and serve as a strong tool in studying those objects. Secondly, they are very good codes. Computational results show they have large minimum distances when $p\equiv 3 \pmod 8$.

Our studies focus on the weight distributions of these codes. We will prove a new discovery about their weight polynomials, i.e. they are divisible by $(x^2 + y^2)^{d-1}$, where $d$ is the corresponding minimum distance. We also show that the weight distributions of these codes are asymptotically normal. Based on the relation between QQR codes and hyperelliptic curves, we will also prove a result on the point distribution on hyperelliptic curves.

Citation: Nigel Boston, Jing Hao. The weight distribution of quasi-quadratic residue codes. Advances in Mathematics of Communications, 2018, 12 (2) : 363-385. doi: 10.3934/amc.2018023
References:
 [1] L. M. J. Bazzi and S. K. Mitter, Some randomized code constructions from group actions, IEEE Transactions on Information Theory, 52 (2006), 3210-3219. doi: 10.1109/TIT.2006.876244. [2] L. M. J. Bazzi, Minimum Distance of Error Correcting Codes Versus Encoding Complexity, Symmetry, and Pseudorandomness, PhD thesis, MIT EECS, 2003. [3] R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach, Cambridge University Press, 2008. [4] I. Duursma, From weight enumerators to zeta functions, Discrete Applied Mathematics, 111 (2001), 55-73. doi: 10.1016/S0166-218X(00)00344-9. [5] P. Gaborit, On quadratic double circulant codes over fields, Electronic Notes in Discrete Mathematics, 6 (2001), 423-432. [6] E. N. Gilbert, A comparison of signalling alphabets, Bell System Technical Journal, 31 (1952), 504-522. doi: 10.1002/j.1538-7305.1952.tb01393.x. [7] T. Helleseth and J. F. Voloch, Double circulant quadratic residue codes, IEEE Transactions on Information Theory, 50 (2004), 2154-2155. doi: 10.1109/TIT.2004.833371. [8] D. Joyner, On quadratic residue codes and hyperelliptic curves, Discrete Mathematics and Theoretical Computer Science, 10 (2008), 129-146. [9] D. Joyner, Selected Unsolved Problems in Coding Theory, Springer, 2011. [10] M. Karlin, New binary coding results by circulants, IEEE Transactions on Information Theory, 15 (1969), 81-92. [11] M. Larsen, The normal distribution as a limit of generalized sato-tate measures, Preprint, 1–15, URL http://mlarsen.math.indiana.edu/~larsen/unpublished.html. [12] F. MacWilliams and N. Sloane, The Theory of Error-Eorrecting Codes, North Holland Publishing Co., 1977. [13] Y. I. Manin, What is the maximum number of points on a curve over $F_2$, Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics, 28 (1981), 715-720. [14] E. M. Rains and N. J. A. Sloane, Self-dual codes, in Handbook of Coding Theory (eds. V. S. P. Huffman and W. C.), Elsevier, 1998,177–294. [15] N. J. A. Sloane, The on-line encyclopedia of integer sequences, Towards Mechanized Mathematical Assistants, 4573 (2007), 130–130, URL https://oeis.org. doi: 10.1007/978-3-540-73086-6_12. [16] C. Tjhai, M. Tomlinson, M. Ambroze and M. Ahmed, On the Weight Distribution of the Extended Quadratic Residue Code of Prime 137, 7th International ITG Conference on Source and Channel Coding, 1 (2008), 1-6. [17] C. Tjhai, M. Tomlinson, R. Horan, M. Ahmed and M. Ambroze, Some results on the weight distributions of the binary double-circulant codes based on primes, IEEE Singapore International Conference on Communication Systems, ICCS 2006, 2006, 1–14. doi: 10.1109/ICCS.2006.301431. [18] C. J. Tjhai and M. Tomlinson, Weight distributions of quadratic residue and quadratic double circulant codes over GF(2), URL http://www.tech.plym.ac.uk/Research/fixed_and_mobile_communications/links/weightdistributions.htm. [19] M. Tomlinson, C. J. Tjhai, M. A. Ambroze, M. Ahmed and M. Jibril, Error-Correction Coding and Decoding, Springer, 2017. [20] R. R. Varshamov, Estimate of the number of signals in error correcting codes, Dokl. Acad. Nauk SSSR, 117 (1957), 739-741. [21] Wikipedia, Double-precision floating-point format, 2017, URL https://en.wikipedia.org/w/index.php?title=Double-precision_floating-point_format&oldid=778810650.

show all references

References:
 [1] L. M. J. Bazzi and S. K. Mitter, Some randomized code constructions from group actions, IEEE Transactions on Information Theory, 52 (2006), 3210-3219. doi: 10.1109/TIT.2006.876244. [2] L. M. J. Bazzi, Minimum Distance of Error Correcting Codes Versus Encoding Complexity, Symmetry, and Pseudorandomness, PhD thesis, MIT EECS, 2003. [3] R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach, Cambridge University Press, 2008. [4] I. Duursma, From weight enumerators to zeta functions, Discrete Applied Mathematics, 111 (2001), 55-73. doi: 10.1016/S0166-218X(00)00344-9. [5] P. Gaborit, On quadratic double circulant codes over fields, Electronic Notes in Discrete Mathematics, 6 (2001), 423-432. [6] E. N. Gilbert, A comparison of signalling alphabets, Bell System Technical Journal, 31 (1952), 504-522. doi: 10.1002/j.1538-7305.1952.tb01393.x. [7] T. Helleseth and J. F. Voloch, Double circulant quadratic residue codes, IEEE Transactions on Information Theory, 50 (2004), 2154-2155. doi: 10.1109/TIT.2004.833371. [8] D. Joyner, On quadratic residue codes and hyperelliptic curves, Discrete Mathematics and Theoretical Computer Science, 10 (2008), 129-146. [9] D. Joyner, Selected Unsolved Problems in Coding Theory, Springer, 2011. [10] M. Karlin, New binary coding results by circulants, IEEE Transactions on Information Theory, 15 (1969), 81-92. [11] M. Larsen, The normal distribution as a limit of generalized sato-tate measures, Preprint, 1–15, URL http://mlarsen.math.indiana.edu/~larsen/unpublished.html. [12] F. MacWilliams and N. Sloane, The Theory of Error-Eorrecting Codes, North Holland Publishing Co., 1977. [13] Y. I. Manin, What is the maximum number of points on a curve over $F_2$, Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics, 28 (1981), 715-720. [14] E. M. Rains and N. J. A. Sloane, Self-dual codes, in Handbook of Coding Theory (eds. V. S. P. Huffman and W. C.), Elsevier, 1998,177–294. [15] N. J. A. Sloane, The on-line encyclopedia of integer sequences, Towards Mechanized Mathematical Assistants, 4573 (2007), 130–130, URL https://oeis.org. doi: 10.1007/978-3-540-73086-6_12. [16] C. Tjhai, M. Tomlinson, M. Ambroze and M. Ahmed, On the Weight Distribution of the Extended Quadratic Residue Code of Prime 137, 7th International ITG Conference on Source and Channel Coding, 1 (2008), 1-6. [17] C. Tjhai, M. Tomlinson, R. Horan, M. Ahmed and M. Ambroze, Some results on the weight distributions of the binary double-circulant codes based on primes, IEEE Singapore International Conference on Communication Systems, ICCS 2006, 2006, 1–14. doi: 10.1109/ICCS.2006.301431. [18] C. J. Tjhai and M. Tomlinson, Weight distributions of quadratic residue and quadratic double circulant codes over GF(2), URL http://www.tech.plym.ac.uk/Research/fixed_and_mobile_communications/links/weightdistributions.htm. [19] M. Tomlinson, C. J. Tjhai, M. A. Ambroze, M. Ahmed and M. Jibril, Error-Correction Coding and Decoding, Springer, 2017. [20] R. R. Varshamov, Estimate of the number of signals in error correcting codes, Dokl. Acad. Nauk SSSR, 117 (1957), 739-741. [21] Wikipedia, Double-precision floating-point format, 2017, URL https://en.wikipedia.org/w/index.php?title=Double-precision_floating-point_format&oldid=778810650.
distribution comparison
Computational Results
 $p$ $d$ $\delta$ Divisible by 3 2 0.33 $(x^2 + y^2)^3$ 11 6 0.27 $(x^2 + y^2)^7$ 19 8 0.21 $(x^2 + y^2)^7$ 43 14 0.16 $(x^2 + y^2)^{15}$ 59 18 0.15 $(x^2 + y^2)^{19}$ 67 22 0.16 $(x^2 + y^2)^{23}$
 $p$ $d$ $\delta$ Divisible by 3 2 0.33 $(x^2 + y^2)^3$ 11 6 0.27 $(x^2 + y^2)^7$ 19 8 0.21 $(x^2 + y^2)^7$ 43 14 0.16 $(x^2 + y^2)^{15}$ 59 18 0.15 $(x^2 + y^2)^{19}$ 67 22 0.16 $(x^2 + y^2)^{23}$
Weight polynomials posted on [18]
 $p$ $k$ $d$ Divisible by 89 45 17 $(x+y)^{17}$ 97 49 15 $(x+y)^{15}$ 103 52 19 $(x+y)^{19}$ 113 57 15 $(x+y)$ 127 64 19 $(x+y)$ 137 69 21 $(x+y)$ 151 76 19 $(x+y)$ 167 84 23 $(x+y)$
 $p$ $k$ $d$ Divisible by 89 45 17 $(x+y)^{17}$ 97 49 15 $(x+y)^{15}$ 103 52 19 $(x+y)^{19}$ 113 57 15 $(x+y)$ 127 64 19 $(x+y)$ 137 69 21 $(x+y)$ 151 76 19 $(x+y)$ 167 84 23 $(x+y)$
Weight polynomials in references
 $p$ $k$ $d$ Divisible by 137 69 21 $(x+y)^{21}$ 151 76 19 $(x+y)^{19}$ 167 84 23 $(x+y)^{23}$
 $p$ $k$ $d$ Divisible by 137 69 21 $(x+y)^{21}$ 151 76 19 $(x+y)^{19}$ 167 84 23 $(x+y)^{23}$
Correction for $p = 127$
 $i$ $A_i$ in table $A_i$ corrected 51 223367511592873280 223367511592873284 52 326460209251122496 326460209251122492 55 840260234424082176 840260234424082220 56 1080334587116677120 1080334587116677140 59 1899366974583683328 1899366974583683220 60 2152615904528174336 2152615904528174316 63 2596788489999036416 2596788489999036307
 $i$ $A_i$ in table $A_i$ corrected 51 223367511592873280 223367511592873284 52 326460209251122496 326460209251122492 55 840260234424082176 840260234424082220 56 1080334587116677120 1080334587116677140 59 1899366974583683328 1899366974583683220 60 2152615904528174336 2152615904528174316 63 2596788489999036416 2596788489999036307
 [1] Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1 [2] Martino Borello, Francesca Dalla Volta, Gabriele Nebe. The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$. Advances in Mathematics of Communications, 2013, 7 (4) : 503-510. doi: 10.3934/amc.2013.7.503 [3] Roberto Avanzi, Nicolas Thériault. A filtering method for the hyperelliptic curve index calculus and its analysis. Advances in Mathematics of Communications, 2010, 4 (2) : 189-213. doi: 10.3934/amc.2010.4.189 [4] Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637 [5] Van Cyr, Bryna Kra. The automorphism group of a minimal shift of stretched exponential growth. Journal of Modern Dynamics, 2016, 10: 483-495. doi: 10.3934/jmd.2016.10.483 [6] Gilberto M. Kremer, Wilson Marques Jr.. Fourteen moment theory for granular gases. Kinetic & Related Models, 2011, 4 (1) : 317-331. doi: 10.3934/krm.2011.4.317 [7] Carla Mascia, Giancarlo Rinaldo, Massimiliano Sala. Hilbert quasi-polynomial for order domains and application to coding theory. Advances in Mathematics of Communications, 2018, 12 (2) : 287-301. doi: 10.3934/amc.2018018 [8] Jaume Llibre, Claudia Valls. Algebraic limit cycles for quadratic polynomial differential systems. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-11. doi: 10.3934/dcdsb.2018070 [9] Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032 [10] Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013 [11] M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks & Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201 [12] Rodrigo Abarzúa, Nicolas Thériault, Roberto Avanzi, Ismael Soto, Miguel Alfaro. Optimization of the arithmetic of the ideal class group for genus 4 hyperelliptic curves over projective coordinates. Advances in Mathematics of Communications, 2010, 4 (2) : 115-139. doi: 10.3934/amc.2010.4.115 [13] François Gay-Balmaz, Cesare Tronci, Cornelia Vizman. Geometric dynamics on the automorphism group of principal bundles: Geodesic flows, dual pairs and chromomorphism groups. Journal of Geometric Mechanics, 2013, 5 (1) : 39-84. doi: 10.3934/jgm.2013.5.39 [14] Manuel Torrilhon. H-Theorem for nonlinear regularized 13-moment equations in kinetic gas theory. Kinetic & Related Models, 2012, 5 (1) : 185-201. doi: 10.3934/krm.2012.5.185 [15] Pierre Lissy. Construction of gevrey functions with compact support using the bray-mandelbrojt iterative process and applications to the moment method in control theory. Mathematical Control & Related Fields, 2017, 7 (1) : 21-40. doi: 10.3934/mcrf.2017002 [16] Wenlei Li, Shaoyun Shi. Singular perturbed renormalization group theory and its application to highly oscillatory problems. Discrete & Continuous Dynamical Systems - B, 2018, 23 (4) : 1819-1833. doi: 10.3934/dcdsb.2018089 [17] Florian Schneider, Andreas Roth, Jochen Kall. First-order quarter-and mixed-moment realizability theory and Kershaw closures for a Fokker-Planck equation in two space dimensions. Kinetic & Related Models, 2017, 10 (4) : 1127-1161. doi: 10.3934/krm.2017044 [18] Karim Samei, Arezoo Soufi. Quadratic residue codes over $\mathbb{F}_{p^r}+{u_1}\mathbb{F}_{p^r}+{u_2}\mathbb{F}_{p^r}+...+{u_t}\mathbb{F}_ {p^r}$. Advances in Mathematics of Communications, 2017, 11 (4) : 791-804. doi: 10.3934/amc.2017058 [19] Pieter Moree. On the distribution of the order over residue classes. Electronic Research Announcements, 2006, 12: 121-128. [20] M. J. Jacobson, R. Scheidler, A. Stein. Cryptographic protocols on real hyperelliptic curves. Advances in Mathematics of Communications, 2007, 1 (2) : 197-221. doi: 10.3934/amc.2007.1.197

2016 Impact Factor: 0.8