Generatorpolynom zu Sequenz finden

16/01/2009 - 09:43 von Jan Reimes | Report spam
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?

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

[1] http://en.wikipedia.org/wiki/Maximu...h_sequence
 

Lesen sie die antworten

#1 Jan Fricke
17/01/2009 - 11:56 | Warnen spam
Jan Reimes wrote:
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

Ähnliche fragen