|
-
Modulverantwortliche/r: Ralf Müller
Lehrende:
Ralf Müller
weitere Studienfächer/Prüfungsordnungsmodule:
Einfrieren der UnivIS-Modul-Beschreibung: 11.10.2021
Information Theory and Coding (90481)
Start semester: |
WS 2021/2022 | Duration: |
1 semester | Cycle: |
halbjährlich (WS+SS) |
Präsenzzeit: |
60 Std. | Eigenstudium: |
90 Std. | Language: |
Englisch |
Lectures:
Inhalt:
1. Introduction: binomial distribution, (7,4)-Hamming code, parity-check matrix, generator matrix
2. Probability, entropy, and inference: entropy, conditional probability, Bayes’ law, likelihood, Jensen’s inequality
3. Inference: inverse probability, statistical inference
4. The source coding theorem: information content, typical sequences, Chebychev inequality, law of large numbers
5. Symbol codes: unique decidability, expected codeword length, prefix-free codes, Kraft inequality, Huffman coding
6. Stream codes: arithmetic coding, Lempel-Ziv coding, Burrows-Wheeler transform
7. Dependent random variables: mutual information, data processing lemma
8. Communication over a noisy channel: discrete memory-less channel, channel coding theorem, channel capacity
9. The noisy-channel coding theorem: jointly-typical sequences, proof of the channel coding theorem, proof of converse, symmetric channels
10. Error-correcting codes and real channels: AWGN channel, multivariate Gaussian pdf, capacity of AWGN channel
11. Binary codes: minimum distance, perfect codes, why perfect codes are bad, why distance isn’t everything
12. Message passing: distributed counting, path counting, low-cost path, min-sum (=Viterbi) algorithm
13. Exact marginalization in graphs: factor graphs, sum-product algorithm
14. Low-density parity-check codes: density evolution, check node degree, regular vs. irregular codes, girth
15. Lossy source coding: transform coding and JPEG compression -- 1. Einleitung: Binomialverteilung, (7,4)-Hamming-Code, Paritätsmatrix, Generatormatrix
2. Wahrscheinlichkeit, Entropie und Inferenz: Entropie, bedingte Wahrscheinlichkeit, Bayes’sches Gesetz, Likelihood, Jensen’sche Ungleichung
3. Inferenz: Inverse Wahrscheinlichkeit, statistische Inferenz
4. Das Quellencodierungstheorem: Informationsgehalt, typische Folgen, Tschebyschev’sche Ungleichung, Gesetz der großen Zahlen
5. Symbolcodes: eindeutige Dekodierbarkeit, mittlere Codewortlänge, präfixfreie Codes, Kraft’sche Ungleichung, Huffmancodierung
6. Stromcodes: arithmetische Codierung, Lempel-Ziv-Codierung, Burrows-Wheeler-Transformation
7. Abhängige Zufallsvariablen: Transinformation, Datenverarbeitungslemma
8. Kommunikation over gestörte Kanäle: diskreter gedächtnisloser Kanal, Kanalcodierungstheorem, Kanalkapazität
9. Das Kanalcodierungstheorem: verbundtypische Folgen, Beweis des Kanalcodierungstheorems, Beweis des Umkehrsatzes, symmetrische Kanaäle
10. Fehlerkorrigierende Codes und reale Kanäle: AWGN-Kanal, mehrdimensionale Gauß’sche WDF, Kapazität des AWGN-Kanals
11. Binäre Codes: Minimaldistanz, perfekte Codes, Warum perfekte Codes schlecht sind, Warum Distanz nicht alles ist
12. Nachrichtenaustausch: verteiltes Zählen, Pfadzählen, günstigster Pfad, Minimumsummenalgorithmus
13. Exakte Marginalisierung in Graphen: Faktorgraph, Summenproduktalgorithmus
14. LDPC-Codes: Dichteevolution, Knotenordnung, reguläre und irreguläre Codes, Graphumfang
15. Verlustbehaftete Quellencodierung: Transformationscodierung und JPEG-Kompression
Lernziele und Kompetenzen:
The students apply Bayesian inference to problems in both communications and everyday's life.
The students explain the concept of digital communications by means of source compression and forward-error correction coding.
For the design of communication systems, they use the concepts of entropy and channel capacity.
They calculate these quantities for memoryless sources and channels.
The students proof both the source coding and the channel coding theorem. The students compare various methods of source coding with respect to compression rate and complexity.
The students apply source compression methods to measure mutual information.
The students factorize multivariate functions, represent them by graphs, and marginalize them with respect to various variables.
The students explain the design of error-correcting codes and the role of minimum distance.
They decode error-correcting codes by means of maximum-likelihood decoding and message passing.
The students apply distributed algorithms to problems in both communications and everyday’s life.
The students improve the properties of low-density parity-check codes by widening the girth and/or irregularity in the degree distribution.
The students transform source images into the frequency domain to improve lossy compression. -- Die Studierenden wenden Bayes’sche Inferenz auf Probleme in der Nachrichtentechnik und im Alltagsleben an.
Die Studierenden erklären die konzeptuelle Trennung von digitaler Übertragung in Quellen- und Kanalcodierung.
Kommunikationssysteme entwerfen sie unter Betrachtung von Entropie und Kanalkapazität.
Sie berechnen diese Größen für gedächtnislose Quellen und Kanäle.
Die Studierenden beweisen sowohl das Quellen- als auch das Kanalcodierungstheorem.
Die Studierenden vergleichen verschiedenartige Quellencodierungsverfahren hinsichtlich Komplexität und Kompressionsrate.
Die Studierenden verwenden Quellencodierverfahren zur Messung von Transinformation.
Die Studierenden faktorisieren Funktionen mehrerer Veränderlicher, stellen diese als Graph dar und marginalisieren sie bezüglich mehrerer Veränderlicher.
Die Studierenden erklären den Entwurf von Kanalcodes und den Einfluss der Minimaldistanz.
Sie decodieren Kanalcodes gemäß maximaler Likelihood und Nachrichtenaustausch.
Die Studierenden wenden verteilte Algorithmen auf Probleme der Nachrichtentechnik und des Alltagslebens an.
Die Studierenden verbessern die Eigenschaften von LDPC-Codes durch Erhöhung des Umfangs und/oder durch irreguäre Knotenordnungsverteilungen.
Die Studierenden transformieren Bildquellen zur Verbesserung verlustbehafteter Kompression iin den Frequenzbereich.
Literatur:
MacKay, D.: Information Theory, Inference, and Learning Algorithms, Cambridge University Press, Cambridge, 2003.
Bemerkung:
Schlüsselwörter: ASC
Organisatorisches:
Die Unterrichts- und Prüfungssprache (Deutsch oder Englisch) wird in der ersten Lehrveranstaltung mit den Studierenden vereinbart.
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
- Berufspädagogik Technik (Bachelor of Science)
(Po-Vers. 2020w | TechFak | Berufspädagogik Technik (Bachelor of Science) | Gesamtkonto | Wahlpflichtmodule Fachwissenschaft | Information Theory and Coding / Informationstheorie und Codierung)
Dieses Modul ist daneben auch in den Studienfächern "123#67#H", "Advanced Signal Processing & Communications Engineering (Master of Science)", "Artificial Intelligence (Master of Science)", "Berufspädagogik Technik (Master of Education)", "Communications and Multimedia Engineering (Master of Science)", "Computational Engineering (Master of Science)", "Computational Engineering (Rechnergestütztes Ingenieurwesen) (Bachelor of Science)", "Computational Engineering (Rechnergestütztes Ingenieurwesen) (Master of Science)", "Elektrotechnik, Elektronik und Informationstechnik (Bachelor of Science)", "Elektrotechnik, Elektronik und Informationstechnik (Master of Science)", "Informatik (Master of Science)", "Information and Communication Technology (Master of Science)", "Informations- und Kommunikationstechnik (Bachelor of Science)", "Informations- und Kommunikationstechnik (Master of Science)", "Mathematik (Bachelor of Science)", "Medizintechnik (Master of Science)", "Wirtschaftsingenieurwesen (Bachelor of Science)", "Wirtschaftsingenieurwesen (Master of Science)" verwendbar. Details
Studien-/Prüfungsleistungen:
Information Theory and Coding / Informationstheorie und Codierung (Prüfungsnummer: 36011)
(englischer Titel: Information Theory and Coding)
zugeh. "mein campus"-Prüfung: | - 36011 Information Theory and Coding / Informationstheorie und Codierung (Gewichtung: 100.0 %, Prüfung, Form: Klausur, Drittelnoten (mit 4,3), Dauer: 90, 5 ECTS, Prüfung).
- 36011 Information Theory and Coding / Informationstheorie und Codierung (Gewichtung: 100.0 %, Prüfung, Form: Klausur, Drittelnoten (mit 4,3), Dauer: 90, 5 ECTS, Prüfung).
- 36011 Information Theory and Coding / Informationstheorie und Codierung (Gewichtung: 100.0 %, Prüfung, Form: Klausur, Drittelnoten (mit 4,3), Dauer: 90, 5 ECTS, Prüfung).
|
- Prüfungsleistung, Klausur, Dauer (in Minuten): 90, benotet, 5.0 ECTS
- Anteil an der Berechnung der Modulnote: 100.0 %
- Prüfungssprache: Englisch
- Erstablegung: WS 2021/2022, 1. Wdh.: SS 2022
1. Prüfer: | Ralf Müller (100355) |
- Termin: 15.02.2022, 14:00 Uhr, Ort: BASPH
Termin: 02.08.2022
Termin: 02.08.2022
|
|
|