Objective of this course is to provide an introductory but thorough background on codes over graphs and covers both classical convolutional codes and the modern theory of random-like codes with iterative decoding. Namely, LDPCs (Low Density Parity Check Codes, Turbo Codes, and Polar Codes. Students will acquire the fundamental knowledge to design and analyze performance of channel codes on graphs, as well as implement the corresponding encoders and decoders.

Technical Content

• Role of channel coding in a communication system.

• Idealized channel models : the binary symmetric channel (BSC), the binary erasure channel (BEC), the constrained-input Gaussian channel.

• Some preliminary basic concepts from linear block codes: Parity Check, Hamming distance, weight enumerating functions, performance evaluations, and performance bounds.

• Factor graphs and belief propagation.

• Binary random-like codes: LDPC codes and message-passing decoding, threshold behaviour of message passing decoding: density evolution analysis. Design of LDPC ensembles.

• Polar Codes: Polarization, polar channel coding, performance, encoding and decoding.

• Binary convolutional codes : the algebraic structure, the dynamic structure, Viterbi decoding, performance analysis via weight enumerating function, the forward-backward BCJR algorithm.

• Other random-like codes: the Turbo Codes. Efficient decoding of Turbo Codes via forward-backward BCJR algorithm and interpretation via factor graphs. Performance analysis and exit charts.
  

Credits: 5