Erasure-only list decoding of Reed-Solomon and BCH codes with applications to their product codes
Yingquan Wu · 2011
In this paper, we first investigate erasure-only list decoding of Reed-Solomon and BCH codes. We consider the scenario in which some locations of a received word are pre-corrected. Accordingly, the rational curve fitting algorithm does not interpolate the known locations, and thus effectively increases the list error correction capability (LECC). For a Reed-Solomon code C(n, k, d), let n* be the effective code length by neglecting known locations, then the resulting LECC is n* - √(n*(n* - d)), independent of the actual code length n. When n* moves toward d, the LECC approaches to d. For a BCH code C(n, k, d), let n* be the effective code length by neglecting known locations, then the resulting LECC is 1 over 2 (n* - √(n*(n* - 2d))), independent of the actual code length n. When n* reduces toward 2d, the LECC approaches to d. In particular, it lists all (up to 2d2+ 2) codewords among any 2d erasure bits by applying twice the list decoding algorithm (one with the given 2d bits, the other with all flipped 2d bits). We then apply the proposed algorithms to the iterative decoding of product Reed-Solomon/BCH codes [C1Θ C2](n1n2, k1k2, d1d2), where some locations of a row (column) word are pre-corrected by preceding column (row) decoding (by neglecting miscorrection). We show that by iterating three rounds, the proposed iterative list decoding algorithm guarantees to correct up to 27/32 d1d2errors for a product Reed-Solomon code, and 27/16 d1d2errors for a product BCH codes (with the underlying assumption that each component word does not correct beyond minimum distance).