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

Counting generalized Reed-Solomon codes

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$.

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.

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

[3]

W.-L. Chow, On the geometry of algebraic homogeneous spaces, Annals of Mathematics. Second Series, 50 (1949), 32-67. doi: 10.2307/1969351.

[4]

P. Dembowski, Finite Geometries Springer, 1968.

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

[6]

D. Eisenbud, Commutative Algebra: With a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1995.

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

[8]

D. G. Glynn, The non-classical 10-arc of $\mathrm{PG}(4,9)$, Discrete Mathematics, 59 (1986), 43-51.

[9]

D. G. Glynn, Rings of geometries, Ⅱ, J. Comb. Theory, Series A, 49 (1988), 26-66. doi: 10.1016/0097-3165(88)90027-1.

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

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

[12]

D. G. Glynn, An invariant for hypersurfaces in prime characteristic, SIAM Journal on Discrete Mathematics, 26 (2012), 881-883. doi: 10.1137/110823274.

[13]

P. Griffiths and J. Harris, Principles of Algebraic Geometry, John Wiley & Sons, New York, 1978.

[14]

J. Harris, Algebraic Geometry: A First Course, Springer-Verlag, New York, 1995.

[15]

J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions The Clarendon Press, Oxford University Press, New York, 1985.

[16]

J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, second edition, 1998.

[17]

J. W. P. Hirschfeld, G. Korchmaros and F. Torres, Algebraic Curves over a Finite Field, Princeton University Press, Princeton, NJ, 2008.

[18]

J. W. P. Hirschfeld and J. A. Thas, General Galois Geometries, Springer Monographs in Mathematics, Springer, London, 2016.

[19]

A. V. IampolskdaA. 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.

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

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

[22]

B. Segre, Lectures on Modern Geometry, Edizioni Cremonese, Roma, 1961.

[23]

R. C. Singleton, Maximum distance $q$-nary codes, IEEE Trans. Information Theory, 10 (1964), 116-118.

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.

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

[3]

W.-L. Chow, On the geometry of algebraic homogeneous spaces, Annals of Mathematics. Second Series, 50 (1949), 32-67. doi: 10.2307/1969351.

[4]

P. Dembowski, Finite Geometries Springer, 1968.

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

[6]

D. Eisenbud, Commutative Algebra: With a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1995.

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

[8]

D. G. Glynn, The non-classical 10-arc of $\mathrm{PG}(4,9)$, Discrete Mathematics, 59 (1986), 43-51.

[9]

D. G. Glynn, Rings of geometries, Ⅱ, J. Comb. Theory, Series A, 49 (1988), 26-66. doi: 10.1016/0097-3165(88)90027-1.

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

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

[12]

D. G. Glynn, An invariant for hypersurfaces in prime characteristic, SIAM Journal on Discrete Mathematics, 26 (2012), 881-883. doi: 10.1137/110823274.

[13]

P. Griffiths and J. Harris, Principles of Algebraic Geometry, John Wiley & Sons, New York, 1978.

[14]

J. Harris, Algebraic Geometry: A First Course, Springer-Verlag, New York, 1995.

[15]

J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions The Clarendon Press, Oxford University Press, New York, 1985.

[16]

J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, second edition, 1998.

[17]

J. W. P. Hirschfeld, G. Korchmaros and F. Torres, Algebraic Curves over a Finite Field, Princeton University Press, Princeton, NJ, 2008.

[18]

J. W. P. Hirschfeld and J. A. Thas, General Galois Geometries, Springer Monographs in Mathematics, Springer, London, 2016.

[19]

A. V. IampolskdaA. 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.

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

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

[22]

B. Segre, Lectures on Modern Geometry, Edizioni Cremonese, Roma, 1961.

[23]

R. C. Singleton, Maximum distance $q$-nary codes, IEEE Trans. Information Theory, 10 (1964), 116-118.

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$
$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]

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

[8]

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

[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]

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

[11]

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

[12]

Kamil Otal, Ferruh Özbudak, Wofgang Willems. Self-duality of generalized twisted Gabidulin codes. Advances in Mathematics of Communications, 2018, 12 (4) : 707-721. doi: 10.3934/amc.2018042

[13]

Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$n into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Jennifer D. Key, Washiela Fish, Eric Mwambene. Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \geq 2$. Advances in Mathematics of Communications, 2011, 5 (2) : 373-394. doi: 10.3934/amc.2011.5.373

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (20)
  • HTML views (196)
  • Cited by (0)

[Back to Top]