Constructions of Quaternary Optimal Locally Repairable Code with Short Length

Ruihu LI; Xiuzhen ZHAN; Qiang FU; Mao ZHANG; Youliang ZHENG

doi:10.11999/JEIT200740

Volume 43 Issue 12

Dec. 2021

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2021 > 43(12): 3749-3757

Ruihu LI, Xiuzhen ZHAN, Qiang FU, Mao ZHANG, Youliang ZHENG. Constructions of Quaternary Optimal Locally Repairable Code with Short Length[J]. Journal of Electronics & Information Technology, 2021, 43(12): 3749-3757. doi: 10.11999/JEIT200740

Citation:

Ruihu LI, Xiuzhen ZHAN, Qiang FU, Mao ZHANG, Youliang ZHENG. Constructions of Quaternary Optimal Locally Repairable Code with Short Length[J]. Journal of Electronics & Information Technology, 2021, 43(12): 3749-3757. doi: 10.11999/JEIT200740

Citation:

PDF( 683 KB)

Constructions of Quaternary Optimal Locally Repairable Code with Short Length

doi: 10.11999/JEIT200740

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

Received Date: 2020-08-24
Rev Recd Date: 2021-04-12

Available Online: 2021-06-04

Publish Date: 2021-12-21

Abstract

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

FullText(HTML)

References(23)

References

[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