Vorlesung im Wintersemester 2003/04

Algorithmen für Gruppen und Codes

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

15. Vorlesung: Gewichtsverteilung von Codes

• Gewichtszählerpolynom:
  formales Polynom W(x,y)=A₀xⁿ+A₁x^(n-1)y¹+...+A_ix^(n-i)yⁱ+...+A_nyⁿ, das die Anzahl A_i der Codeworte vom Gewicht i codiert
• Satz von MacWilliams: Das Gewichtszählerpolynom des dualen Codes ist W'(x,y)=1/|C|*W(x+(1-q)y,x-y)
• Berechne ggf. die Gewichtsverteilung des dualen Codes und daraus die Gewichtsverteilung sowie Minimaldistanz des Codes, falls der duale Code "klein" ist.
• Kongruenzen für die Koeffizienten A_i:
  • Automorphismengruppe Aut(C): Menge aller Permutationen (evtl. zusätzlich Multiplikation der Spalten mit Körperelementen), die den Code als Menge fest lassen
  • Zerlege den Code in Codeworte, die von einem nichttrivialen Element h einer Untergruppe H von Aut(C) stabilisiert werden und den Rest ==> Kongruenzen modulo |H|
  • Ist die Ordnung von H eine Primzahl, so der stabilisierte Teilcode linear.
• selbstduale Codes:
  • Das Gewichtszählerpolynom ist invariant unter einer linearen Transformation.
  • Berechnung der möglichen Gewichtsverteilungen via Invariantentheorie, z. B.
    • selbstduale Binärcodes mit geraden Gewichten:
      Gewichtszählerpolynom ist Polynom in f₁ und f₂ mit
      f₁:=x²+y² und f₂:=x⁸+14y⁴y⁴+y⁸
    • selbstduale Binärcodes mit durch vier teilbaren Gewichten:
      Gewichtszählerpolynom ist Polynom in g₁ und g₂ mit
      g₁:=x⁸+14x⁴y⁴+y⁸ und g₂:=x²⁴ +752y¹⁶y⁸ +2576x¹²y¹² +752x⁸y¹⁶ +y²⁴

• MacWilliams, F. J. and Sloane, N. J. A.
  The Theory of Error-Correcting Codes.
  Amsterdam: North-Holland, 1977.