Course 904: Error Control Coding (ECC) Fundamentals

Error control coding (ECC) uses controlled redundancy to detect and correct errors. When ECC is used to correct errors this is called Forward Error Correction (FEC). The method of error control coding used depends on the requirements of the system (e.g. data, voice, and video) and the nature of the channel (e.g. wireless, mobile, high interference).

Error control coding (ECC) Fundametals provides a concise introduction to basic coding techniques and their application. The fundamental concepts of coding theory are explained using simple examples with minimum use of complex mathematical tools. The selection of appropriate codes and the design of decoders are discussed.

This course is an introduction to error control coding. The field of error control coding is aimed at devising efficient encoding and decoding procedures to achieve reliable transmission of information across channels which are corrupted by noise.

In this course we will focus on various encoding and decoding strategies which have proved important in practice. Upon completion of this course, the participant should have a knowledge of the following topics:

• Error Control Coding (ECC)
• Linear Algebra for Coding
• Linear Block Codes
• Cyclic Codes
• Goppa - BCH Codes
• Finite Geometry Codes
• Block codes Convolutional Codes
• Convolutional encoders-
• Burst Error Codes
• Viterbi decoding
• List decoding
• Sequential decoding
• Trellis coded modulation
• Combining Modulation and Coding (Trellis Coding)
• Hybrid ARQ
• Applications of ECC

• Channel coding – why is it necessary?
• Introduction to algebra
• Linear block codes
• Generator and parity check matrices
• Standard array and syndrome table decoding
• Minimum distance of a block code
• Error detection and error correction
• Weight distribution of block codes
• Performance of block codes over binary symmetric channels
• Hamming codes
• Modifying block codes – puncturing, shortening, etc.
• Existence of codes with a given minimum distance and rate
• Galois Fields
• Construction of GF(2m)
• Computations in GF(2m)

Introduction to Error Coding

• Why error control?
• Block codes
• Block codes vs. convolutional codes
• Viterbi decoding
• List decoding
• Sequential decoding
• Convolutional encoders
• Convolutional codes
• Block codes

Cyclic Codes

• Generator and parity check matrices for cyclic codes
• Encoding and decoding of cyclic codes
• Error detection capability of cyclic codes
• Shortened cyclic codes – CRC codes
• Hadamard codes
• Golay codes
• Reed Muller codes
• BCH codes
• Primitive and non-primitive BCH codes
• Minimum distance of BCH codes
• Decoding of BCH codes, Berlekamp’s algorithm
• Reed-Solomon (RS) Codes
• Minimum distance of RS codes
• Decoding of RS Codes
• Burst error correcting codes, Fire codes

Convolutional codes

• Convolutional encoders
• Convolutional codes and their encoders
• The Smith form of polynomial convolutional encoders
• Equivalent convolutional encoders
• Systematic convolutional encoders
• Catastrophic convolutional encoders
• Convolutional codes with good distance properties
• Path enumeration
• Computing distance spectrum
• State diagrams
• Trellis diagrams,
• Catastrophic codes
• Weight enumerators and minimum distance of convolutional codes
• Decoding of Convolutional codes, Viterbi algorithm
• Hard decision decoding and soft decision decoding
• Performance analysis of convolutional codes, union bound
• Punctured convolutional codes
• Burst error correcting convolutional codes
• Trellis coded modulation (optional – if there is interest)
• Design of TCM schemes for AWGN, set partitioning
• Decoding using Viterbi algorithm
• Performance analysis

Viterbi decoding

• The Viterbi algorithm
• Error probability bounds for fixed convolutional codes
• Tailbiting trellisis

List decoding

• Algorithms
• performance

Sequential decoding

• The Fano metric
• The Stack algorithm
• The Fano algorithm

• Computational analysis

Block codes

• Reed-Solomon (RS) codes
• Cyclic codes
• Shift-register synthesis
• Generalized discrete Fourier transforms
• Decoding RS codes
  Trellis coded modulation
• Different squared Euclidean distances
• Set partitioning. Lattice codes
• Trellis codes
• Coding gain

Workshops 1

Workshops 2

LAB 1

LAB 2

LAB 3