Algebraic list-decoding of Reed-Solomon product codes
Farzad Parvaresh, Mostafa El‐Khamy, M. A. Stepanov, Daniel Augot, Robert J. McEliece, Alexander Vardy · International Workshop Algebraic and Combinatorial Coding Theory · 2006
Product Reed-Solomon codes are widely used in data storage, optical and satellite communication systems. ReedSolomon product codes can be regarded as evaluation of a bivariate polynomial with constraints on its X and Y -degrees. In this work, we propose polynomial time algorithms to decode ReedSolomon product codes beyond half the minimum distance. The first algorithm is based on a generalization of the GuruswamiSudan type decoders. We are able to show that if fraction of number of errors is smaller than 1− 6 p4Rp, where Rp is the rate of the product code, then the algorithm can efficiently recover the transmitted codeword. The other algorithm is based on the fact that Reed-Solomon product codes can be viewed as subfieldsubcode of a generalized Reed-Solomon code. So, the decoding algorithms for Reed-Solomon codes are inherited to decoding of RS product codes. By using this fact, we prove that if fraction of number of errors is smaller than 1− 4 p4Rp then the algorithm is able to recover the transmitted codeword. 1