Counting generalized Reed-Solomon codes

Previous Article
On the performance of optimal double circulant even codes
AMC Home
This Issue
Next Article
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}$

November 2017, 11(4): 777-790. doi: 10.3934/amc.2017057

Counting generalized Reed-Solomon codes

Peter Beelen ^1, , David Glynn ^2,3, , Tom Høholdt ^1, and Krishna Kaipa ^4,

1.	Department of Applied Mathematics and Computer Science, Technical University of Denmark, Matematiktorvet 303B, DK-2800 Kgs. Lyngby, Denmark
2.	School of Computer Science, Engineering and Mathematics, Flinders University, GPO Box 2100, Adelaide, SA 5001, Australia
3.	Department of Mathematics King Abdulaziz University, Jeddah 21859, Saudi Arabia
4.	Department of Mathematics, Indian Institute of Science Education and Research (IISER), Dr. Homi Bhabha Road, Pashan, Pune 411008, India

Received May 2016 Published November 2017

In this article we count the number of $[n, k]$ generalized Reed-Solomon (GRS) codes, including the codes coming from a non-degenerate conic plus nucleus. We compare our results with known formulae for the number of $[n, 3]$ MDS codes with $n=6, 7, 8, 9$.

Keywords: Generalized Reed-Solomon codes, MDS codes, n-arcs.

Mathematics Subject Classification: Primary: 94B27, 51E21.

Citation: Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057

References:

[1]	S. Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis, J. Eur. Math. Soc., 14 (2012), 733-748. Google Scholar
[2]	S. Ball and J. De Beule, On sets of vectors of a finite vector space in which every subset of basis size is a basis Ⅱ, Des. Codes Cryptography, 65 (2012), 5-14. doi: 10.1007/s10623-012-9658-6. Google Scholar
[3]	W.-L. Chow, On the geometry of algebraic homogeneous spaces, Annals of Mathematics. Second Series, 50 (1949), 32-67. doi: 10.2307/1969351. Google Scholar
[4]	P. Dembowski, Finite Geometries Springer, 1968. Google Scholar
[5]	A. Dür, The automorphism groups of Reed-Solomon codes, J. Comb. Theory, Series A, 44 (1987), 69-82. doi: 10.1016/0097-3165(87)90060-4. Google Scholar
[6]	D. Eisenbud, Commutative Algebra: With a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1995. Google Scholar
[7]	S. R. Ghorpade and G. Lachaud, Hyperplane sections of Grassmannians and the number of MDS linear codes, Finite Fields and Their Applications, 7 (2001), 468-506. doi: 10.1006/ffta.2000.0299. Google Scholar
[8]	D. G. Glynn, The non-classical 10-arc of $\mathrm{PG}(4,9)$, Discrete Mathematics, 59 (1986), 43-51. Google Scholar
[9]	D. G. Glynn, Rings of geometries, Ⅱ, J. Comb. Theory, Series A, 49 (1988), 26-66. doi: 10.1016/0097-3165(88)90027-1. Google Scholar
[10]	D. G. Glynn, Every oval of $\text{PG}(2,q)$, $q$ even, is the product of its external lines, Bull. Inst. Combin. Appl., 9 (1993), 65-68. Google Scholar
[11]	D. G. Glynn, A condition for arcs and MDS codes, Designs Codes and Cryptography, 58 (2011), 215-218. doi: 10.1007/s10623-010-9404-x. Google Scholar
[12]	D. G. Glynn, An invariant for hypersurfaces in prime characteristic, SIAM Journal on Discrete Mathematics, 26 (2012), 881-883. doi: 10.1137/110823274. Google Scholar
[13]	P. Griffiths and J. Harris, Principles of Algebraic Geometry, John Wiley & Sons, New York, 1978. Google Scholar
[14]	J. Harris, Algebraic Geometry: A First Course, Springer-Verlag, New York, 1995. Google Scholar
[15]	J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions The Clarendon Press, Oxford University Press, New York, 1985. Google Scholar
[16]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, second edition, 1998. Google Scholar
[17]	J. W. P. Hirschfeld, G. Korchmaros and F. Torres, Algebraic Curves over a Finite Field, Princeton University Press, Princeton, NJ, 2008. Google Scholar
[18]	J. W. P. Hirschfeld and J. A. Thas, General Galois Geometries, Springer Monographs in Mathematics, Springer, London, 2016. Google Scholar
[19]	A. V. Iampolskda, A. N. Skorobogatov and E. A. Sorokin, Formula for the number of $[9,3]$ MDS codes, IEEE Trans. Inf. Theory, 41 (1995), 1667-1671. doi: 10.1109/18.476239. Google Scholar
[20]	K. V. Kaipa, An asymptotic formula in $q$ for the number of $[n,k]$ $q$-ary MDS codes, IEEE Trans. Inf. Theory, 60 (2014), 7047-7057. doi: 10.1109/TIT.2014.2349903. Google Scholar
[21]	R. Rolland, The number of MDS $[7,3]$ codes on finite fields of characteristic $2$, Appl. Algebra Engrg. Comm. Comput., 3 (1992), 301-310. doi: 10.1007/BF01294838. Google Scholar
[22]	B. Segre, Lectures on Modern Geometry, Edizioni Cremonese, Roma, 1961. Google Scholar
[23]	R. C. Singleton, Maximum distance $q$-nary codes, IEEE Trans. Information Theory, 10 (1964), 116-118. Google Scholar

show all references

References:

[1]	S. Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis, J. Eur. Math. Soc., 14 (2012), 733-748. Google Scholar
[2]	S. Ball and J. De Beule, On sets of vectors of a finite vector space in which every subset of basis size is a basis Ⅱ, Des. Codes Cryptography, 65 (2012), 5-14. doi: 10.1007/s10623-012-9658-6. Google Scholar
[3]	W.-L. Chow, On the geometry of algebraic homogeneous spaces, Annals of Mathematics. Second Series, 50 (1949), 32-67. doi: 10.2307/1969351. Google Scholar
[4]	P. Dembowski, Finite Geometries Springer, 1968. Google Scholar
[5]	A. Dür, The automorphism groups of Reed-Solomon codes, J. Comb. Theory, Series A, 44 (1987), 69-82. doi: 10.1016/0097-3165(87)90060-4. Google Scholar
[6]	D. Eisenbud, Commutative Algebra: With a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1995. Google Scholar
[7]	S. R. Ghorpade and G. Lachaud, Hyperplane sections of Grassmannians and the number of MDS linear codes, Finite Fields and Their Applications, 7 (2001), 468-506. doi: 10.1006/ffta.2000.0299. Google Scholar
[8]	D. G. Glynn, The non-classical 10-arc of $\mathrm{PG}(4,9)$, Discrete Mathematics, 59 (1986), 43-51. Google Scholar
[9]	D. G. Glynn, Rings of geometries, Ⅱ, J. Comb. Theory, Series A, 49 (1988), 26-66. doi: 10.1016/0097-3165(88)90027-1. Google Scholar
[10]	D. G. Glynn, Every oval of $\text{PG}(2,q)$, $q$ even, is the product of its external lines, Bull. Inst. Combin. Appl., 9 (1993), 65-68. Google Scholar
[11]	D. G. Glynn, A condition for arcs and MDS codes, Designs Codes and Cryptography, 58 (2011), 215-218. doi: 10.1007/s10623-010-9404-x. Google Scholar
[12]	D. G. Glynn, An invariant for hypersurfaces in prime characteristic, SIAM Journal on Discrete Mathematics, 26 (2012), 881-883. doi: 10.1137/110823274. Google Scholar
[13]	P. Griffiths and J. Harris, Principles of Algebraic Geometry, John Wiley & Sons, New York, 1978. Google Scholar
[14]	J. Harris, Algebraic Geometry: A First Course, Springer-Verlag, New York, 1995. Google Scholar
[15]	J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions The Clarendon Press, Oxford University Press, New York, 1985. Google Scholar
[16]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, second edition, 1998. Google Scholar
[17]	J. W. P. Hirschfeld, G. Korchmaros and F. Torres, Algebraic Curves over a Finite Field, Princeton University Press, Princeton, NJ, 2008. Google Scholar
[18]	J. W. P. Hirschfeld and J. A. Thas, General Galois Geometries, Springer Monographs in Mathematics, Springer, London, 2016. Google Scholar
[19]	A. V. Iampolskda, A. N. Skorobogatov and E. A. Sorokin, Formula for the number of $[9,3]$ MDS codes, IEEE Trans. Inf. Theory, 41 (1995), 1667-1671. doi: 10.1109/18.476239. Google Scholar
[20]	K. V. Kaipa, An asymptotic formula in $q$ for the number of $[n,k]$ $q$-ary MDS codes, IEEE Trans. Inf. Theory, 60 (2014), 7047-7057. doi: 10.1109/TIT.2014.2349903. Google Scholar
[21]	R. Rolland, The number of MDS $[7,3]$ codes on finite fields of characteristic $2$, Appl. Algebra Engrg. Comm. Comput., 3 (1992), 301-310. doi: 10.1007/BF01294838. Google Scholar
[22]	B. Segre, Lectures on Modern Geometry, Edizioni Cremonese, Roma, 1961. Google Scholar
[23]	R. C. Singleton, Maximum distance $q$-nary codes, IEEE Trans. Information Theory, 10 (1964), 116-118. Google Scholar

Table 1. Number of GRS and MDS codes of small length and dimension 3

$q$	$n$	$\#$ GRS	$\#$ MDS
$4$	$6$	$486$	$486$
$5$	$6$	$6144$	$6144$
$7$	$6$	$466560$	$1088640$
$7$	$7$	$5598720$	$5598720$
$7$	$8$	$33592320$	$33592320$
$8$	$6$	$2016840$	$6554730$
$8$	$7$	$42353640$	$141178800$
$8$	$8$	$592950960$	$2964754800$
$8$	$9$	$4150656720$	$41506567200$
$8$	$10$	$290545970400$	$290545970400$
$9$	$6$	$6881280$	$28901376$
$9$	$7$	$220200960$	$1604321280$
$9$	$8$	$5284823040$	$15854469120$
$9$	$9$	$84557168640$	$84557168640$
$9$	$10$	$676457349120$	$676457349120$

Table Options

Download as excel

$q$	$n$	$\#$ GRS	$\#$ MDS
$4$	$6$	$486$	$486$
$5$	$6$	$6144$	$6144$
$7$	$6$	$466560$	$1088640$
$7$	$7$	$5598720$	$5598720$
$7$	$8$	$33592320$	$33592320$
$8$	$6$	$2016840$	$6554730$
$8$	$7$	$42353640$	$141178800$
$8$	$8$	$592950960$	$2964754800$
$8$	$9$	$4150656720$	$41506567200$
$8$	$10$	$290545970400$	$290545970400$
$9$	$6$	$6881280$	$28901376$
$9$	$7$	$220200960$	$1604321280$
$9$	$8$	$5284823040$	$15854469120$
$9$	$9$	$84557168640$	$84557168640$
$9$	$10$	$676457349120$	$676457349120$

[1]	Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015
[2]	Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69
[3]	Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005
[4]	José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467
[5]	Janne I. Kokkala, Patric R. J. Östergård. Further results on the classification of MDS codes. Advances in Mathematics of Communications, 2016, 10 (3) : 489-498. doi: 10.3934/amc.2016020
[6]	Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041
[7]	Diego Napp, Roxana Smarandache. Constructing strongly-MDS convolutional codes with maximum distance profile. Advances in Mathematics of Communications, 2016, 10 (2) : 275-290. doi: 10.3934/amc.2016005
[8]	Ilias S. Kotsireas, Christos Koukouvinos, Dimitris E. Simos. MDS and near-MDS self-dual codes over large prime fields. Advances in Mathematics of Communications, 2009, 3 (4) : 349-361. doi: 10.3934/amc.2009.3.349
[9]	José Ignacio Iglesias Curto. Generalized AG convolutional codes. Advances in Mathematics of Communications, 2009, 3 (4) : 317-328. doi: 10.3934/amc.2009.3.317
[10]	Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021
[11]	Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[12]	Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
[13]	Kamil Otal, Ferruh Özbudak, Wolfgang Willems. Self-duality of generalized twisted Gabidulin codes. Advances in Mathematics of Communications, 2018, 12 (4) : 707-721. doi: 10.3934/amc.2018042
[14]	Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$ⁿ into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385
[15]	Alonso sepúlveda Castellanos. Generalized Hamming weights of codes over the $\mathcal{GH}$ curve. Advances in Mathematics of Communications, 2017, 11 (1) : 115-122. doi: 10.3934/amc.2017006
[16]	Pankaj Kumar, Monika Sangwan, Suresh Kumar Arora. The weight distributions of some irreducible cyclic codes of length $p^n$ and $2p^n$. Advances in Mathematics of Communications, 2015, 9 (3) : 277-289. doi: 10.3934/amc.2015.9.277
[17]	Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the symmetry group of extended perfect binary codes of length $n+1$ and rank $n-\log(n+1)+2$. Advances in Mathematics of Communications, 2012, 6 (2) : 121-130. doi: 10.3934/amc.2012.6.121
[18]	Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163
[19]	Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225
[20]	Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039

2018 Impact Factor: 0.879

Tools

Metrics

Tools

Article outline

Figures and Tables

2018 Impact Factor: 0.879

Tools

Figures and Tables

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences