Decoding of Lifted Affine-Invariant Codes

被引：0
作者：
Holzbaur, Lukas [1 ]
Polyanskii, Nikita [1 ,2 ]
机构：
[1] Tech Univ Munich, Munich, Germany
[2] Skolkovo Inst Sci & Technol, Moscow, Russia
来源：
2020 IEEE INFORMATION THEORY WORKSHOP (ITW) | 2021年
关键词：
REED-MULLER CODES;
D O I：
10.1109/ITW46852.2021.9457613
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Lifted Reed-Solomon codes, a subclass of lifted affine-invariant codes, have been shown to be of high rate while preserving locality properties similar to generalized Reed-Muller codes, which they contain as subcodes. This work introduces a simple bounded distance decoder for (subcodes of) lifted affine-invariant codes that is guaranteed to decode up to half of an asymptotically tight bound on their minimum distance. Further, long q-ary lifted affine-invariant codes are shown to correct almost all error patterns of relative weight q - 1/q - epsilon for epsilon > 0.
引用
收藏
页数：5
相关论文
共 18 条
  • [1] Improved low-degree testing and its applications
    Arora, S
    Sudan, M
    [J]. COMBINATORICA, 2003, 23 (03) : 365 - 426
  • [2] Ben-Sasson Eli, 2011, Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques. Proceedings 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, P400, DOI 10.1007/978-3-642-22935-0_34
  • [3] PARTITIONS OF A VECTOR-SPACE
    BU, T
    [J]. DISCRETE MATHEMATICS, 1980, 31 (01) : 79 - 83
  • [4] ON GENERALIZED REED-MULLER CODES AND THEIR RELATIVES
    DELSARTE, P
    GOETHALS, JM
    MACWILLI.FJ
    [J]. INFORMATION AND CONTROL, 1970, 16 (05): : 403 - &
  • [5] Recursive decoding and its performance for low-rate Reed-Muller codes
    Dumer, I
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2004, 50 (05) : 811 - 823
  • [6] Gao SH, 2003, SPRINGER INT SER ENG, V712, P55
  • [7] Goldreich Oded, 2000, SIAM J. Discret. Math., V13, P535, DOI [10.1137/S0895480198344540, DOI 10.1137/S0895480198344540]
  • [8] Guo A., 2013, P 4 C INN THEOR COMP, P529, DOI 10.1145/2422436.2422494
  • [9] List-Decoding Algorithms for Lifted Codes
    Guo, Alan
    Kopparty, Swastik
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2016, 62 (05) : 2719 - 2725
  • [10] Holzbaur L, 2020, IEEE INT SYMP INFO, P634, DOI [10.1109/ISIT44484.2020.9174402, 10.1109/isit44484.2020.9174402]
12