19. Oktober

Organisatorisches,
Ausblick auf die Inhalte der Vorlesung,
Ein kleiner Vorgeschmack auf die Vorlesung.

Literatur, Notizen zu mathematischem Handwerkszeug

23. Oktober

Erläuterungen zum Entropiebegriff - siehe auch die Notizen
Optimale Pferdewetten (Kelly gambling)

Entropiebegriff

Erstes Übungsblatt

26. Oktober

Stochastische Quellen und Kanäle, Verteilungen, Entscheidungsfunktionen, der binäre symmetrische Kanal und seine Erweiterungen, Parallel- und Hintereinanderschaltung von Kanälen, data processing inequality, Fano-Ungleichung

Kanäle und ihre Kapazität

30. Oktober

Beweis der Fano-Ungleichung, Kapazität von Kanälen, Beispiele für die Berechnung von Kapazitäten, Anwendung der Fano-Ungleichung: Decodierungsfehler bei Coderaten oberhalb der Kanalkapazität, typische und untypische Wörter bei gedächtnisfreien Quellen, Heuristik für fehlerfreie Decodierung

Zweites Übungsblatt

2. November

Shannons Schema der Nachrichtenübertragung über gestörte Kanäle, Codes, lineare Codes, Minimaldistanz, Rate, Fehlerwahrscheinlichkeit (Blockfehler, Bitfehler) etc.
q-ärer symmetrischer Kanal, Repetitionscodes, der [7,4]-Hamming-Code

6. November

Geometrische und algebraische Aspekte des [7,4]-Hamming-Codes, Fano-Ebene, Gruppeneigenschaft, Perfektheit, Minimaldistanz, Kontroll- und Generatormatrizen, NC-Decodierung mittels Syndromberechnung

Drittes Übungsblatt

9. November

Block- und Bitfehlerwkeit für den (7,4)-Hamming-Code im BSC,
binäre Hamming-Codes allgemein, Perfektheit, Dualität, Simplexcodes, Erweiterungen,
Allgemeine Definitionen, Begriffe, Eigenschaften von linearen Codes (Minimaldistanz, Kontroll- und Generatormatrizen, NC-Decodierung mittels Syndromberechnung)

Beispiel zur Decodierung des (7,4)-Hammingcodes

Definitionen etc.

Viertes Übungsblatt

13. November

Heute findet keine Vorlesung statt. Es wird empfohlen, die Blätter zu den REED-MULLER-Codes zu studieren.

Reed-Muller-Codes

Illustration zu den Reed-Muller-Codes

16. November

Shannnons Kanalcodierungstheorem

Folien zur heutigen Vorlesung

20. November

Kanalunabhängige Fehlererkennung und -korrektur
Erweiterung auf Kanäle mit Löschung
Ergänzungen zu den Aufgaben 9 und 10:
Gewichtspolynome und MacWilliams-Identität

Fünftes Übungsblatt

23. November

Schranken für die Existenz von Codes: Singleton, Hammming, Gilbert-Vashamov, Plotkin,
Volumen der q-ären Hamming-Kugeln und Anschätzung mittels der q-ären Entropiefunktion,
asymptotische Schranken

Hamminggeometrie

27. November

Asymptotische Schranken für linear Codes,
Fehlerverhalten in q-ären symmetrischen Kanal,
Abschätzung mittels der Divergenzfunktion,
Komplexität (NP-Vollständigkeit) der Decodierung linearer Codes (Berlekamp, McEliece, van Tilborg),
Das Kryptosystem von McEliece

Sechstes Übungsblatt

30. November

Das Hütespiel und der Hamming-Code
Das Kanalcodierungstheorem von Shannon im Fall des q-ären symmetrschen Kanals und seine Umkehrung
Unterräume von endlichen Vektorräumen

Shannons Theorem

4. Dezember

Unterräume von endlichen Vektorräumen, Matrizen in Stufennormalform, q-Binomialkoeffizienten
Konstruktion uind Eigenschaften von (endlichen) Körpern
Konstruktion eines binären [15,7,5]-Codes
Fehlerkorrektur für den [15,7,5]-Code Code

Eigenschaften von Körpern

7. Dezember

Anmerkungen zur Aufgabe 16 (Gewichtspolynome von selbstdualen Codes)
Vandermonde-Determinante
GRS-Codes

Folien zur heutigen Vorlesung

Siebtes Übungsblatt

11. Dezember

primitive Elemente (Polynome) in endlichen Körpern,
GRS-Codes, duale GRS-Codes, RS-Codes, Alternante Codes, BCH-Codes, Codierung mittels Multiplikation bzw. mittels Division

Achtes Übungsblatt

14. Dezember

Fehlerkorrektur für CD-Audio

18. Dezember

Decodierungsverfahren für GRS-Codes (I):
error-locator und error-evaluator Polynome
Lösen eines linearen Gleichungssystems (Peterson-Gorenstein-Zierler)
Euklidischer Algorithmus (Sugiyama et al.)

Maple-worksheet

Folien zur heutigen Vorlesung

21. Dezember

Decodierungsverfahren für GRS-Codes (II):
Euklidischer Algorithmus (Sugiyama et al.) (Forts.)
lineare Rekursionen, Berlekamp-Massey-Algorithmus

Neuntes Übungsblatt

11. Januar

Decodierungsverfahren für GRS-Codes (III):
lineare Rekursionen, Berlekamp-Massey-Algorithmus

18. Januar

Decodierungsverfahren für GRS-Codes (IV):
Beispiel zum Berlekamp-Massey-Algorithmus
Decodierung mittels Interpolation

Neuntes Übungsblatt

22. Januar

Decodierungsverfahren für GRS-Codes (V):
Decodierung mittels Interpolation:
Algorithmen von Sudan und Guruswami-Sudan

Folien zur Interpolationsdecodeierung

25. Januar

Expandergraphen, Expandercodes
Konstruktion von Sipser-Spielman

Folien zu "Graphen und Codes"

29. Januar 2010

Graphen und ihre Eigenwerte,
Margulis-Graphen als Beispiele
Eigenwerte und Expansionseigenschaften
Expander Mixing Lemma

1. Februar 2010

Beispiel zur Decodierung mittels "belief propagation"
Durchmesser von Graphen, Eigenwerte und Expansion
linksreguläre bipartite Graphen und Expander
"fast jeder" linksreguläre bipartite Graph ist ein Expander
Anwendung: Konstruktion von Superkonzentratoren

5. Februar 2010

Rayleigh-Quotienten und Eigenwerte
Spektrallücke und Expansionseigenschaften
Heiratssatz
Konstruktion von Superkonzentratoren
"error amplification" für die Komplexitätklasse Random Polynomial Time (z.B. Miller-Rabin-Test)

8. Februar 2010

Zemor-Codes

12. Februar 2010

Konstruktion von Expandern:
Verfahren von Margulis, Reingold et al., Lubotsky et al.

Folien zu "Graphen und Codes"