Rechnernetze

Zur Darstellung von Bitfolgen durch Polynome

Der zu übertragende Block enthalte k Bits Nutzinformation, denen noch r = n–k Bits Prüfinformation hinzugefügt werden. Wir nennen diesen n Bits langen Block Übertragungsnachricht und schreiben meistens C (von Code) dafür.

Als erstes soll ein Verfahren vorgestellt werden, mit dem Nachrichtenblöcke etwas abstrakter dargestellt werden können. Statt wie bisher eine Bitfolge durch eine Folge von Nullen und Einsen zu schreiben, verwenden wir die Polynomschreibweise, d.h. die Bifolge: (c_i)_i=0..n-1 wird durch das Polynom in X:

V(X)  =  c_i · X_i

dargestellt; z.B. würde die Bitfolge mit 17 Bits

10001110011001001

als folgendes Polynom geschrieben werden:

X¹⁶ + X¹² + X¹¹ + X¹⁰ + X⁷ + X⁶ + X³ + 1

wobei üblicherweise X⁰ = 1 und X¹ = X geschrieben wird. Es ist eigentlich beliebig, welches Bit der Bitfolge man der 1=X⁰ bzw. X^r zuordnet. Wir vereinbaren daher, dass das von rechts erste Bit stets der 1 zugeordnet werden soll, wodurch diese Schreibweise direkt in die Darstellung für die Polynomdivision übertragen werden kann.

Mathematisch handelt es sich bei dieser Schreibweise um den Ring der Polynome in X über dem Körper {0,1}; für die Elemente dieses Körpers gelten die folgenden Rechenregeln

Eine Potenz von X nennen wir auch einen Term. Dem Zeichenwert c_k wird der Term c_k·X^k zugeordnet. Bei der Schreibung werden Terme mit dem Koeffizient '0' fortgelassen, während Terme mit dem Koeffizienten '1' addiert werden, wobei der Koeffizient nicht ausdrücklich geschrieben wird. Die Zeichenwerte '0' bzw. '1' des Codeworts werden also als Zahlenwerte null bzw. eins interpretiert.

Der Grad der Polynome wird durch die höchste Potenz definiert. Der Grad ist durch die längste Bitfolge beschränkt und beträgt bei einer Codelänge von n Bits höchstens n-1, im obigen Beispiel offenbar 16.

Fasst man die Terme Xⁱ als Basisvektoren auf, was aufgrund ihrer algebraischen Eigenschaften zulässig ist, so sind Terme unterschiedlichen Grads unabhängig voneinander; daher beinhaltet die Polynom-Schreibweise eines Codeworts im wesentlichen die gleiche Information wie die direkte Schreibung der Bitfolge.

Zur Einübung des Rechnens mit Polynomen sollen hier einige Rechenaufgaben vorgeführt werden. Als erstes Beispiel stellen wir die Polynom-Addition vor:

Bei der Addition ist zu beachten, dass X^k+X^k = 0 ist, da nach den Rechenregeln für den Körper {0,1} gilt: 1+1 = 0. Aus diesem Grunde liefert die Subtraktion zweier Polynome jeweils das gleiche Ergebnis wie die Addition.

Für Polynome kann sowohl eine Multiplikation als auch eine Division eingeführt werden. Es gelten die üblichen distributiven, assoziativen und kommutativen Gesetze, so dass das Produkt zweier Polynome einfach ausmultipliziert werden kann. Es gilt für die beiden folgenden Polynome

Die Division zweier Polynome wird im Prinzip als die umgekehrte Operation der Multiplikation definiert. Das Verfahren ist analog der üblichen manuellen Division, d.h. der Divisor wird vom dem Dividenden abgezogen und das restliche Polynom weiter dividiert, bis es kein Vielfaches des Divisors mehr gibt. Letzteres wird als Rest der Division bezeichnet und wird uns im folgenden besonders interessieren. Insbesondere sind auch Verfahren zu entwickeln, den Rest möglichst effizient und automatisch bei der Übertragung von Nachrichtenblöcken zu ermitteln. Zunächst betrachten wir jedoch auch hier ein Beispiel. Es sollen die beiden folgenden Polynome dividiert werden

V₁(X) = X³ + X + 1

V₂(X) = X + 1

Man kann sich die Polynome so hinschreiben, als wären es ganze Zahlen; dazu wird der Divisor derart mit einem passenden Term X^k erweitert, dass der Grad von Divisor und Dividend übereinstimmen.

Das Ergebnis wird üblicherweise in der folgenden Form als Produkt aufgeschrieben:

V₁(X) = (X²+X)*V₂(X) + 1