Graduate seminar "Fuzzy Coding"

Responsible

Michael Nüsken, Prof. Dr. Joachim von zur Gathen

Time & Place

Wednesday, 15:00 - 17:00, b-it 1.25.
Organizational meeting: Tuesday, 3 April 2007,
16:00, b-it 1.25 (cosec meeting room).
First session: Wednesday, 2 May 2007, 15:00.

Ok, we changed the topic. We will deal with list decoding this semester. Coding theory is a rather old topic. It started evolving when electro-magnetic transmissions were coming up. The need to tolerate errors during the transmission made it necessary to find better ways than just repeating bits. Actually, you need to repeat each bit three times to get something better than just sending any bit once. The classical task is to encode short words to slightly longer words, and to decode the possibly distorted long words back to the short words. One single bit flip inside the long word should still lead to the original word. Or maybe two bit flips... Essentially, we introduce redundancy. Only we want to do that cleverly, as the increase in length decreases our transmission rate. Classically, the research focused on finding sets of code words that have large distance to each other, so that when only half that many bits are wrong the code word can still be found. Encoding and decoding were not important in this context. List decoding actually is "fuzzy decoding". A cleartext is encoded by a codeword. The possibly distorted codeword is decoded and some possibilities, ie. a list, for the original codeword are given. Formally, the decoding problem is given any word to find all codewords that differ in at most e places from the given word. Clearly, if that shall be efficient the output list must be short. If we limit the list length to 1 we have the classical problem. Further the obvious question is what the use of such a "fuzzy" code might be, if we are not able to decode uniquely. Actually, we will shed light on this. We will follow the book Guruswami (2004).

Schedule

Note that this is a working seminar. Its sessions might be less structured, talks more ad-hoc and with more discussion than usual. A session might thus expand and use another week or shrink.

Wednesday 02.05.2007 / 09.05.2007 :: Michael Nüsken, Introduction & Preliminaries
Wednesday 09.05.2007 /Tuesday 15.05.2007 13⁰⁰:: Michael Nüsken, Johnson-Type Bounds and Applications to List Decoding
Wednesday 06.06.2007 14⁰⁰ - 17¹⁵:: Daniel Loebenberger, Limits to List Decodability
Wednesday 13.06.2007 /Wednesday 20.06.2007 :: Damien Vergnaud, List Decodability vs. Rate
Wednesday 27.06.2007 :: NN, Reed-Solomon and Algebraic-Geometric Codes
Wednesday 04.07.2007 :: NN, A Unified Framework for List Decoding of Algebraic Codes
Wednesday 11.07.2007 :: NN, List Decoding of Concatenated Codes
??: NN, New, Expander-Based List Decodable Codes
??: NN, List Decoding from Erasures
??: NN, Linear-Time Codes for Unique Decoding
??: NN, Sample Applications Outside Coding Theory

Application

Contact Michael Nüsken.

Literature

Venkatesan Guruswami (2004). List Decoding of Error-Correcting Codes . LNCS 3282, Springer, Berlin, Heidelberg.
Jacobus H. van Lint (1999/1992/1982). Introduction to Coding Theory. Springer, Berlin. ISBN 978-3540641339.
F. J. MacWilliams & Neil J. A. Sloane (1998/1981). The theory of error-correcting codes. Elsevier/North-Holland, Amsterdam. ISBN 978-0444851932.
Wikipedia. Shannon theorem . (Tells what the best rate for a channel of given capacity can be and that this is asympotically almost achievable.)
Wikipedia. Shannon-Hartley theorem. (Tells what the capacity is for a electro-magnetic connection of a given band width and signal to noise ratio with only white noise.)

Allocation

Media Informatics, Communication Skills.
University of Bonn - Computer Science, A or A1.
University of Bonn - Mathematics, ??.