Low-Density-Parity-Check-Code

Low-Density-Parity-Check-Code

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

Inhaltsverzeichnis

Notation

(n,l,R)LDPC

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

Begriffsdefinition

  • a * oder al Quellcodewort (Infowort)
  • ak redundanter Teil des Kanalcodewortes
  • a Kanalcodewort
  • b Empfangsfolge
  • H Kontrollmatrix

Reguläre und nicht reguläre Codes

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 muss hierbei nicht der Größe des Spaltengewichtes entsprechen.

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

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 Codierung funktioniert folgendermaßen: Das Kanalcodewort a ist zusammengesetzt aus den zu sendenden Daten al (welche bekannt sind) und dem redundanten Teil ak. Da a oben genannte Formel erfüllen muss, muss ak entsprechend berechnet werden:

  • Sei a = [ak,al] und H = [Hk,Hl]
  • Es soll gelten: [Hk,Hl] * [ak,al]T = 0
  • Dies kann umgeformt werden: [Hk][ak] = [Hl][al]
  • 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.

Decodierung

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 bM, 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

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:

  • Progressive Edge Growth (PEG) [4] [5]
  • Konstruktion nach David J. C. MayKay und Radford M. Neal [6]
  • Zufällige Konstruktion der Kontrollmatrix [7]

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

Praktischer Einsatz von LDPC Codes

LDPC Codes haben in verschiedenen Technologien praktische Anwendung gefunden. In der Regel werden sie verkettet eingesetzt. So dienen LDPC Codes beispielsweise zur fehlerkorrigierenden Datenübertragung von DVB-S2 Signalen. 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.

Einzelnachweise

  1. Robert G. Gallager: Low-Density Parity-Check Codes. 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
  4. Alex Balatsoukas-Stimming: The Progressive Edge Growth Algorithm
  5. David MacKay: C - Implementierung des PEG Algorithmus für LDPC Codes
  6. Design and Implementation of LDPC Codes
  7. a b Design of LDPC Codes
  8. IEEE: IEEE Standard 802.11n
  9. IEEE: IEEE Standard 802.16e

Literatur

  • 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).
  • 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), ([1]).

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Low-density parity-check code — In information theory, a low density parity check code (LDPC code) is an error correcting code, a method of transmitting a message over a noisy transmission channel. [David J.C. MacKay (2003) Information theory, inference and learning algorithms …   Wikipedia

  • Parity-Check-Code — Codetafel dualergänztes gerades Paritätsbit (E = even = gerade) Codetafel dualergänztes ungerades Paritätsbit (O = odd = ungerade) Die Paritätskontrol …   Deutsch Wikipedia

  • Multidimensional parity-check code — A multidimensional parity check code (MDPC) is a simple type of error correcting code that operates by arranging the message into a multidimensional grid, and calculating a parity digit for each row and column. In general, an n dimensional parity …   Wikipedia

  • Parity — Codetafel dualergänztes gerades Paritätsbit (E = even = gerade) Codetafel dualergänztes ungerades Paritätsbit (O = odd = ungerade) Die Paritätskontrol …   Deutsch Wikipedia

  • Parity-Bit — Codetafel dualergänztes gerades Paritätsbit (E = even = gerade) Codetafel dualergänztes ungerades Paritätsbit (O = odd = ungerade) Die Paritätskontrol …   Deutsch Wikipedia

  • Code — redirects here. CODE may also refer to Cultural Olympiad Digital Edition. Decoded redirects here. For the television show, see Brad Meltzer s Decoded. For code (computer programming), see source code. For other uses, see Code (disambiguation).… …   Wikipedia

  • Error-correcting code — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Fehlerkorrekturverfahren (englisch: Error Correction Code, kurz… …   Deutsch Wikipedia

  • Error Detecting Code — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Fehlerkorrekturverfahren (englisch: Error Correction Code, kurz… …   Deutsch Wikipedia

  • Hamming code — In telecommunication, a Hamming code is a linear error correcting code named after its inventor, Richard Hamming. Hamming codes can detect and correct single bit errors. In other words, the Hamming distance between the transmitted and received… …   Wikipedia

  • Raptor code — In computer science, raptor codes are one of the first known classes of fountain codes with linear time encoding and decoding. They were invented by Amin Shokrollahi in 2000/2001 and were first published in 2004 as an extended abstract.Raptor… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”