טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentKolan Tom
SubjectCoding Techiques for Burst Errors
DepartmentDepartment of Computer Science
Supervisor Professor Ronny Roth
Full Thesis textFull thesis text - English Version


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.