Construction of Maximum Distance Separable Codes and Near Maximum Distance Separable Codes Based on Cyclic Subgroup of <inline-formula><tex-math id="M2">\begin{document}$ \mathbb{F}_{{q}^{2}}^{*} $\end{document}</tex-math></inline-formula>

DU Xiaoni; XUE Jing; QIAO Xingbin; ZHAO Ziwei

doi:10.11999/JEIT251204

Article Contents

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

DU Xiaoni, XUE Jing, QIAO Xingbin, ZHAO Ziwei. Construction of Maximum Distance Separable Codes and Near Maximum Distance Separable Codes Based on Cyclic Subgroup of $ \mathbb{F}_{{q}^{2}}^{*} $[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251204

Citation:

DU Xiaoni, XUE Jing, QIAO Xingbin, ZHAO Ziwei. Construction of Maximum Distance Separable Codes and Near Maximum Distance Separable Codes Based on Cyclic Subgroup of $ \mathbb{F}_{{q}^{2}}^{*} $[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251204

Citation:

DU Xiaoni, XUE Jing, QIAO Xingbin, ZHAO Ziwei. Construction of Maximum Distance Separable Codes and Near Maximum Distance Separable Codes Based on Cyclic Subgroup of $ \mathbb{F}_{{q}^{2}}^{*} $[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251204

PDF( 888 KB)

Construction of Maximum Distance Separable Codes and Near Maximum Distance Separable Codes Based on Cyclic Subgroup of $ \mathbb{F}_{{q}^{2}}^{*} $

doi: 10.11999/JEIT251204 cstr: 32379.14.JEIT251204

DU Xiaoni^{1, 2, 3},
XUE Jing^{1
,
,},
QIAO Xingbin^{1, 2},
ZHAO Ziwei¹

1.
College of Mathematics and Statistic, Northwest Normal University, Lanzhou 730070, China
2.
Key Laboratory of Cryptography and Data Analytics, Northwest Normal University, Lanzhou 730070, China
3.
Gansu Provincial Research Center for Basic Disciplines of Mathematics and Statistics, Lanzhou 730070, China

Funds: The National Natural Science Foundation of China (62172337, 62562055), The Key Project of Gansu Natural Science Foundation (23JRRA685), The Funds for Innovative Fundamental Research Group Project of Gansu Province (23JRRA684)

Received Date: 2025-11-14
Accepted Date: 2026-01-12
Rev Recd Date: 2026-01-08

Available Online: 2026-01-25

Abstract

Abstract

Objective The demand for higher performance and efficiency in error-correcting codes has increased with the rapid development of modern communication technologies. These codes detect and correct transmission errors. Because of their algebraic structure, straightforward encoding and decoding, and ease of implementation, linear codes are widely used in communication systems. Their parameters follow classical bounds such as the Singleton bound: for a linear code with length $ n $ and dimension $ k $, the minimum distance $ d $ satisfies $ d\leq n-k+1 $. When $ d=n-k+1 $, the code is a Maximum Distance Separable (MDS) code. MDS codes are applied in distributed storage systems and random error channels. If $ d=n-k $, the code is Almost MDS (AMDS); when both a code and its dual are AMDS, the code is Near MDS (NMDS). NMDS codes have geometric properties that are useful in cryptography and combinatorics. Extensive research has focused on constructing structurally simple, high-performance MDS and NMDS codes. This paper constructs several families of MDS and NMDS codes of length $ q+3 $ over the finite field $ {\mathbb{F}}_{{{q}^{2}}} $ of even characteristic using the cyclic subgroup $ {U}_{q+1} $. Several families of optimal Locally Repairable Codes (LRCs) are also obtained. LRCs support efficient failure recovery by accessing a small set of local nodes, which reduces repair overhead and improves system availability in distributed and cloud-storage settings. Methods In 2021, Wang et al. constructed NMDS codes of dimension 3 using elliptic curves over $ {\mathbb{F}}_{q} $. In 2023, Heng et al. obtained several classes of dimension-4 NMDS codes by appending appropriate column vectors to a base generator matrix. In 2024, Ding et al. presented four classes of dimension-4 NMDS codes, determined the locality of their dual codes, and constructed four classes of distance-optimal and dimension-optimal LRCs. Building on these works, this paper uses the unit circle $ {U}_{q+1} $ in $ {\mathbb{F}}_{{{q}^{2}}} $ and elliptic curves to construct generator matrices. By augmenting these matrices with two additional column vectors, several classes of MDS and NMDS codes of length $ q+3 $ are obtained. The locality of the constructed NMDS codes is also determined, yielding several classes of optimal LRCs. Results and Discussions In 2023, Heng et al. constructed generator matrices with second-row entries in $ \mathbb{F}_{q}^{*} $ and with the remaining entries given by nonconsecutive powers of the second-row elements. In 2025, Yin et al. extended this approach by constructing generator matrices using elements of $ {U}_{q+1} $ and obtained infinite families of MDS and NMDS codes. Following this direction, the present study expands these matrices by appending two column vectors whose elements lie in $ {\mathbb{F}}_{{{q}^{2}}} $. The resulting matrices generate several classes of MDS and NMDS codes of length $ q+3 $. Several classes of NMDS codes with identical parameters but different weight distributions are also obtained. Computing the minimum locality of the constructed NMDS codes shows that some are optimal LRCs satisfying the Singleton-like, Cadambe–Mazumdar, Plotkin-like, and Griesmer-like bounds. All constructed MDS codes are Griesmer codes, and the NMDS codes are near Griesmer. These results show that the proposed constructions are more general and unified than earlier approaches. Conclusions This paper constructs several families of MDS and NMDS codes of length $ q+3 $ over $ {\mathbb{F}}_{{{q}^{2}}} $ using elements of the unit circle $ {U}_{q+1} $ and oval polynomials, and by appending two additional column vectors with entries in $ {\mathbb{F}}_{q} $. The minimum locality of the constructed NMDS codes is analyzed, and some of these codes are shown to be optimal LRCs. The framework generalizes earlier constructions, and the resulting codes are optimal or near-optimal with respect to the Griesmer bound.
- Maximum Distance Separable(MDS) code,
- NMDS code,
- weight enumerator,
- locally recoverable code,
- Griesmer bound

FullText(HTML)

References(19)

References

[1]	SUN Huan, YUE Qin, and JIA Xue. The weight distributions of several classes of few-weight linear codes[J]. Advances in Mathematics of Communications, 2025, 19(1): 69–90. doi: 10.3934/amc.2023037.
[2]	QIAO Xingbin and DU Xiaoni. Weight distributions and weight hierarchies of a class of binary linear codes with a few weights[J]. Advances in Mathematics of Communications, 2025, 19(1): 245–258. doi: 10.3934/amc.2023056.
[3]	高健, 张耀宗, 孟祥蕊, 等. 几类指标为2的不可约拟循环码的重量分布[J]. 电子与信息学报, 2022, 44(12): 4312–4318. doi: 10.11999/JEIT211104. GAO Jian, ZHANG Yaozong, MENG Xiangrui, et al. Weight distributions of some classes of irreducible quasi-cyclic codes of index 2[J]. Journal of Electronics & Information Technology, 2022, 44(12): 4312–4318. doi: 10.11999/JEIT211104.
[4]	DINH Haiquang, WANG Xiaoqiang, LIU Hongwei, et al. Hamming distances of constacyclic codes of length $ 3{p}^{s} $ and optimal codes with respect to the Griesmer and Singleton bounds[J]. Finite Fields and Their Applications, 2021, 70: 101794. doi: 10.1016/j.ffa.2020.101794.
[5]	WANG Qiuyan and HENG Ziling. Near MDS codes from oval polynomials[J]. Discrete Mathematics, 2021, 344(4): 112277. doi: 10.1016/j.disc.2020.112277.
[6]	TAN Pan, FAN Cuiling, DING Cunsheng, et al. The minimum locality of linear codes[J]. Designs, Codes and Cryptography, 2023, 91(1): 83–114. doi: 10.1007/s10623-022-01099-z.
[7]	HENG Ziling and WANG Xinran. New infinite families of near MDS codes holding $ t $-designs[J]. Discrete Mathematics, 2023, 346(10): 113538. doi: 10.1016/j.disc.2023.113538.
[8]	YIN Yanan and YAN Haode. Constructions of several families of MDS codes and NMDS codes[J]. Advances in Mathematics of Communications, 2025, 19(4): 1222–1247. doi: 10.3934/amc.2024051.
[9]	DING Yun, LI Yang, and ZHU Shixin. Four new families of NMDS codes with dimension 4 and their applications[J]. Finite Fields and Their Applications, 2024, 99: 102495. doi: 10.1016/j.ffa.2024.102495.
[10]	LUO Gaojun and CAO Xiwang. Constructions of optimal binary locally recoverable codes via a general construction of linear codes[J]. IEEE Transactions on Communications, 2021, 69(8): 4987–4997. doi: 10.1109/TCOMM.2021.3083320.
[11]	TANG Chunming and DING Cunsheng. An infinite family of linear codes supporting 4-designs[J]. IEEE Transactions on Information Theory, 2021, 67(1): 244–254. doi: 10.1109/TIT.2020.3032600.
[12]	HUFFMAN W C and PLESS V. Fundamentals of Error-Correcting Codes[M]. Cambridge: Cambridge University Press, 2003: 71–72. doi: 10.1017/CBO9780511807077.
[13]	DODUNEKOV S and LANDGEV I. On near-MDS codes[J]. Journal of Geometry, 1995, 54(1): 30–43. doi: 10.1007/BF01222850.
[14]	FALDUM A and WILLEMS W. Codes of small defect[J]. Designs, Codes and Cryptography, 1997, 10(3): 341–350. doi: 10.1023/A:1008247720662.
[15]	LIDL R and NIEDERREITER H. Finite Fields[M]. 2nd ed. Cambridge: Cambridge University Press, 1997: 268–342.
[16]	GOPALAN P, HUANG Cheng, SIMITCI H, et al. On the locality of codeword symbols[J]. IEEE Transactions on Information Theory, 2012, 58(11): 6925–6934. doi: 10.1109/TIT.2012.2208937.
[17]	CADAMBE V and MAZUMDAR A. An upper bound on the size of locally recoverable codes[C]. 2013 International Symposium on Network Coding (NetCod), Calgary, Canada, 2013: 1–5. doi: 10.1109/NetCod.2013.6570829.
[18]	HAO Jie, XIA Shutao, SHUM K W, et al. Bounds and constructions of locally repairable codes: Parity-check matrix approach[J]. IEEE Transactions on Information Theory, 2020, 66(12): 7465–7474. doi: 10.1109/TIT.2020.3021707.
[19]	杜小妮, 薛婧, 乔兴斌, 等. 几类MDS码和NMDS码的构造[J]. 西北师范大学学报(自然科学版), 2026, 62(1): 41–48. doi: 10.16783/j.cnki.nwnuz.2026.01.005.