Reed-Solomon Coding Algorithms Based on Reed-Muller Transform for Any Number of Parities

Based on the Reed-Muller (RM) transform, this paper proposes a Reed-Solomon (RS) encoding/erasure decoding algorithm for any number of parities. Specifically, we first generalize the previous RM-based syndrome calculation, which allows only up to seven parities, to support any number of parities. Th...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2023-09, Vol.72 (9), p.2677-2688
Main Authors: Yu, Leilei, Lin, Sian-Jheng, Hou, Hanxu, Li, Zhengrui
Format: Article
Language:English
Subjects:
Algorithms
Codes
Coding
computational complexity
Computational efficiency
Computing time
Decoding
Encoding
Galois fields
Linear equations
Mathematical analysis
Mathematical models
Matrix decomposition
Reed-Muller transform
Reed-Solomon code
storage erasure codes
Transforms
Vandermonde matrix
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Based on the Reed-Muller (RM) transform, this paper proposes a Reed-Solomon (RS) encoding/erasure decoding algorithm for any number of parities. Specifically, we first generalize the previous RM-based syndrome calculation, which allows only up to seven parities, to support any number of parities. Then we propose a general encoding/erasure decoding algorithm. The proposed encoding algorithm eliminates the operations in solving linear equations, and this improves the computational efficiency of existing RM-based RS algorithms. In terms of erasure decoding, this paper employs the generalized RM-based syndrome calculation and lower-upper (LU) decomposition to accelerate the computational efficiency. Analysis shows that the proposed encoding/erasure decoding algorithm approaches the complexity of \lfloor \lg T \rfloor + 1 ⌊lgT⌋+1 XORs per data bit with N N increasing, where T T and N N denote the number of parities and codeword length respectively. To highlight the advantage of the proposed RM-based algorithms, the implementations with Single Instruction Multiple Data (SIMD) technology are provided. Simulation results show that the proposed algorithms are competitive, as compared with other cutting-edge implementations.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2023.3262922