Hinweise zur Vorlesung "Verfahren zur
Kanalcodierung"
am Institut für Nachrichtentechnik, KIT (Karlsruher
Institut für Technologie)
Jeweils im Sommersemester
(2 SWS, zweiwöchentlich)
| Titel: | Verfahren zur Kanalcodierung |
| Lv-Nr.: | 23546 |
| Raum: | kl. ETI |
| Tag: | Freitag |
| Zeit: | 14.00 - 17.15 |
| Turnus: | 14-tägig unregelmäßig |
| 7 Vorlesungs-Termine in 2020 |
24.4. |
| 2 Prüfungs-Termine: |
24.7.2020 |
| Prüfungsmodus: | mündlich |
Inhalt der Vorlesung:
Einführung.
Diskrete Kanäle.
Grundprinzip der Blockcodierung.
Maximum-Likelihood-Decodierung.
Asymptotischer Codierungsgewinn.
Kanalcodierungstheoreme.
Lineare Codes.
Fehlerwahrscheinlichkeiten.
Syndrom-Decodierung.
Zyklische Codes.
Systematischer Encoder.
Korrektur und Erkennung von Einzel- und Bündelfehlern.
Galoisfelder.
RS- und BCH-Codes.
Decodierung mit dem Berlekamp-Massey und dem Euklidischen Algorithmus.
Faltungscodes mit Zustands- und Trellisbeschreibung.
Viterbi-Algorithmus.
Trelliscodierte Modulation.
Anwendungen (Mobilfunk, Satellitenkommunikation, Modems, CD Player).
Die Vorlesung basiert teilweise auf dem Buch:
Bernd Friedrichs: Kanalcodierung - Grundlagen und Anwendungen in modernen Kommunikationssystemen. Springer-Verlag 1995. (Näheres dazu auf der Seite Bücher)
Die für die Vorlesung relevanten Teile des Buches sind
hier verfügbar
(6200 KB, Bilder in englisch)
Organisation Sommersemester 2020
Im Sommersemester 2020 findet die Vorlesung aufgrund der Corona-Pandemie nicht als Präsenzveranstaltung sondern nur Online statt.
Das in der Vorlesung verwendete Material (Folien, Tafelanschriebe, etc.)
ist in den nachfolgenden pdf-Dokumenten annähernd enthalten.
Die sieben Dokumente entsprechen genau den sieben Doppel-Doppelstunden zu
jeweils 2*90 Minuten.
Teil 1: Einführung, Diskrete Kanäle (DMC, BSC, AWGN), Hard- und Soft-Decision,
statistische Beschreibung (Q-Funktion),
Rechnen mit bedingten Wahrscheinlichkeiten am Beispiel medizinischer Testverfahren (Corona),
Grundprinzip der Blockcodierung, Hammingdistanz,
Maximum-Likelihood-Decodierung allgemein und speziell für DMC und AWGN
(36 Seiten, aktualisiert am 17.6.2020)
Teil 2: Codierungsgewinn, Shannon'sches Kanalcodierungstheorem, R0-Theorem,
Abstand zu den theoretischen Grenzen, Spektrale Bitrate,
Lineare Blockcodes, Fehlererkennung und Fehlerkorrektur, Kugelmodelle,
Decoder-Strategien (MLD, BMDD)
(43 Seiten)
Teil 3: Schranken für die Minimaldistanz (Singleton, Hamming, Gilbert-Varshamov),
Asymptotische Schranken für die Minimaldistanz,
Wahrscheinlichkeit unerkannter Fehler bei Fehlererkennungscodes,
Fehlerwahrscheinlichkeit bei Hard-Decision/Soft-Decision,
Generatormatrix, Prüfmatrix, Hamming-Codes, Einfache Modifikationen linearer Codes
(38 Seiten)
Teil 4: Nebenklassen-Zerlegung, Syndrom-Decodierung,
Definition zyklischer Codes und Polynombeschreibung, Generatorpolynom, Prüfpolynom,
Systematische Encodierung, Syndrom,
Erkennung von Einzelfehlern und Bündelfehlern sowie CRC-Codes,
Korrektur von Einzelfehlern und Bündelfehlern
(47 Seiten)
Teil 5: Motivation Galoisfelder, Kurzeinführung Galoisfelder mit Bespielen GF(8) und GF(16),
Spektraltransformation auf Galoisfeldern,
RS-Codes (Definition und BER-Kurven), BCH-Codes (Definition und BER-Kurven),
Compact Disc Digital Audio (Interleaving, Verkettung, Verkürzung, Ausfallkorrektur),
Definition und Schieberegister-Beschreibung von Faltungscodes, Polynombeschreibung,
Spezielle Codeklassen: Terminierte und punktierte Faltungscodes, RCPC-Codes, UEP-Anwendung
(67 Seiten)
Teil 6: Nicht-katastrophale Encoder und Encoder-Inverses, Distanzeigenschaften,
optimale Faltungscodes, Trellisdiagramm, Zustandsdiagramm,
Viterbi-Metrik, Viterbi-Algorithmus für terminierte und nicht-terminierte Codes,
Implementierung und Synchronisation, Fehlerwahrscheinlichkeit von Faltungscodes, Fehlerstrukturen,
Verkettete Codes, Vergleich Blockcodes-Faltungscodes
(56 Seiten)
Teil 7a: Übersicht zur Satellitenkommunikation, RS*CC-Verkettung (CCSDS-Standard,
Implementierung, Fehlerrate, Fehlerstruktur, Beispiel mit Detailcheck),
Simulator für Satellitenkommunikation und Imperfektionen (Nichtlineare Verstärker, Verstauchungen
von APSK, Intermodulations-Verzerrungen, nicht-Gaußisches und nicht-weißes Rauschen, digitaler Demodulator,
BMD-Prinzip), Zusammenhang der Fehlerraten von Modulationssymbolen und Codesymbolen,
Galileo Orbiter und Software Radio,
Link Budget Berechnung - ist eine Kommunikation mit außerirdischen Radiozivilisationen (Aliens) möglich?
(44 Seiten)
Teil 7b: EDRS System (European Data Relay Satellite) und hybride Nutzlast (optische / RF Links):
Architektur des Netzes, Digitale Verarbeitungseinheiten, Kanalcodierung. Simulation, Außenansicht Satellit,
34 kbit/s Modems für den Telefonkanal: eine Anwendung von gestern aber ein Höhepunkt der Kanalcodierung,
GSM-Mobilfunk: Kanalmodell mit zeit- und frequenzselektivem Fading und angepasste Kanalcodierung;
Kombinierte Kanal- und Quellencodierung; von VoIP überrollte Erweiterungen der Viterbi-Metrik
(64 Seiten)
Für den Gesamtzusammenhang und weitere Erläuterungen über das
unmittelbare Vorlesungsmaterial hinaus verweise ich auf die Möglichkeit
die relevanten Teile meines zugrunde liegenden Buches direkt herunterzuladen
(siehe den Link oben auf dieser Seite). Das Buch basiert natürlich
auf Vektorgrafik, während ich die sieben Vorlesungs-Dokumente auf die Schnelle
nur über Pixelgrafiken erstellen kann, für die resultierende
Unschärfe bitte ich um Nachsicht.
Über meine email-Adresse sind aber in jedem Fall und zu jeder Zeit
jegliche Fragen, Rückmeldungen, Kritik und Anregungen willkommen.
Ich werde mich um schnelle Antwort bemühen. Das Material ist frei zugänglich,
ich empfehle jedoch allen Hörern (bzw. Lesern) der Vorlesung mir
in jedem Fall eine Notiz zukommen zu lassen damit eine Interaktion auch unter
diesen besonderen Umständen möglich wird.
Von einem Hörer habe ich folgende Frage bekommen (11.7.2020):
Ich habe eine Frage zum Kanalkodierungstheorem:
Laut Theorem muss C>R*ld(q) damit die Wortfehlerwahrscheinlichkeit beliebig klein gemacht werden kann.
Jedoch hat der RS(255,128,128) Code mit q=256 ein R*ld(q) von 4. Somit könnte man mit diesen Code bei einem Kanal mit Pe von 0.01, die Wortfehlerwahrscheinlichkeit
nicht beliebig klein machen da C = 0.919. Existiert dann bei diesem Kanal mit der gennanten RS-Kodierung dann tatsächlich eine minimale Wortfehlerwahrscheinlichkeit?
Antwort: Da in dieser Frage mehrere Missverständnisse liegen nehme ich dankbar die Gelegenheit zur Klarstellung auf:
In der Vorlesung und im Buch wird weitgehend stillschweigend vorausgesetzt dass die Stufenzahl der Codesymbole und die Stufenzahl der Modulationssymbole übereinstimmen
und diese Zahl wurde mit q bezeichnet. In der Realität gibt es diese Übereinstimmung manchmal aber nicht immer. Die Stufenzahl der Code- und Infosymbole ist q=p^m
(=2^m mit p=2 normalerweise), während die Stufenzahl der Modulationssymbole 2^M beträgt. Es kann sowohl m<M wie m=M wie m>M sein. Dadurch wird es komplizierter,
siehe dazu die Online-Folien Teil 7a, Folie 29ff, auch das Thema Gray-Codierung wird relevant. Für das Verständnis der Codierungsalgorithmen ist das unwichtig, für das
Verständnis der Wirkung von Codes ist es dagegen wichtig.
Die Kanalkapazität C ist eine Eigenschaft des Kanals und nicht des Codes mit der Einheit Infobits pro Kanalbenutzung. Hier ist 2^M relevant, die binäre Coderate R_b = M*R
bezieht sich auch auf die Anzahl der Infobits pro Kanalbenutzung. Die Stufenzahl der Codesymbole ist für das Kanalcodierungstheorem erstmal irrelevant.
Also R_b=M*128/255 für die Fragestellung.
Die in der Frage zitierte Kanalkapazität bezieht sich auf binäre Modulation mit M=1. Andere Modulationsverfahren werden in der Vorlesung nicht thematisiert, im Buch jedoch
schon, siehe dazu Bild 2.5 (C für ASK) und die Bilder 2.6 und 2.8 (R0 für ASK und PSK).
Für einen Code und einen Kanal (gekennzeichnet durch p_b bei Hard/BSC oder Ec/N0 bei Soft/AWGN) ergibt sich eine feste Fehlerwahrscheinlichkeit die immer größer als
Null ist. Die Aussage des Kanalcodierungstheorems (die Fehlerrate kann beliebig klein gemacht werden durch Wahl des Codes) bedeutet dass immer kleinere Fehlerraten immer
komplexere Codes mit immer größerer Blocklänge erfordern. Eine gegen Null konvergierende Fehlerrate kann nicht mit einem einzelnen Code erreicht werden sondern mit einer
Codefamilie. So ist das im Buch auf Seite 39 auch erklärt (fehlt leider in den Folien). Die Familie der RS-Codes ist für diese Konvergenz der Fehlerrate gegen Null vermutlich
überhaupt nicht geeignet - RS Codes lassen sich dagegen gut implementieren, sind eher für Bündelfehler geeignet und die eigentlich besser geeigneten BCH-Codes sind
asymptotisch schlecht (siehe Teil 5, Folie 40). Der theoretische Aspekt einer gegen Null konvergierenden Fehlerrate einerseits und der praktische Nutzen durch Kanalcodierung
andererseits können weit auseinander driften.
Für alle kurz vor der Prüfung stehenden Studenten: nicht verwirren lassen! Beim Kanalcodierungstheorem ist wichtig dass der Kanal den Durchsatz begrenzt aber nicht die Qualität.
Viel mehr muss man für die Prüfung an dieser Stelle nicht wissen.
Zurück zur Hauptseite