Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2014 / Codierungstheorie


Inhaltsbereich

Codierungstheorie

Vorlesung, 3-std., Mi 10-12, Do 10-11 Hofmann, Cichon; Übungen 1-std., Do 11-12, Hofmann, Cichon

Aktuelles

  • Es wurde eine Uniworx Seite eingerichtet. Bitte dort anmelden und Hausaufgaben abgeben.

Inhalt

Die Codierungstheorie befasst sich mit der Übertragung von Information über fehlerbehaftete Kanäle. Anders als bei der Kryptographie geht es nicht darum, die Informationen vor unerwünschten Zuhörern zu schuetzen, sondern darum, Fehler bei der Übertragung zu erkennen oder zu korrigieren.

Eine einfache Aufgabe der Codierungstheorie ist die folgende: man codiere eine Bitfolge (zum Beispiel 4 Bit) so, dass ein Bitfehler korrigiert werden kann.

Sendet man die vier Bit einfach doppelt, so hat man acht Bit verbraucht und kann einen Fehler erkennen, nicht aber korrigieren. Kommt etwa 00100011 an, so weiß man, dass ein Fehler aufgetreten ist; die urspruenglich gesendete Information koennte aber 0010 (Fehler im achten Bit) oder 0011 (Fehler im vierten Bit) gewesen sein. Sendet man die vier Bit dreimal hintereinander, so kann man per Mehrheitsentscheidung einen Bitfehler korrigieren, hat aber zwölf Bit aufgewendet.

Wir lernen in der Vorlesung gleich zu Beginn ein Verfahren, den Hamming-Code, kennen, welches die vier Bit auf nur sieben Bit aufblaeht und doch die Korrektur eines Fehlers erlaubt.

Bei einer Mars-Expedition in den 70er Jahren wurde ein Codierungsverfahren verwendet, der (5,1)-Reed-Muller Code, welcher 5 Informationsbits mit 32 Bit codiert und dadurch 7 Bitfehler korrigieren kann.

Bei Audio-CDs und im Mobilfunk wiederum kommt der modernere Reed-Solomon Code zum Einsatz, welcher effizienter ist und  Burstfehler (mehrere aufeinanderfolgende Bitfehler, "Kratzer") besonders gut korrigiert.


Die Vorlesung behandelt solche Verfahren und die dazugehoerigen Grundlagen. Außerdem gibt es Ausblicke auf praktische Aspekte wie Bild- und Videokodierung, etwas Informationstheorie und moderne Entwicklungen, wie Faltungs-, Turbo- und LDPC-Codes, die zum Beispiel bei DVB-Fernsehen vorkommen.


Organisation

 

Planung

 

Es wird im allgemeinen an jedem dritten Termin eine Übung geben, dementsprechend verteilen sich Vorlesung und Übung wie 2:1. Die vorläufige Planung ist wie folgt.

Vorläufige Vorlesungsplanung

Nr. Datum Thema Dozent Hinweise
1. 9.4. Motivation, Einf. Beispiele, (7,16,3)-Hamming Code. MH
2. 10.4.

Information,  Shannon-Fano, Kraft'sche Ungleichung, Hauptsatz der Quellencodierung

MH
16.4 Übung MH
17.4. Termin entfällt wg Gründonnerstag
3. 23.4. Hamming-Distanz, Kanalkapazität, Kanalcodierungssatz MH

4. 24.4. Lineare Codes, Algebr. Grundlagen MH
30.4. Übung GC
5. 7.5.

Praktische Aspekte der Quellencodierung: Bild- und Videocodierung

GC

6. 8.5.

Kanalcodierung: Modulationsverfahren, Kanaleigenschaften,

Interleaver, Fading, Soft-/ Hard Bits

GC
14.5. Übung GC
7. 15.5. Wdh: Lin. Alg.: OFDM, FFT, Basistransformationen in Vektorräumen MH
8. 21.5. Satz von Varsamov, Syndrom Decodierung, Simplex-Code, Plotkin-Schranke MH
22.5. Übung MH
9. 28.5. Reed-Muller Code, Mehrheitsdecodierung GC
10. 4.6. Reed-Solomon Codes GC
5.6. Übung GC

11. 11.6. Cyclic Redundancy Checks; zusammengesetzte Codes (Konkatenation, Block, CIRC) MH
12. 12.6. Zyklische Codes, BCH Schranke MH
18.6. Übung MH
13. 25.6. Faltungscodes, Generatormatrizen, Potenzreihen GC
14. 26.6. Freie Distanz, Decodierung von Faltungscodes, Viterbi Algorithmus, Fano Algorithmus, Punktierung, Tailbiting. GC
2.7. Übung MH
15. 3.7. Turbo Codes GC
16. 9.7. LDPC Codes GC
10.7. Wiederholung / Slack GC
. 29.7. Klausur
26.9. Nachholklausur


Zeit und Ort

Veranstaltung  Zeit  Ort Beginn
Vorlesung Mi, 10-12 c.t. Amalienstr. 73A, Seminarraum 018 09.04.2014
Vorlesung + Übung Do, 10–12 c.t. Geschw.-Scholl-Pl. 1 (D), D Z001 10.04.2014

Materialien

Skripte und gesammelten Materialien finden sich hier.


Übungen

Für die Teilnahme an der Klausur müssen mindestens 50% der Hausaufgaben "bestanden" werden. Bearbeitete Hausaufgaben können über Uniworx eingereicht werden und werden dann von uns korrigiert. Eine Aufgabe gilt als "bestanden", wenn sie mit "ausreichend" bewertet würde, also in etwa zur Haelfte richtig gelöst ist.

 


Literatur

  • Richard W. Hamming: Coding and Information Theory, Prentice-Hall, 1980.
  • Wolfgang Willems: Codierungstheorie, Gruyter, Berlin 1999.
  • W. Heise, P. Quattrocchi: "Informations- und Codierungstheorie", Springer 1995.
  • Pless, Huffman (Hrsg.): Handbook of Coding Theory, (2 Volumes), Elsevier, Amsterdam 1998

Klausur

 

Für die Teilnahme an der Klausur ist die Bearbeitung von Hausaufgaben verpflichtend stark empfohlen, s.o.

Bitte beachten Sie die Hinweise zur Neuregelung für die Dokumentation der Prüfungen.

Zur Teilnahme an den Klausuren ist eine Anmeldung vorab bei Uniworx verpflichtend.

Erstklausur: Dienstag, 29. Juli 2014, 10-12h, Oe. Hörsaal 151

Nachklausur: Freitag, 26. September 2014, 14-16h, Oettingenstraße Hörsaal BU101

Artikelaktionen


Funktionsleiste