The Study of New Algorithms for Correcting Both Errors and Erasures of Reed-Solomon Codes

A new time-domain decoder of Reed-Solomon (RS) codes is proposed. Since the decoder can correct both errors and erasures without computing the erasure locator polynomial, the errata locator polynomial and the errata evaluator polynomial, the computational complexity can be reduced substantially. To demonstrate the benefit, the complexity comparisons of the proposed decoder with the Truong-Jeng-Hung and the Lin-Costello decoders are presented. These comparisons show that the proposed decoder always has lower computational requirement to correct all combination of u erasures and v errors than both the two related decoders on the condition of 2v+u smaller than the minimum Hamming distance. Finally, the (255, 223) and the (63, 39) RS codes are used as examples for the complexity comparisons. For decoding the two RS codes, the new decoder can save about 40 % additions and multiplications, compared with the two related decoders. Furthermore, it can also save just 50 % requirement of inverses.

Project ID:PB10308-2711
External Project ID:MOST103-2221-E182-014