Low-Density-Parity-Check-Code

Low-Density-Parity-Check-Codes, auch als LDPC-Codes oder Gallager-Codes bezeichnet, sind lineare Blockcodes zur Fehlerkorrektur. Sie wurden 1962 von Robert G. Gallager im Rahmen seiner Dissertation am MIT entwickelt ^[1].

Low-Density-Parity-Check-Codes beschreiben mit Hilfe einer Matrix viele zusammenhängende Paritätsprüfungen. Es wird dabei das Prinzip einer Kontrollmatrix angewandt: $H\cdot b^T= 0$ , wobei $H$ die Kontrollmatrix (parity-check matrix)und $b$ die Folge der empfangenen Codesymbole darstellt. H ist nur dünn besetzt (daher die Bezeichnung low-density).

Inhaltsverzeichnis

1 Notation
2 Begriffsdefinition
3 Kodierung
4 Dekodierung
5 Einzelnachweise
6 Literatur

[Bearbeiten] Notation

$(n, l, R) L D P C$

$n$ = Kodewortlänge
$l$ = Anzahl an Informationsstellen
$R$ = Koderate

[Bearbeiten] Begriffsdefinition

$a *$ oder $a l$ Quellkodewort (Infowort)
$a k$ redundanter Teil des Kanalkodewortes
$a$ Kanalkodewort
$b$ Empfangsfolge
$H$ Kontrollmatrix

[Bearbeiten] Kodierung

Es gilt eine zu sendende Folge $a$ zu finden, die der Gleichung $H\cdot a^T = 0$ genügt.

Eine mögliche Form der Kodierung funktioniert folgendermaßen: Das Kanalkodewort $a$ ist zusammengesetzt aus den zu sendenden Daten $a l$ (welche bekannt sind) und dem redundanten Teil $a k$ . Da $a$ oben genannte Formel erfüllen muss, muss $a k$ entsprechend berechnet werden:

Sei $a = [a k, a l]$ und $H = [H k, H l]$
Es soll gelten: $[H k, H l] * [a k, a l] T = 0$
Dies kann umgeformt werden: $[H k][a k] = [H l][a l]$
Daraus ergibt sich $a_k^T=H_k^{-1}\cdot H_l\cdot a_l$

In Worten ausgedrückt, muss dabei der 1. quadratische Teil der Kontrollmatrix mit dem verbliebenen Teil der Kontrollmatrix und den zu sendenden Daten multipliziert werden.

[Bearbeiten] Dekodierung

Hierbei gilt es ebenso das Problem $H\cdot b^T = 0$ zu lösen. Hierzu werden häufig iterative Graph-basierte Algorithmen gewählt. Nach der Übertragung des Kanalkodewortes $a$ über einen Übertragungskanal, z. B. einen AWGN-Kanal (additives weißes (Gauß'sches) Rauschen), wird in der Regel das Wort $b M$ bestehend aus reellen Werten empfangen.

[Bearbeiten] Einzelnachweise

? Robert G. Gallager: Low-Density Parity-Check Codes. in IRE Transactions on Information Theory, Seiten 21 bis 28, 1962

[Bearbeiten] Literatur

Robert G. Gallager: Low-Density Parity-Check Codes. MIT Press Classic Series, Cambridge, MA, 1963, ISBN 0262571773 (andere Fassung)
David J. C. MacKay: Information theory, inference and learning algorithms, Cambridge University Press, Cambridge 2003, ISBN 0521642981 (auch online verfügbar)
Todd K. Moon: Error Correction Coding, Mathematical Methods and Algorithms. Wiley-Interscience, Hoboken, NJ, 2005, ISBN 0471648000
Amin Shokrollahi: LDPC Codes: An Introduction, 2002, ([1])

Home | Impressum