Kanalkodierung - Informations-und Kodierungstheorie - page 158

Dabei ist der Erweiterungskörper isomorph zum Zyklus der Polynomreste.
Anstelle von x i stehen die Elemente des Erweiterungskörpers mit x 0 = α 0 ,
x 1 = α 1 , x 2 = α 2 , ... . Die Bestimmung der Periode p kann damit auch im
Erweiterungskörper erfolgen. p wird als Ordnung des Elements α bezeich-
net. Ist M ( x ) primitiv, dann ist die Ordnung des Elements α maximal mit
p = p max =2

− 1 . In diesem Zusammenhang bezeichnet man α als primiti-
ves Element des Erweiterungskörpers GF (2

k 1

k 1

) . Die Ordnung des Elements α

bestimmt die Kodewortlänge n .
Mit dem Element α wurde nun eine Nullstelle für M ( x )= x 3 + x 2 +1 (aus
Beispiel 8.5.4) mit M ( x = α )= α 3 + α 2 +1= α 2 +1+ α 2 +1=0 definiert. 13
Entsprechend dem Fundamentalsatz der Algebra (vgl. Gl. (8.27)) muss gelten:
M ( x )= x 3 + x 2 +1=( x − α 1 )( x − α 2 )( x − α 3 ) ,
d. h., α 1 = α 1 , α 2 und α 3 sind Nullstellen im Erweiterungskörper GF (2 3 ) .
Die Zuordnung zu den Elementen von GF (2

k 1

) ergibt sich wie folgt:

α j = α 2 j− 1 i mod p ( j =1 , 2 , ..., k 1 (= grad M ( x ))) . (8.28)

Die Nullstellen eines Polynoms stellen damit eine Aufeinanderfolge der Ele-
mente α 2 0 i ,α 2 1 i , ..., α 2 k 1 − 1 i mod p

k 1

− 2) dar, die
zueinander konjugiert sind. Man sagt, die konjugierten Elemente befinden sich
in einem Zyklus und konjugierte Elemente liefern den gleichen Zyklus .
Die Nullstellen von M ( x )= x 3 + x 2 +1 sind damit die im Zyklus i =1 ste-
henden zu α 1 konjugierten Elemente α 2 = α 2 und α 3 = α 4 ( i =2 und i =4
liefern demzufolge den gleichen Zyklus; z. B. i =2: α 2 ,α 4 ,α 8mod 7 = α 1 ).
Die Anzahl der Elemente in einem Zyklus wird durch k 1 = grad M ( x ) begrenzt
und ist für p = p max ∈ P

im Zyklus i ( i =0 , 1 , 2 , ..., 2

für alle Zyklen gleich (ausgenommen: i =0 ).
Die Berechnung von M ( x ) über die Nullstellen führt zum gewünschten Ergeb-
nis:
M ( x )=( x − α 1 )( x − α 2 )( x − α 4 )
=( x + α 1 )( x + α 2 )( x + α 4 ) im GF (2)
= x 3 + x 2 ( α + α 2 + α 4 )+ x ( α 3 + α 5 + α 6 )+ α 7
= x 3 + x 2 +1 .

13 Berechnungsbeispiele für die Addition und Multiplikation im GF (2 3 ) , s. Beispiel 8.5.4:
α i + α j = α i mod M ( α )+ α j mod M ( α )= α k ;

ist i = j gilt α i + α j =0 .

Z. B. α 5 + α 2 = α 2 = α 4 bzw. α 5 + α 2 = (011) ⊕ (100) = (111) = α 4 α +1+

α 2 + α 2 = (100) ⊕ (100) = (000)
α i · α j = α ( i + j ) mod p .
Z. B. α 4 · α 5 = α 9 mod 7 = α 2