Diese Präsentation zeigt einige der in mathGUIde eingebauten Möglichkeiten des Rechnens in Polynomringen
Die Beispiele stammen aus dem Buch Teschl, Gerald; Teschl, Susanne: Mathematik für Informatiker, Band 1: Diskrete Mathematik und Lineare Algebra, Springer, Berlin, 3. Aufl., 2008, ISBN: 978-3-540-77431-0.
Wir untersuchen die Addition und Multiplikation im Polynomring
Die folgenden Programmzeilen geben die Additionstafel und die Multiplikationstafel in diesem Ring aus.
Der mathGUIde-Funktion printTable
werden Funktionen
zur Berechnung der Zellelemente übergeben.
Wir ersparen uns die separate Definition dieser Funktionen, indem wir sogenannte
anonyme Funktionen verwenden.
Diese werden mit dem Schlüsselwort lambda definiert:
Nach dem lambda kommt die Parameterliste,
danach ein Doppelpunkt und der Funktionswert.
m = Poly([1,1,1], 2) # 1 + x + x² # Alle Polynome mod m # 0 1 x 1+x P = [Poly([0],2), Poly([1],2), Poly([0,1],2), Poly([1,1],2)] printTable(4, 4, lambda i,k: ((P[i] + P[k]) % m).pretty(), # allgemeines Tabellenelement rowHeadFn = lambda i: P[i].pretty(), # Zeilenköpfe colHeadFn = lambda k: P[k].pretty(), # Spaltenköpfe cellAlign = "left", title = "Addition in Z2[x]x²+x+1", corner = "+") printTable(4, 4, lambda i,k: ((P[i] * P[k]) % m).pretty(), rowHeadFn = lambda i: P[i].pretty(), colHeadFn = lambda k: P[k].pretty(), cellAlign = "left", title = "Multiplikation in Z2[x]x²+x+1", corner = "*")
In der Multiplikationstabelle finden Sie in jeder Zeile (außer für Null) eine Eins als Multiplikationsergebnis. Mit anderen Worten: Jedes von Null verschiedene Element hat ein multiplikatives Inverses. Daher ist der Ring sogar ein Körper.
Zum Vergleich machen wir das gleiche Experiment modulo eines anderen Polyonms:
m = Poly([1,0,1], 2) # 1 + x² # Alle Polynome mod m # 0 1 x 1+x P = [Poly([0],2), Poly([1],2), Poly([0,1],2), Poly([1,1],2)] printTable(4, 4, lambda i,k: ((P[i] + P[k]) % m).pretty(), rowHeadFn = lambda i: P[i].pretty(), colHeadFn = lambda k: P[k].pretty(), cellAlign = "left", title = "Addition in Z2[x]x²+1", corner = "+") printTable(4, 4, lambda i,k: ((P[i] * P[k]) % m).pretty(), rowHeadFn = lambda i: P[i].pretty(), colHeadFn = lambda k: P[k].pretty(), cellAlign = "left", title = "Multiplikation in Z2[x]x²+1", corner = "*")
Hier sieht man, dass es zu x+1 kein multiplikatives Inverses gibt und der Ring daher kein Körper ist.
p, q = Poly([0,1,0,1], 2), Poly([1,1], 2) p + q # 4.3 a) q + q # 4.3 b) p * q # 4.3 c)
p, q = Poly([1,2,1], 3), Poly([2,1], 3) p + q # 4.3 d) p * q # 4.3 e)
# Teschl: Beispiel 4.5 a): Division und Rest:
print(Poly([0,-2,0,1,3]) / Poly([1,0,1]))
print(Poly([0,-2,0,1,3]) % Poly([1,0,1]))
# Teschl: Beispiel 4.5 b)
print(Poly([-2,1,1]) / Poly([-1,1]))
print(Poly([-2,1,1]) % Poly([-1,1]))
# Teschl: Beispiel 4.9 a)
a = 4 * Poly([-1,1])^2
b = 8 * Poly([-1,1])
Poly.gcd(a, b)
# Teschl: Beispiel 4.9 b)
a = Poly([-1,3]) * Poly([2,1])^4
b = Poly([Rational(-1,3),1]) * Poly([2,5])
print(a.pretty())
print(b.pretty())
print(Poly.gcd(a, b).pretty())
# Teschl: Beispiel 4.9 c)
a = 5 * Poly([-1,1])
b = 5 * Poly([1,1])
Poly.gcd(a, b)
a = Poly([1,-2,0,1]) b = Poly([-1,0,1]) Poly.gcd(a, b)
Definition
Ein Polynom vom Grad > 0 heißt irreduzibel (Primpolynom), wenn es nicht Produkt von Polynomen niedrigerer Grade ist.
Das folgende Programmstück findet alle irreduziblen Polynome
aus Z2[x] bis zum Grad 5.
Dazu erzeugt es der Reihe nach die Polynome aus den Bitmustern der Binärzahlen
bis 63 (26-1) und prüft, ob es durch eines der bisher gefundenen
irreduziblen Polynome teilbar ist:
primeList = [] for i in fromTo(2, 63): f = Poly(NumeralSystem.toBase(i, 2, True), 2) divisible = False # Teiler suchen: for p in primeList: if f % p == 0: divisible = True break if not divisible: primeList.append(f) print("{0:3d} --> {1}".format(i, f.pretty()))
Dieser Abschnitt ist noch unfertig.
Um Blöcke von n Bits zu codieren, wählt man zunächst eine Faktorisierung dex Polynoms xn + 1:
# Z_2[x]_x^7+1 x7_1 = Poly([1,0,0,0,0,0,0,1], 2)
Wir testen, ob g(x) = x4 + x3 + x2 + 1 ein Teiler ist
g = Poly([1,0,1,1,1], 2) print(x7_1 % g)
Ja. g ist das Generatorpolynom, der andere Faktor das Kontrollpolynom.
h = x7_1 / g print(h)
Wir haben den zyklischen Code
Da deg(g) = 4 und x7 = 1 in Z2[x]x7+1, kommen für f(x) nur die Polynome vom Grad < 3 in Frage.
# Beispiel: Codierung des Worts 101 --> f(x) = x² + 1 m = Poly([1, 0, 1], 2) c = m * g % x7_1 # Probe: Ist c ein gültiges Codewort? c * h % x7_1 # Decodierung c / g # Alle Codewörter: for m in fromTo(0,7): f = Poly(NumeralSystem.binary(m, True), 2) c = f * g print(m, " --> ", c)