Low-Density-Parity-Check-Code

Low-Density-Parity-Check-Codes, auch als LDPC oder Gallager-Codes bezeichnet, sind lineare Blockcodes zur Vorwärtsfehlerkorrektur. Sie wurden 1962 von Robert Gray Gallager im Rahmen seiner Dissertation am MIT entwickelt.

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

Nachdem sie lange vergessen waren, erlebten sie eine Renaissance, als Rüdiger Urbanke und Thomas J. Richardson 2001 zeigten, dass sie nahe der Shannon-Grenze operieren konnten und als irreguläre LDPC effizient implementiert werden konnten. Zu den irregulären LDPC gehören die Tornado Codes für Erasure Coding (Michael Luby, Michael Mitzenmacher, Daniel A. Spielman, Amin Shokrollahi 2001).