allgemeiner Blockcode:
Teilmenge von GF(q)n
⇒ Beschreibung des Codes linear in der Anzahl der
Codeworte (alle Codeworte)
linearer Blockcode C=[n,k,d]q:
Vektorraum der Dimension k über GF(q)
⇒ Beschreibung des Codes logarithmisch in der Anzahl der
Codeworte (Generatormatrix)
Codierabbildung i → c=i·G (Zeilenvektoren)
Fehlererkennung
Test, ob v∈GF(q)n ein Codewort ist
lineares Gleichungssystem i·G=v
Berechnung des Fehlersyndroms
s=v·Ht mit Hilfe
der (n-k)×nPrüfmatrix;
Ht
es gilt G· Ht=0
Fehlersyndrom unabhängig vom Codewort: v·Ht=(v+e)·Ht=e·Ht
Fehlerkorrektur ist NP-hart
Eingabe:
Binärmatrix H, Binärvektor s,
positive ganze Zahl w
Problem:
Existiert ein Vektor e mit e· Ht=s
und wgt(e)≤w
Literatur:
Berlekamp, E.; McEliece, R.; van Tilborg, H. On the inherent intractability of certain coding problems.
IEEE Transactions on Information Theory, Vol. 24, No .3, May 1978,
pp. 384-386. IEEE Xplore
Berechnung des Minimalgewichts ist NP-hart
Eingabe:
Binärmatrix H, positive ganze Zahl w
Problem:
Existiert ein Vektor c, c≠0 mit e· Ht=0
und wgt(e)≤w
Literatur:
Vardy, A. The intractability of computing the minimum distance of a code.
IEEE Transactions on Information Theory, Vol. 43, No .6, Nov. 1997, pp. 1757-1766. IEEE Xplore
lineare Codes: Minmaldistanz = Minimalgewicht
naiver Algorithmus:
Aufzählen aller Vektoren der Länge n mit
aufsteigendem Gewicht w, bis ein Codewort gefunden
wurde.
⇒ mehr als
d-1
∑(
n
)(q-1)w-1
w
w=1
Vektoren müssen aufgezählt werden (erste von null
verschiedene Stelle ist eins)
systematische Generatormatrix
Umformen der (Zeilen) der Generatormatrix G, so
daß o. B. d. A. an den ersten k
Spalten eine Einheitsmatrix steht.
systematische Codierung G=(I|A) ⇒
c:=i·G=(i,i·A)
mit wgt(c)≥wgt(i)
verbesserter Algorithmus:
Aufzählen aller Vektoren i der Länge k mit
aufsteigendem Gewicht w, systematische Codierung c=(i,i·A).
aufgezählte Codeworte liefern obere Schranke für
das Minimalgewicht
noch nicht aufgezählte Codeworte haben mindestens das
Gewicht w+1, falls alle Worte i
vom Gewicht wgt(i)≤w aufgezählt
wurden.