一种有效的局部可修复码的构造方法

doi:10.19665/j.issn1001-2400.2019.03.005

西安电子科技大学学报 ›› 2019, Vol. 46 ›› Issue (3): 26-31.doi: 10.19665/j.issn1001-2400.2019.03.005

一种有效的局部可修复码的构造方法

王祥旭,车书玲,纪玉晖

西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安 710071

收稿日期:2018-11-26 出版日期:2019-06-20 发布日期:2019-06-19
作者简介:王祥旭(1994-),男,西安电子科技大学硕士研究生, E-mail: wxx71516@qq.com.
基金资助:
国家自然科学基金(61771364);陕西省国际合作与交流计划(2017KW-003);上海市特种光纤与光接入网重点实验室开放课题(SKLSF02014-06)

Effective construction method for locally repairable codes

WANG Xiangxu,CHE Shuling,JI Yuhui

State Key Lab. of Integrated Service Networks, Xidian Univ., Xi’an 710071, China

Received:2018-11-26 Online:2019-06-20 Published:2019-06-19

摘要/Abstract

摘要：

为了能够同时优化局部可修复码的平均信息修复度、平均修复度以及更新复杂度,并降低构造局部可修复码的算法复杂度,通过分析Tanner图的特点,提出了一种新的构造方法。首先,对局部校验节点进行设计,在满足局部可修复码的平均信息修复度为最优的基础上,通过区分局部组的特点,对重叠组进行分类构造,优化码的平均修复度;其次,对全局校验节点进行设计,优化码的更新复杂度;最后对构造码的算法复杂度进行分析和对比。结果表明,所提出的方法优化了以上所述的性能,且降低了局部可修复码在构造过程中的复杂度。

关键词: 局部可修复码, Tanner图, 更新复杂度, 平均修复度, 平均信息修复度

Abstract:

In order to optimize average information locality, average locality and update complexity of Locally Repairable Codes(LRC) at the same time, and reduce the algorithm complexity of constructing LRC, a new construction method is proposed by analyzing the characteristics of the Tanner graph. First, the local check nodes are designed. On the basis of the fact that the LRC’s average information locality is optimal, by distinguishing the characteristics of the local groups, the average locality is optimized by construction of overlapping groups; second, the update complexity is optimized by designing the global check nodes; finally, the algorithm complexity is analyzed and compared. The results show that the proposed method optimizes the performance above and reduces the complexity of constructing LRC.

Key words: locally repairable codes, Tanner graph, update complexity, average locality, average information locality

中图分类号:

TN911.2

王祥旭,车书玲,纪玉晖. 一种有效的局部可修复码的构造方法[J]. 西安电子科技大学学报, 2019, 46(3): 26-31.

WANG Xiangxu,CHE Shuling,JI Yuhui. Effective construction method for locally repairable codes[J]. Journal of Xidian University, 2019, 46(3): 26-31.

图/表 5

图1

表1

与修正单纯形法复杂度对比"

对局部校验节点的构造	复杂度
修正单纯形法	≥O $C m p - 1 J - 1 2$
笔者提出的方法	O(1)

表1

表2

图2

表3

参考文献 12

[1]	SHAHABINEJAD M, KHABBAZIAN M, ARDAKANI M . On the Average Locality of Locally Repairable Codes[J]. IEEE Transactions on Communications, 2018,66(7):2273-2783.
[2]	MEHRABI M, ARDAKANI M . On Minimum Distance of Locally Repairable Codes [C]//Proceedings of the 2017 15th Canadian Workshop on Information Theory. Piscataway: IEEE, 2017: 7994819.
[3]	POLLANEN A, WESTERBACK T, FREIJ-HOLLANTI R , et al. Bounds on the Maximal Minimum Distance of Linear Locally Repairable Codes [C]//Proceedings of the 2016 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2016: 1586-1590.
[4]	WANG A Y, ZHANG Z F, LIN D D . Bounds and Constructions for Linear Locally Repairable Codes over Binary Fields [C]// Proceedings of the 2017 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2017: 2033-2037.
[5]	HUANG P F, YAAKOBI E, UCHIKAWA H , et al. Binary Linear Locally Repairable Codes[J]. IEEE Transactions on Information Theory, 2016,62(11):6268-6283. doi: 10.1109/TIT.2016.2605119
[6]	徐恒舟, 孙成, 白宝明 . 循环差族构造的多元LDPC码[J]. 西安电子科技大学学报, 2017,44(1):6-11.
	XU Hengzhou, SUN Cheng, BAI Baoming . Nonbinary LDPC Codes Constructed Based on Cyclic Difference Families[J]. Journal of Xidian University, 2017,44(1):6-11.
[7]	KIM C, NO J S . New Constructions of Binary and Ternary Locally Repairable Codes Using Cyclic Codes[J]. IEEE Communications Letters, 2018,22(2):228-231. doi: 10.1109/LCOMM.2017.2776141
[8]	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. doi: 10.1109/TIT.2018.2854717
[9]	MEHRABI M, SHAHABINEJAD M, ARDAKANI M , et al. Improving the Update Complexity of Locally Repairable Codes[J]. IEEE Transactions on Communications, 2018,66(9):3711-3720. doi: 10.1109/TCOMM.2018.2827053
[10]	MEHRABI M, ARDAKANI M, KHABBAZIAN M . Minimizing the Update Complexity of Facebook HDFS-RAID Locally Repairable Code [C]//Proceedings of the 2018 IEEE Vehicular Technology Conference. Piscataway: IEEE, 2018: 1-5.
[11]	SHAHABINEJAD M, KHABBAZIAN M, ARDAKANI M . Locally Repairable Codes with the Optimum Average Information Locality [C] //Proceedings of the 2017 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2017: 181-185.
[12]	郭强 . 修正单纯形法的计算量的注记[J]. 运筹与管理, 1999 , 8(2):1-3.
	GUO Qiang . A Note on the Computational Quantity of Revised Simplex Method[J]. Operations Research and Management Science, 1999,8(2):1-3.

(n,k,d)	局部校验节点		全局校验节点
(n,k,d)	笔者提出的方法	修正单纯形法	笔者提出的方法	文献[9]中方法2
(27,12,12)	O(1)		≥O(35²)		O(1)	O(490)
(16,10,5)	O(1)		≥O(3²)		O(1)	O(12)
(12,5,6)	O(1)		≥O(6²)		O(1)	O(20)

一种有效的局部可修复码的构造方法

Effective construction method for locally repairable codes

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 12

相关文章 3

Metrics

本文评价

推荐阅读 10

对全局校验节点的构造	复杂度
文献[9]中相应方法	$O(\lceil \frac{n}{(r+1)}\rceil \times \phi^{2}+\phi \times C_{n-k-\phi}^{J-1})$
笔者提出的方法	O(1)

[1]	郭军军;慕建君. 一种LDPC码有限字母表迭代译码器选择算法[J]. J4, 2013, 40(6): 111-115.
[2]	焦晓鹏;慕建君;周利华. 一种Tanner图短环计数新方法[J]. J4, 2010, 37(2): 311-314.
[3]	陈汝伟1;2;黄华伟3;杜小妮4;丁勇2;肖国镇1. Tanner 图中最短圈的计数 [J]. J4, 2008, 35(6): 983-985.