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

[2]

L. M. J. Bazzi, Minimum Distance of Error Correcting Codes Versus Encoding Complexity, Symmetry, and Pseudorandomness, PhD thesis, MIT EECS, 2003.  Google Scholar

[3]

R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach, Cambridge University Press, 2008.  Google Scholar

[4]

I. Duursma, From weight enumerators to zeta functions, Discrete Applied Mathematics, 111 (2001), 55-73.  doi: 10.1016/S0166-218X(00)00344-9.  Google Scholar

[5]

P. Gaborit, On quadratic double circulant codes over fields, Electronic Notes in Discrete Mathematics, 6 (2001), 423-432.   Google Scholar

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

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

[8]

D. Joyner, On quadratic residue codes and hyperelliptic curves, Discrete Mathematics and Theoretical Computer Science, 10 (2008), 129-146.   Google Scholar

[9]

D. Joyner, Selected Unsolved Problems in Coding Theory, Springer, 2011.  Google Scholar

[10]

M. Karlin, New binary coding results by circulants, IEEE Transactions on Information Theory, 15 (1969), 81-92.   Google Scholar

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

[12]

F. MacWilliams and N. Sloane, The Theory of Error-Eorrecting Codes, North Holland Publishing Co., 1977.  Google Scholar

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

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

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

[16]

C. TjhaiM. TomlinsonM. 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.   Google Scholar

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

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

[19]

M. Tomlinson, C. J. Tjhai, M. A. Ambroze, M. Ahmed and M. Jibril, Error-Correction Coding and Decoding, Springer, 2017.  Google Scholar

[20]

R. R. Varshamov, Estimate of the number of signals in error correcting codes, Dokl. Acad. Nauk SSSR, 117 (1957), 739-741.   Google Scholar

[21]

Wikipedia, Double-precision floating-point format, 2017, URL https://en.wikipedia.org/w/index.php?title=Double-precision_floating-point_format&oldid=778810650. Google Scholar

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

[2]

L. M. J. Bazzi, Minimum Distance of Error Correcting Codes Versus Encoding Complexity, Symmetry, and Pseudorandomness, PhD thesis, MIT EECS, 2003.  Google Scholar

[3]

R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach, Cambridge University Press, 2008.  Google Scholar

[4]

I. Duursma, From weight enumerators to zeta functions, Discrete Applied Mathematics, 111 (2001), 55-73.  doi: 10.1016/S0166-218X(00)00344-9.  Google Scholar

[5]

P. Gaborit, On quadratic double circulant codes over fields, Electronic Notes in Discrete Mathematics, 6 (2001), 423-432.   Google Scholar

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

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

[8]

D. Joyner, On quadratic residue codes and hyperelliptic curves, Discrete Mathematics and Theoretical Computer Science, 10 (2008), 129-146.   Google Scholar

[9]

D. Joyner, Selected Unsolved Problems in Coding Theory, Springer, 2011.  Google Scholar

[10]

M. Karlin, New binary coding results by circulants, IEEE Transactions on Information Theory, 15 (1969), 81-92.   Google Scholar

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

[12]

F. MacWilliams and N. Sloane, The Theory of Error-Eorrecting Codes, North Holland Publishing Co., 1977.  Google Scholar

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

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

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

[16]

C. TjhaiM. TomlinsonM. 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.   Google Scholar

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

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

[19]

M. Tomlinson, C. J. Tjhai, M. A. Ambroze, M. Ahmed and M. Jibril, Error-Correction Coding and Decoding, Springer, 2017.  Google Scholar

[20]

R. R. Varshamov, Estimate of the number of signals in error correcting codes, Dokl. Acad. Nauk SSSR, 117 (1957), 739-741.   Google Scholar

[21]

Wikipedia, Double-precision floating-point format, 2017, URL https://en.wikipedia.org/w/index.php?title=Double-precision_floating-point_format&oldid=778810650. Google Scholar

Figure 1.  distribution comparison
Table 1.  Computational Results
$p$ $d$ $\delta$Divisible by
320.33 $(x^2 + y^2)^3$
1160.27 $(x^2 + y^2)^7$
1980.21 $(x^2 + y^2)^7$
43140.16 $(x^2 + y^2)^{15}$
59180.15 $(x^2 + y^2)^{19}$
67220.16 $(x^2 + y^2)^{23}$
$p$ $d$ $\delta$Divisible by
320.33 $(x^2 + y^2)^3$
1160.27 $(x^2 + y^2)^7$
1980.21 $(x^2 + y^2)^7$
43140.16 $(x^2 + y^2)^{15}$
59180.15 $(x^2 + y^2)^{19}$
67220.16 $(x^2 + y^2)^{23}$
Table 2.  Weight polynomials posted on [18]
$p$ $k$ $d$Divisible by
894517 $(x+y)^{17}$
974915 $(x+y)^{15}$
1035219 $(x+y)^{19}$
1135715 $(x+y)$
1276419 $(x+y)$
1376921 $(x+y)$
1517619 $(x+y) $
1678423 $(x+y)$
$p$ $k$ $d$Divisible by
894517 $(x+y)^{17}$
974915 $(x+y)^{15}$
1035219 $(x+y)^{19}$
1135715 $(x+y)$
1276419 $(x+y)$
1376921 $(x+y)$
1517619 $(x+y) $
1678423 $(x+y)$
Table 3.  Weight polynomials in references
$p$ $k$ $d$Divisible by
1376921 $(x+y)^{21}$
1517619 $(x+y)^{19}$
1678423 $(x+y)^{23}$
$p$ $k$ $d$Divisible by
1376921 $(x+y)^{21}$
1517619 $(x+y)^{19}$
1678423 $(x+y)^{23}$
Table 4.  Correction for $p = 127$
$i$ $A_i$ in table $A_i$ corrected
51223367511592873280223367511592873284
52326460209251122496326460209251122492
55840260234424082176840260234424082220
5610803345871166771201080334587116677140
5918993669745836833281899366974583683220
6021526159045281743362152615904528174316
6325967884899990364162596788489999036307
$i$ $A_i$ in table $A_i$ corrected
51223367511592873280223367511592873284
52326460209251122496326460209251122492
55840260234424082176840260234424082220
5610803345871166771201080334587116677140
5918993669745836833281899366974583683220
6021526159045281743362152615904528174316
6325967884899990364162596788489999036307
[1]

Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020464

[2]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374

[3]

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

[4]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[5]

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

[6]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[7]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[8]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020276

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (218)
  • HTML views (281)
  • Cited by (0)

Other articles
by authors

[Back to Top]