###### Sprachumschaltung

You are here: Home / Coding Theory

# Coding Theory

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

## News

• Add pictures of whiteboard in Materials
• Exam date has changed to 2/23.

## 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, power series 09-08.12. 12/12 T Reed-Solomon Tutorial 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 1/16 T tutorial 17 1/17 L gc Turbo codes paper of Silvio Abrantes 18 1/19 L gc LDPC codes slides of Jack Wolf 1/23 T tutorial 19 1/24 L gc advanced topics: LTE Advanced, MIMO, HARQ 20 1/26 L gc exam preparation

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

## Tutorials

Exercises and problem sheets will be available on Uniworx

## Exam

Date: Feb. 23rd, 2017
Time:
2pm-4pm
Location:
room C123, Theresienstr. 41

Make-Up Exam:

Date: April 20rd, 2017
Time:
1pm-6pm
Location:
room B U101, Oettingenstr. 67