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]

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

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]

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

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

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

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

Fengwei Li, Qin Yue, Fengmei Liu. The weight distributions of constacyclic codes. Advances in Mathematics of Communications, 2017, 11 (3) : 471-480. doi: 10.3934/amc.2017039
[14]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021
[15]

Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, Wolfgang Willems. Algebraic structures of MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 499-510. doi: 10.3934/amc.2016021
[16]

Carlos Durán, Diego Otero. The projective Cartan-Klein geometry of the Helmholtz conditions. Journal of Geometric Mechanics, 2018, 10 (1) : 69-92. doi: 10.3934/jgm.2018003
[17]

Yiwei Liu, Zihui Liu. On some classes of codes with a few weights. Advances in Mathematics of Communications, 2018, 12 (2) : 415-428. doi: 10.3934/amc.2018025
[18]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[19]

Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87
[20]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (80)
  • HTML views (276)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences