Generatorpolynom zu Sequenz finden
Jan Reimes
ich habe einige Schwierigkeiten mit folgendem Problem:
Gegeben sei ein (zunächst unbekanntes) Generatorpolynom im GF(2):
g(x) = x^n + a_{n-1} * x^{n-1} + ... + a_1 * x + a_0
Eine MLS Folge [1] sei definiert durch:
s_{k+n} = a_{n-1} * s_{k+n-1} + ... + a_0 * s_k
Die Elemente s_{i} für i = 0...k+n-1 können aufgrund der Zyklizität
zur Periode m = 2^n - 1 leicht ermittelt werden.
Bei der Aufgabenstellungen nun sowohl die Rekursionsvorschrift als
auch s_{i} selbst bekannt. Die Frage(n) wäre nun:
- Wie kann man prüfen, ob es sich bei der Folge s_{i} um eine MLS
Folge handelt?
- Optional/Beser: Kann man aus den gegebenen Größen das
Generatorpolynom (bzw. dessen Koeffizienten a_k) ermitteln?
Ein Beispiel soll meinen Lösungsansatz verdeutlichen:
Gegeben sei ein Generatorpolynom g(x) = x^3 + x + 1
(-> n = 3, m = 2^n - 1 = 7, [a] = [0 1 1]) ... mit einem zufälligem
Anfangszustands des Schieberegisters (<> 0 0 0) ergibt sich z.B.
folgende Sequenz:
... 1 1 1 0 0 1 0 | 1 1 1 0 0 1 0 | 1 1 1 0 0 1 0 ...
Wende ich die obige Rekursionformel an, ergibt sich nach 6
Beobachtungen von s_{i} ein Gleichungssystem im GF(2):
|s_3| |s_2 s_1 s_0| |a_2|
|s_4| = |s_3 s_2 s_1| * |a_1|
|s_5| |s_4 s_3 s_2| |a_0|
Wenn ich das per Hand ausrechne, stimmt das auch. Die Prüfung auf eine
gültige Sequenz wäre dann, dass das Gleichungssystem eindeutig lösbar
ist.
Aber wie löst man so etwas allgemein/algebraisch im GF(2)? "Einfach
mal eben" die Matrix invertieren ist ja auch nicht so einfach oder ist
das ganze doch total einfach und ich hab da nur ne Blockade?!
Gruß,
Jan
Jan Fricke
> Hallo zusammen,
>
> ich habe einige Schwierigkeiten mit folgendem Problem:
>
> Gegeben sei ein (zunächst unbekanntes) Generatorpolynom im GF(2):
> g(x) = x^n + a_{n-1} * x^{n-1} + ... + a_1 * x + a_0
>
> Eine MLS Folge [1] sei definiert durch:
> s_{k+n} = a_{n-1} * s_{k+n-1} + ... + a_0 * s_k
>
> Die Elemente s_{i} für i = 0...k+n-1 können aufgrund der Zyklizität
> zur Periode m = 2^n - 1 leicht ermittelt werden.
>
> Bei der Aufgabenstellungen nun sowohl die Rekursionsvorschrift als
> auch s_{i} selbst bekannt. Die Frage(n) wäre nun:
> - Wie kann man prüfen, ob es sich bei der Folge s_{i} um eine MLS
> Folge handelt?
> - Optional/Beser: Kann man aus den gegebenen Größen das
> Generatorpolynom (bzw. dessen Koeffizienten a_k) ermitteln?
Wenn ich Dich richtig verstehe, dann weißt Du, dass die Folge s_{i}
einer linearen Rekursionsvorschrift genügt (der Körper spielt im
folgenden keine Rolle), und Du willst die zugehörige Rekursionsgleichung
finden.
Wir nehmen an, dass die Rekursionsgleichung
s_{k+n} = a_{n-1} * s_{k+n-1} + ... + a_0 * s_k
lautet. Das können wir als lineare Gleichung in den Koeffizienten a_i
auffassen. Wenn wir die Gleichungen für die nächsten n Folgeglieder
hinzunehmen, erhalten wir ein (inhomogenes) Gleichungssystem mit der
erweiterten Koeffizientenmatrix
/ s_{n+k} s_{n+k-1} ... s_k \
| s_{n+k+1} s_{n+k} ... s_{k+1} |
| ............. |.
\ s_{2n+k} ... s_{n+k} /
Wenn das Gleichungssystem lösbar ist, dann muss die Determinante davon
Null sein, und (-1,a_{n-1},...,a_0) liegt im Kern der Matrix.
Das ganze muss man natürlich nur für k=0 machen, alle weiteren Werte
überprüft man per linearer Rekursion.
Algorithmus:
============
(1) Setze n=1.
(2) Erstelle die (n+1)x(n+1)-Matrix A mit den Einträgen s_{n+i-j}.
(3) Falls det(A)!=0, erhöhe n um 1 und zurück zu (2).
(4) Bestimme das Kernelement (-1,a_{n-1},...,a_0). [Siehe Bemerkung unten.]
(5) Teste, ob {s_k} der Rekursionsgleichung genügt:
(5a) Falls es für s_K nicht stimmt, setze n:=K und zurück zu (2).
(6) Fertig!
Hinweis zu (4): Der Algorithmus sorgt dafür, dass es eine reguläre
(nxn)-Untermatrix gibt. Der Rang ist also mindestens n, der Kern
höchstens eindimensional, also ist dieses Kernelement eindeutig bestimmt.
Um zu überprüfen, ob die gefundene Rekrusionsgleichung eine MLS liefert,
muss man nur testen, ob das Polynom irreduzibel ist. Das steht aber auch
in dem von Dir zitierten Wikipedia-Artikel.
Viele Grüße Jan
Jan Reimes
Danke erstmal für deine Antwort!
Jan Fricke schrieb:
> Wenn ich Dich richtig verstehe, dann weißt Du, dass die Folge s_{i}
> einer linearen Rekursionsvorschrift genügt (der Körper spielt im
> folgenden keine Rolle), und Du willst die zugehörige Rekursionsgleichung
> finden.
Im Prinzip schon, da die (binären) Koeffizienten der Rekursionsgleichung
denen des Generatorpolynoms entsprechen.
> Wir nehmen an, dass die Rekursionsgleichung
> s_{k+n} = a_{n-1} * s_{k+n-1} + ... + a_0 * s_k
> lautet. [...]
> Wenn das Gleichungssystem lösbar ist, dann muss die Determinante davon
> Null sein, und (-1,a_{n-1},...,a_0) liegt im Kern der Matrix.
Auch wenn du schon auf beliebige Räume verallgemeinert hast, für den
betrachteten Fall GF(2) würde das Kernelement mit a_n = 1 (->
Generatorpolynom) hier (1,a_{n-1},...,a_0) ergeben...
Zu deinem vorgeschlagenem Algorithmus noch einige Fragen:
> Algorithmus:
> ============
> (1) Setze n=1.
Im Prinzip ist zwar auch die Ordnung n bzw. die Periode m=2^n -1
bekannt, aber für eine Verallgemeinerung bzw. eine Suche von n ist das
natürlich auch gut zu gebrauchen.
> (2) Erstelle die (n+1)x(n+1)-Matrix A mit den Einträgen s_{n+i-j}.
> (3) Falls det(A)!=0, erhöhe n um 1 und zurück zu (2).
> (4) Bestimme das Kernelement (-1,a_{n-1},...,a_0). [Siehe Bemerkung unten.]
Hier ebenso noch eine dumme Frage - wie bestimme ich det(A) und kern(A)
im GF(2)?! Also mit den Rechenvorschriften 1+1=0, etc.?
Bzw. was sind hierzu die Stichwörter für weitere Literatur/Recherche?
Entweder suche ich nach den falschen Begriffen oder das scheint kein
triviales Problem zu sein :-)
> Um zu überprüfen, ob die gefundene Rekrusionsgleichung eine MLS liefert,
> muss man nur testen, ob das Polynom irreduzibel ist. Das steht aber auch
> in dem von Dir zitierten Wikipedia-Artikel.
Ja, wenn man die Koeffienten hat, ist es ein relativ überschaubares
<Problem.
Danke & Gruß,
Jan
Jan Fricke
> Zu deinem vorgeschlagenem Algorithmus noch einige Fragen:
>
>> Algorithmus:
>> ============
>> (1) Setze n=1.
>
> Im Prinzip ist zwar auch die Ordnung n bzw. die Periode m=2^n -1
> bekannt, aber für eine Verallgemeinerung bzw. eine Suche von n ist das
> natürlich auch gut zu gebrauchen.
sequentiell herein kommen. Wenn n bekannt ist, dann vereinfacht sich das
ganze sogar noch. Dann bleibt tatsächlich nur noch:
>> (2) Erstelle die (n+1)x(n+1)-Matrix A mit den Einträgen s_{n+i-j}.
>> (4) Bestimme das Kernelement (-1,a_{n-1},...,a_0).
Die Eindeutigkeit des Kerns ergibt sich dann automatisch.
> Hier ebenso noch eine dumme Frage - wie bestimme ich det(A) und kern(A)
> im GF(2)?! Also mit den Rechenvorschriften 1+1=0, etc.?
Genau! Aus "+" und "-" wird "xor", aus "*" wird "and".
Viele Grüße Jan