短码长四元最优局部修复码的构造

李瑞虎; 展秀珍; 付强; 张茂; 郑尤良

doi:10.11999/JEIT200740

短码长四元最优局部修复码的构造

doi: 10.11999/JEIT200740

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

基金项目: 国家自然科学基金(11801564, 11901579)，陕西省自然科学基金(2021JM-216, 2021JQ-335)，空军工程大学基础部研究生创新基金

详细信息

作者简介:
李瑞虎：男，1966年生，教授，博士生导师，主要研究方向为群论、图论、编码和密码学

展秀珍：女，1995年生，硕士生，研究方向为大数据存储编码

付强：男，1989年生，讲师，博士，研究方向为射影几何、经典编码与量子纠错码

张茂：男，1996年生，硕士，研究方向为编码理论

郑尤良：男，1996年生，硕士，研究方向为分布式存储编码和纠删码

通讯作者:
李瑞虎　liruihu@aliyun.com

中图分类号: TN918.3; O157.4
计量
- 文章访问数: 830
- HTML全文浏览量: 436
- PDF下载量: 60
- 被引次数: 0
出版历程
- 收稿日期: 2020-08-24
- 修回日期: 2021-04-12
- 网络出版日期: 2021-06-04
- 刊出日期: 2021-12-21

Constructions of Quaternary Optimal Locally Repairable Code with Short Length

Fundamentals Department, Air Force Engineering University, Xi’an 710051, China

Funds: The National Science Foundation of China (11801564, 11901579), Shaanxi Natural Science Foundation (2021JM-216, 2021JQ-335), The Graduate Scientific Research Foundation of Fundamentals Department of Air Force Engineering University

摘要

摘要: 在分布式存储系统中，当节点发生故障时局部修复码(LRC)可以通过访问少量其他节点来恢复数据，然而LRC的局部度不尽相同，该文构造了短码长且局部度较小的四元LRC。当码长不超过20，最小距离大于2时，若四元距离最优线性码的生成阵维数不超过校验阵维数，可利用其生成阵给出LRC，否则利用其校验阵给出LRC。对已构造的LRC的生成阵或校验阵，利用删除、并置等方法得到新矩阵，从而构造出190个码长$n \le 20$，最小距离$d \ge 2$的LRC。除12个LRC外，其他LRC是局部度最优的。
- 最优码 /
- 局部修复码 /
- 生成阵 /
- 校验阵
Abstract: In distributed storage system, when a node fails, Locally Repairable Code (LRC) can access other nodes to recover data. However, the locality of LRC is not the same. Quaternary LRC with short code length and small locality is constructed. When code length is not more than 20 and minimum distance is greater than 2, if the dimension of generator matrix of a quaternary distance optimal linear code does not exceed the dimension of parity-check matrix, an LRC can be constructed from generator matrix, otherwise parity-check matrix can be used to construct an LRC. From generator matrices or parity-check matrices of LRCs constructed, other LRC are given by operations of deleting and juxtaposition. There are 190 LRC with code length n ≤ 20 and minimum distance d ≥ 2 to be constructed. Except for 12 LRC, other LRC are all locality optimal.
- Optimal code /
- Locally Repairable Code (LRC) /
- Generator matrix /
- Parity-check matrix

HTML全文

表 1 $d \ge 3$, $n \le 20$时四元LRC的结果

n/k	1	2	3	4	5	6	7	8	9
3	3(1)
4	4(1)	3(2)
5	5(1)	4(2)	3(3)
6	6(1)	4(1)	4(3)
7	7(1)	5(2)	4(2)	3(3)
8	8(1)	6(1)	5(2)	4(3)	3(4)
9	9(1)	7(2)	6(2)	5(3)	4(4)	3(4)
10	10(1)	8(1)	6(1)	6(3)	5(4)	4(5)	3(5)
11	11(1)	8(1)	7(2)	6(3)	6(4)	5(5)	4(6)	3(6)
12	12(1)	9(1)	8(1)	7(3)	6(3)	6(5)	4(3)	4(6)	3(6)
13	13(1)	10(1)	9(2)	8(3)	7(3)	6(4)	5(4)	4(4)	4(7)
14	14(1)	11(1)	10(2)	9(3)	8(3)	7(4)	6(4)	5(5)	4(4)
15	15(1)	12(1)	11(2)	10(3)	8(3)	8(4)	7(5)	6(5)	5(5)
16	16(1)	12(1)	12(2)	11(3)	9(3)	8(4)	8(5)	7(6)	6(5)
17	17(1)	13(1)	12(2)	12(3)	10(3)	9(4)	8(5)	8(6)	7(7)
18	18(1)	14(1)	13(2)	12(3)	10(2)	10(4)	9(5)	8(5)	8(7)
19	19(1)	15(1)	14(2)	12(2)	11(3)	10(3)	9(5)	8(5)	8(6)
20	20(1)	16(1)	15(2)	13(2)	12(3)	11(3)	10(5)	9(4)	8(5)

n/k	10	11	12	13	14	15	16	17
13	3(7)
14	4(8)	3(8)
15	4(4)	4(9)	3(9)
16	5(6)	4(5)	4(10)	3(10)
17	6(6)	5(7)	4(5)	4(11)	3(11)
18	6(6)	6(6)	5(8)	4(5)	3(7)	3(12)
19	7(6)	6(7)	6(7)	5(9)	4(6)	3(8)	3(13)
20	8(7)	7(7)	6(7)	6(7)	5(10)	4(7)	3(9)	3(14)

下载: 导出CSV

参考文献(23)

[1]	WEATHERSPOON H and KUBIATOWICZ J D. Erasure coding vs. replication: A quantitative comparison[C]. The 1st International Workshop on Peer-to-Peer Systems, Cambridge, UK, 2002: 328–337. doi: 10.1007/3-540-45748-8_31.
[2]	HUANG Cheng, SIMITCI H, XU Yikang, et al. Erasure coding in windows azure storage[C]. 2012 USENIX Annual Technical Conference, Boston, USA, 2012: 15–26.
[3]	BALAJI S B, KRISHNAN M N, VAJHA M, et al. Erasure coding for distributed storage: An overview[J]. Science China Information Sciences, 2018, 61(10): 100301. doi: 10.1007/s11432-018-9482-6
[4]	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
[5]	PAPAILIOPOULOS D S and DIMAKIS A G. Locally repairable codes[C]. 2012 IEEE International Symposium on Information Theory, Cambridge, USA, 2012: 2771–2775. doi: 10.1109/ISIT.2012.6284027.
[6]	CADAMBE V and MAZUMDAR A. An upper bound on the size of locally recoverable codes[C]. 2013 International Symposium on Network Coding, Calgary, Canada, 2013: 1–5. doi: 10.1109/NetCod.2013.6570829.
[7]	GOPARAJU S and CALDERBANK R. Binary cyclic codes that are locally repairable[C]. 2014 International Symposium on Information Theory, Honolulu, USA, 2014: 676–680. doi: 10.1109/ISIT.2014.6874918.
[8]	HAO Jie, XIA Shutao, and CHEN Bin. Some results on optimal locally repairable codes[C]. 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016: 440–444. doi: 10.1109/ISIT.2016.7541337.
[9]	HAO Jie and XIA Shutao. Bounds and constructions of locally repairable codes: Parity-check matrix approach[EB/OL]. https://arxiv.org/abs/1601.05595v1, 2019.
[10]	FU Qiang, LI Ruihu, GUO Luobin, et al. Locality of optimal binary codes[J]. Finite Fields and Their Applications, 2017, 48: 371–394. doi: 10.1016/j.ffa.2017.08.013
[11]	杨森, 李瑞虎, 付强, 等. 二元局部修复码的新构造[J]. 空军工程大学学报: 自然科学版, 2019, 20(6): 104–108. YANG Sen, LI Ruihu, FU Qiang, 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]	HAO Jie, XIA Shutao, and CHEN Bin. On optimal ternary locally repairable codes[C]. 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 2017: 171–175. doi: 10.1109/ISIT.2017.8006512.
[13]	YANG Ruipan, LI Ruihu, GUO Luobin, et al. Locality of some optimal ternary linear codes[J]. Procedia Computer Science, 2017, 107: 164–169. doi: 10.1016/j.procs.2017.03.073
[14]	WESTERBACK T, ERNVALL T, and HOLLANTI C. Almost affine locally repairable codes and matroid theory[C]. 2014 IEEE Information Theory Workshop, Hobart, Australia, 2014: 621–625. doi: 10.1109/ITW.2014.6970906.
[15]	ERNVALL T, WESTERBÄCK T, and HOLLANTI C. Constructions of optimal and almost optimal locally repairable codes[C]. The 4th International Conference on Wireless Communications, Vehicular Technology, Information Theory and Aerospace & Electronic Systems (VITAE), Aalborg, Denmark, 2014: 1–5. doi: 10.1109/VITAE.2014.6934442.
[16]	BARG A, HAYMAKER K, HOWE E W, et al. Locally Recoverable Codes from Algebraic Curves and Surfaces[M]. HOWE E W, LAUTER K E, and WALKER J L. Algebraic Geometry for Coding Theory and Cryptography. Cham: Springer, 2016, 95–127. doi: 10.1007/978-3-319-63931-4_4.
[17]	FU Qiang, LI Ruihu, GUO Luobin, 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, 2021, E104-A(1): 319–323. doi: 10.1587/transfun.2019eal2158
[18]	JIN Lingfei, MA Liming, and XING Chaoping. Construction of optimal locally repairable codes via automorphism groups of rational function fields[J]. IEEE Transactions on Information Theory, 2020, 66(1): 210–221. doi: 10.1109/TIT.2019.2946637
[19]	PLANK J, GREENAN K, and MILLER E. Screaming fast Galois field arithmetic using Intel SIMD instructions[C]. The 11th USENIX Conference on File and Storage Technologies, San Jose, USA, 2013: 299–306.
[20]	吴昭军, 张立民, 钟兆根, 等. 一种软判决下的RS码识别算法[J]. 电子与信息学报, 2020, 42(9): 2150–2157. doi: 10.11999/JEIT190690 WU Zhaojun, ZHANG Limin, ZHONG Zhaogen, et al. Blind recognition of RS codes based on soft decision[J]. Journal of Electronics &Information Technology, 2020, 42(9): 2150–2157. doi: 10.11999/JEIT190690
[21]	FEULNER T. Classification and nonexistence results for linear codes with prescribed minimum distances[J]. Designs, Codes and Cryptography, 2014, 70(1): 127–138. doi: 10.1007/s10623-012-9700-8
[22]	GRASSL M. Bounds on the minimum distance of linear codes[EB/OL]. http://www.codetables.de, 2020.
[23]	BOUYUKLIEV I, GRASSL M, and VARBANOV Z. New bounds forand classification of some optimal codes over[J]. Discrete Mathematics, 2004, 281(1/3): 43–66. doi: 10.1016/j.disc.2003.11.003