Technical Report MSC-2011-20

TR#:MSC-2011-20
Class:MSC
Title: Coding Techniques for Burst Errors
Authors: Tom Kolan
Supervisors: Ronny Roth
PDFMSC-2011-20.pdf
Abstract: Error-correcting codes constitute one of the main methods for improving the reliability required in communication systems. Using this method, the sender adds redundant data to a message by coding it. The receiver is able to retrieve the sent message using a decoding algorithm, assuming that there are not too many errors caused by the channel. Let F be a finite alphabet, and assume without loss of generality that F is an Abelian group. A block code C of length n over F is a subset of Fn. Assume that a codeword c is transmitted over a communication channel and a word y is received, where e=y-c is the error word. The goal is to decode the word y successfully and find the transmitted codeword c. Our research focuses on (l,t)-burst list decoders. In this model, the error word e is a t-burst; namely, the errors are contained in t continuous coordinates of the received word. In contrary to unique decoding, the decoder outputs a list D(y) of at most l codewords that contains all codewords c' in C such that y-c' is a t-burst. A decoding success in the context of list decoding is the event where the transmitted codeword is in the returned list. Clearly, the decoding will be successful if the error word e is a t-burst. Standard list decoding has been thoroughly researched, and there are many codes, bounds, and algorithms suitable for it. On the other hand, although burst errors are common error patterns in many communication channels, list decoding of such errors has been hardly researched so far. In this work, we present codes achieving previously known bounds for list decoding of burst errors. These codes have two main advantages: their block length is the largest known so far and they have a low-complexity decoding algorithm. We also present new bounds for codes having an (l,t)-burst list decoder, which are in fact generalizations of previously known bounds. Constructions of codes achieving the new bounds are also shown. Finally, we show bounds and constructions for phased burst error correction.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2011/MSC/MSC-2011-20), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2011
To the main CS technical reports page

Computer science department, Technion
admin