Error Control Coding

Antal poäng: 5.0. Valfri för: D4, E4. Kursansvarig: Mats Cedervall. Förkunskapskrav: Digitalteknik Rekommenderade förkunskaper: Informationsteori Prestationsbedömning: Godkänt projekt är ett krav för att få tentera. Tentamen (5 tim) är skriftlig och av problemlösningstyp. Övrigt: 2 frivilliga laborationer Webbsida http://www.it.lth.se/ecc


Error control coding should protect digital data against errors which occur during transmission over a noisy communication channel or during storage in an unreliable memory. The last decade has been characterized by not only an exceptional increase in data transmission and storage but also in a rapid development in microelectronics providing us with both a need for and the possibility to implement sophisticated algorithms for error control.

Introduction. Why error control? Block codes - a primer, a first encounter with convolutional codes, block codes vs. convolutional codes.

Convolutional encoders - structural properties. Convolutional codes and their encoders, the Smith form of polynomial encoding matrices, equivalent and basic encoding matrices, minimal - basic and minimal encoding matrices, minimal encoders, syndrome formers and dual encoders, systematic encoders.

Distance properties of convolutional codes. Distance measures, distances for cascaded convolutional codes, upper and lower bounds on the free distance, lower bound on the distance profile, path enumeration.

Viterbi decoding. The Viterbi algorithm, error probability bounds for convolutional codes, quantization of channel outputs.

List decoding. Decoding with limited resources, list decoding (algorithm, error probability bounds).

Sequential decoding. The Fano metric, the Stack algorithm, computational analysis, the Fano algorithm.

Convolutional encoders with good distance properties. Computing distance spectrum (FAST), some classes of rate R = 1/2 encoders.

Block codes. Reed-Solomon (RS) codes, cyclic codes, discrete Fourier transforms, decoding RS codes (the Berlekamp-Massey algorithm), erasures and errors decoding.

Trellis coded modulation. Band-limited channels and QAM, coding fundamentals, lattice-type trellis codes, geometrically uniform trellis codes, decoding of modulation codes, precoding.


Johannesson, R. & Zigangirov, K. Sh.: Fundamentals of Convolutional Coding, IEEE Press, 1999.