The contents of the lecture can be grouped into two blocks: iterative decoding methods and algebraic decoding methods, which are suited for different kinds of applications.

Iterative decoding methods are interesting for operating points close to capacity in applications where codes with large block lengths can be applied. In the lecture, two classes of iterative decoding schemes will be considered. The class of Turbo Codes was introduced 1993 by C. Berrou, A. Glavieux and P. Thitimasjshima. A Turbo Code consists of simple parallel concatenated component codes, which can efficiently be decoded by a symbol-by-symbol A Posteriori Probability (s/s APP) decoder. Such an s/s APP decoder is capable of utilizing reliability information from the channel and can compute reliabilities for the code symbols. After formally introducing the concept reliabilities on the basis of probabilities, the principle of s/s APP decoding will be explained. After this, several tools for analyzing Turbo decoders are considered.

Another class of iteratively decodable codes is the class of Low Density Parity Check (LDPC) codes. Such codes are either described by sparsely occupied matrices or by bipartite graphs. Both descriptions will be considered, and it will be explained how LDPC codes can be constructed on the basis of these descriptions. After explaining how LDPC codes can be decoded iteratively, tools for analyzing them will be considered.

Algebraic decoding of Reed-Solomon codes is used in many technical data transmission and data storage systems like hard disks, CDs, DVDs, digital video broadcasting, and many other applications. Two types of decoding strategies will be considered: syndrome-based decoding and interpolation-based decoding. Syndrome-based techniques for decoding Reed-Solomon codes are known for more than 30 years, and allow for decoding errors up to half the minimum code distance. Since such methods can be implemented very efficiently, they are applied in many algebraic error correcting schemes. After introducing these classical syndrome-based methods, it will be explained how these techniques may be applied in interleaved Reed-Solomon (IRS) schemes for decoding errors beyond half the minimum distance.

In 1997, M. Sudan proposed a novel algorithm for decoding Reed-Solomon codes, which is based on bivariate polynomial interpolation. This algorithm can also decode errors beyond half the minimum distance by creating lists of codewords to resolve ambiguous decoding situations. Moreover, derivatives of the Sudan algorithm are capable of using lists of symbols at their inputs. The principles behind such interpolation-based techniques will be considered in the last part of the lecture. It will be explained how the list decoding concept can be used for decoding errors beyond half the minimum distance, and how the problem of list decoding is solved by the Sudan algorithm and its derivatives.

In the exercise, students have the opportunity to implement selected algorithms from the lecture using MATLAB under guidance of a research assistant.

Iterative Decoding Methods:

• Turbo-Codes
  • A Posteriori Probability (APP) Decoding
  • Intrinsic and Extrinsic Information
  • Statistical Analysis Methods like Monte-Carlo Simulation and Exit-Chart-Analysis
• Low Density Single Parity Check (LDPC) Codes
  • Matrix and Graph Representation of LDPC Codes
  • Code Construction
  • Iterative Decoding by "Message Passing"
  • Statistical and Graph-Based Analysis Methods like Density Evolution and Stopping Sets

Algebraic Decoding Methods:

• Syndrome-Based Techniques
  • Reed-Solomon (RS) Codes
  • Classical Decoding Approaches like the Peterson-Gorenstein-Zierler and Forne Algorithms
  • Interleaved Reed-Solomon (IRS) Codes and Collaborative Decoding
• Interpolation-Based Techniques
  • Interpretation of the Decoding Problem as a Polynomial Interpolation Problem
  • The Sudan Algorithm and its Derivatives
  • List Decoding Concepts

• Bossert M., Channel Coding for Telecommunications, John Wiley & Sons, 1999
• Blahut R. E., Algebraic Codes for Data Transmission, Cambridge University Press, 2003
• Roth R., Introduction to Coding Theory, Cambridge University Press, 2006
• Justesen J. and Hoeholdt, T., A Course In Error Correcting Codes, EMS Publishing House, 2004
• MacWilliams F. J. and Sloane N. J. A., The Theory of Error-Correcting Codes, Elsevier, 1977
  
  

The script can be ordered from the Fachschaft Elektrotechnik, check here.

The complete collection of slides in one file can be downloaded here.

• Notes from Lecture 3 (s/s-APP) can be downloaded here.
• Notes from Lecture 5 (EXIT-Charts) can be downloaded here.
• Notes from Lecture 6 can be downloaded here.
• Notes from Lecture 7 can be downloaded here.
• Notes from Lecture 8 can be downloaded here.
• Notes from Lecture 12 can be downloaded here.

First lecture on 2012-04-16.

First exercise on Thursday, 2012-05-10.

Please check this site regularly for any last-minute changes and announcements!