高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

李瑞虎, 展秀珍, 付强, 张茂, 郑尤良. 短码长四元最优局部修复码的构造[J]. 电子与信息学报, 2021, 43(12): 3749-3757. doi: 10.11999/JEIT200740
引用本文: 李瑞虎, 展秀珍, 付强, 张茂, 郑尤良. 短码长四元最优局部修复码的构造[J]. 电子与信息学报, 2021, 43(12): 3749-3757. doi: 10.11999/JEIT200740
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

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

doi: 10.11999/JEIT200740
基金项目: 国家自然科学基金(11801564, 11901579),陕西省自然科学基金(2021JM-216, 2021JQ-335),空军工程大学基础部研究生创新基金
详细信息
    作者简介:

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

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

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

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

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

    通讯作者:

    李瑞虎 liruihu@aliyun.com

  • 中图分类号: TN918.3; O157.4

Constructions of Quaternary Optimal Locally Repairable Code with Short Length

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是局部度最优的。
  • 表  1  $d \ge 3$, $n \le 20$时四元LRC的结果

    n/k123456789
    33(1)
    44(1)3(2)
    55(1)4(2)3(3)
    66(1)4(1)4(3)
    77(1)5(2)4(2)3(3)
    88(1)6(1)5(2)4(3)3(4)
    99(1)7(2)6(2)5(3)4(4)3(4)
    1010(1)8(1)6(1)6(3)5(4)4(5)3(5)
    1111(1)8(1)7(2)6(3)6(4)5(5)4(6)3(6)
    1212(1)9(1)8(1)7(3)6(3)6(5)4(3)4(6)3(6)
    1313(1)10(1)9(2)8(3)7(3)6(4)5(4)4(4)4(7)
    1414(1)11(1)10(2)9(3)8(3)7(4)6(4)5(5)4(4)
    1515(1)12(1)11(2)10(3)8(3)8(4)7(5)6(5)5(5)
    1616(1)12(1)12(2)11(3)9(3)8(4)8(5)7(6)6(5)
    1717(1)13(1)12(2)12(3)10(3)9(4)8(5)8(6)7(7)
    1818(1)14(1)13(2)12(3)10(2)10(4)9(5)8(5)8(7)
    1919(1)15(1)14(2)12(2)11(3)10(3)9(5)8(5)8(6)
    2020(1)16(1)15(2)13(2)12(3)11(3)10(5)9(4)8(5)
    n/k1011121314151617
    133(7)
    144(8)3(8)
    154(4)4(9)3(9)
    165(6)4(5)4(10)3(10)
    176(6)5(7)4(5)4(11)3(11)
    186(6)6(6)5(8)4(5)3(7)3(12)
    197(6)6(7)6(7)5(9)4(6)3(8)3(13)
    208(7)7(7)6(7)6(7)5(10)4(7)3(9)3(14)
    下载: 导出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] 杨森, 李瑞虎, 付强, 等. 二元局部修复码的新构造[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
  • 加载中
表(1)
计量
  • 文章访问数:  718
  • HTML全文浏览量:  349
  • PDF下载量:  57
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-08-24
  • 修回日期:  2021-04-12
  • 网络出版日期:  2021-06-04
  • 刊出日期:  2021-12-21

目录

    /

    返回文章
    返回