ECE 710 Topic 5 - Fall 2013

ECE 710 Topic 5 - Algebraic Coding Theory

Instructor

Professor Oussama Damen

General description

This course covers the classical algebraic coding theory and some advanced topics in coding such as turbo and LDPC codes. If time allows, more recent coding topics such as lattice codes and their application over different communications channels, space-time codes, polar codes can be (slightly) covered. The course comprises two projects on implementing coding and decoding algorithms covered in the lectures. The following topics will be covered: finite fields Algebra, Hamming distance, bounds on the minimum distance of block codes, linear block codes, BCH codes, Reed-Solomon codes, convolutional codes, discrete channel and hard-decision decoding, algebraic decoding of BCH and Reed-Solomon codes, convolutional codes over additive white Gaussian noise channels, optimal decoding of convolutional codes (the Viterbi algorithm) and suboptimal decoding of convolutional codes (sequential decoding), forward-backward algorithm and soft-in soft-out decoding, turbo codes and iterative decoding, LDPC codes and the sum-product algorithm.

Textbook

No required textbook. For some topics indicated herewith, the following references will be used.

References

  1. Error Control Coding, 2nd ed., by S. Lin and D. Costello, Prentice-Hall, 2004.
  2. Introduction to Coding Theory, R. M. Roth, Cambridge University Press, 2006.
  3. Papers in the Transactions of the IEEE (to be communicated during the lectures).
  4. Sphere Packing, Lattices and Groups, 3rd ed. by J.H. Conway and N.J. Sloane.
  5. Information Theory and Reliable Communication, by R. Gallagar.

Course outline

  1. Introduction and finite fields Algebra
    • Revision of communication channels, representation of signals, sampling theorem, channel coding theorem, error exponents.
    • Finite fields Algebra: Groups, rings, fields. Arithmetic in Galois fields. Irreducible polynomials and primitive elements.Vector spaces and matrices.
  2. Error correcting codes over discrete channels.
  3. Linear block codes and the Hamming distance properties.
  4. Cyclic codes, BCH codes and Reed-Solomon codes.
  5. Convolutional codes, trellis representation of convolutional codes and distance properties.
  6. Turbo and LDPC codes.
  7. Receiver architecture
    • Algebraic decoding of BCH and Reed-Solomon codes. (The first project will cover algebraic decoding implementation over discrete channels).
    • The Viterbi algorithm.
    • Sequential decoding. (The second project will cover the implementation of Viterbi or Sequential decoding).
      • The Stack algorithm.
      • The Fano algorithm.
      • Performance characteristics of sequential decoding.
    • The turbo receiver and the sum-product algorithm.

Grading

The grading consists in two projects, a midterm and a final. Projects (2 × 15 = 30%), midterm (30%) and final (40%).