Low-Complexity Chase Decoding of Reed-Solomon Codes Using Module
- 27 July 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 68 (10) , 6012-6022
Abstract
The interpolation based algebraic soft decoding yields a high decoding performance for Reed-Solomon (RS) codes with a polynomial-time complexity. Its computationally expensive interpolation can be facilitated using the module structure. The desired Gröbner basis can be achieved by reducing the basis of a module. This paper proposes the low-complexity Chase (LCC) decoding algorithm using this module basis reduction (BR) interpolation technique, namely the LCC-BR algorithm. By identifying η unreliable symbols, 2η decoding test-vectors will be formulated. The LCC-BR algorithm first constructs a common basis which will be shared by the decoding of all test-vectors. This eliminates the redundant computation in decoding each test-vector, resulting in a lower decoding complexity and latency. This paper further proposes the progressive LCC-BR algorithm that decodes the test-vectors sequentially and terminates once the maximum-likelihood decision decoding outcome is reached. Exploiting the difference between the adjacent test-vectors, this progressive decoding is realized without any additional memory cost. Complexity analysis shows that the LCC-BR algorithm yields a lower complexity and latency, especially for high rate codes, which will be validated by the numerical results.Keywords
Funding Information
- National Natural Science Foundation of China (61671486)
- International Program for Ph.D. Candidates, Sun Yat-Sen University
This publication has 32 references indexed in Scilit:
- List decoding of Reed–Solomon codes from a Gröbner basis perspectiveJournal of Symbolic Computation, 2008
- Algebraic soft-decision decoding of reed-solomon codesIEEE Transactions on Information Theory, 2003
- On lattice reduction for polynomial matricesJournal of Symbolic Computation, 2003
- Ideal Bases and Primary Decomposition: Case of Two VariablesJournal of Symbolic Computation, 1985
- Fast solution of toeplitz systems of equations and computation of Padé approximantsJournal of Algorithms, 1980
- Fast algorithms for rational Hermite approximation and solution of Toeplitz systemsIEEE Transactions on Circuits and Systems, 1979
- Class of algorithms for decoding block codes with channel measurement informationIEEE Transactions on Information Theory, 1972
- Shift-register synthesis and BCH decodingIEEE Transactions on Information Theory, 1969
- Generalized minimum distance decodingIEEE Transactions on Information Theory, 1966
- Theorie der höheren Differentiale in einem algebraischen Funktionenkörper mit vollkommenem Konstantenkörper bei beliebiger Charakteristik.Journal für die reine und angewandte Mathematik (Crelles Journal), 1936