Channel Coding on Graphs
*Description* In today's communications world, channel coding underlies the physical layer of all major communication systems. For example: algebraic block coding (Reed-Solomon codes) are used in the CD and DVD standards; trellis coded modulation is used in line modems; low-density parity check codes (LDPC) are used in satellite communications (DVB-S2 standard), LAN (10GBase-T Ethernet) and wireless LAN (Wi-Fi 802.11); turbo codes are implemented in 3G/4G mobile communications (e.g. in UMTS and LTE) and in (deep space) satellite communications. Recently, polar codes have been adopted for the eMBB (Enhanced Mobile Broadband) control channels for the 5G NR (5th Generation New Radio) interface. 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.