Channel Coding on Graphs (ChCoGraph)5 ECTS
(englische Bezeichnung: Channel Coding on Graphs)
(Prüfungsordnungsmodul: Channel Coding on Graphs)

Lehrveranstaltungen:

• • Channel Coding on Graphs
    (Vorlesung, 3,5 SWS, Laura Cottatellucci, Di, 12:15 - 13:45, 01.021; Mi, 14:15 - 15:45, 01.021, (außer Mi 13.5.2020, Mi 10.6.2020, Mi 8.7.2020))
  • Tutorial for Channel Coding on Graphs
    (Übung, 0,5 SWS, Nikita Shanin, jede 4. Woche Mi, 14:15 - 15:45, 01.021; ab 13.5.2020)

Empfohlene Voraussetzungen:

Es wird empfohlen, folgende Module zu absolvieren, bevor dieses Modul belegt wird:

Kanalcodierung (WS 2019/2020)

Inhalt:

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 algorithm.

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

Lernziele und Kompetenzen:

The student
• Uses idealized channel models (the binary symmetric channel (BSC), the binary erasure channel (BEC), the constrained-input Gaussian channel) to compute their capacities
• Contrasts soft output decoders with disjoint detection and decoding, maximum likelihood and maximum a posteriori decoders
• Relates the concepts of Parity Check, Hamming distance, weight enumerating functions to the performance analysis of codes on graphs
• Devises factor graphs of proposed communication systems
• Assesses and justifies the applicability of belief propagation to given factor graphs
• Assesses and justifies the applicability of message passing to codebooks defined in terms of Tanner graph or parity check matrix
• Applies message passing to codebooks defined in terms of Tanner graph or parity check matrix
• Analyses the performance of LDPC code decoding via density evolution
• Computes exit charts for LDPC codes for the equations of the density evolution
• Designs LDPC ensemble for a given channel to maximize the code rate
• Justifies the design of LDPC codes via design of LDPC ensembles
• Interprets convolutional codes as linear block codes
• Compares algebraic and dynamic representations of convolutional codes
• Computes steps of the Viterbi algorithm
• Summarizes and justifies the fundamental structure of the Viterbi algorithm
• Computes steps of the BCJR algorithm
• Summarizes and justifies the fundamental structure of BCJR algorithm
• Compares Viterbi and BCJR algorithms
• Justifies low complexity and/or practical implementations of the Viterbi and the BCJR algorithm
• Attaches a direct graph to a convolutional code and computes its transfer function
• Assesses the performance of the Viterbi decoder via (bit) weight enumerating function based on the transfer function method
• Interprets a BCJR algorithm as message passing over a factor graph
• Combines encoders of convolutional codes to generate parallel concatenated codes with interleaver (turbo codes) of given rate
• Combines encoders of convolutional codes to generate serial concatenated codes with interleaver (turbo codes)
• Compares the key features of parallel concatenated codes with interleaver (turbo codes) to serial concatenated codes with interleaver (turbo codes)
• Designs decoders for turbo codes utilizing coupled BCJR-based decoders for convolutional codes
• Interprets turbo decoders as factor graphs and justifies their implementation via message passing
• Assesses the performance of turbo codes using exit charts
• Formulates the concept of source polarization and relates it to polar channel coding
• Interprets polar channel coding as factor graphs
• Designs polar channel codes
• Argues about capacity achievability of polar channel codes

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Communications and Multimedia Engineering (Master of Science)
   (Po-Vers. 2011 | TechFak | Communications and Multimedia Engineering (Master of Science) | Gesamtkonto | Wahlmodule | Technische Wahlmodule | Channel Coding on Graphs)

Studien-/Prüfungsleistungen:

Channel Coding on Graphs (Prüfungsnummer: 412023)

(englischer Titel: Channel Coding on Graphs)

Prüfungsleistung, Klausur, Dauer (in Minuten): 90, benotet, 5 ECTS

Anteil an der Berechnung der Modulnote: 100.0 %

weitere Erläuterungen:
Possibly carried out as a 30-minute digital remote exam with ZOOM.
Evtl. digitale Fernprüfung von 30 Minuten Dauer mittels ZOOM.

Prüfungssprache: Englisch

Erstablegung: SS 2020, 1. Wdh.: WS 2020/2021

1. Prüfer:

Laura Cottatellucci