Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Teaching / Winter 2016/17 / Coding Theory


Inhaltsbereich

Coding Theory

Lecture, Tu noon-2pm, Th 4pm-6pm, Hofmann, Cichon; Tutorial, Mo noon-2pm, Cichon

News

  • Please sign up for the course at UniWorx.

Contents

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.


Organization

    • Volume: 3+2 academic hours per week, 6 ECTS
    • Lecture: Prof. Dr. Martin Hofmann, Dr. Gordon Cichon
    • Tutorials: Dr. Gordon Cichon

Place and Time

SessionTimeBegin
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.

# Date Type Topic Lecture Notes
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.
10/24 T tutorial
3 10/25 L gc source coding: image and video compression Lecture Slides, Background
4 10/27 L gc channel coding: modulation, channel estimation, interleaving, fading, soft- and hard bits
10/31 T tutorial
5 11/3 L gc channel coding (cont'd)
11/7 T tutorial
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.
11/14 T tutorial
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.
11/28 T tutorial
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/5 T tutorial
12 12/6 L mh cyclic codes, BCH bound 08-06.12.
13 12/8 L mh convolutional codes, generator matrices, power series 09-08.12.
12/12 T tutorial
14 12/13 L mh free distance, decoding of convolutional codes, Fano Algorithm
15 12/15 L mh Viterbi algorithm, puncturing, tail biting
16  1/12 L mh slack (possibly Reed-Muller Codes)
1/16 T tutorial
17 1/17 L gc Turbo codes
18 1/19 L gc LDPC codes
1/23 T tutorial
19 1/24 L gc advanced topics
20 1/26 L gc exam preparation
21 2/9 E exam

Legend: L means lecture, T means tutorial, E means exam


Tutorials

Exercises and problem sheets will be available on Uniworx


Material


Exam

exam will take place on 2/9/2017

Document Actions


Funktionsleiste