The weight distribution of quasi-quadratic residue codes

Nigel Boston; Jing Hao

doi:10.3934/amc.2018023

Article Contents

2018, Volume 12, Issue 2: 363-385. Doi: 10.3934/amc.2018023

This issue Previous Article Further results on the existence of super-simple pairwise balanced designs with block sizes 3 and 4 Next Article New families of strictly optimal frequency hopping sequence sets

The weight distribution of quasi-quadratic residue codes

Nigel Boston^1, and
Jing Hao^2,

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: April 30, 2017

Published: April 2018

The first author is supported by Simons Foundation grant MSN179747

Abstract Full Text(HTML) Figure(1) / Table(4) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94B15, 94B60; Secondary: 11G20.

Citation:

Full Text(HTML)

Figure 1. distribution comparison

Download: Full-size image PowerPoint slide

Table 1. 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}$

| Show Table

DownLoad: CSV

Table 2. 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)$

| Show Table

DownLoad: CSV

Table 3. 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}$

| Show Table

DownLoad: CSV

Table 4. 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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	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.
	L. M. J. Bazzi, Minimum Distance of Error Correcting Codes Versus Encoding Complexity, Symmetry, and Pseudorandomness, PhD thesis, MIT EECS, 2003.
	R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach, Cambridge University Press, 2008.
	I. Duursma , From weight enumerators to zeta functions, Discrete Applied Mathematics, 111 (2001) , 55-73. doi: 10.1016/S0166-218X(00)00344-9.
	P. Gaborit , On quadratic double circulant codes over fields, Electronic Notes in Discrete Mathematics, 6 (2001) , 423-432.
	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.
	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.
	D. Joyner , On quadratic residue codes and hyperelliptic curves, Discrete Mathematics and Theoretical Computer Science, 10 (2008) , 129-146.
	D. Joyner, Selected Unsolved Problems in Coding Theory, Springer, 2011.
	M. Karlin , New binary coding results by circulants, IEEE Transactions on Information Theory, 15 (1969) , 81-92.
	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.
	F. MacWilliams and N. Sloane, The Theory of Error-Eorrecting Codes, North Holland Publishing Co., 1977.
	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.
	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.
	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.
	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.
	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.
	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.
	M. Tomlinson, C. J. Tjhai, M. A. Ambroze, M. Ahmed and M. Jibril, Error-Correction Coding and Decoding, Springer, 2017.
	R. R. Varshamov , Estimate of the number of signals in error correcting codes, Dokl. Acad. Nauk SSSR, 117 (1957) , 739-741.
	Wikipedia, Double-precision floating-point format, 2017, URL https://en.wikipedia.org/w/index.php?title=Double-precision_floating-point_format&oldid=778810650.