Sunflower based construction of locally repairable codes

doi:10.11772/j.issn.1001-9081.2020060839

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (3): 763-767.DOI: 10.11772/j.issn.1001-9081.2020060839

Special Issue: 网络空间安全

• Cyber security • Previous Articles Next Articles

Sunflower based construction of locally repairable codes

ZHANG Mao, LI Ruihu, ZHENG Youliang, FU Qiang

Department of Basic Sciences, Air Force Engineering University, Xi'an Shaanxi 710051, China

Received:2020-06-17 Revised:2020-10-16 Online:2021-03-10 Published:2021-01-15
Supported by:
This work is partially supported by the National Natural Science Foundation of China (11901579,11801564), the Graduate Scientific Research Foundation of Department of Basic Sciences of Air Force Engineering University.

基于sunflower的局部修复码构造

张茂, 李瑞虎, 郑尤良, 付强

空军工程大学基础部, 西安 710051

通讯作者: 李瑞虎
作者简介:张茂(1996-),男,陕西西安人,硕士研究生,主要研究方向:大数据存储编码;李瑞虎(1966-),男,安徽阜阳人,教授,博士,主要研究方向:图论、群论、编码理论;郑尤良(1996-),男,陕西西安人,硕士研究生,主要研究方向:编码信息处理;付强(1989-),男,陕西西安人,讲师,博士,主要研究方向:量子纠错码、射影几何。
基金资助:
国家自然科学基金资助项目（11901579，11801564）；空军工程大学基础部研究生创新基金资助项目。

Abstract

Abstract: The construction of binary Locally Repairable Code (LRC) achieving C-M (Cadambe-Mazumdar) bound has been fully studied while there are few researches on general fields. In order to solve the problem, the construction of LRC on general fields was studied. Firstly, a method for determining the number of elements in sunflower was proposed by projective geometry theory. Then, the parameters such as code length, dimension and locality of LRC were clearly described by depicting LRC through the disjoint repair group. Finally, based on the parity-check matrix with disjoint local repair group, two families of LRC on general fields with the minimum distance of 6 were constructed by sunflower, many of which were optimal or almost optimal. Compared with the existing LRC constructed by methods such as subfield subcode, generalized concatenated code and algebraic curve, the constructed two families of codes improve the information rate under the same code minimum distance and locality. These results can be applied to the construction of other LRC on general fields.

Key words: Locally Repairable Code (LRC), general field, parity-check matrix, C-M (Cadambe-Mazumdar) bound, sunflower, disjoint local repair group

摘要： 针对目前构造达到C-M界的二元局部修复码（LRC）的相关研究已经较为充分，但在一般域上还相对较少的问题，研究了一般域上LRC的构造。首先，提出了通过射影几何理论确定sunflower中元素个数的方法。其次，通过不相交局部修复组刻画LRC，从而清楚地描述LRC的码长、维数和局部度等参数。最后，在具有不相交局部修复组的校验矩阵的基础上，利用sunflower构造了两类一般域上最小距离为6的LRC，其中很多LRC是最优或拟最优的。相较于现有利用子域子码、广义级联码和代数曲线等方法构造的LRC，所构造得到的两类码在相同的码的最小距离和局部度下提升了信息率。这些结果说明所提方法可应用于一般域上其他LRC的构造。

关键词: 局部修复码, 一般域, 校验矩阵, C-M界, sunflower, 不相交局部修复组

CLC Number:

TP309.3

ZHANG Mao, LI Ruihu, ZHENG Youliang, FU Qiang. Sunflower based construction of locally repairable codes[J]. Journal of Computer Applications, 2021, 41(3): 763-767.

张茂, 李瑞虎, 郑尤良, 付强. 基于sunflower的局部修复码构造[J]. 计算机应用, 2021, 41(3): 763-767.

References

[1] WEATHERSPOON H,KUBIATOWICZ J D. Erasure coding vs. replication:a quantitative comparison[C]//Proceedings of the 2002 International Workshop on Peer-to-Peer Systems, LNCS 2429. Berlin:Springer,2002:328-337.
[2] HUANG C,SIMITCI H,XU Y,et al. Erasure coding in windows azure storage[C]//Proceedings of the 2012 USENIX Annual Technical Conference. Berkeley:USENIX Association, 2012:15-26.
[3] KOPPARTY S,SARAF S,YEKHANIN S. High-rate codes with sublinear-time decoding[C]//Proceedings of 43rd ACM Symposium on Theory of Computing. New York:ACM,2011:167-176.
[4] 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.
[5] CADAMBE V R,MAZUMDAR A. An upper bound on the size of locally recoverable codes[C]//Proceedings of 2013 International Symposium on Network Coding. Piscataway:IEEE,2013:1-5.
[6] CADAMBE V R,MAZUMDAR A. Bounds on the size of locally recoverable codes[J]. IEEE Transactions on Information Theory, 2015,61(11):5787-5794.
[7] NAM M Y,SONG H Y. Binary locally repairable codes with minimum distance at least six based on partial t-spreads[J]. IEEE Communications Letters,2017,21(8):1683-1686.
[8] SILBERSTEIN N,ZEH A. Optimal binary locally repairable codes via anticodes[C]//Proceedings of 2015 IEEE International Symposium on Information Theory. Piscataway:IEEE, 2015:1247-1251.
[9] MA J,GE G. Optimal binary linear locally repairable codes with disjoint repair groups[J]. SIAM Journal on Discrete Mathematics, 2019,33(4):2509-2529.
[10] FU Q,LI R,GUO L,et al. Locality of optimal binary codes[J]. Finite Fields and Their Applications,2017,48:371-394.
[11] 杨森, 李瑞虎, 付强, 等. 二元局部修复码的新构造[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.)
[12] BLAUM M. On Locally Repairable Codes (LRC)[EB/OL].[2020-03-26]. https://arxiv.org/pdf/1512.06161.pdf.
[13] SENGER C,SHIVAKUMAR H K. Subfield subcodes of TamoBarg locally recoverable codes[C]//Proceedings of 29th Biennial Symposium on Communications. Piscataway:IEEE,2018:1-5.
[14] BARG A, HAYMAKER K, HOWE E W, et al. Locally recoverable codes from algebraic curves and surfaces[M]//HOWE E W,LAUTER K E,WALKER J L,ed. Algebraic Geometry for Coding Theory and Cryptography,AWMS 9. Cham:Springer, 2017:95-127.
[15] CHEN H,WENG J,LUO W. Long optimal or small-defect LRC codes with unbounded minimum distance[EB/OL].[2020-03-26]. https://arxiv.org/pdf/1910.07627.pdf.
[16] CHEN B, XIA S, HAO J. Improved bounds and optimal constructions of locally repairable codes with distance 5 and 6[C]//Proceedings of the 2019 International Symposium on Information Theory. Piscataway:IEEE,2019:2823-2827.
[17] PAPAILIOPOULOS D,DIMAKIS A. Locally repairable codes[C]//Proceedings of the 2012 International Symposium on Information Theory. Piscataway:IEEE,2012:2771-2775.
[18] HIRSCHFELD J W P. Projective Geometries Over Finite Fields:2nd Ed[M]. Oxford:Clarendon Press,1998:23-24.

Sunflower based construction of locally repairable codes

基于sunflower的局部修复码构造

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 8

Recommended Articles

Metrics

[1]	LI Jinjin, JIA Xiaoqi, DU Haichao, WANG Lipeng. Efficient virtualization-based approach to improve system availability [J]. Journal of Computer Applications, 2017, 37(4): 986-992.
[2]	WANG Feng, LI Lixin, CAO Jingyuan, PAN Cong. Research on replication consistency of cache in publish/subscribe systems [J]. Journal of Computer Applications, 2016, 36(6): 1510-1514.
[3]	LIU Qing, FU Yinjin, NI Guiqiang, MEI Jianmin. Distributed deduplication storage system based on Hadoop platform [J]. Journal of Computer Applications, 2016, 36(2): 330-335.
[4]	PENG Zhen CHEN Lanxiang GUO Gongde. Fountain code based data recovery system for cloud storage [J]. Journal of Computer Applications, 2014, 34(4): 986-993.
[5]	WU Hao LIU Xiaojie LUO Peng. TRAP-4 based continuous data protection system [J]. Journal of Computer Applications, 2014, 34(1): 54-57.
[6]	ZHU Yuanyuan WANG Xiaojing. HDFS optimization program based on GE coding [J]. Journal of Computer Applications, 2013, 33(03): 730-733.
[7]	YANG De-ming. Fast recovery method of effective data based on FAT32 [J]. Journal of Computer Applications, 2012, 32(09): 2500-2503.
[8]	LI Hong-yan. Methods of metadata management in block-level continuous data protection system [J]. Journal of Computer Applications, 2012, 32(08): 2141-2149.