Kanalkodierung - Informations-und Kodierungstheorie - page 183

Nullstellen x i (kurz: exp ( x i ) ) sind die Fehlerstellen.
Man nutzt somit den Zusammenhang über die bereits bekannten Fehlersyndro-
me s j zur Bestimmung der Koe zienten σ i und damit des Lokatorpolynoms
σ ( x ) , um im nächsten Schritt die Null-/Fehlerstellen x i zu berechnen.
Aus
σ ( x = x i )= x i + σ 1 x ν− i + ... + σ ν− 1 x i + σ ν =0
erhält man in Anlehnung an Gl. (8.38) durch Multiplikation mit x i
x j + i + σ 1 x j + ν− i + ... + σ ν− 1 x j + i + σ ν x i =0
und Summenbildung über i =1 bis ν den folgenden Zusammenhang
s j + ν + σ 1 s j + ν− 1 + ... + σ ν− 1 s j +1 + σ ν s j =0 .
Nach Umstellung sind die zu lösenden Gleichungen:
σ ν s j + σ ν− 1 s j +1 + ... + σ 1 s j + ν− 1 = s j + ν

( j =1 , 2 , ..., ν );

in Matrizennotation:
⎛

⎛ ⎞ ⎛ ⎞

⎞

σ ν
σ ν− 1
.
σ 1

s ν +1
s ν +2
.
s 2 ν

s 1 s 2 ... s ν
s 2 s 3 ... s ν +1
...............
s ν s ν +1 ...s 2 ν− 1

⎝ ⎠ = ⎝ ⎠

⎝ ⎠

. (8.39)

Das Gleichungssystem kann zum Beispiel mit dem GAUSSschen Eliminati-
onsprinzip gelöst werden. Zu Beginn werden ν = f k Gleichungen aufgebaut.
Treten bei der Lösung Abhängigkeiten auf oder werden keine ν Nullstellen in
σ ( x ) gefunden (Schritt 3.), ist das Gleichungssystem entsprechend zu redu-
zieren, im ungünstigsten Fall ( f k − 1) mal. Bei Reduzierung finden nicht alle
Fehlersyndrome Berücksichtigung. Es lassen sich dann mehrere ( ≥ 2 ) Glei-

chungssysteme aufstellen, deren Ergebnisse bei ν Fehlern gleich sein müssen.
3. Bestimmung der Fehlerstellen
Die Fehlerstellen werden durch systematisches Probieren ermittelt. Es sind mit

0 −→

x i = α j , exp ( x i )= j

σ ( x = α j

)= ( j =0 , 1 , ..., n − 1) (8.40)

sonst

die Nullstellen x i ( i =1 , 2 , ..., ν ) von σ ( x ) zu finden. Die Suche lässt sich be-
schleunigen, wenn nach dem Finden einer Nullstelle x i das Lokatorpolynom
um den Linearfaktor ( x + x i ) reduziert wird.
Eine andere Herangehensweise zeigt der CHIEN-Algorithmus (1964). Der ite-
rativ arbeitende Algorithmus ist im Folgenden in Struktogrammnotation ange-
geben [DUD 93]. σ k ( k =1 , 2 , ..., ν ) sind die Koe zienten des Lokatorpolynoms