Constructions of Several Classes of Optimal Linear Codes with Few Weights

LI Guanghui; LUO Gaojun; CAO Xiwang; GAO Jian

doi:10.11999/JEIT260984

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2026 >

LI Guanghui, LUO Gaojun, CAO Xiwang, GAO Jian. Constructions of Several Classes of Optimal Linear Codes with Few Weights[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260984

Citation:

LI Guanghui, LUO Gaojun, CAO Xiwang, GAO Jian. Constructions of Several Classes of Optimal Linear Codes with Few Weights[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260984

LI Guanghui, LUO Gaojun, CAO Xiwang, GAO Jian. Constructions of Several Classes of Optimal Linear Codes with Few Weights[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260984

Citation:

PDF( 0 KB)

Constructions of Several Classes of Optimal Linear Codes with Few Weights

doi: 10.11999/JEIT260984 cstr: 32379.14.JEIT260984

LI Guanghui^1
,,
LUO Gaojun^{1, 2
,
,},
CAO Xiwang^{2, 3},
GAO Jian¹

1.
School of Mathematics and Statistics, Shandong University of Technology, Zibo 255000, China
2.
School of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
3.
Key Laboratory of Mathematical Modelling and High Performance Computing of Air Vehicles MIIT, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

Funds: The Natural Science Foundation of Shandong Province (ZR2024YQ057, ZR2026QC0025), Jiangsu Funding Program for Excellent Postdoctoral Talent (2024ZB552), The National Natural Science Foundation of China (126011033, 12401690, 12571575, 12671652), China Post-Doctoral Science Foundation(GZC20242234)

Received Date: 2026-07-17
Accepted Date: 2026-10-16
Rev Recd Date: 2026-10-16

Available Online: 2026-10-26

Abstract

Abstract

Objective Few-weight linear codes have attracted considerable attention in coding theory due to their applications in secret sharing schemes, authentication codes, association schemes, and strongly regular graphs. In recent years, significant progress has been made in the construction of few-weight linear codes from defining sets, leading to some classes of linear codes with good parameters. Most existing constructions are based on specific types of defining sets or particular algebraic structures. Therefore, it is of interest to develop more general defining set constructions and establish corresponding criteria for code optimality. Motivated by this, we investigate linear codes over finite fields constructed from defining sets given by the complements of unions of subgroup cosets. As a consequence, several classes of few-weight linear codes are obtained, and explicit computable criteria are established for determining their optimality with respect to the Griesmer bound. Methods The main technique of this paper is a unified defining set construction based on the complements of unions of additive or multiplicative subgroup cosets. Linear codes are constructed within the Ding–Niederreiter framework, and character sum theory is employed to investigate their parameters. For additive subgroups, the orthogonality relations of additive characters are used to derive explicit expressions for the Hamming weights of codewords. For multiplicative subgroups, multiplicative characters and Gauss sums are applied to characterize the Hamming weights and determine the parameters of linear codes. By specializing the subgroup structures and exploiting explicit evaluations of character sums, several classes of linear codes with few weights are obtained. Furthermore, the Griesmer bound is employed to establish explicit computable criteria for optimality, which lead to the construction of several infinite families of optimal and distance-optimal linear codes. Results and Discussions The motivation of this paper is to search for optimal or distance-optimal linear codes with few weights. The results and discussions can be summarized as follows. Let $ G $ be an additive subgroup of $ {\mathbb{F}}_{{{q}^{k}}} $. When $ \mathcal{D}={\mathbb{F}}_{{{q}^{k}}}\backslash \cup _{i=1}^{h}({\alpha }_{i}+G) $, we derive an explicit expression for the Hamming weight of $ {\mathbf{c}}_{x} $in $ {\mathcal{C}}_{\mathcal{D}} $with the form (1) (see Lemma 3). Setting $ G=\{g\in {\mathbb{F}}_{{{q}^{k}}}\colon {\text{Tr}}_{{{q}^{k}}/q}(g)=0\} $, we compute the exact parameters of $ {\mathcal{C}}_{\mathcal{D}} $, and show that it is optimal with respect to the Griesmer bound (see Theorem 1). If $ G={\langle {{\gamma }_{1}},{{\gamma }_{2}},\cdots ,{{\gamma }_{s}}\rangle }_{{{\mathbb{F}}_{{{q}^{l}}}}} $, then we establish an explicit and computable criterion under which $ {\mathcal{C}}_{\mathcal{D}} $ is a (distance-)optimal linear code. (see Theorem 2). Let$ G $be a multiplicative subgroup of $ \mathbb{F}_{{q}^{k}}^{*} $. Suppose that $ \mathcal{D}=\mathbb{F}_{{q}^{k}}^{*}\backslash \cup _{i=1}^{h}{\alpha }_{i}G $ and $ {\mathcal{C}}_{\mathcal{D}} $ is the linear code defined in (1). We prove that the Hamming weight of $ {\mathbf{c}}_{x} $ in $ {\mathcal{C}}_{\mathcal{D}} $ can be depicted by Gauss sums (see Lemma 4). Using character sums over finite fields, we determine the parameters of the constructed linear codes (see Theorem 3). Subsequently, we characterize the optimality of these codes with respect to the Griesmer bound (see Proposition 1 and Proposition 2). All theoretical results are rigorously verified using Magma. Table 1 summarizes some optimal or distance-optimal linear codes satisfying the Griesmer bound. Conclusions Given a linear code$ {\mathcal{C}}_{\mathcal{D}} $, we mainly focused on the defining set having the form $ \mathcal{D}={\mathbb{F}}_{{{q}^{k}}}\backslash \cup _{i=1}^{h}({\alpha }_{i}+G) $ and$ \mathcal{D}=\mathbb{F}_{{q}^{k}}^{*}\backslash \cup _{i=1}^{h}{\alpha }_{i}G $. Within this framework, we proposed several classes of linear codes and then characterized their optimality in certain cases. As a result, we obtained several infinite families of optimal or distance-optimal linear codes with respect to the Griesmer bound. The construction of linear codes with few weights remains an interesting and challenging problem. In this regard, we list two open questions below, which we hope to address in future work. From Lemma 3, we derive an explicit expression for the Hamming weight of the codeword in $ {\mathcal{C}}_{\mathcal{D}} $. It would be nice if infinite families of optimal linear codes with few weights can be obtained from the defining set by appropriately selecting different additive subgroups $ G $. By Lemma 4, we find that the Hamming weights of the constructed codes can be expressed in terms of Gauss sums. In this paper, we focus on a specific class of Gauss sums and restrict our attention to multiplicative characters of prime order. It would be of interest to investigate other types of Gauss sums or multiplicative characters of composite order.
- Linear code,
- Optimality,
- Griesmer code,
- Finite field

FullText(HTML)

References(32)

References

[1]	CARLET C, DING Cunsheng, and YUAN Jin. Linear codes from perfect nonlinear mappings and their secret sharing schemes[J]. IEEE Transactions on Information Theory, 2005, 51(6): 2089–2102. doi: 10.1109/TIT.2005.847722.
[2]	DING Cunsheng and WANG Xuesong. A coding theory construction of new systematic authentication codes[J]. Theoretical Computer Science, 2005, 330(1): 81–99. doi: 10.1016/j.tcs.2004.09.011.
[3]	CALDERBANK A R and GOETHALS J M. Three-weight codes and association schemes[J]. Philips Journal of Research, 1984, 39(4/5): 143–152.
[4]	CALDERBANK R and KANTOR W M. The geometry of two-weight codes[J]. Bulletin of the London Mathematical Society, 1986, 18(2): 97–122. doi: 10.1112/blms/18.2.97.
[5]	杜小妮, 胡金霞, 金文刚, 等. 两类极小二元线性码的构造[J]. 电子与信息学报, 2022, 44(10): 3643–3649. doi: 10.11999/JEIT210720. DU Xiaoni, HU Jinxia, JIN Wengang, et al. Construction of two classes of minimal binary linear codes[J]. Journal of Electronics & Information Technology, 2022, 44(10): 3643–3649. doi: 10.11999/JEIT210720.
[6]	MESNAGER S and SINAK A. Minimal linear codes derived from weakly regular bent and plateaued functions[J]. Journal of Algebra and its Applications, 2024, 23(7): 2550077. doi: 10.1142/S021949882550077X.
[7]	JIN Wengang, LI Kangquan, and QU Longjiang. Several classes of minimal linear codes from weakly regular and non-weakly regular bent functions[J]. Discrete Applied Mathematics, 2025, 373: 53–76. doi: 10.1016/j.dam.2025.04.044.
[8]	JIN Wengang, LI Kangquan, and QU Longjiang. Several new classes of self-orthogonal minimal linear codes violating the Ashikhmin-Barg condition[J]. IEEE Transactions on Information Theory, 2025, 71(10): 7699–7714. doi: 10.1109/TIT.2025.3600002.
[9]	DING Cunsheng and NIEDERREITER H. Cyclotomic linear codes of order 3[J]. IEEE Transactions on Information Theory, 2007, 53(6): 2274–2277. doi: 10.1109/TIT.2007.896886.
[10]	ZHOU Zijian, LI Kangquan, and ZHOU Yue. Topological invariants for linear codes and APN functions[J]. IEEE Transactions on Information Theory, 2025, 71(9): 6771–6784. doi: 10.1109/TIT.2025.3583010.
[11]	ZHOU Zhengchun, LI Nian, FAN Cuiling, et al. Linear codes with two or three weights from quadratic Bent functions[J]. Designs, Codes and Cryptography, 2016, 81(2): 283–295. doi: 10.1007/s10623-015-0144-9.
[12]	HU Shupeng, LI Fei, and LI Xiumei. Weight hierarchies of a class of three-weight $ p $-ary linear codes from inhomogeneous quadratic functions[J]. Applicable Algebra in Engineering, Communication and Computing, 2025, 36(5): 877–896. doi: 10.1007/s00200-024-00645-7.
[13]	LI Xiumei, CHEN Zongxi, and LI Fei. Some three-weight linear codes and their complete weight enumerators and weight hierarchies[J]. Designs, Codes and Cryptography, 2026, 94(2): 34. doi: 10.1007/s10623-025-01747-0.
[14]	TANG Chunming, LI Nian, QI Yanfeng, et al. Linear codes with two or three weights from weakly regular bent functions[J]. IEEE Transactions on Information Theory, 2016, 62(3): 1166–1176. doi: 10.1109/TIT.2016.2518678.
[15]	MESNAGER S and SINAK A. Several classes of minimal linear codes with few weights from weakly regular plateaued functions[J]. IEEE Transactions on Information Theory, 2020, 66(4): 2296–2310. doi: 10.1109/TIT.2019.2956130.
[16]	LI Kangquan, LI Chunlei, HELLESETH T, et al. Binary linear codes with few weights from two-to-one functions[J]. IEEE Transactions on Information Theory, 2021, 67(7): 4263–4275. doi: 10.1109/TIT.2021.3068743.
[17]	MESNAGER S, QIAN Liqin, CAO Xiwang, et al. Several families of binary minimal linear codes from two-to-one functions[J]. IEEE Transactions on Information Theory, 2023, 69(5): 3285–3301. doi: 10.1109/TIT.2023.3236955.
[18]	HYUN J Y, LEE J, and LEE Y. Infinite families of optimal linear codes constructed from simplicial complexes[J]. IEEE Transactions on Information Theory, 2020, 66(11): 6762–6773. doi: 10.1109/TIT.2020.2993179.
[19]	HU Zhao, XU Yunge, LI Nian, et al. New constructions of optimal linear codes from simplicial complexes[J]. IEEE Transactions on Information Theory, 2024, 70(3): 1823–1835. doi: 10.1109/TIT.2023.3305609.
[20]	HYUN J Y, KIM H K, WU Yansheng, et al. Optimal minimal linear codes from posets[J]. Designs, Codes and Cryptography, 2020, 88(12): 2475–2492. doi: 10.1007/s10623-020-00793-0.
[21]	HU Zhao, LI Nian, ZENG Xiangyong, et al. A subfield-based construction of optimal linear codes over finite fields[J]. IEEE Transactions on Information Theory, 2022, 68(7): 4408–4421. doi: 10.1109/TIT.2022.3163651.
[22]	柴烨, 朱士信, 开晓山. 一类线性码及其子域码[J]. 电子与信息学报, 2026, 48(1): 222–229. doi: 10.11999/JEIT250775. CHAI Ye, ZHU Shixin, and KAI Xiaoshan. A family of linear codes and their subfield codes[J]. Journal of Electronics & Information Technology, 2026, 48(1): 222–229. doi: 10.11999/JEIT250775.
[23]	LUO Gaojun and LING San. Application of optimal $ p $-ary linear codes to alphabet-optimal locally repairable codes[J]. Designs, Codes and Cryptography, 2022, 90(5): 1271–1287. doi: 10.1007/s10623-022-01040-4.
[24]	QIU Jing and FU Fangwei. Some new constructions of optimal linear codes and alphabet-optimal (γ, δ)-locally repairable codes[J]. Designs, Codes and Cryptography, 2024, 92(10): 2971–2991. doi: 10.1007/s10623-024-01423-9.
[25]	HU Zhao, QIU Mingxiu, LI Nian, et al. Several classes of linear codes with few weights derived from Weil sums[J]. Finite Fields and Their Applications, 2025, 108: 102679. doi: 10.1016/j.ffa.2025.102679.
[26]	HYUN J Y, KIM H K, and NA M. Optimal non-projective linear codes constructed from down-sets[J]. Discrete Applied Mathematics, 2019, 254: 135–145. doi: 10.1016/j.dam.2018.07.007.
[27]	CHENG Yingjie, CAO Xiwang, and LUO Gaojun. Three new constructions of optimal linear codes with few weights[J]. Computational and Applied Mathematics, 2023, 42(7): 321. doi: 10.1007/s40314-023-02472-x.
[28]	HUFFMAN W C and PLESS V. Fundamentals of Error-Correcting Codes[M]. Cambridge: Cambridge University Press, 2003: 53–95. doi: 10.1017/CBO9780511807077.
[29]	GRIESMER J H. A bound for error-correcting codes[J]. IBM Journal of Research and Development, 1960, 4(5): 532–542. doi: 10.1147/rd.45.0532.
[30]	SOLOMON G and STIFFLER J J. Algebraically punctured cyclic codes[J]. Information and Control, 1965, 8(2): 170–179. doi: 10.1016/S0019-9958(65)90080-X.
[31]	LIDL R and NIEDERREITER H. Finite Fields[M]. Reading: Addison-Wesley, 1983: 189.
[32]	BERNDT B C, EVANS R J, and WILLIAMS K S. Gauss and Jacobi Sums[M]. New York: Wiley, 1998: 364.