Novel Burst Error Correction Algorithms for Reed-Solomon Codes
Yingquan Wu · IEEE Transactions on Information Theory · 2012
In this paper, we present three novel burst error correcting algorithms for an (n,k) Reed-Solomon code. The algorithmic complexities are of the same order as error-and-erasure decoding,O(rn), wherer=n-k. In particular, their hardware implementation shares elements of Blahut error-and-erasure decoding. In contrast, all existing single-burst error correcting algorithms, which are equivalent to the proposed first algorithm, have complexityO(r2n). The first algorithm corrects the shortest single-burst with lengthfup tor-1. The algorithm follows the key characterization that the ending locations of all candidate bursts can be purely determined by the roots of a polynomial which is a linear function of syndromes, and moreover, the shortest burst is associated with the longest sequence of consecutive roots. The algorithmic miscorrection probability is bounded byq-(r-1-f), whereqdenotes the field size. The second algorithm extends the first one to correct the shortest burst with lengthf≤r-3 and additionally a random symbol error. The algorithmic miscorrection probability is bounded byq-(r-3-f). The third algorithm probabilistically corrects the shortest burst with lengthf≤r-1-2δ and additionally δ (a small constant) random symbol errors. The algorithmic miscorrection and failure probabilities are both bounded byq-(r-1-2δ-f). Our simulation results for (60, 40) and (30, 16) shortened Reed-Solomon codes verify that the miscorrection probability for three algorithms and the failure probability for the third algorithm all decay exponentially (at the rate ofq-1) with respect to the length of burst.