| |
Coding theory
| Credits |
8 credit points |
| Instructors |
Tilborg, H.C.A. van (Technische Universiteit Eindhoven), Willems, F. (Technische Universiteit Eindhoven), Pellikaan, G.R. (Technische Universiteit Eindhoven) |
| E-mail |
H.C.A.v.Tilborg@tue.nl, f.m.j.willems@tue.nl, g.r.pellikaan@TUE.nl |
| Aim |
To use structured redundancy to protect digital data efficiently against noise. These techniques are commonly applied whenever information is digitally stored and transmitted. The focus of the course will be on two approaches: (A) block codes and algebraic decoding methods and (B) convolutional codes and probabilistic methods.
|
| Description |
I Block Codes and Algebraic Decoding Methods
* Shannon's communication model, the capacity of the BSC channel.
* Linear codes, characteristic parameters (like the dimension, the minimum distance and the covering radius), a generator matrix, a parity-check matrix, coset leaders and syndrome decoding.
* Some bounds, e.g. those of Hamming, Gilbert-Varshamov, Griesmer
* The weight enumerator and the MacWilliams relations.
* Hamming codes with their weight enumerator, Reed-Muller codes and their decoding.
* Cyclic codes with the standard notions, like the generator polynomial and the parity check polynomial. Construction and description by means of finite fields and extension fields.
* BCH codes, Reed Solomon codes and the two Golay codes.
* Decoding cyclic codes.
* Algebraic geometry codes II Convolutional Codes and Probabilistic Decoding Methods
* Convolutional Codes (state diagrams and trelisses, Viterbi decoding, path enumeration and error bounds)
* Channel Capacity (modulation, additive Gaussian noise channel, signal-to-noise ratio, capacity, channel input and output quantization, binary symmetric channel, capacity considerations)
* Forward Backward Algorithm (maximum a posteriori and maximum likelihood rules, word vs. symbol error probability, alpha and beta recursion, producing soft output)
* Turbo Codes (structure, feedback convolutional code, extrinsic information, iterative decoding, simulations)
* Low Density Parity-Check Codes (structure, a lemma, decoding a digit using (a) only channel information, (b) using a simple parity-check equation, (c) using several parity-check equations, iteration, log-likelihood ratios, density evolution, min-sum approximation)
|
| Organization |
7 weeks on block codes followed by 5 weeks on convolutional codes. |
| Examination |
Written |
| Literature |
* Henk van Tilborg, Error-Correcting Codes - A First Course, Studentlitteratur, Lund, Sweden, 1993 (Out of print, copy obtainable from lecturer).
* T. Hoeholdt, J.H. van Lint and R. Pellikaan, Algebraic geometry codes, in: V. Pless and W. Huffman eds., Handbook of Coding Theory, vol 1, Elsevier, 1998, 871-961.
* R.J. McEliece: The Algebraic Theory of Convolutional Codes, in: V. Pless, W. Huffman (eds.), Handbook of Coding Theory, vol. 1, Elsevier, 1998, 1065-1138 (copy can be obtained from the lecturer).
* Other articles or hand-outs will be announced throughout the course.
|
| Prerequisites |
Abstract algebra in particular finite fields, Combinatorics, Probability Theory. |
| Remarks |
Written exam: tuesday 20 Januari 2009 UvA
Roetereilandcomplex
gebouw A, zaal D.
Roetersstraat 15,
Amsterdam |
|
