Low-Density-Parity-Check-Code (LDPC-Codes) ist Verfahren zur linearen Fehlerkorrektur.

Beschreibung

---

LDPC-Codes sind lineare Blockcodes zur Fehlerkorrektur. Sie beschreiben mit Hilfe einer Matrix viele zusammenhängende Paritätschecks. Es wird dabei das Prinzip einer Kontrollmatrix angewandt:

$H\backslash cdot\; b^T=\; 0$,

wobei $H$ die Kontrollmatrix und $b$ die Empfangsfolge darstellt. H ist nur leicht besetzt.

Notation

---

$(n,l,R)LDPC$

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

Begriffsdefinition

---

• $a^*$ oder $a\_l$ Quellkodewort
• $a\_k$ redundanter Teil des Kanalkodewortes
• $a$ Kanalkodewort
• $b$ Empfangsfolge
• $H$ Kontrollmatrix

Kodierung

---

Es gilt eine zu sendende Folge $a$ zu finden, die der Gleichung $H\backslash 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=*$
• ebenso sei $H=*$

Es soll gelten:

• $***^T=0$

Dies kann umgeformt werden:

Daraus ergibt sich

• $a\_k^T=H\_k^\{-1\}\backslash cdot\; H\_l\backslash 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.

Dekodierung

---

Hierbei gilt es ebenso das Problem $H\backslash cdot\; b^T\; =\; 0$ zu lösen.

Nach der Übertragung des Kanalkodewortes $a$ über einen AWGN-Kanal (additives weißes (Gauß'sches) Rauschen) wird das Wort $b\_M$ (reelle Werte) empfangen.

Literatur

---

• Robert G. Gallager: Low-Density Parity-Check Codes. MIT Press Classic Series, Cambridge, MA, 1963, ISBN 0262571773
• 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

Nachrichtentechnik | Rechnerarchitektur | Digitaltechnik

Low-density parity-check code | Low-density Parity-check code