A New Upper Bound for Linear Codes and Vanishing Partial Weight Distributions
Authors: 
Hao Chen, Conghui XieAuthors Info & Claims
Pages 8713 - 8722
Abstract
In this paper, we give a new upper bound on sizes of linear codes related to weight distributions of codes as follows. Let C be a linear <inline-formula> <tex-math notation="LaTeX">$[n,k,d]_{q}$ </tex-math></inline-formula> code, such that, between d and <inline-formula> <tex-math notation="LaTeX">$d\left ({{1+\frac {1}{q-1}}}\right)-1$ </tex-math></inline-formula>, the largest weight of codewords in C is the weight <inline-formula> <tex-math notation="LaTeX">$d\left ({{1+\frac {1}{q-1}}}\right)-1-v$ </tex-math></inline-formula>, then <inline-formula> <tex-math notation="LaTeX">$k \leq n-d\left ({{1+\frac {1}{q-1}}}\right)+2+v$ </tex-math></inline-formula>. Some infinite families of linear codes with arbitrary minimum distances attaining this bound are constructed. This bound is stronger than the Singleton bound for linear codes. Hence we prove that there is no codeword of weights in the range <inline-formula> <tex-math notation="LaTeX">$\left [{{\frac {qd}{q-1}-v,\frac {qd}{q-1}-1}}\right]$ </tex-math></inline-formula> for a linear <inline-formula> <tex-math notation="LaTeX">$[n,k,d]_{q}$ </tex-math></inline-formula> code, if <inline-formula> <tex-math notation="LaTeX">$v=\frac {qd}{q-1}+k-n-2 \geq 2$ </tex-math></inline-formula>. This is the first such kind of result, which concludes vanishing partial weight distributions from four parameters <inline-formula> <tex-math notation="LaTeX">$n,k,d$ </tex-math></inline-formula> and q. Then we give vanishing partial weight distribution results for many best known linear codes, some almost MDS codes, general small Griesmer defect codes, some BCH codes, and some cyclic codes. Upper bounds on the number of nonzero weights of binary Griesmer codes and some small Singleton defect codes are also given.
References
[1]
T. L. Alderson, “On the weights of general MDS codes,” IEEE Trans. Inf. Theory, vol. 66, no. 9, pp. 5414–5418, Sep. 2020.
[2]
A. Ashikhmin and A. Barg, “Minimal vectors in linear codes,” IEEE Trans. Inf. Theory, vol. 44, no. 5, pp. 2010–2017, Sep. 1998.
[3]
E. F. Assmus and H. F. Mattson, “New 5-designs,” J. Combinat. Theory, vol. 6, no. 2, pp. 122–151, Mar. 1969.
[4]
L. D. Baumert and R. J. McEliece, “A note on the Griesmer bound,” IEEE Trans. Inf. Theory, vol. IT-19, no. 1, pp. 134–135, Jan. 1973.
[5]
M. A. De Boer, “Almost MDS codes,” Designs, Codes Cryptogr., vol. 9, no. 2, pp. 143–155, Oct. 1996.
[6]
R. C. Bose and D. K. Ray-Chaudhuri, “On a class of error correcting binary group codes,” Inf. Control, vol. 3, no. 1, pp. 68–79, Mar. 1960.
[7]
R. C. Bose and D. K. Ray-Chaudhuri, “Further results on error correcting binary group codes,” Inf. Control, vol. 3, no. 3, pp. 279–290, Sep. 1960.
[8]
R. Calderbank and W. M. Kantor, “The geometry of two-weight codes,” Bull. London Math. Soc., vol. 18, no. 2, pp. 97–122, Mar. 1986.
[9]
C. H. Chan and M. Xiong, “On the complete weight distribution of subfield subcodes of algebraic-geometric codes,” IEEE Trans. Inf. Theory, vol. 65, no. 11, pp. 7079–7086, Nov. 2019.
[10]
B. Chen and G. Zhang, “A tight upper bound on the number of non-zero weights of a cyclic code,” IEEE Trans. Inf. Theory, vol. 69, no. 2, pp. 995–1004, Feb. 2023.
[11]
H. Chen, L. Qu, C. Li, S. Lyu, L. Xu, and M. Zhou, “Generalized singleton type upper bounds,” IEEE Trans. Inf. Theory, vol. 70, no. 5, pp. 3298–3308, May 2024.
[12]
H. Chen, “Many non-Reed–Solomon type MDS codes from arbitrary genus algebraic curves,” IEEE Trans. Inf. Theory, vol. 70, no. 7, pp. 4856–4864, Jul. 2024.
[13]
P. Delsarte, “Four fundamental parameters of a code and their combinatorial significance,” Inf. Control, vol. 23, no. 5, pp. 407–438, Dec. 1973.
[14]
C. Ding and J. Yang, “Hamming weights in irreducible cyclic codes,” Discrete Math., vol. 313, no. 4, pp. 434–446, Feb. 2013.
[15]
C. Ding, “Linear codes from some 2-designs,” IEEE Trans. Inf. Theory, vol. 61, no. 6, pp. 3265–3275, Jun. 2015.
[16]
K. Ding and C. Ding, “A class of two-weight and three-weight codes and their applications in secret sharing,” IEEE Trans. Inf. Theory, vol. 61, no. 11, pp. 5835–5842, Nov. 2015.
[17]
S. M. Dodunekov and N. L. Manev, “Minimum possible block length of a linear code for some distances,” Problems Inf. Transmiss., vol. 20, no. 1, pp. 12–18, Jan. 1984.
[18]
S. Dodunekov and I. Landgev, “On near-MDS codes,” J. Geometry, vol. 54, nos. 1–2, pp. 30–43, Nov. 1995.
[19]
S. R. Ghorpade and G. Lachaud, “Hyperplane sections of Grassmannians and the number of MDS linear codes,” Finite Fields Their Appl., vol. 7, no. 4, pp. 468–506, Oct. 2001.
[20]
M. Grassl. Bounds Minimum Distance Linear Codes Quantum Codes. Accessed: Apr. 20, 2024. [Online]. Available: https://www.codetables.de
[21]
J. H. Griesmer, “A bound for error-correcting codes,” IBM J. Res. Develop., vol. 4, no. 5, pp. 532–542, Nov. 1960.
[22]
C. Güneri, “Optimal binary linear complementary pairs from Solomon–Stiffler codes,” IEEE Trans. Inf. Theory, vol. 69, no. 10, pp. 6512–6517, Oct. 2023.
[23]
T. Helleseth and H. C. A van Tilborg, “The classification of all (145, 7, 72) binary linear codes,” Dept. Math. Comput. Sci., Eindhoven Univ. Tech., Eindhoven, The Netherlands, Tech. Rep. 80-WSK-01, Apr. 1980, vol. 80.
[24]
T. Helleseth and H. van Tilborg, “A new class of codes meeting the Griesmer bound,” IEEE Trans. Inf. Theory, vol. IT-27, no. 5, pp. 548–555, Sep. 1981.
[25]
T. Helleseth, “New constructions of codes meeting the Griesmer bound,” IEEE Trans. Inf. Theory, vol. IT-29, no. 3, pp. 434–439, May 1983.
[26]
Z. Heng and Q. Yue, “Several classes of cyclic codes with either optimal three weights or a few weights,” IEEE Trans. Inf. Theory, vol. 62, no. 8, pp. 4501–4513, Aug. 2016.
[27]
R. Hill, “Optimal linear codes,” in Cryptography and Coding II. London, U.K.: Oxford Univ. Press, 1992, pp. 75–104.
[28]
A. Hocquenghem, “Codes correcteurs d’erreurs,” Chiffres, vol. 2, pp. 147–156, Jan. 1959.
[29]
Z. Hu, N. Li, X. Zeng, L. Wang, and X. Tang, “A subfield-based construction of optimal linear codes over finite fields,” IEEE Trans. Inf. Theory, vol. 68, no. 7, pp. 4408–4421, Jul. 2022.
[30]
Z. Hu, Y. Xu, N. Li, X. Zeng, L. Wang, and X. Tang, “New constructions of optimal linear codes from simplicial complexes,” IEEE Trans. Inf. Theory, vol. 70, no. 3, pp. 1823–1835, Mar. 2024.
[31]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes. Cambridge, U.K.: Cambridge Univ. Press, 2003.
[32]
J. Y. Hyun, J. Lee, and Y. Lee, “Infinite families of optimal linear codes constructed from simplicial complexes,” IEEE Trans. Inf. Theory, vol. 66, no. 11, pp. 6762–6773, Nov. 2020.
[33]
T. Kasami, T. Fujiwara, and S. Lin, “An approximation to the weight distribution of binary linear codes,” IEEE Trans. Inf. Theory, vol. IT-31, no. 6, pp. 769–780, Nov. 1985.
[34]
Y. Kageyama and T. Maruta, “On the geometric construction of optimal linear codes,” Des. Codes Cryptogr., vol. 81, pp. 469–480, Jan. 2016.
[35]
D. Kawabata and T. Maruta, “On the nonexistence of ternary linear codes attaining the Griesmer bound,” Designs, Codes Cryptogr., vol. 90, no. 4, pp. 947–956, Feb. 2022.
[36]
I. Landjev and A. Rousseva, “The main conjecture for near-MDS codes,” in Proc. 9th Int. Workshop Coding Cryptogr. (WCC), 2015. [Online]. Available: https://hal.inria.fr/hal-01276222/document
[37]
F. Li, Q. Yue, and F. Liu, “The weight distribution of a class of cyclic codes containing a subclass with optimal parameters,” Finite Fields Their Appl., vol. 45, pp. 183–202, May 2017.
[38]
J. H. van Lint, Introduction to Coding Theory, 3rd ed., Berlin, Germany: Springer, 1999.
[39]
G. Luo, X. Cao, M. F. Ezerman, and S. Ling, “On the weights of linear codes with prescribed automorphisms,” IEEE Trans. Inf. Theory, vol. 70, no. 7, pp. 4983–4989, Jul. 2024.
[40]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, vol. 16, 3rd ed., Amsterdam, The Netherlands: North Holland, 1977.
[41]
T. Maruta. Webpage Known Griesmer Almost Griesmer Codes. Accessed: Apr. 20, 2024. [Online]. Available: https://mars39.lomo.jp/opu/griesmer.html
[42]
V. Miloslavskaya, B. Vucetic, and Y. Li, “Computing the partial weight distribution of punctured, shortened, precoded polar codes,” IEEE Trans. Commun., vol. 70, no. 11, pp. 7146–7159, Nov. 2022.
[43]
S. Noguchi, X.-N. Lu, M. Jimbo, and Y. Miao, “BCH codes with minimum distance proportional to code length,” SIAM J. Discrete Math., vol. 35, no. 1, pp. 179–193, Jan. 2021.
[44]
J. Pang, H. Mahdavifar, and S. S. Pradhan, “New bounds on the size of binary codes with large minimum distances,” IEEE J. Sel. Areas Inf. Theory, vol. 4, pp. 219–230, 2023.
[45]
E. Prange, Cyclic Error-Correcting Codes Two Symbols, document TN-57-013, Air Force Cambridge Res. Lab, Cambridge, MA, USA, 1957.
[46]
M. Sala and A. Tamponi, “A linear programming estimate of the weight distribution of BCH (255,k),” IEEE Trans. Inf. Theory, vol. 46, no. 6, pp. 2235–2237, Sep. 2000.
[47]
M. Shi, H. Zhu, P. Solé, and G. D. Cohen, “How many weights can a linear code have?,” Designs, Codes Cryptogr., vol. 87, no. 1, pp. 87–95, Jan. 2019.
[48]
M. Shi, A. Neri, and P. Solé, “How many weights can a quasi-cyclic code have?,” IEEE Trans. Inf. Theory, vol. 66, no. 11, pp. 6855–6862, Nov. 2020.
[49]
G. Solomon and J. J. Stiffler, “Algebraically punctured cyclic codes,” Inf. Control, vol. 8, no. 2, pp. 170–179, Apr. 1965.
[50]
H. N. Ward, “Divisibility of codes meeting the Griesmer bound,” J. Combinat. Theory A, vol. 83, no. 1, pp. 79–93, Jul. 1998.
[51]
S. Zhu, Z. Sun, and X. Kai, “A class of narrow-sense BCH codes,” IEEE Trans. Inf. Theory, vol. 65, no. 8, pp. 4699–4714, Aug. 2019.
Index Terms
- A New Upper Bound for Linear Codes and Vanishing Partial Weight Distributions
Index terms have been assigned to the content through auto-classification.
Recommendations
Codes with the same coset weight distributions as the Z4-linear Goethals codes
We study the coset weight distributions of the family of Z4 -linear Goethals-like codes of length N=2m+1, m⩾3 odd, constructed by Helleseth, Kumar, and Shanbhag (see Designs, Codes and Cryptography, vol.17, no.1-3, p.246-62, 1999). These codes have ...
Minihypers and Linear Codes Meeting the Griesmer Bound: Improvements to Results of Hamada, Helleseth and Maekawa
This article improves results of Hamada, Helleseth and Maekawa on minihypers in projective spaces and linear codes meeting the Griesmer bound. In [10,12], it was shown that any \{\sum^{t-1}_{i=0}\epsilon_i v_{i+1},\sum^{t-1}_{i=0}\epsilon_i v_i;t,q\} -...
Codes with the Same Weight Distributions as the Goethals Codes and the Delsarte-Goethals Codes
The Goethals code is a binary nonlinear code of length 2^{m+1} which has 2^{2^{m+1}-3m-2} codewords and minimum Hamming distance 8 for any odd m \geq 3 . Recently, Hammons et. al. showed that codes with the same weight distribution can be obtained via ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
0018-9448 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 26 August 2024
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in