Search Advanced

AIMS Mathematics

2026, Volume 11, Issue 8: 26337-26358. doi: 10.3934/math.20261057
Previous Article Next Article
Research article

Array codes with local properties: Explicit constructions, erasure decoding, and MSSS application

  • 1.
    School of Telecommunications Engineering & Intelligentization, Dongguan University of Technology, Dongguan 523808, China
  • 2.
    School of Mathematics and Information Science, Guangzhou University, Guangzhou, Guangdong 510006, China
  • 3.
    Tsinghua Shenzhen International Graduate School, Tsinghua University, Shenzhen 518055, China
  • 4.
    Institute of Network Coding, The Chinese University of Hong Kong, Hong Kong 999077, China
  • 5.
    Shenzhen University of Advanced Technology, Shenzhen 518107, China
  • Published: 24 August 2026

  • MSC : 11T71, 94B05

  • This paper presents two constructions of $ q $-ary array codes that possess column local properties; that is, any erasure can be recovered using only the remaining symbols within a single column of a codeword. The first construction generalizes the extended Blaum-Roth codes as a special case. An explicit formulation of Construction Ⅰ is further developed, which enables the code length to grow exponentially as $ 2^{\kappa} $, where $ \kappa $ denotes the minimum degree among the irreducible factors of $ m(x) $. Leveraging the recursive structure of the associated polynomials and the Reed-Muller transform, we devise two fast erasure decoding algorithms based on recursive branching: one tailored for redundancy $ r\le 3 $ and the other applicable to arbitrary $ r $. The second family of array codes is applied to the modified Shamir secret sharing (MSSS) scheme. Compared with the existing BR/GRDP-based MSSS scheme, the proposed approach offers the following advantages: (ⅰ) support for a larger number of participants, (ⅱ) self-repairability of every share, and (ⅲ) lower encoding complexity.

    Citation: Xian Lian, Jingjie Lv, Hongwei Zhu, Shu-Tao Xia, Hanxu Hou. Array codes with local properties: Explicit constructions, erasure decoding, and MSSS application[J]. AIMS Mathematics, 2026, 11(8): 26337-26358. doi: 10.3934/math.20261057

    Related Papers:

  • This paper presents two constructions of $ q $-ary array codes that possess column local properties; that is, any erasure can be recovered using only the remaining symbols within a single column of a codeword. The first construction generalizes the extended Blaum-Roth codes as a special case. An explicit formulation of Construction Ⅰ is further developed, which enables the code length to grow exponentially as $ 2^{\kappa} $, where $ \kappa $ denotes the minimum degree among the irreducible factors of $ m(x) $. Leveraging the recursive structure of the associated polynomials and the Reed-Muller transform, we devise two fast erasure decoding algorithms based on recursive branching: one tailored for redundancy $ r\le 3 $ and the other applicable to arbitrary $ r $. The second family of array codes is applied to the modified Shamir secret sharing (MSSS) scheme. Compared with the existing BR/GRDP-based MSSS scheme, the proposed approach offers the following advantages: (ⅰ) support for a larger number of participants, (ⅱ) self-repairability of every share, and (ⅲ) lower encoding complexity.



    加载中


    [1] D. A. Patterson, P. Chen, G. Gibson, R. H. Katz, Introduction to redundant arrays of inexpensive disks (RAID), In: Thirty-fourth IEEE computer society international conference: Intellectual leverage, San Francisco: IEEE, 1989,112–117. https://doi.org/10.1109/CMPCON.1989.301912
    [2] M. Blaum, P. G. Farrell, H. C. A. van Tilborg, Chapter on array codes, In: Handbook of coding theory, Elsevier, 2 (1998), 1855–1909.
    [3] H. Hou, P. P. C. Lee, A new construction of EVENODD codes with lower computational complexity, IEEE Commun. Lett., 22 (2018), 1120–1123. https://doi.org/10.1109/LCOMM.2018.2820007 doi: 10.1109/LCOMM.2018.2820007
    [4] P. Corbett, B. English, A. Goel, T. Grcanac, S. Kleiman, J. Leong, et al., Row-diagonal parity for double disk failure correction, In: Proceedings of the 3rd USENIX conference on file and storage technologies, 2004.
    [5] G. L. Feng, R. H. Deng, F. Bao, J. C. Shen, New efficient MDS array codes for RAID. Part I: Reed-Solomon-like codes for tolerating three disk failures, IEEE Trans. Comput., 54 (2005), 1071–1080. https://doi.org/10.1109/TC.2005.150 doi: 10.1109/TC.2005.150
    [6] C. Huang, L. Xu, STAR: An efficient coding scheme for correcting triple storage node failures, IEEE Trans. Comput., 57 (2008), 889–901. https://doi.org/10.1109/TC.2007.70830 doi: 10.1109/TC.2007.70830
    [7] M. Blaum, A family of MDS array codes with minimal number of encoding operations, In: 2006 IEEE international symposium on information theory (ISIT), Seattle: IEEE, 2006, 2784–2788. https://doi.org/10.1109/ISIT.2006.261569
    [8] M. Blaum, J. Bruck, A. Vardy, MDS array codes with independent parity symbols, IEEE Trans. Inf. Theory., 42 (1996), 529–542. https://doi.org/10.1109/18.485722 doi: 10.1109/18.485722
    [9] M. Blaum, R. M. Roth, New array codes for multiple phased burst correction, IEEE Trans. Inf. Theory, 39 (1993), 66–77. https://doi.org/10.1109/18.179343 doi: 10.1109/18.179343
    [10] J. Lv, W. Fang, X. Chen, J. Yang, S. T. Xia, New constructions of $q$-ary MDS array codes with multiple parities and their effective decoding, IEEE Trans. Inf. Theory, 69 (2023), 7082–7096. https://doi.org/10.1109/TIT.2023.3300919 doi: 10.1109/TIT.2023.3300919
    [11] W. Fang, J. Lv, B. Chen, S. T. Xia, X. Chen, New constructions of MDS array codes and optimal locally repairable array codes, IEEE Trans. Inf. Theory, 70 (2024), 1806–1822. https://doi.org/10.1109/TIT.2024.3353111 doi: 10.1109/TIT.2024.3353111
    [12] Z. Zhai, S. Jin, Q. T. Sun, S. Liu, X. Chen, Z. Li, New construction of MDS array codes and explicit characterization of decoding matrices, IEEE Trans. Commun., 73 (2025), 5592–5606. https://doi.org/10.1109/TCOMM.2025.3541085 doi: 10.1109/TCOMM.2025.3541085
    [13] M. Blaum, S. R. Hetzler, Array codes with local properties, IEEE Trans. Inf. Theory, 66 (2020), 3675–3690. https://doi.org/10.1109/TIT.2019.2951693 doi: 10.1109/TIT.2019.2951693
    [14] H. Hou, Y. S. Han, P. P. C. Lee, Y. Wu, G. Han, M. Blaum, A generalization of array codes with local properties and efficient encoding/decoding, IEEE Trans. Inf. Theory, 69 (2023), 107–125. https://doi.org/10.1109/TIT.2022.3202140 doi: 10.1109/TIT.2022.3202140
    [15] Y. Tian, F. W. Fu, A fast algorithm of Syndrome computations for binary optimal locally repairable array codes, IEEE Trans. Commun., 73 (2025), 13117–13129. https://doi.org/10.1109/TCOMM.2025.3615764 doi: 10.1109/TCOMM.2025.3615764
    [16] S. J. Lin, An encoding algorithm of triply extended Reed–Solomon codes with asymptotically optimal complexities, IEEE Trans. Commun., 66 (2018), 3235–3244. https://doi.org/10.1109/TCOMM.2017.2737441 doi: 10.1109/TCOMM.2017.2737441
    [17] L. Yu, S. J. Lin, H. Hou, Z. Li, Reed-Solomon coding algorithms based on Reed-Muller transform for any number of parities, IEEE Trans. Comput., 72 (2023), 2677–2688. https://doi.org/10.1109/TC.2023.3262922. doi: 10.1109/TC.2023.3262922
    [18] J. Kurihara, S. Kiyomoto, K. Fukushima, T. Tanaka, A new (k, n)-threshold secret sharing scheme and its extension, In: Information security. ISC 2008, Berlin: Springer, 2008,455–470. https://doi.org/10.1007/978-3-540-85886-7_31
    [19] A. Shamir, How to share a secret, Commun. ACM, 22 (1979), 612–613. https://doi.org/10.1145/359168.359176 doi: 10.1145/359168.359176
    [20] A. Hineman, M. Blaum, A modified Shamir secret sharing scheme with efficient encoding, IEEE Commun. Lett., 26 (2022), 758–762. https://doi.org/10.1109/LCOMM.2022.3144375 doi: 10.1109/LCOMM.2022.3144375
    [21] Y. Wang, Y. Desmedt, Efficient secret sharing schemes achieving optimal information rate, In: 2014 IEEE information theory workshop (ITW 2014), Hobart: IEEE, 2014,516–520. https://doi.org/10.1109/ITW.2014.6970885
    [22] L. Chen, T. M. Laing, K. M. Martin, Efficient, XOR-based, ideal $(t, n)$-threshold schemes, In: Cryptology and network security. CANS 2016., Cham: Springer, 2016,467–483. https://doi.org/10.1007/978-3-319-48965-0_28
    [23] F. J. MacWilliams, N. J. A. Sloane, The theory of error-correcting codes, In: North-Holland mathematical library, Elsevier, 16 (1977), 1–762.
    [24] J. Lv, H. Zhu, W. Fang, H. Hou, S. T. Xia, New constructions of $q$-ary MDS array codes derived from $\mathbb{F}_q[x] / \langle x^m + \lambda \rangle$ and their efficient erasure encoding/decoding, IEEE Trans. Inf. Theory, 71 (2025), 8429–8446. https://doi.org/10.1109/TIT.2025.3610497 doi: 10.1109/TIT.2025.3610497
    [25] C. Ding, D. Pei, A. Salomaa, Chinese remainder theorem: Applications in computing, coding, cryptography, United States: World Scientific Publishing Co., Inc., 1996.
    [26] X. Lian, J. Lv, H. Zhu, S. Xia, H. Hou, Array codes with local properties and their application to Shamir secret sharing scheme, In: IEEE International symposium on information theory (ISIT), Guangzhou: IEEE, 2026, in press.
    [27] S. L. Yang, On the LU factorization of the Vandermonde matrix, Discrete Appl. Math., 146 (2005), 102–105. https://doi.org/10.1016/j.dam.2004.08.003 doi: 10.1016/j.dam.2004.08.003
  • Reader Comments
  • © 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.6

Metrics

Article views(20) PDF downloads(3) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(1)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog