Constructions of Several Classes of Optimal Linear Codes with Few Weights
-
摘要: 少重量线性码在秘密共享、强正则图、关联方案和认证码等领域具有广泛应用。该文提出一种基于子群$ G $的陪集分解构造线性码的方法。$ G $为加法子群时，给出线性码中码字汉明重量的表达式。此外，建立了可显式计算的判定准则，用于判断线性码是否关于Griesmer界为最优码或距离最优码。结果表明，所构造线性码为最优少重量码或距离最优码。$ G $为乘法子群时，证明码字的汉明重量可以通过Gauss和进行刻画。利用有限域上特征标理论，明确所构造线性码的参数，由此产生了一类最优常重量线性码。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. -
Key words:
- Linear code /
- Optimality /
- Griesmer code /
- Finite field
-
表 1 几类由式(1)定义的最优或距离最优线性码
参数 性质 注释 $ {\left[\dfrac{{q}^{m}-|\Delta |}{q-1},m,{{q}^{m-1}}-\displaystyle\sum \nolimits_{i=1}^{h}{q}^{|{{\mathcal{A}}_{i}}|-1}\right]}_{q} $ (距离)最优 [18，定理20]$ q=2 $；[23，定理3.2]$ q=p $；
[19，定理1]任意$ q $$ {[{{q}^{m}}-|{{\Omega }_{1}}|,m,(q-1)({{q}^{m-1}}-\displaystyle\sum \nolimits_{i=1}^{h}{q}^{{{r}_{i}}-1})]}_{q} $ (距离)最优 [21，定理1]$ {r}_{i}|m $ $ {[{{q}^{m}}-(h+1){{q}^{r}},m,(q-1)({{q}^{k-1}}-(h+1){{q}^{r-1}})]}_{q} $ 最优 [21，定理2]$ q\geq h+1 $，$ r|m $ $ {[{{q}^{m}}-(h+1){{q}^{r}},m,(q-1){{q}^{m-1}}-h{{q}^{r}}]}_{q} $ 距离最优 [21，定理2]$ q \lt h+1 $，$ r|m $ $ {[{{q}^{m}}-{{q}^{r}},m,(q-1)({{q}^{m-1}}-{{q}^{r-1}})]}_{q} $ 最优 [21，定理3]$ r|m $ $ {[s\dfrac{{p}^{m}-1}{p-1}-\displaystyle\sum \nolimits_{r=1}^{s}|{\mathcal{D}_{r}^{c}}|,m,s{{p}^{m-1}}-\displaystyle\sum \nolimits_{i=1}^{l}{p}^{|{{\mathcal{A}}_{i}}|-1}]}_{p} $ (距离)最优 [24，定理2] $ {[{{q}^{2}}-1,2,{{q}^{2}}-q]}_{q} $ 最优 [25，推论1] $ {[s{{q}^{2}},3,s({{q}^{2}}-q)]}_{q} $ 最优 [25，推论1，推论2]$ s\in \{1,2\} $ $ {[{{p}^{n}}-s(r+1),n,{{p}^{n}}-{{p}^{n-1}}-s(r+1)+1]}_{p} $ 最优 [26，定理4.1，定理4.4，定理4.7]$ s\in \{1,2,3\} $ $ {[{{p}^{n}}-s(r+1),n,{{p}^{n}}-{{p}^{n-1}}-(s-1)r-p+1]}_{p} $ 最优 [26，定理4.11, 定理4.14]$ s\in \{p-2,p-1\} $ $ {[{{q}^{s}}-1-\alpha ,s,{{q}^{s-1}}(q-1)-\displaystyle\sum \nolimits_{i=1}^{h}\dfrac{q-1}{N}{{q}^{{{r}_{i}}-1}}]}_{q} $ 距离最优 [27，定理3.1]$ {r}_{i}|s $ $ {[{{q}^{s}}-1-\dfrac{h({q}^{r}-1)}{N},s,{{q}^{s-1}}(q-1)-\dfrac{h{q}^{r-1}(q-1)}{N}]}_{q} $ (距离)最优 [27，定理3.4]$ r|s $ $ {[{{q}^{k-1}}(q-h),k,(q-1)(q-h){{q}^{k-2}}]}_{q} $ 最优 定理1 $ {[{{q}^{k}}-h{{q}^{ls}},k,(q-1)({{q}^{k-1}}-h{{q}^{ls-1}})]}_{q} $ 最优 定理 2 $ {[{{q}^{k}}-h{{q}^{ls}},k,(q-1){{q}^{k-1}}+{{q}^{ls}}(1-h)]}_{q} $ 距离最优 定理 2 $ {[\dfrac{(N-h)({q}^{k}-1)}{N},k,\dfrac{(q-1)(N-h){q}^{k-1}}{N}]}_{q} $ 最优 定理3 $ {[\dfrac{(N-h)({q}^{k}-1)}{N},k,\dfrac{(q-1)({q}^{k}(N-h)-h{q}^{k/2})}{qN}]}_{q} $ 距离最优 定理3 其中$ |{\Omega }_{1}|=\displaystyle\sum\nolimits_{\varnothing \neq S\subseteq \Upsilon }{(-1)}^{|S|-1}{q}^{{{r}_{S}}} $，$ \mathcal{D}_{r}^{c}=\cup _{j=1}^{{l}_{r}}{P}_{{\mathcal{B}_{j}^{(r)}}} $，$ |\Delta |={\sum }_{\varnothing \neq S\subseteq \mathcal{A}}{(-1)}^{|S|-1}{q}^{|\cap S|} $ 
下载: 导出CSV
-
[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. -
下载: 
表(1)
计量
- 文章访问数: 20
- HTML全文浏览量: 1
- PDF下载量: 0
- 被引次数: 0
