M.Sc Student | Kolan Tom |
---|---|

Subject | Coding Techiques for Burst Errors |

Department | Department of Computer Science |

Supervisor | Professor Ronny Roth |

Full Thesis text |

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 *F ^{n}*.
Assume that a codeword

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.