Vorlesung im Wintersemester 2003/04

Algorithmen für Gruppen und Codes

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

16. Vorlesung: Punktieren und Verkürzen von Codes

• Punktieren (puncturing):
  Streichen einer Stelle des Codes liefert C_p=[n-1,k,d'≥d]_q (falls d>1)
• Verkürzen (shortening):
  Auswahl aller Codeworte, die an einer Stelle null sind, und streichen dieser Stelle liefert C_s=[n-1,k'≥k-1,d'≥d]_q
• Wiederholtes Verkürzen (Construction Y1):
  Verkürzen an den Stellen ungleich null eines Worts des Dualcodes liefert eine um mindestens eins größere Dimension.
• Wiederholtes Punktieren:
  
  • HITTING SET: Teilmenge von {1,...,n}, die für jedes Codewort minimalen Gewichts mindestens eine Nullposition enthält.
  • Punktieren an den Stellen eines HITTING SETs liefert eine um mindestens eins größere Minimaldistanz.
  • Bestimmung eines HITTING SETs:
    • NP-hart und schlecht approximierbar
    • Greedy-Algorithmus liefert "gute" Approximation (im wesentlichen so gut wie jeder andere poly. Algorithmus)
    • Formulierung als lineares Programm, rationale Lösung liefert untere Schranken für die Größe des HITTING SETs.

• Grassl, Markus and White, Gerg.
  "New Good Linear Codes by Special Puncturings".
  submitted to IEEE International Symposium on Information Theory 2004.
  PostScript