Low-Density-Parity-Check-Code

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

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 (repräsentiert als Zeilenvektor) darstellt. H ist nur dünn besetzt (daher die Bezeichnung low-density).

Notation[Bearbeiten]

(n,l,R)\;\text{LDPC}

  • n = Codewortlänge
  • l = Anzahl an Informationsstellen
  • R = Coderate

Begriffsdefinition[Bearbeiten]

  • a^* oder a_l Quellcodewort (Infowort)
  • a_k redundanter Teil des Kanalcodewortes
  • a Kanalcodewort
  • b Empfangsfolge
  • H Kontrollmatrix

Reguläre und nicht reguläre Codes[Bearbeiten]

Ein LDPC-Code, dessen Kontrollmatrix in jeder Zeile und in jeder Spalte die gleiche Anzahl an Einsen (Zeilen- und Spaltengewicht) enthält, wird regulär genannt. Das Zeilengewicht braucht hierbei nicht der Größe des Spaltengewichtes zu entsprechen.

Ein LDPC-Code, der dieser Anforderung nicht genügt (also ein Code, in dem Spalten- oder Zeilengewichte variieren) wird hingegen als „irregulär“ bezeichnet.

Codierung[Bearbeiten]

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

Eine mögliche Form der Codierung funktioniert folgendermaßen: Das Kanalcodewort 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 invertierte quadratische – der erste – Teil Hk der Kontrollmatrix mit dem verbleibenden Rest Hl der Kontrollmatrix und den zu sendenden Daten al multipliziert werden.

Decodierung[Bearbeiten]

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 Kanalcodewortes 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. Aus diesen wird, im Regelfall mit Hilfe eines iterativen Verfahrens, eine Näherungslösung berechnet. Durch die Gleichungsmatrix H werden N Gleichungen vorgegeben; jede dieser Gleichungen erlaubt es, unabhängige Informationen zu den enthaltenen Elementen zu berechnen. Nun werden diese Informationen in den anderen Gleichungsberechnungen wiederverwendet. Zu beachten ist dabei, dass die Informationen, die mit einer Gleichung berechnet wurden, in der nächsten Iteration vor der erneuten Berechnung entfernt werden müssen.

Konstruktion von LDPC-Codes[Bearbeiten]

LDPC-Codes werden durch Ihre Kontrollmatrix H beschrieben. Einen LDPC-Code zu entwickeln heißt also, eine geeignete Kontrollmatrix zu finden oder zu konstruieren. Die zum Erstellen von Kodewörtern benötigte Generatormatrix G kann mit Hilfe des Gauß-Jordan Verfahrens aus H hergeleitet werden. Zur Generierung von Kontrollmatrizen eignen sich u.a. die folgenden Verfahren, welche teilweise darauf basieren, die Kontrollmatrix als Tanner-Graph[3] zu versinnbildlichen und diesen unter Zuhilfenahme verschiedener Algorithmen zu bearbeiten:

Um die Anzahl der in der Matrix vorkommenden Einsen zu verhältnismäßig gering zu halten, können auch noch sogenannte „Row Splitting“- und „Column Splitting“-Algorithmen eingesetzt werden.[7]

Praktischer Einsatz von LDPC Codes[Bearbeiten]

LDPC-Codes werden in unterschiedlichen Gebieten der Technik angewendet. In der Regel werden sie verkettet eingesetzt. So dienen LDPC-Codes beispielsweise zur fehlerkorrigierenden Datenübertragung von digitalen Fernsehsignalen nach DVB-S2 und bei Digital Terrestrial Multimedia Broadcast (DTMB). Neben neueren WLAN-Standards wie dem IEEE 802.11n[8] („n-WLAN“ oder „n-Draft WLAN“) implementiert auch der WLAN-ähnliche Standard 802.16e[9] (Wimax) LDPC-Codes. Weitere Standards sind GMR-1, IEEE 802.3an, IEEE 802.22, CMMB, sowie WiMedia 1.5.[10]

Einzelnachweise[Bearbeiten]

  1. Robert G. Gallager: Low-Density Parity-Check Codes. (PDF; 1,1 MB) in IRE Transactions on Information Theory, Seiten 21 bis 28, 1962
  2. Robert G. Gallager: Low-Density Parity-Check Codes. - 1963
  3. Jian Sun: An Introduction to Low Density Parity Check (LDPC) Codes (Version vom 13. Januar 2012 im Internet Archive)
  4. Alex Balatsoukas-Stimming: The Progressive Edge Growth Algorithm (PDF; 261 kB)
  5. David MacKay: C - Implementierung des PEG Algorithmus für LDPC Codes
  6. Design and Implementation of LDPC Codes (PDF; 255 kB)
  7. a b Design of LDPC Codes (PDF; 563 kB)
  8. IEEE: IEEE Standard 802.11n
  9. IEEE: IEEE Standard 802.16e
  10. Liste standardisierter LDPC-Codes mit Eigenschaften und Erklärungen

Literatur[Bearbeiten]

  • Robert G. Gallager: Low-Density Parity-Check Codes. M.I.T. Press Classic Series, Cambridge MA, 1963 (M.I.T. Press research monographs 21, ZDB-ID 597839-7), (andere Fassung; PDF; 655 kB).
  • David J. C. MacKay: Information theory, inference and learning algorithms. Cambridge University Press, Cambridge u. a. 2003, ISBN 0-521-64298-1 (auch online verfügbar).
  • Todd K. Moon: Error Correction Coding. Mathematical Methods and Algorithms. Wiley-Interscience, Hoboken NJ, 2005, ISBN 0-471-64800-0.
  • Amin Shokrollahi: LDPC Codes: An Introduction. In: Keqin Feng u. a. (Hrsg.): Coding, cryptography and combinatorics. Birkhäuser, Basel u. a. 2004, ISBN 3-7643-2429-5, S. 85–112 (Progress in computer science and applied logic 23), (PDF).