短碼長(zhǎng)四元最優(yōu)局部修復(fù)碼的構(gòu)造

李瑞虎; 展秀珍; 付強(qiáng); 張茂; 鄭尤良

doi:10.11999/JEIT200740

短碼長(zhǎng)四元最優(yōu)局部修復(fù)碼的構(gòu)造

doi: 10.11999/JEIT200740

空軍工程大學(xué)基礎(chǔ)部　西安　710051

基金項(xiàng)目: 國(guó)家自然科學(xué)基金(11801564, 11901579)，陜西省自然科學(xué)基金(2021JM-216, 2021JQ-335)，空軍工程大學(xué)基礎(chǔ)部研究生創(chuàng)新基金

詳細(xì)信息

作者簡(jiǎn)介:
李瑞虎：男，1966年生，教授，博士生導(dǎo)師，主要研究方向?yàn)槿赫?、圖論、編碼和密碼學(xué)

展秀珍：女，1995年生，碩士生，研究方向?yàn)榇髷?shù)據(jù)存儲(chǔ)編碼

付強(qiáng)：男，1989年生，講師，博士，研究方向?yàn)樯溆皫缀巍⒔?jīng)典編碼與量子糾錯(cuò)碼

張茂：男，1996年生，碩士，研究方向?yàn)榫幋a理論

鄭尤良：男，1996年生，碩士，研究方向?yàn)榉植际酱鎯?chǔ)編碼和糾刪碼

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

中圖分類(lèi)號(hào): TN918.3; O157.4
計(jì)量
- 文章訪問(wèn)數(shù): 860
- HTML全文瀏覽量: 504
- PDF下載量: 60
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2020-08-24
- 修回日期: 2021-04-12
- 網(wǎng)絡(luò)出版日期: 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

摘要

摘要: 在分布式存儲(chǔ)系統(tǒng)中，當(dāng)節(jié)點(diǎn)發(fā)生故障時(shí)局部修復(fù)碼(LRC)可以通過(guò)訪問(wèn)少量其他節(jié)點(diǎn)來(lái)恢復(fù)數(shù)據(jù)，然而LRC的局部度不盡相同，該文構(gòu)造了短碼長(zhǎng)且局部度較小的四元LRC。當(dāng)碼長(zhǎng)不超過(guò)20，最小距離大于2時(shí)，若四元距離最優(yōu)線性碼的生成陣維數(shù)不超過(guò)校驗(yàn)陣維數(shù)，可利用其生成陣給出LRC，否則利用其校驗(yàn)陣給出LRC。對(duì)已構(gòu)造的LRC的生成陣或校驗(yàn)陣，利用刪除、并置等方法得到新矩陣，從而構(gòu)造出190個(gè)碼長(zhǎng)$n \le 20$，最小距離$d \ge 2$的LRC。除12個(gè)LRC外，其他LRC是局部度最優(yōu)的。
- 最優(yōu)碼 /
- 局部修復(fù)碼 /
- 生成陣 /
- 校驗(yàn)陣
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$時(shí)四元LRC的結(jié)果

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)

下載: 導(dǎo)出CSV

參考文獻(xiàn)(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]	楊森, 李瑞虎, 付強(qiáng), 等. 二元局部修復(fù)碼的新構(gòu)造[J]. 空軍工程大學(xué)學(xué)報(bào): 自然科學(xué)版, 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碼識(shí)別算法[J]. 電子與信息學(xué)報(bào), 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