短碼長(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)新基金
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)的。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.-
Key words:
- Optimal code /
- Locally Repairable Code (LRC) /
- Generator matrix /
- Parity-check matrix
-
表 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
-
[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/JEIT190690WU 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 -
表(1)
計(jì)量
- 文章訪問(wèn)數(shù): 860
- HTML全文瀏覽量: 504
- PDF下載量: 60
- 被引次數(shù): 0