Vorlesung im Wintersemester 2004/05

Algorithmen für Gruppen und Codes

(Dr. Markus Grassl)

15. Vorlesung: Kongruenzen für die Gewichte & Aufzählen von Codeworten

Kongruenzen für Gewichte

• Lemma:
  Ein linearer Binärcode hat nur Worte von geradem Gewicht, falls alle Zeilen der Generatormatrix ein gerades Gewicht haben.
• Dualcode: C^⊥={v: v∈ GF(q)ⁿ | ∀ c∈ C: <v|c>=0 }.
• selbstorthogonaler Code: C⊆C^⊥
• Lemma:
  Ein linearer Binärcode hat nur Worte, deren Gewicht durch vier teilbar ist, falls alle Zeilen der Generatormatrix ein durch vier teilbares Gewicht haben und der Code selbstorthogonal ist, d. h. G·G^t=0.

• Lemma:
  Ein linearer Code über GF(3) (ternärer Code) hat nur Worte, deren Gewicht durch drei teilbar ist, falls der Code selbstorthogonal ist, d. h. G·G^t=0.

• Verkettung von Codes:
  • GF(4)={0,1,α,&alpha²} ist ein Vektorraum der Dimension zwei über GF(2)
  • Der Binärcode C₂=[3,2,2]₂={(000), (110), (101), (011)} enthält nur Worte vom Gewicht null und zwei.
  • Man kann jedem Element von GF(4) ein Codewort aus C₂ zuordnen.
  • Komponentenweise Anwendung dieser Abbildung liefert einen GF(2)-Vektorraum-Isomorphismus Φ:GF(4)ⁿ→GF(2)³ⁿ mit wgt(Φ((v)))=2wgt(v).
• Lemma:
  Ein linearer Code C über GF(4) hat nur Worte geraden Gewichts, falls der Binärcode Φ(C) doubly-even ist.
• Generatormatrix von Φ(C):
  • GF(4) als Matrixalgebra über GF(2):

    0	1	α	&alpha2
    [0 0] [0 0]	[1 0] [0 1]	[0 1] [1 1]	[1 1] [1 0]

  • komponentenweise Ersetzung der Elemente der Generatormatrix G über GF(4) durch 2×2-Matrizen über GF(2) liefert G'
  • Multiplikation von G' mit I_n ⊗ G₂ liefert Φ(G), wobei

    G2=	[1 0 1] [0 1 1]

  • direkte Berechnung: ersetze die Einträge in G enstprechend der folgenden Tabelle:

    0	1	α	&alpha2
    [0 0 0] [0 0 0]	[1 0 1] [0 1 1]	[0 1 1] [1 1 0]	[1 1 0] [1 0 1]

Effizientes Aufzählen von Codeworten

• Grundaufgabe:

  gegeben:

  Generatormatrix G mit Zeilen g₁,...,g_k sowie Gewicht w

  Aufgabe:

  Generiere alle Codeworte c=i·G für alle Informationsworte i∈GF(q)^k mit wgt(i)=w, o. B. d. A. ist die erste von Null verschiedene Position von i gleich eins.

• Teilaufgaben:
  1. generiere alle w-Teilmengen von {g₁,...,g_k}
  2. durchlaufe alle w-Tupel (&gamma₁,...,&gamma_w) über GF(q)\{0} und berechne die Linearkombination c:=∑_j &gamma_jg_ij.
• Beobachtung: Die Berechnung der Linearkombination c kann in das Aufzählen integriert werden.
• verallgemeinerter Gray-Code: [vgl. Knuth]
  Zähle die Tupel (&gamma₁,...,&gamma_w) so auf, daß sich in jedem Schritt nur ein Element ändert, z. B. &gamma_j → &gamma'_j.
  ⇒ c'=c+(&gamma'_j-&gamma_j) g_ij
  ⇒ nur eine Vektoroperation, Vektoren (&gamma'_j-&gamma_j) g_ij können vorberechnet werden
• Algorithm 382 ("Revolving Door Algorithm")
  Aufzählen von w-Teilmengen, so daß in jedem Schritt nur ein Element ausgetauscht wird, z. B. i_j → i'_j.
  ⇒ für &gamma_j=1 ist c'=c+(g_i'j-g_ij)
  ⇒ nur eine Vektoroperation, Vektoren g_a-g_b können vorberechnet werden

Literatur

• Donald E. Knuth.
  The Art of Programming, Vol. 4.
  Pre-Fascicle 2a: Generating all n-tuples.
  http://www-cs-faculty.stanford.edu/~knuth/news.html
• Donald E. Knuth.
  The Art of Programming, Vol. 4.
  Pre-Fascicle 3a: Generating all combinations.
  http://www-cs-faculty.stanford.edu/~knuth/news.html
• Phillip J. Chase.
  Algorithm 382: Combinations of M out of N Objects.
  Communications of the ACM, vol. 13, no. 6, p. 368 & p.  376, June 1970.
  ACM Online
• James R. Bitner, Gideon Ehrlich, and Edward M. Reingold.
  Efficient Generation of the Binary Reflected Gray Code and Its Applications.
  Communications of the ACM, vol. 19, no. 9, pp. 517-521, September 1976.
  ACM Online