Coding for Communications
List Decoding

Fast Soft Decision Decoding of Linear Block Codes Using Partial Syndrome Search

Changryoul Choi, Jechang Jeong

Date & Time

01:00 am – 01:00 am


Ordered statistics-based decoding (OSD) is a soft decision decoding algorithm for linear block codes, yielding near maximum likelihood decoding performance. The OSD algorithm first sorts the received symbols in descending order based on the reliability and partitions the sorted symbols into the most reliable bases (MRB) and least reliable bases (LRB). Owing to the nature of the ordering symbols in the LRB, we presume that the expected number of errors in the leftmost (or most significant) part of LRB is relatively small compared to that in the other parts of LRB. Based on this observation, we can omit the impossible candidates in advance, by using Hamming weights of partial syndromes. This results in huge computational savings without compromising the decoding performance. Compared with OSD based on probabilistic necessary conditions and probabilistic sufficient conditions [3], [4], incorporation of the proposed algorithm into fast and scalable OSD [7] exhibits speed-up gains of a factor of approximately 405 (at 3.0 dB) for (127,64) BCH codes (maximum order 5), without compromising the decoding performance.


Changryoul Choi

Hanyang University

Jechang Jeong

Hanyang University

Session Chair

Michael Lentmaier

Lund University