Vorlesung im Wintersemester 2003/04

Algorithmen für Gruppen und Codes

(Prof. Dr. Thomas Beth, Dr. Markus Grassl)

11. Vorlesung: Fehlerkorrigierende Codes

• lineare Blockcodes C=[n,k,d]_q
• Minimaldistanz/Minimalgewicht
• asymptotische Eigenschaften/Tabelle mit Parametern
• Vorteile linearer Codes
  • einfache Codierung
  • Fehlererkennung via Fehlersyndrom
• NP-harte Probleme: Fehlerkorrektur & Minimaldistanz
• naive Algorithmen
• systematische Codierung

• E. Berlekamp, R. McEliece, and H. van Tilborg.
  "On the inherent intractability of certain coding problems".
  IEEE Transactions on Information Theory, vol. 24, no. 3, May 1978, pp. 384-386.
  online
• MacWilliams, F. J. and Sloane, N. J. A.
  The Theory of Error-Correcting Codes.
  Amsterdam: North-Holland, 1977.
• A. Vardy.
  "The intractability of computing the minimum distance of a code".
  IEEE Transactions on Information Theory, vol. 43, no. 6, Nov. 1997, pp. 1757-1766.
  online