דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
תום קולן (הרצאה סמינריונית למגיסטר)
event date icon
יום רביעי, 15.06.2011, 16:00
event location icon
in Taub 601
event speaker icon
מנחה: Prof. Ronny Roth
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.