Novel burst error correcting algorithms for Reed-Solomon codes

In this paper, we present three novel burst error correcting algorithms for an (n,k,r = n - k) Reed-Solomon code. The algorithmic complexities are of the same order for erasure-and-error decoding, O(rn), moreover, their hardware implementation shares the elements of the Blahut erasure-and-error decoding. In contrast, all existing single-burst error correcting algorithms, which are equivalent to the proposed first algorithm, have cubic complexity, O(r²n). The first algorithm corrects the shortest single-burst with length f <r. The algorithm follows the key characterization that the starting 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 rate is bounded by nq^f-r, where q denotes the field size. The second algorithm extends the first one to correct the shortest burst with length f < r-2 with up to a random error. The algorithmic miscorrection rate is bounded by n²q^f+1-r. The third algorithm aims to correct the shortest burst with length f < r -2¿ with up to ¿ random errors, where ¿ is a given small number. The algorithmic miscorrection rate is bounded by n^¿+1q^-(r-f-¿) while its defect rate is bounded by nq^{-(r-2¿-f)¿} (whereas no defect occurs to the proposed first and second algorithms).