Submitted by admin on Mon, 06/10/2024 - 05:00
In this paper, we first formulate a novel Chase Guruswami-Sudan algorithm which list corrects not only all errors among the Chase flipping symbols but also the number of errors up to the enhanced Johnson bound among remaining positions, for Reed-Solomon and $q$ -ary BCH codes. The enhanced Johnson bound is induced by shortening the code without those Chase flipping symbols. We next devise a novel Chase Kötter-Vardy algorithm for soft decision decoding of Reed-Solomon codes. We show that the a posteriori probabilities of two branches of one of the least unreliable symbols which undergo Chase flipping shall be merged and assigned to the correct branch out of the two (it does not matter anyway if neither is correct), based on the rationale that one of exhaustive Chase flipping patterns must hit the genie pattern among the flipped symbols. During the exhaustive trial-and-error Chase decoding, each flipping pattern is treated as the genie and thus the associated branches of each flipping symbol are assigned with the merged a posteriori probabilities while its alternative branch is amortized. The multiplicity matrix is constructed using the state-of-the-art Kötter-Vardy transformation. We show by both theoretical analysis and simulations that the proposed Chase Kötter-Vardy algorithm significantly outperforms the original Kötter-Vardy algorithm under a similar complexity. We then extend this approach to a coded Chase decoding scheme wherein the Chase pattern set comes from a covering code. Surprisingly, simulations show that the best performance is typically achieved by concatenating the exhaustive Chase flipping on a number of the most reliable secondary indexes and a coded Chase flipping on the remaining secondary most reliable secondary indexes. We also employ a novel preprocessing technique that enforces a zero constant term for the message polynomial, by equivalently sacrificing one parity symbol. It effectively eradicates spurious candidate bivariate polynomials by merely computing and checking their constant terms, and thus dramatically reduces the number of candidate bivariate polynomials that are actually interpolated and factorized.
Yingquan Wu
Jun Ma