- Please sign up for the course at UniWorx.
Coding theory studies the transmission of information over lossy channels. In contrast to cryptography, the aim is not to protect information from evesdropping, but to recognise and correct transmission errors.
A simple task in coding theory is to encode a series of bit (of 4 bits, say) such that one bit error can be corrected. By sending the bit sequence twice, one needs to transmit eight bits and can recognise one error, but there is not enough information to correct errors. If one receives 00100011, for example, then one knows that there has been an error; the original information could have been 0010 (error in bit four) or 0011 (error in bit eight). If one sends the bit sequence three times, then it is possible to correct one bit error using a majority decision, but one has used twelve bits to do so. This lecture presents Hamming Codes, using which one can correct one error using only seven bits overall.
Other examples are Reed-Muller and Reed-Solomon codes. The (5,1)-Reed-Muller code, which was developed for a Mars expedition in the seventies, encodes 6 bits of information in 32 bits and can correct 7 bit errors. Reed-Solomon codes are used in audio CDs and mobile telephony and are especially good at correcting burst errors (e.g. several adjacents bit errors resulting from scratches).
This course presents such encoding methods and their fundamentals.
- Volume: 3+2 academic hours per week, 6 ECTS
Place and Time
|Lecture||Tuesday, noon-2pm||Amalienstr. 73A, 101||18.10.2016|
|Lecture||Thursday, 4pm-6pm||Amalienstr. 73A, 101|
|Tutorial||Monday, noon-2pm||Amalienstr. 73A, 120||24.10.2016|
To reach the planned 3 hours per week, lectures will only be held on the dates shown in the table below. Tutorials are held every week.
|1||10/18||L||mh||Motivation, Introductory examples, (7,16,3)-Hamming Code||01-18.10.|
|2||10/20||L||mh||Information, Shannon-Fano, Kraft's Inequality, Shannon's Theorem||02-20.10.|
|3||10/25||L||gc||source coding: image and video compression||Background|
|4||10/27||L||gc||channel coding: modulation, channel estimation, interleaving, fading, soft- and hard bits|
|5||11/3||L||gc||channel coding (cont'd)|
|6||11/8||L||mh||transinformation, perfect encryption, Fano's bound|
|7||11/10||L||mh||Hamming distance, channel capacity, channel coding theorem||03-10.11.|
|8||11/15||L||mh||linear codes, algebraic foundations||04-15.11.|
|9||11/17||L||mh||Varsamov Theorem, syndrome decoding, simplex code, Plotkin bound||05-17.11.|
|10||11/29||L||gc||Reed Solomon Codes||06-29.11.|
|11||12/1||L||gc||Cyclic Redundancy Checks, composite codes (concatenation, block, CIRC)||07-01.12.|
|12||12/6||L||mh||cyclic codes, BCH bound||08-06.12.|
|13||12/8||L||mh||convolutional codes, power series||09-08.12.|
|14||12/13||L||mh||generator matrices, catastrophic codes, recursive convolutional codes||see last note|
|15||12/20||L||mh||free distance, decoding of convolutional codes, Fano Algorithm||10-20.12.|
|16||1/12||L||mh||Viterbi algorithm, puncturing, tail biting|
|17||1/17||L||gc||Turbo codes||paper of Silvio Abrantes|
Legend: L means lecture, T means tutorial, E means exam
- Lecture Note on channel coding theorem (German). Not treated in class, not relevant for the exam.
- Lecture Note on Reed Muller codes and their decoding by majority vote (German). Not treated in class, not relevant for the exam.
exam will take place on 2/9/2017