Niedrigdichte-Paritätsprüfcodes

Ein Niedrigdichte-Paritätsprüfcode ist ein Code, der durch eine Paritätsprüfmatrix mit den folgenden Eigenschaften spezifiziert ist: Jede Spalte enthält eine kleine feste Anzahl j ≥ 3 von 1en und jede Reihe enthält eine kleine feste Anzahl k > j von 1en. Der typische Mindestabstand dieser Codes wächst linear mit der Blocklänge bei festem Code-Rate und festem j. Bei Verwendung mit Maximum-Likelihood-Dekodierung auf einem ausreichend ruhigen binären, symmetrischen Kanal nimmt die typische Wahrscheinlichkeit eines Dekodierungsfehlers exponentiell mit der Blocklänge ab, bei festem Code-Rate und festem j. Ein einfaches, aber nicht optimales Dekodierungsschema, das direkt von den Kanal-a-posteriori-Wahrscheinlichkeiten ausgeht, wird beschrieben. Sowohl die Gerätekomplexität als auch die Datenverarbeitungskapazität in Bits pro Sekunde dieses Dekodierers steigen ungefähr linear mit der Blocklänge. Für j > 3 und eine ausreichend niedrige Rate wird gezeigt, dass die Fehlerwahrscheinlichkeit bei Verwendung dieses Dekodierers auf einem binären symmetrischen Kanal mindestens mindestens exponentiell mit der Wurzel der Blocklänge abnimmt. Einige experimentelle Ergebnisse zeigen, dass die tatsächliche Wahrscheinlichkeit eines Dekodierungsfehlers viel kleiner ist als diese theoretische Grenze.