The Taub Faculty of Computer Science Events and Talks

List decoding of error-correcting codes is a generalization of unique decoding: while unique decoding relates to the case where the decoder outputs only one word (the correct codeword), list decoding allows to output a list of codewords, as long as the correct codeword is included in the list. Codes for burst error correction have been studied mainly for the purpose of unique decoding. Understanding list decoding of burst errors is desirable for reliable delivery of data over various unreliable communication channels. In this work, we derive new bounds for list decodable burst error correcting codes, as well as codes achieving these bounds. The bounds are genralizations of the Reiger bound for burst error correcting codes, which states that a code is able to correct all \tau-bursts only if its redundancy is at least 2\tau. We find bounds for group codes (e.g. linear codes) and also for general block codes. We present explicit constructions of codes achieving the bounds. Furthermore, we present explicit constructions of codes achieving the previously known bounds having higher code lengths than the known codes. Decoding of burst errors is a fairly straight forward and low complexity algorithm, so the codes can be used in actual communication systems.