Rechnernetze
Home Nach oben

Definition und Eigenschaften von Bitfiltern

Um die folgende Analyse knapp halten zu können, werden nur die wichtigsten Definitionen und Ergebnisse angegeben, während die zugehörigen Beweise nur skizziert werden.

Definition von Bitfiltern

Ein Bitfilter dient dem Herausfiltern gewisser Stellen aus einer Folge von Bits. Diese Stellen können selbst durch eine Bitfolge beschrieben werden, welche an den herauszufilternden Stellen eine '1' stehen und sonst eine '0' hat. Daher kann ein Bitfilter sowohl als Bitfolge als auch in Form eines Polynoms geschrieben werden.

Operatoren für Bitfilter

Ein Bitfilter ist eine (im Prinzip unbeschränkte) Folge von Bits, die wir als Polynom mit F(X) bezeichnen. Soll F(X) aus dem Polynom V(X) Bits herausfiltern, so definieren wir als Ergebnis genau das Polynom jener Terme Xs, die sowohl in V(X) als auch in F(X) vorkommen. Wir können daher das Herausfiltern auch als Verknüpfung von F(X) und V(X) schreiben mit dem Verknüpfungssymbol '&':

V(X) = X9 + X7 + X5 + X4 + X3 + 1
F(X) = X8 + X7 + X6 + X4 + X2 + X
V(X)&F(X) = X7 + X4

Es handelt sich also logisch-algebraisch gesehen um eine bitweise Konjunktion. Man zeigt leicht, dass der Operator '&' kommutativ, assoziativ und distributiv über '+' ist. Als Bitfolge dargestellt würden wir für das obige Beispiel folgendermaßen schreiben:

 

X9

X8

X7

X6

X5

X4

X3

X2

X

1

V

=

1

0

1

0

1

1

1

0

0

1

F

=

0

1

1

1

0

1

0

1

1

0

V&F

=

0

0

1

0

0

1

0

0

0

0

Gerade Bitfilter

Wir betrachten jetzt nur noch solche Bitfilter F(X), die bezogen auf ein Generatorpolynom G(X) der Bedingung genügen

Für alle Zahlen s=0 gilt:   |(G(X)·Xs) & F(X)|  ist gerade.

Hier beschreibe |V(X)| die Anzahl von Termen in V(X), bzw. die Anzahl von 1-Bits in dem Vektor v. Stattdessen können wir auch schreiben:

Für alle Zahlen s>0 gilt:   (G(X)·Xs) & F(X)  |X=1  =  0

da die Summe einer geraden Anzahl von '1' den Wert null ergibt. In Vektorschreibweise bedeutet dieses, dass bei jeder Lage der Generatorbitfolge im Vergleich zum Bitfilter die Konjunktion beider Vektoren eine gerade Anzahl gesetzter Bits ergibt. Wir nennen dieses auch einen geraden Bitfilter (in Bezug auf das Generatorpolynom G(X)) oder kürzer gerader Bitfilter zu G(X) oder - da wir nur noch gerade Bitfilter betrachten - auch einfach nur Bitfilter

Wichtige Eigenschaften gerader Bitfilter

Jeder gerade Bitfilter zu G(X) hat jetzt die folgende wichtige Eigenschaft: Ist Ei(X) ein Polynom, welches aus E(X) durch Subtraktion von G(X)·Xs für geeignete Exponenten s entsteht, so hat Ei(X)&F(X) die gleiche Parität wie E(X)&F(X). Denn dies gilt nach Voraussetzung für E0(X)=E(X). Gilt dieses für Ei(X), so folgt wegen Ei+1(X) = Ei(X) + G(X)·Xu

Ei+1(X)&F(X)|X=1  =  (Ei(X) + G(X)·Xu) & F(X)  |X=1
= Ei(X)&F(X) |X=1 + (G(X)·Xu) & F(X) |X=1
= Ei(X)&F(X) |X=1

Gibt es somit zu einem Generatorpolynom G(X) einen Bitfilter F(X), der aus einem Fehlerpolynom E(X) eine ungerade Anzahl von Termen filtert (E(X)&F(X)|X=1=1), so lässt E(X)/G(X) einen Rest, d.h. es wird ein Fehler angezeigt. Somit genügt es, die Bitfilter zu einem Generatorpolynom zu betrachten, um dessen Eigenschaften zur Fehlererkennung studieren zu können.

Konstruktion gerader Bitfilter

Aus einer Folge von r Bits an beliebiger Stelle lässt sich genau ein gerader Bitfilter zu G(X) eindeutig bestimmen, da jedes Generatorpolynom die Terme 1 und Xr enthält; denn sind die r Stellen: Xu…Xu+r-1 aus F(X) festgelegt, so ergeben sich für die Stellen Xu-1 und Xu+r die Bedingungen:

F(X)&Xu-1  |X=1   =   (G(X)·Xu-1)&(F(X)&(Xu-1+…+Xu+r-2))  |X=1
F(X)&Xu+r  |X=1   =   (G(X)·Xu)&(F(X)&(Xu+…+Xu+r-1))  |X=1

Daher gibt es zu einem Generatorpolynom vom Grad r genau 2r verschiedene Bitfilter. Konstruiert man einen Bitfilter aus einer Folge von r Bits, so muss sich wegen der Eindeutigkeit diese Bitfolge von r Bits nach spätestens 2r Bits wiederholen. Somit enthält jeder Bitfilter genau einen Zyklus einer bestimmten Länge p, die wir als Periode bezeichnen. Durch diesen Zyklus werden offenbar p verschiedene Bitfilter bestimmt, die durch zyklisches Verschieben auseinander hervorgehen. Solche Bitfilter werden kongruent genannt. Enthalten zwei Bitfilter keine gleichen Bitfolgen, so heißen sie disjunkt.

Spezielle gerade Bitfilter

Das Polynom F(X)=0 ist offenbar für jedes Generatorpolynom ein gerader Bitfilter zu jedem G(X). Hat G(X) eine gerade Anzahl von Termen, so ist offenbar F(X)=1+X+X2+.. (jeder Term ist vorhanden) ebenfalls ein gerader Bitfilter zu diesem G(X), wie man leicht zeigt. Da dieser Bitfilter trivialer Weise aus jedem Fehlerpolynom mit ungerader Anzahl von Bits eine ungerade Anzahl von Bits ausfiltert, werden bei solchen Generatorpolynomen alle Fehler mit einer ungeraden Anzahl von fehlerhaften Bits erkannt.

Fehlerbursts

Da es zu jeder Bitfolge der Länge r an jeder Stelle genau einen Bitfilter gibt, kann ein Bitfilter stets so gewählt werden, dass er aus einem Fehlerburst, der nicht länger als r ist, eine ungerade Anzahl von Bits ausfiltert. Damit werden also alle Fehlerburst bis zur Länge r erkannt.

Ein Fehlerburst der Länge r+1 wird nicht erkannt, wenn E(X)=G(X)·Xu für ein geeignetes u ist, da dann E(X)/G(X)=G(X)·Xu/G(X)=Xu keinen Rest lässt. Alle anderen Fehlerbursts der Länge r+1 werden jedoch erkannt. Enthält E(X) nämlich einen Term Xw, der nicht in Xu·G(X) liegt, so definiert Xu·(Xr+Xw+1) einen Bitfilter zu G(X), welcher eine ungerade Anzahl von Termen aus E(X) herausfiltert. Enthält E(X) nur Terme, die auch in Xu·G(X) liegen, so liegt ein Term Xw von Xu·G(X) mit Sicherheit nicht in E(X), da E(X) ungleich Xu·G(X) angenommen ist. Dann definiert Xu·(Xr+1) eine Bitfolge der Länge r+1 (an der Stelle Xu+r,...Xu=0…010…01), welche einen Bitfilter zu G(X) definiert, der nur eine ungerade Anzahl von Termen aus E(X) ausfiltert (nämlich Xu). Von den 2r+1 möglichen Bitfehlern werden somit 2r+1–1 erkannt, d.h. die Wahrscheinlichkeit, einen Fehlerburst der Länge r+1 nicht zu erkennen, ist 1/2r+1, wenn alle Bitfehler gleichwahrscheinlich sind.

2-Bit-Fehler

Wir zeigen jetzt, dass von den 2-Bit-Fehlern alle erkannt werden, bis auf jene, die in Abständen zueinander liegen, die ein Vielfaches der Perioden aller Bitfilter sind. Ist nämlich E(X) = Xu+Xw, wobei u-w nicht durch die Periode p zumindest eines geraden Bitfilters zu G(X) teilbar ist, so gibt es für diesen Bitfilter mindestens einen kongruenten Bitfilter F(X), der genau einen der beiden Terme Xu+Xw enthält, den anderen jedoch nicht. Daher enthält F(X)&E(X) genau einen Term, also eine ungerade Anzahl, so dass dieser Fehler erkannt wird.

Zusammenfassung

Mit diesen Ergebnissen sollen unsere Überlegungen zu Bitfiltern abgeschlossen werden. Man beachte, dass es zu einem Generatorpolynom Bitfilter sehr unterschiedlicher Länge geben kann, so dass für solche Fälle die obigen Überlegungen noch verfeinert werden müssten.

Wir fassen daher die Ergebnisse dieses Abschnitts in einem Satz zusammen.

Satz

Jedes Generatorpolynom erkennt sämtliche Fehler, bei denen genau ein Bit falsch ist.
Jedes Generatorpolynom mit gerader Anzahl von Termen erkennt alle Fehler mit einer ungeraden Anzahl fehlerhafter Bits.
Jedes Generatorpolynom vom Grad r erkennt jeden Fehlerburst, dessen Länge nicht größer als r ist; und von jedem Fehlerburst der Länge r+1 erkennt es alle Fehler bis auf einen.
Jedes Generatorpolynom vom Grad r erkennt sämtliche 2-Bit-Fehler, die nicht in einem Vielfachen des Periodenabstands aller Generatorbitfilter zu G(X) liegen.