Fachrat Informatik - Forum

Kann mir evtl. jemand erklären, wie die Erzeugermatrix in Standardform aufgestellt wird, ich gucke mir das im Skript an und verstehe da im Moment irgendwie nur Bahnhof. Evtl. an einem konkreten Beispiel, z.B. an dem aus dem Skript.

http://www.iag.uni-hannover.de/~behrens/…trukturen10.pdf (auf der 2ten Seite)

Ich schäme mich zwar etwas diese Frage zu stellen, aber ich machs mal trotzdem

wie funktioniert modulo bei negativen zahlen ?

also wenn es -2 mod 5 ist, ist das ergebnis 3, wenn der taschenrechner nicht lügt
aber wie funktioniert das ganze, wenn man z.B. -5 mod 2 rechnen soll ?

(a modulo b) ist meine ich durch mod(a,b) = a - floor(a/b) * b definiert (Floor rundet auf die nächstkleinere ganze Zahl ab), also z.B.

... mod(-4,3)=2, mod(-3,3)=0, mod(-2,3)=1, mod(-1,3)=2, mod(0,3)=0, mod(1,3)=1, mod(2,3)=2, mod(3,3)=0, mod(4,3)=1...
Hast also immer diese kreisförmige Struktur (...,0, 1, 2, ..., b, 0, 1, 2, ..., b, ...) für a mod b, das setzt sich in die negativen Zahlen genauso fort.

Theoretische Hintergründe gibts im nächsten Post, oder z.B. hier: http://www.iti.fh-flensburg.de/lang/algo…en/zahlenth.htm

a = b mod c, falls es eine ganze Zahl k gibt, mit a - b = k * c.

Für deine Beispiele ergibt sich also:
-2 - 3 = (-1) * 5, also -2 = 3 mod 5
-5 - 1 = (-3) * 2, also -5 = 1 mod 2

Zitat von »Torrero«

Kann mir evtl. jemand erklären, wie die Erzeugermatrix in Standardform aufgestellt wird, ich gucke mir das im Skript an und verstehe da im Moment irgendwie nur Bahnhof. Evtl. an einem konkreten Beispiel, z.B. an dem aus dem Skript.

http://www.iag.uni-hannover.de/~behrens/…trukturen10.pdf (auf der 2ten Seite)

Hey!

Das würde mich auch sehr interessieren... irgendwie erklärt das Skript nicht wirklich, wie das funktionieren mag



lg
lars

Ich war beim Übungsleiter, und er hat es mir in 5 Minuten verständlich erklärt. Ist einfacher, als es auf den ersten Blick aussieht. Aber hier irgendwie doch schwer zu beschreiben.

Ganz einfach ist es, wenn man die Kontrollmatrix H hat, dann musst du diese nur transponieren und einfach die entsprechende Einheitsmatrix dranhängen.

Die andere Methode versuche ich jetzt auch mal :
Du hast z.B. 3 Gleichungen mit 7 Variablen, dann ist die Dimension 4, also hat die Erzeugermatrix 4 Zeilen und 7 Spalten,
dann kannst du als erstes die 4x4 Einheitsmatrix hinschreiben, denn die Erzeugermatrix ist G=(E|P)

Und die anderen 3 Elemente jeder Zeile rauszukriegen, nimmst du dir Zeile für Zeile die Einheitsmatrix her, und setzst diese in die Gleichungen ein, und dann musst zu gucken, welche übrigen Variablen der Gleichungen 0 oder 1 werden müssen, um die Gleichung zu erfüllen.

Dann nochmal was zur Gleichungsberechnung in Z_N :

Es gibt die 2 Gleichungen aus der Übung in Z_7 :

(1) x + 2y = 4
(2) 4x + 3y = 4

Dann stelle ich die erste zuerst nach x um
(1) x = 4 - 2y / dann muss man die -2y ja noch nach Z_7 "transferieren" also (-2+7)y=5y
==> x = 4 + 5y

Dann setzt man das in (2) ein

(2) 4(4+5y) + 3y = 4
ausmultipliziert gibt das 16 + 20y + 3y = 4
der nächste Schritt in der Lösung ist, dass das dann in Z_7 = 2+2y ist
kommt man darauf, indem man die 16 und die 23y jeweils mod 7 nimmt ?
16 mod 7 = 2 und 23 mod 7 = 2, also 2+2y = 2 ?

Ha, cool... danke für den Tipp. Das macht Sinn.

Zu Deiner Frage: Ja, Du hast Recht. 16 + 23y wird durch mod 7 zu 2 + 2y.
Hab ich auch erst eine Zeit lang drüber nachgedacht..

Ich dachte schon, dass ich das mit den Gleichungen kapiert habe, aber ein Schritt kann ich da noch nicht so nachvollziehen :

da ist am Ende der Berechnung :

2 y = 2 und wird dann umgeformt zu y = 4 * 2 = 8 = 1 (das ganze immer noch in z_7)

wie kommt die 4 bei y = 4*2 zustande ?

2*y = 2 => 8 * y = 8 => y = 1

Genau. Die 4 die dich da stört ist nämlich das multiplikative Inverse von 2 (im Ring der Restklassen modulo 7).
Also 4 * 2 = 8 = 1 (mod 7)

Normalerweise würdest du die Gleichung ja auflösen indem du mit 1/2 multiplizierst. Das bringt aber nur was, weil 1/2 das multiplikative Inverse von 2 ist.
Also 2 * 1/2 = 2/2 = 1.