Efficient Ordered Statistics Decoding of BCH Codes Without Gaussian Elimination
- 24 September 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (11) , 8294-8311
Abstract
Ordered statistics decoding (OSD) can achieve near maximum likelihood (ML) decoding performance for BCH codes. However, Gaussian elimination (GE) that delivers the systematic generator matrix of the code has an uncompromised latency. Addressing this challenge, this paper proposes a low-latency OSD (LLOSD) for BCH codes. Since BCH codes are binary subcodes of Reed-Solomon (RS) codes, codeword candidates can be produced using the RS systematic generator matrix, whose entries can be generated in parallel. By eliminating the non-binary codeword candidates and identifying the ML codeword, the LLOSD yields a lower latency as well as complexity than the OSD. It is shown that the LLOSD can be interpreted as generating the codeoword candidates through systematic encoding of a punctured BCH codeword, explaining its low-complexity feature. Moreover, the segmented variant is proposed to further facilitate the LLOSD. In order to decode long BCH codes, a hybrid soft decoding (HSD) is finally proposed. It integrates the LLOSD and the algebraic Chase decoding that can effectively provide extra TEPs for the LLOSD, enhancing the decoding performance. Both the complexity and performance of the proposed decoding are analyzed, demonstrating their advantage over the relevant state-of-the-art decoding.Keywords
Funding Information
- Natural Science Foundation of Guangdong Province (2024A1515010213)
- National Natural Science Foundation of China (62471503)
This publication has 33 references indexed in Scilit:
- Ordered-Statistics Decoding with Adaptive Gaussian Elimination Reduction for Short Codes2022
- Efficient error-correcting codes in the short blocklength regimePhysical Communication, 2019
- Factorization-free Low-complexity Chase soft-decision decoding of Reed-Solomon codes2009
- Probabilistic Sufficient Conditions on Optimality for Reliability Based Decoding of Linear Block Codes2006
- On lattice reduction for polynomial matricesJournal of Symbolic Computation, 2003
- Improved decoding of Reed-Solomon and algebraic-geometry codesIEEE Transactions on Information Theory, 1999
- A unified method for evaluating the error-correction radius of reliability-based soft-decision algorithms for linear block codesIEEE Transactions on Information Theory, 1998
- Complementary reliability-based decodings of binary linear block codesIEEE Transactions on Information Theory, 1997
- Soft-decision decoding of linear block codes based on ordered statisticsIEEE Transactions on Information Theory, 1995
- An efficient maximum-likelihood-decoding algorithm for linear block codes with algebraic decoderIEEE Transactions on Information Theory, 1994