American Institute of Mathematical Sciences

Advanced
February  2019, 13(1): 101-119. doi: 10.3934/amc.2019006

Maximum weight spectrum codes

Tim Alderson 1, and  Alessandro Neri 2,

1. 

Dept. of Mathematics and Statistics, University of New Brunswick Saint John, Saint John, NB, E5S 2A6, Canada
2. 

Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland

Received  April 2018 Revised  July 2018 Published  December 2018

Fund Project: The first author acknowledges the support of the NSERC of Canada Discovery Grant program.
The second author acknowledges the support of Swiss National Science Foundation grant n.169510.

In the recent work [9], a combinatorial problem concerning linear codes over a finite field $\mathbb{F}_q$ was introduced. In that work the authors studied the weight set of an $[n,k]_q$ linear code, that is the set of non-zero distinct Hamming weights, showing that its cardinality is bounded above by $\frac{q^k-1}{q-1}$. They showed that this bound was sharp in the case $ q = 2 $, and in the case $ k = 2 $. They conjectured that the bound is sharp for every prime power $ q $ and every positive integer $ k $. In this work we quickly establish the truth of this conjecture. We provide two proofs, each employing different construction techniques. The first relies on the geometric view of linear codes as systems of projective points. The second approach is purely algebraic. We establish some lower bounds on the length of codes that satisfy the conjecture, and the length of the new codes constructed here are discussed.

Keywords: Linear codes, Hamming weights, algebraic coding theory, weight spectrum, projective geometry.
Mathematics Subject Classification: Primary: 11T71; Secondary: 05D99, 94B05.
Citation: Tim Alderson, Alessandro Neri. Maximum weight spectrum codes. Advances in Mathematics of Communications, 2019, 13 (1) : 101-119. doi: 10.3934/amc.2019006
References:
[1]

T. L. Alderson and A. A. Bruen, Coprimitive sets and inextendable codes, Des. Codes Cryptogr., 47 (2008), 113-124.  doi: 10.1007/s10623-007-9079-0.

[2]

S. Ball, Finite Geometry and Combinatorial Applications, volume 82. Cambridge University Press, 2015. doi: 10.1017/CBO9781316257449.

[3]

P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Information and Control, 23 (1973), 407-438.  doi: 10.1016/S0019-9958(73)80007-5.

[4]

H. Enomoto, P. Frankl, N. Ito and K. Nomura, Codes with given distances, Graphs and Combinatorics, 3 (1987), 25-38.  doi: 10.1007/BF01788526.

[5]

A. Haily and D. Harzalla, On binary linear codes whose automorphism group is trivial, Journal of Discrete Mathematical Sciences and Cryptography, 18 (2015), 495-512.  doi: 10.1080/09720529.2014.927650.

[6]

J. MacWilliams, A theorem on the distribution of weights in a systematic code, The Bell System Technical Journal, 42 (1963), 79-94.  doi: 10.1002/j.1538-7305.1963.tb04003.x.

[7]

J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, Journal of the ACM (JACM), 27 (1980), 701-717.  doi: 10.1145/322217.322225.

[8]

M. Shi, X. Li, A. Neri and P. Solé, How many weights can a cyclic code have?, arXiv: 1807.08418, 15, November, 2018.

[9]

M. Shi, H. Zhu, P. Solé and G. D. Cohen, How many weights can a linear code have?, Des. Codes Cryptogr., (2018). doi: 10.1007/s10623-018-0488-z.

[10]

D. Slepian, A class of binary signaling alphabets, Bell Labs Technical Journal, 35 (1956), 203-234.  doi: 10.1002/j.1538-7305.1956.tb02379.x.

[11]

M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes, volume 58 of Mathematics and its Applications (Soviet Series), Kluwer Academic Publishers Group, Dordrecht, 1991. Translated from the Russian by the authors. doi: 10.1007/978-94-011-3810-9.

[12]

O. Veblen and J. W. Young, Projective Geometry, Vol. 1, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1965.

show all references

References:
[1]

T. L. Alderson and A. A. Bruen, Coprimitive sets and inextendable codes, Des. Codes Cryptogr., 47 (2008), 113-124.  doi: 10.1007/s10623-007-9079-0.

[2]

S. Ball, Finite Geometry and Combinatorial Applications, volume 82. Cambridge University Press, 2015. doi: 10.1017/CBO9781316257449.

[3]

P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Information and Control, 23 (1973), 407-438.  doi: 10.1016/S0019-9958(73)80007-5.

[4]

H. Enomoto, P. Frankl, N. Ito and K. Nomura, Codes with given distances, Graphs and Combinatorics, 3 (1987), 25-38.  doi: 10.1007/BF01788526.

[5]

A. Haily and D. Harzalla, On binary linear codes whose automorphism group is trivial, Journal of Discrete Mathematical Sciences and Cryptography, 18 (2015), 495-512.  doi: 10.1080/09720529.2014.927650.

[6]

J. MacWilliams, A theorem on the distribution of weights in a systematic code, The Bell System Technical Journal, 42 (1963), 79-94.  doi: 10.1002/j.1538-7305.1963.tb04003.x.

[7]

J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, Journal of the ACM (JACM), 27 (1980), 701-717.  doi: 10.1145/322217.322225.

[8]

M. Shi, X. Li, A. Neri and P. Solé, How many weights can a cyclic code have?, arXiv: 1807.08418, 15, November, 2018.

[9]

M. Shi, H. Zhu, P. Solé and G. D. Cohen, How many weights can a linear code have?, Des. Codes Cryptogr., (2018). doi: 10.1007/s10623-018-0488-z.

[10]

D. Slepian, A class of binary signaling alphabets, Bell Labs Technical Journal, 35 (1956), 203-234.  doi: 10.1002/j.1538-7305.1956.tb02379.x.

[11]

M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes, volume 58 of Mathematics and its Applications (Soviet Series), Kluwer Academic Publishers Group, Dordrecht, 1991. Translated from the Russian by the authors. doi: 10.1007/978-94-011-3810-9.

[12]

O. Veblen and J. W. Young, Projective Geometry, Vol. 1, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1965.

Figure 1.   
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.   
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.   
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008
[2]

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

Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409
[4]

Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195
[5]

Nupur Patanker, Sanjay Kumar Singh. Generalized Hamming weights of toric codes over hypersimplices and squarefree affine evaluation codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021013
[6]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129
[7]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485
[8]

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

David Keyes. $\mathbb F_p$-codes, theta functions and the Hamming weight MacWilliams identity. Advances in Mathematics of Communications, 2012, 6 (4) : 401-418. doi: 10.3934/amc.2012.6.401
[10]

Chengju Li, Sunghan Bae, Shudi Yang. Some two-weight and three-weight linear codes. Advances in Mathematics of Communications, 2019, 13 (1) : 195-211. doi: 10.3934/amc.2019013
[11]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044
[12]

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

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[14]

Claude Carlet. Expressing the minimum distance, weight distribution and covering radius of codes by means of the algebraic and numerical normal forms of their indicators. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022047
[15]

Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233
[16]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[17]

Toshiharu Sawashima, Tatsuya Maruta. Nonexistence of some ternary linear codes with minimum weight -2 modulo 9. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021052
[18]

Canze Zhu, Qunying Liao. Constructions for several classes of few-weight linear codes and their applications. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022041
[19]

Tonghui Zhang, Hong Lu, Shudi Yang. Two-weight and three-weight linear codes constructed from Weil sums. Mathematical Foundations of Computing, 2022, 5 (2) : 129-144. doi: 10.3934/mfc.2021041
[20]

Alex L Castro, Wyatt Howard, Corey Shanbrom. Bridges between subriemannian geometry and algebraic geometry: Now and then. Conference Publications, 2015, 2015 (special) : 239-247. doi: 10.3934/proc.2015.0239

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (412)
  • HTML views (330)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy