Analyseverfahren spart Rechenzeit
Polynome schneller auf Primitivität prüfen
Fortsetzung des Artikels von Teil 1
Eigenschaften von LFSR
Bei der Festlegung der Konvention sind zwei neue Begriffe eingeführt worden: die Transformationsmatrix Tm und die Rückkopplung Rk. Beide sind eng miteinander verknüpft. Es gibt viele Möglichkeiten den nächsten Zustand des Schieberegisters aus dem aktuellen Zustand zu bestimmen. Die Nutzung einer Matrix hierfür bietet Vorteile. Die gesuchten Transformationsmatrizen Tm-F und Tm-G können Schritt für Schritt aus einer zyklischen Matrix MZ_L abgeleitet werden, die eine 1-bit-Linksverschiebung bewirkt. Solch eine r x r zyklische Matrix besteht aus einer (r – 1) x (r - 1) Einheitsmatrix E(r - 1), die Links und nach unten mit einer Spalte bzw. Zeile erweitert wird, wie es durch die Gleichung 6 dargestellt wird.
Charakteristisch für die betrachtete zyklische Matrix ist, dass die einzige 1 in der ersten Spalte ganz unten bzw. in der letzten Zeile an der ersten Stelle steht. Es lässt sich leicht verifizieren, dass durch das Tauschen der letzten Zeile mit einem Zeilenvektor [gr gr-1 ... g2 g1] mit r Koeffizienten, die Transformationsmatrix Tm-F gewonnen werden kann. Die Transformationsmatrix Tm-G lässt sich durch den Tausch der ersten Spalte mit dem Spaltenvektor [gr-1 gr-2 ... g1 g0]T gewinnen. Diese zwei Vektoren sind nichts anders als die in der Konvention vorgestellten Rückkopplungen Rk für die Implementierung F-LFSR und G-LFSR.
Jobangebote+ passend zum Thema
Wird die Signatur eines Datenblocks (Nutzdaten) der Länge k bei einer F-LFSR Implementierung generiert, so steht nach k Takten im Schieberegister die Signatur des Datenblocks. Um daraus ein Codewort zu bilden, ist eine Manipulation des Inhalts des Schieberegisters erforderlich. Hierzu werden die nächsten r bit seriell im Dateneingang eingeschoben (Bild 4). Das i-te Bit besteht aus dem Skalarprodukt der Rückkopplung mit dem aktuellen Zustand des Schieberegisters vor der Schiebung für i = 1 bis r. Zu beachten ist, dass es sich bei der Bildung des Skalarprodukts um eine Modulo-Zwei-Addition handelt. Wie diese Manipulation abläuft verdeutlicht Bild 4. Es werden vier Datenbits (1111) in das F-LFSR eingeschoben, das mit dem Polynom 3-ten Grades dh (binär: 1101) gebildet wurde. Die Signatur nach vier Takten beträgt: 101. Das Skalarprodukt des aktuellen Inhalts (101) des Schieberegisters mit der Rückkopplung 110 beträgt 1. Die weiteren zwei Bits, die eingeschoben werden, haben ebenfalls den Wert 1. Nach sieben Takten beträgt der Inhalt des Schieberegisters dreimal 0 (000), da es sich bei den sieben Bits um ein Codewort handelt: dreimal 1, die tatsächliche Signatur, und viermal 1, die Nutzdaten.
Die beiden Verfahren (G-LFSR und F-LFSR) sind vollkommen kompatibel zueinander. Dies bedeutet, dass die Grundeigenschaften, wie z.B. Zykluslänge, Verlauf der Hammingdistanz, die einzelnen Codewörter, Gewichtsverteilung der Codewörter, Restfehlerwahrscheinlichkeit usw., die für eine G-LFSR-Implementierung in [1] vorgestellt wurden, gelten uneingeschränkt auch für eine F-LFSR-Implementierung. Wenn Unterschiede festgestellt werden, so sind sie struktureller Natur, wie z.B. die Zusammensetzung der Inhalte und Zustände in einem Zyklus, wobei die Zykluslänge in beiden Fällen den gleichen Wert annimmt. Beide Verfahren ergänzen sich gegenseitig und sind uneingeschränkt austauschbar. In der Tabelle 1 sind die Vor- und Nachteile beider Verfahren zusammengefasst.
| G-LFSR-Implementierung | F-LFSR-Implementierung | |
|---|---|---|
| Vorteile | Die ermittelte Signatur kann nach n Takten (k Datenbits + r Prüfbits) ohne Modifikation weiter genutzt werden. Wenn die Daten am Ausgang verknüpft werden, steht die Signatur sofort nach k Takten zur Verfügung. Diese Variante von G-LFSR wurde hier nicht erörtert, siehe hierzu [1]. | Einfache Realisierung und bietet im Layout Vorteile bei der Chip-Herstellung. Leicht verständlich und einfacher zu analysieren, der nächste Zustand lässt sich sogar im Kopf berechnen. |
| Nachteile | Komplexerer Aufbau, benötigt mehr Chipfläche. | Die nach k Takten erzeugte Signatur muss modifiziert werden, damit die Signatur vom gesamten Datenblock der Länge n (inklusive Prüfbits) null wird. Dies ist aber ohne Zeitverlust durchführbar. |
Tabelle 1. Vor- und Nachteile der beiden Verfahren G-LFSR und F-LFSR.
- Polynome schneller auf Primitivität prüfen
- Eigenschaften von LFSR
- Primitive Polynome und ihre Bestimmung
Lesen Sie mehr zum Thema
Das könnte Sie auch interessieren
