Gute Fehlerkorrekturcodes basierend auf sehr spärlichen Matrizen

Wir untersuchen zwei Familien von Fehlerkorrekturcodes, die in Bezug auf sehr spärliche Matrizen definiert sind. "MN" (MacKay-Neal (1995)) Codes sind kürzlich erfunden worden, und "Gallager-Codes" wurden erstmals 1962 untersucht, scheinen jedoch weitgehend vergessen worden zu sein, trotz ihrer hervorragenden Eigenschaften. Die Dekodierung beider Codes kann mit einem praktischen Sum-Produkt-Algorithmus angegangen werden. Wir beweisen, dass diese Codes "sehr gut" sind, da es Codefolgen gibt, die, wenn sie optimal dekodiert werden, Informationsraten bis zur Shannon-Grenze erreichen. Dieses Ergebnis gilt nicht nur für den binär-symmetrischen Kanal, sondern auch für jeden Kanal mit symmetrischem stationärem ergodischem Rauschen. Wir geben experimentelle Ergebnisse für binär-symmetrische Kanäle und Gaußsche Kanäle, die zeigen, dass eine praktische Leistung, die erheblich besser ist als die von Standard-Convolutional- und konkatenierenden Codes, erreicht werden kann; in der Tat ist die Leistung von Gallager-Codes fast so nahe an der Shannon-Grenze wie die von Turbo-Codes.