Several Constructions of Near MDS Codes and Optimal Locally Recoverable Codes

WANG Xin-ran; HENG Zi-ling

doi:10.12263/DZXB.20220634

您当前的位置：

首页 >

文章列表页 >

Several Constructions of Near MDS Codes and Optimal Locally Recoverable Codes

PAPERS | 更新时间：2025-12-11

- Several Constructions of Near MDS Codes and Optimal Locally Recoverable Codes
- ACTA ELECTRONICA SINICA Vol. 52, Issue 3, Pages: 957-966(2024)
- 作者机构：
  
  长安大学理学院，陕西西安710064
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(11901049);The Young Talent Fund of University Association for Science and Technology in Shaanxi, China(20200505);Fundamental Research Funds for the Central Universities, CHD(300102122202)
- DOI：10.12263/DZXB.20220634
  CLC： O236.2;TN911.22
- Received：31 May 2022，
  
  Revised：2022-08-11，
  
  Published：25 March 2024
- 稿件说明：
移动端阅览
王鑫然,衡子灵.几类near MDS码和最优局部修复码的构造[J].电子学报,2024,52(03):957-966.

WANG Xin-ran, HENG Zi-ling.Several Constructions of Near MDS Codes and Optimal Locally Recoverable Codes[J].Acta Electronica Sinica, 2024, 52(03): 957-966.
王鑫然,衡子灵.几类near MDS码和最优局部修复码的构造[J].电子学报,2024,52(03):957-966. DOI：10.12263/DZXB.20220634

WANG Xin-ran, HENG Zi-ling.Several Constructions of Near MDS Codes and Optimal Locally Recoverable Codes[J].Acta Electronica Sinica, 2024, 52(03): 957-966. DOI：10.12263/DZXB.20220634

摘要

局部修复码是一种通过局部修复提高存储节点修复效率的重要编码方法，在分布式存储和云存储中有重要应用. 本文首先构造了几类维数为4或5的near MDS （near Maximum Distance Separable）码，精确计算出了它们的参数和重量分布. 特别地，得到了一些参数相同但重量分布不同的near MDS码. 此外，通过确定near MDS码的局部度，得到了几类距离最优和维数最优的局部修复码. 这些局部修复码的参数和文献中已知最优局部修复码的参数不同.

Abstract

Locally recoverable codes offer an efficient way to improve the repair efficiency of storage nodes by local recovery. They are widely used in distributed storage and cloud storage. In this paper

we first present several constructions of near MDS (near maximum distance separable) codes of dimension 4 or 5. The parameters and weight distributions of the codes are explicitly determined. In particular

some families of near MDS codes with the same parameters but different weight distributions are derived. Then the locality of the near MDS codes is also studied. Several families of distance-optimal and dimension-optimal locally recoverable codes are obtained. These locally recoverable codes have different parameters from those of known ones in the literature.

关键词

Keywords

references

LI C J , YUE Q , LI F W . Weight distributions of cyclic codes with respect to pairwise coprime order elements [J ] . Finite Fields and Their Applications , 2014 , 28 : 94 - 114 .

DING C S . Designs from Linear Codes [M ] . Singapore : World Scientific , 2019 .

HENG Z L , DING C S , ZHOU Z C . Minimal linear codes over finite fields [J ] . Finite Fields and Their Applications , 2018 , 54 : 176 - 196 .

杜小妮 , 吕红霞 , 王蓉 , 等 . 两类四重线性码的构造 [J ] . 西北师范大学学报(自然科学版) , 2018 , 54 ( 6 ): 1 - 4 .

DU X N , LÜ H X , WANG R , et al . A construction of two classes of linear codes with four-weights [J ] . Journal of Northwest Normal University (Natural Science) , 2018 , 54 ( 6 ): 1 - 4 . (in Chinese)

杨淑娣 , 岳勤 . 一类线性码的完全重量分布 [J ] . 计算机工程与科学 , 2019 , 41 ( 2 ): 281 - 285 .

YANG S D , YUE Q . Complete weight enumerators of a class of linear codes [J ] . Computer Engineering and Science , 2019 , 41 ( 2 ): 281 - 285 . (in Chinese)

YANG S D , YAO Z G . Complete weight enumerators of a family of three-weight linear codes [J ] . Designs, Codes and Cryptography , 2017 , 82 ( 3 ): 663 - 674 .

杜小妮 , 李晓丹 , 吕红霞 , 等 . 几类二重和三重线性码的构造 [J ] . 西北师范大学学报(自然科学版) , 2018 , 54 ( 2 ): 30 - 35 .

DU X N , LI X D , LÜ H X , et al . A construction of several classes of two-weight and three-weight linear codes [J ] . Journal of Northwest Normal University (Natural Science) , 2018 , 54 ( 2 ): 30 - 35 . (in Chinese)

杜小妮 , 吕红霞 , 王蓉 . 一类四重和六重线性码的构造 [J ] . 电子与信息学报 , 2019 , 41 ( 12 ): 2995 - 2999 .

DU X N , LÜ H X , WANG R . Construction of a class of linear codes with four-weight and six-weight [J ] . Journal of Electronics & Information Technology , 2019 , 41 ( 12 ): 2995 - 2999 . (in Chinese)

杨淑娣 , 唐春明 . 循环码的完全重量分布 [J ] . 江苏师范大学学报(自然科学版) , 2018 , 36 ( 2 ): 64 - 68 .

YANG S D , TANG C M . The complete weight enumerator of cyclic codes [J ] . Journal of Jiangsu Normal University (Natural Science Edition) , 2018 , 36 ( 2 ): 64 - 68 . (in Chinese)

胡丽琴 , 岳勤 , 朱小萌 . 具有两个非零点循环码的权重分布 [J ] . 中国科学(数学) , 2014 , 44 ( 9 ): 1021 - 1034 .

HU L Q , YUE Q , ZHU X M . Weight distribution of cyclic codes with two non-zero points [J ] . Scientia Sinica (Mathematica) , 2014 , 44 ( 9 ): 1021 - 1034 . (in Chinese)

李瑞虎 , 展秀珍 , 付强 , 等 . 短码长四元最优局部修复码的构造 [J ] . 电子与信息学报 , 2021 , 43 ( 12 ): 3749 - 3757 .

LI R H , ZHAN X Z , FU Q , et al . Constructions of quaternary optimal locally repairable code with short length [J ] . Journal of Electronics & Information Technology , 2021 , 43 ( 12 ): 3749 - 3757 . (in Chinese)

杨森 , 李瑞虎 , 付强 , 等 . 二元局部修复码的新构造 [J ] . 空军工程大学学报(自然科学版) , 2019 , 20 ( 6 ): 104 - 108 .

YANG S , LI R H , FU Q , et al . The new constructions of binary locally repairable codes [J ] . Journal of Air Force Engineering University (Natural Science Edition) , 2019 , 20 ( 6 ): 104 - 108 . (in Chinese)

展秀珍 , 李瑞虎 , 付强 , 等 . 低维四元局部修复码的构造 [J ] . 空军工程大学学报(自然科学版) , 2021 , 22 ( 3 ): 104 - 110 .

ZHAN X Z , LI R H , FU Q , et al . Construction of quaternary locally repairable code with low dimension [J ] . Journal of Air Force Engineering University (Natural Science Edition) , 2021 , 22 ( 3 ): 104 - 110 . (in Chinese)

LUO G J , CAO X W . Constructions of optimal binary locally recoverable codes via a general construction of linear codes [J ] . IEEE Transactions on Communications , 2021 , 69 ( 8 ): 4987 - 4997 .

GOPALAN P , HUANG C , SIMITCI H , et al . On the locality of codeword symbols [J ] . IEEE Transactions on Information Theory , 2012 , 58 ( 11 ): 6925 - 6934 .

CADAMBE V , MAZUMDAR A . An upper bound on the size of locally recoverable codes [C ] // 2013 International Symposium on Network Coding (NetCod) . Piscataway : IEEE , 2013 : 1 - 5 .

TAN P , FAN C L , DING C S , et al . The minimum linear locality of linear codes [J ] . Designs, Codes and Cryptography , 2023 , 91 ( 1 ): 83 - 114 .

DODUNEKOV S , LANDGEV I . On near-MDS codes [J ] . Journal of Geometry , 1995 , 54 ( 1/2 ): 30 - 43 .

FALDUM A , WILLEMS W . Codes of small defect [J ] . Designs, Codes and Cryptography , 1997 , 10 ( 3 ): 341 - 350 .

Pommerening K . Quadratic equations in finite fields of characteristic 2 [EB/OL ] . ( 2022-04-26 )[ 2022-05-20 ] . https://www.staff.unimainz.de/pommeren/MathMisc/QuGlChar2.pdf https://www.staff.unimainz.de/pommeren/MathMisc/QuGlChar2.pdf .

WANG Q Y , HENG Z L . Near MDS codes from oval polynomials [J ] . Discrete Mathematics , 2021 , 344 ( 4 ): 112277 .

MASCHIETTI A . Difference sets and hyperovals [J ] . Designs, Codes and Cryptography , 1998 , 14 ( 1 ): 89 - 98 .

XU G K , CAO X W , QU L J . Infinite families of 3-designs and 2-designs from almost MDS codes [J ] . IEEE Transactions on Information Theory , 2022 , 68 ( 7 ): 4344 - 4353 .

LUO Y , XING C P , YUAN C . Optimal locally repairable codes of distance 3 and 4 via cyclic codes [J ] . IEEE Transactions on Information Theory , 2019 , 65 ( 2 ): 1048 - 1053 .

FU Q , LI R H , GUO L B , et al . Singleton-type optimal LRCs with minimum distance 3 and 4 from projective code [J ] . IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , 2021 , E104.A( 1 ): 319 - 323 .

JIN L F . Explicit construction of optimal locally recoverable codes of distance 5 and 6 via binary constant weight codes [J ] . IEEE Transactions on Information Theory , 2019 , 65 ( 8 ): 4658 - 4663 .

LI X R , HENG Z L . Constructions of near MDS codes which are optimal locally recoverable codes [J ] . Finite Fields and Their Applications , 2023 , 88 : 102184 .

LI X R , HENG Z L . A construction of optimal locally recoverable codes [J ] . Cryptography and Communications , 2023 , 15 : 553 - 563 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

An Erasure Coding Technology Supporting Near-Data Processing in Distributed Storage Systems

BSS: A Storage Optimization Scheme for the Permissioned Blockchain

MacWilliams Identities of Linear Codes over Non-principal ideal Ring F_-p+vF_-p

Threshold Byzantine Quorum System and Distributed Storage

Related Author

WANG Xin-ran

LI Hao-ran

HUANG Zhi-jie

ZHANG Xiao

ZHAO Nan-nan

ZHAO Cheng-jia

SHI Yu-long

LIU Xiao-guang

Related Institution

School of Computer Science, Northwestern Polytechnical University

College of Computer Science， Nankai University

Tianjin Key Laboratory of Network and Data Security Technology， Nankai University

Institute of Computer Network SystemHefei University of TechnologyHefeiAnhui 230009China

School of Mathematics Sciences of Anhui UniversityHefeiAnhui 240601China

⁰