M.Sc Thesis
M.Sc Student Kolan Tom Coding Techiques for Burst Errors Department of Computer Science Professor Ronny Roth

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.