30. Aug 2008, 04:57

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: , 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)LDPC

• 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 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

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

1. ↑ 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])

Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.

Abkürzungen • Dateiendungen • Netzjargon