Rechnernetze

Fehlerwahrscheinlichkeiten

Wir gehen im folgenden davon aus, dass die Daten binär kodiert sind. Dieses trifft zumindest im Bereich der lokalen Netze stets zu. Im Bereich der öffentlichen Netze müssen evtl. zusätzlich weitere Überlegungen angestellt werden. Die Nutzdatenlänge sei k Bits, und die Übertragungsdatenlänge sei n Bits. Die Differenz r=n-k ist somit die Länge der Prüfinformation; die Redundanz ist .

Um die Qualität eines Fehlererkennungsverfahrens beurteilen zu können, muss zunächst die Wahrscheinlichkeit ps berechnet werden, dass in einem Block der Länge n bei einer Bitfehlerwahrscheinlichkeit von p genau s fehlerhafte Bits auftreten. Sind die Fehler unabhängig, so ist entsprechend der Binomialverteilung

In der folgenden Tabelle werden für verschiedene Blocklängen n und verschiedene Bitfehlerwahrscheinlichkeiten p die Wahrscheinlichkeiten angegeben, dass in einem Block genau s Fehler auftreten:

Die beige unterlegten Werte geben jeweils die Wahrscheinlichkeit an, dass mindestens ein Fehler in einem entsprechenden Block auftritt. So enthält ein Block mit 100 Bits und einer Bitfehlerwahrscheinlichkeit von 0,001 (0.1 %) mit einer Wahrscheinlichkeit von 9.5 % mindestens einen Fehler; d.h. dass jeder zehnte bis elfte Block (im Mittel) einen Fehler enthält. Diese Zahl ist natürlich viel zu hoch. Für realistischere Blockgrößen wie beim Ethernet (bis zu 12000 Bits) erhält man bei einer Bitfehlerwahrscheinlichkeit von 10-5, dass jeder 8. Block einen Fehler enthält. Würde man keine Maßnahmen ergreifen, so würde dieses nach einigen Übertragungen zu ausschließlich fehlerbehaftete Dateien führen, was natürlich nicht hinzunehmen ist.

Das folgende Diagramm stellt dieses noch einmal grafisch dar. Man kann aus diesem Diagramm und aus einer gegebenen Fehlerwahrscheinlichkeit je Bit auf die Blocklänge schließen, um eine gewisse Fehlererkennungswahrscheinlichkeit zu finden.  

Beispielsweise ist bei einer Fehlerwahrscheinlichkeit für einen Bitfehler von 10-8 und einer gewünschten Wahrscheinlichkeit, einen Bitfehler zu übersehen, von 10-18 eine Blocklänge von etwa 128 Bits zulässig, wenn nur jeweils ein Bitfehler erkannt werden kann. Können ein oder zwei Bitfehler erkannt werden, so können die Blöcke eine Länge von ca. 1000 Bits haben. Können auch drei, aber nicht mit Sicherheit vier Bitfehler erkannt werden, so liegt die Grenze bei 12000 Bits. 

Zwei weitere Begriffe sind hier von Interesse. Die mittlere Zeit, die nach einem Fehler vergeht bis der nächste Fehler auftritt, wird als mittlere Zeit zwischen zwei Fehlern bezeichnet (mean time between error, MTBE). Im obigen Beispiel des Ethernets könnte man etwa folgendermaßen schließen: werden Blöcke mit 15000 Bits Länge übertragen, so könnten bei 10 MBit/s etwa 667 Blöcke je Sekunde übertragen werden. Wäre davon jeder 8. falsch, so wäre die mittlere Zeit zwischen zwei Fehlern ca. 12 ms. Wenn in jeder Sekunde über 80 Fehler auftreten, so ist das sicherlich nicht hinnehmbar.

Es müssen daher Maßnahmen zur Entdeckung solcher Fehler getroffen werden. Die mittlere Zeit, die nach einem unentdeckten Fehler vergeht bis der nächste unentdeckte Fehler auftritt, wird als mittlere Zeit zwischen zwei unentdeckten Fehlern bezeichnet (mean time between undiscovered error, MTBU). Die folgende Tabelle gibt die Wahrscheinlichkeiten an, dass in einem Block bis zu s Fehler auftreten.

Könnte man beispielsweise statt keinen Fehler jeden Block mit einem, zwei oder drei Bitfehlern entdecken, so wäre die Wahrscheinlichkeit eines unentdeckten fehlerhaften Ethernetblocks maximaler Länge 5,6·10-7. Also wäre die Zeit, die zwischen zwei unentdeckten fehlerhaften Blöcke vergeht, ca. 10.000 Sekunden oder 3 Stunden. Das ist zwar auch noch eine beachtliche Fehlerchance, aber es zeigt sich, dass bereits durch die Entdeckung auch nur einiger Fehlertypen die Qualität des Systems erheblich verbessert werden kann. Offenbar ergibt sich eine weitere Verbesserung durch Verringerung der Bitfehlerwahrscheinlichkeiten und durch Verkleinerung der Blöcke.