Interpolation-Based Low-Complexity Chase Decoding Algorithms for Hermitian Codes
- 25 December 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 66 (4) , 1376-1385
Abstract
Algebraic-geometric (AG) codes have good error-correction capability due to their generally large code word length. However, their decoding remains complex, preventing practical applications. Addressing the challenge, this paper proposes two interpolation-based low-complexity Chase (LCC) decoding algorithms for one of the most popular AG codes-Hermitian codes. By choosing η unreliable symbols and realizing them with the two most likely decisions, 2 η decoding test-vectors can be formulated. The first LCC algorithm performs interpolation for the common elements of the test-vectors, producing an intermediate outcome that will be shared by the uncommon element interpolation. It eliminates the redundant computation for decoding each test-vector, resulting in a low-complexity. With an interpolation multiplicity of one, the decoding is further facilitated by removing the requirement of pre-calculating the Hermitian curve's corresponding coefficients. The second LCC algorithm is an adaptive variant of the first algorithm, where the number of test-vectors is determined by the reliability of received information. When the channel condition improves, it can reduce the complexity without compromising the decoding performance. Simulation results show that the both LCC algorithms outperform a number of existing algebraic decoding algorithms for Hermitian codes. Finally, our complexity analysis will reveal the proposals' low-complexity feature.Keywords
Funding Information
- National Natural Science Foundation of China (NSFC) (61671486, 61372079)
This publication has 15 references indexed in Scilit:
- Construction and performance of algebraic–geometric codes over AWGN and fading channelsIEE Proceedings - Communications, 2005
- Algebraic soft-decision decoding of reed-solomon codesIEEE Transactions on Information Theory, 2003
- Efficient root-finding algorithm with application to list decoding of algebraic-geometric codesIEEE Transactions on Information Theory, 2001
- Decoding Hermitian Codes with Sudan’s Algorithm1999
- Improved decoding of Reed-Solomon and algebraic-geometry codesIEEE Transactions on Information Theory, 1999
- Algebraic-geometry codesIEEE Transactions on Information Theory, 1998
- Decoding of Reed Solomon Codes beyond the Error-Correction BoundJournal of Complexity, 1997
- Fast decoding of algebraic-geometric codes up to the designed minimum distanceIEEE Transactions on Information Theory, 1995
- Decoding algebraic-geometric codes up to the designed minimum distanceIEEE Transactions on Information Theory, 1993
- Shift-register synthesis and BCH decodingIEEE Transactions on Information Theory, 1969