 |
|
|
|
|
||||||||
 |
||||||||||||
|
||||||||||||
 |
||||||||||||
|
|
|
|
||
Erhöhung der Zuverlässigkeit von Rechnersystemen (Teil 2 von 4) Im ersten Teil der Serie wurde gezeigt, daß die Zuverlässigkeit von Systemen sowohl durch
Fehlervermeidung als auch durch Fehlertoleranz erhöht werden kann. Fehlertoleranz setzt zuverlässige Fehlererkennungsmethoden voraus. Eine effektive Methode zur Fehlererkennung stellt die Verwendung redundanter Codes
dar. Während im ersten Teil die nötigen Grundbegriffe erläutert wurden, sollen im folgenden einige Codierverfahren genauer betrachtet werden. Von Klaus Eppele Paritätsprüfung Ein in der Datenverarbeitung häufig angewendetes Verfahren erhält man, indem man ein m-stelliges Nachrichtenwort um ein Paritätsbit erweitert. Bei ungerader Parität ist der
Wert des Paritätsbits so zu wählen, daß die Zahl der Einsen im erweiterten Codewort ungerade ist, während bei gerader Parität das Datenwort auf eine gerade Anzahl von Einsen ergänzt wird. Durch Hinzufügen des
Paritätsbits unterscheiden sich zwei gültige Codewörter um mindestens zwei Binärstellen voneinander. Der Hamming-Abstand beträgt also d=2, so daß sich ein Übertragungsfehler in einem Bit des Codeworts sicher erkennen
läßt. Weiterhin ist jede ungerade Anzahl von Bitfehlern erkennbar. Ungerade Parität bietet gegenüber gerader Parität den Vorteil, daß erkannt wird, wenn alle Bits eines Datenwortes zu Nullen oder bei einem Datenwort mit
einer geraden Stellenanzahl zu Einsen verfälscht wurden. Paritätscodes sind linear separierbar. Die En- bzw. Decodierung ist deshalb einfach durchzuführen, was eine direkte Fehlererkennung begünstigt. Vor allem bei
der seriellen Übertragung von Daten kann der Codiervorgang einfach durch eine modulo-2 Addition mittels eines XOR-Gatters erfolgen. Bei paralleler Übertragung besteht der Paritätsgenerator meist aus einem Baum von
XOR-Gattern mit je zwei Eingängen der Tiefe /ld(m+1)/. Werden sehr lange Datenwörter mit einem Paritätsbit gesichert, ergibt sich deshalb neben der schlechteren Fehlerüberdeckung eine größere Verzögerungszeit bei der
Codierung, da mit der Anzahl der Bits pro Datenwort auch die Tiefe des XOR-Baums zunimmt. Außerdem ist in der Regel bei paralleler Übertragung eine zusätzliche Leitung zur Übertragung des Paritätsbit nötig. Hier ist zu
prüfen, ob bereits im System vorhandene Redundanz für diesen Zweck ausgenutzt werden kann. Beispielsweise wird ein LSI-11-Netzwerk mittels eines parallelen Busses realisiert, bei dem drei Leitungen für die Übertragung
des Operationscodes reserviert sind. Der Operationscode für öDatum lesenö lautet 110, für „Datum schreiben“ 010. Zwei Operationscodes (111 und 011) sind keine Bedeutung zugeordnet, so daß bei Datenübertragungen das
dritte Bit des Operationscodes zur Übermittlung der Parität verwendet werden kann. Da etwa 90 Prozent der Busoperationen aus Datentransaktionen bestehen, ist durch diese Methode für 90 Prozent der Busaktivitäten eine
Fehlererkennung vorhanden, ohne daß eine weitere Busleitung benötigt wird. Um einen für bestimmte Anwendungen optimalen Paritätscode zu erhalten, wurden mehrere Varianten dieser Methode entwickelt. So kennt man neben
der oben erwähnten Bit-pro-Wort Sicherung auch eine Bit-pro-Byte Sicherung oder eine verflochtene Paritätssicherung. Werden ganze Blocks von Daten übertragen, bietet es sich an, nicht nur die einzelnen Wörter mit
einer Parität zu sichern (Quersicherung, engl. vertical redundancy check), sondern auch für alle Bits der gleichen Wertigkeit innerhalb einer Folge von Wörtern ein Paritätsbit zu generieren (Längssicherung, engl.
longitudinal recundancy check). Die Gesamtheit aller Längssicherungen eines Datenblocks ergibt ein weiteres Zeichen (Block Check Character), das gesondert übertragen werden muß. Eine Blocksicherung erfordert so neben
struktureller Redundanz zur Übertragung der Querparität auch noch eine zeitliche Redundanz zur Übertragung der zusätzlichen Blocksicherung in Form des Block Check Characters. Die gleichzeitige Anwendung von Zeichen- und
Blockparität wird auch als Kreuzsicherung bezeichnet. Dabei muß vereinbart werden, wie das Paritätsbit des Block Check Characters gebildet werden soll, entweder als Quer- oder als Längsparität (siehe Beispiel).
Beispiel: Kreuzsicherung der Zahl 12345. Da sich bei der Kreuzsicherung ein Bitfehler sowohl auf die Quer- als auch auf die Längsparität auswirkt, wird ein einzelner Bitfehler nicht nur erkannt - er kann auch exakt im
Datenblock lokalisiert werden. m-von-n-Codes Ein m-von-n-Code besteht aus n-bit langen Wörtern, die genau m Einsen enthalten. Soll die Prüfinformation separiert werden, dann erfordert dieser Code viel
Redundanz. Werden z.B. alle der 2k möglichen k-Bit langen Wörter durch einen m-von-n-Code in der Form gesichert, daß die ursprüngliche Information und die Prüfbits getrennt vorliegen, so sind an jedes Wort k weitere
Stellen anzufügen. Für k=4 ergeben sich 24=16 zu sichernde Codewörter, denen man je weitere 4 Bit an Prüfinformation anfügen muß, wenn der gesicherte Code separierbar sein soll. Der entstehende 4-von-8-Code enthält (8
über 4) = 70 gültige Codewörter, also mehr als viermal so viele wie nötig. Ein 3-von-6-Code besteht aus 20 gültigen Codewörtern und reicht zur Sicherung von 16 Datenwörtern vollkommen aus. Die Ersparnis an Redundanz muß
bei Anwendung des 3-von-6-Codes allerdings wegen der nicht vorhandenen Separierbarkeit mit einem erhöhtem Aufwand bei der Codierung erkauft werden. Neben der Einsparung an Redundanz bietet der 3-von-6-Code für dieses
Beispiel den Vorteil, daß er nur vier (20 gültige minus 16 benutzte) unbenutzte Codewörter enthält, die nicht als falsch erkannt werden können. Dagegen können bei Anwendung des 4-von-8-Code 54 (70 minus 16) unbenutzte
Codewörter eine Fehlererkennungsschaltung passieren, ohne als falsch erkannt zu werden. Müssen nicht alle der möglichen 2k Codewörter gesichert werden, so kann man unter Umständen eine noch weniger redundante Codierung
finden. Beispiel: 0011, 0101, 0110, 1001, 1010, 1100, Gültige Codewörter eines 2-von-4-Codes Zyklische Codes Ein Code heißt zyklisch, wenn jede zyklische Verschiebung der Stellen eines gültigen Codewörters
wieder ein gültiges Codewort ergibt. Ist beispielsweise X=(x1,x2,...,xn) ein gültiges Codewort, so sind auch (xn,x1,...,xn-1), (xn-1,xn,x1,...,xn-2),..., (x2,x3,...,xn,x1) gültige Codewörter.
Die Codewortbildung läuft folgendermaßen ab: An ein beliebiges m-stelliges Nachrichtenwort werden zuerst k binäre Nullstellen angehängt. Die einzelnen Binärstellen des Nachrichtenworts können als Koeffizienten eines
n-stelligen Polynoms (n=m+k) betrachtet werden. Dieses wird durch ein (k+1)-stelliges Generatorpolynom modulo-2 dividiert. Dabei entsteht ein Restpolynom vom Grad (k-1) mit k Koeffizienten. Zieht man dieses Restpolynom
vom Dividenden ab, dann ergibt sich ein neues Polynom, das ohne Rest durch das Generatorpolynom teilbar ist und ein Codewort darstellt. Da Subtraktion und Addition der modulo-2-Rechnung gleichbedeutend sind, kann man
das bei der Division entstandene Restpolynom dem Dividendenpolynom auch hinzuaddieren, um ein gültiges Codewort zu erhalten. Die Addition des Restpolynoms entspricht dem Anfügen der k Prüfstellen (des Restpolynoms) an
das zu codierende m-stellige Nachrichtenwort. Beispiel: Nachrichtenwort: 1001 (m=4) Man erhält also wieder einen separierbaren Code. Der Empfänger muß, um Übertragungsfehler erkennen zu können, das erhaltene n-stellige Nachrichtenwort ebenfalls durch das
Generatorpolynom modulo-2 dividieren. Bleibt bei der Division kein Rest übrig wird das empfangene Wort als fehlerfrei gewertet. Die Realisierung der zyklischen Codierung als Divisionsvorgang erfolgt technisch mit
Hilfe linear rückgekoppelter Schieberegister. Ein Schieberegister ist eine Anordnung von k hintereinander geschalteteten binären Speicherzellen. In diese wird die Information schrittweise eingelesen. Die Division durch
das Generatorpolynom wird hierbei durch entsprechende Rückkopplungen realisiert. Bild 1 zeigt schematisch ein über XOR-Gatter rückgekoppeltes Schieberegister das eine Division durch das Generatorpolynom G:=x3+x+1
ausführt. Bild 1: Über Exklusiv-Oder rückgekoppeltes Schieberegister Die Wahrscheinlichkeit einen Fehler zu entdecken ist bei gleichwahrscheinlichen Nachrichtenworten nur von der Registerlänge abhängig. Die Tabelle
in Bild 2 zeigt die Abhängigkeit der Wahrscheinlichkeit einen Fehler zu entdecken von der Registerlänge.
Registerlänge : Wahrscheinlichkeit Bild 2: Zusammenhang zwischen
Registerlänge in Bit und Fehlererkennungswahrscheinlichkeit Zyklische Codes eignen sich vor allem für serielle Übertragungen. Die für eine geforderte Fehlererkennungswahrscheinlichkeit nötige relative Redundanz ist
gering (siehe Bild 2) und die Codierung einfach zu realisieren. Bei Verwendung zyklischer Codes können alle Einfachfehler, alle Bündelfehler bis zur Länge k+1 sowie verschiedene vom Generatorpolynom abhängige
Fehlermuster erkannt werden. Praktische Anwendungen für zyklische Codes finden sich im Abramson-Code, Fire-Code oder BCH-Code. Prüfsummen Ein Fehlererkennungsverfahren, das wenig Redundanz benötigt, ist die
Anwendung von Prüfsummen. Ein Block von s Datenwörtern wird modulo-n aufaddiert, wobei n beliebig gewählt werden kann. Die s Datenwörter bilden zusammen mit der Prüfsumme ein Codewort in einem linear separierbaren Code.
Die Länge der Prüfsumme ist gewöhnlich beschränkt und hat meist die Stellenanzahl m eines normalen Datenworts, damit nicht etwa bei einer parallelen Übertragung zusätzliche Leitungen benötigt werden. Die Beschränkung
der Länge der Prüfsumme hat jedoch den Nachteil, daß Fehler in den höherwertigen Bits der Datenwörter schlechter erkannt werden, als Fehler der niederwertigen Bits. Der Grund dafür ist, daß Verfälschungen einzelner Bits
entweder Auswirkungen auf das gleichwertige Bit der Prüfsumme oder auf den Übertrag haben. Da aber der Übertrag der höherwertigen Stellen nicht betrachtet wird, sind diese nicht so gut gesichert. Damit die
Fehlererkennung für alle Stellen gleich gut ist, muß man eine Prüfsummenlänge von (m+k) Stellen mit s<2k vorsehen. Die Fehlerüberdeckung ist somit direkt eine Funktion von Blocklänge s und Prüfsummenlänge (m+k).
Ist bei einer Datenübertragung eine dedizierte Hardware zur Summenbildung vorhanden, so bleibt trotz der zusätzlichen Rechenarbeit die Leistungsfähigkeit des Systems erhalten und eine direkte Fehlererkennung ist
möglich. Wird eine Störung erkannt, so muß der gesamte Datenblock erneut übertragen werden, der von der entsprechenden Prüfsumme überdeckt wird. Dies stellt gegenüber den Fehlererkennungsmethoden, die jedes Datenwort
für sich auf Korrektheit überprüfen, einen Nachteil dar. Prüfsummen können auch zur Fehlererkennung in Speichern verwendet werden. Hier hat das Verfahren jedoch den Nachteil, daß immer, wenn ein Wort im Speicher
geändert werden soll, alle zum Block gehörigen Wörter gelesen und zu einer neuen Prüfsumme aufaddiert werden müssen. Es ist darauf zu achten, daß die Prüfsumme getrennt vom zugehörigen Datenblock gespeichert wird, damit
schwerwiegende Fehler nicht gleichzeitig die Datenwörter und die Prüfsumme verändern können. Soll mittels Prüfsummen der korrekte Ablauf eines Programms überprüft werden, so kann man folgendermaßen vorgehen. Man
addiert während der Abarbeitung eines Programms die als Binärwörter kodierten, jeweils aktiven Instruktionen des Programms in einem Addierakkumulator zu einer Testsumme auf und vergleicht in bestimmten Programmpunkten
die erhaltene Ist-Summe mit einem bereits im voraus berechneten Sollwert. Wenn der Ist-Wert vom Soll-Wert abweicht, dann wird ein Fehler angezeigt. Bei der Berechnung des Sollwerts müssen Programmschleifen und
Programmverzweigungen berücksichtigt werden. Arithmetische Codes Ein arithmetischer Code A hat die Eigenschaft, daß für alle Datenwörter b und c und für gewisse Operationen ö*ö, wie Addition oder
Multiplikation, der Zusammenhang A(b*c)=A(b)*A(c) gilt. Die Codebildung ist also abgeschlossen gegenüber bestimmter arithmetischer Operationen. Dabei ist A(x) das arithmetische Codewort zum Datenwort x. Diese
Codierung ermöglicht neben der Erkennung und Korrektur von Fehlern auch die Überprüfung der Ergebnisse bestimmter arithmetischer Operationen, die von Funktionseinheiten des Rechensytems ausgeführt werden. Ein
einfacher Vertreter dieser Codes sind die AN-Codes. Ein Datenwort wird codiert, indem man es mit einer Zahl A multipliziert. Dabei werden, was die Fehlererkennung betrifft, die besten Ergebnisse erreicht, wenn man
A=2a-1 setzt wobei die Länge der Codewörter ein Vielfaches von a ist. Ein Beispiel für einen AN-Code der einen Fehler im Datenwort erkennen kann, ist der 3N-Code. Ein Datenwort der Länge n wird codiert, indem es mit
der Zahl drei multipliziert wird. Die Multiplikation kann von einem (n+1)-Bit-Addierer ausgeführt werden und erweitert das Datenwort um bis zu zwei zusätzliche Bits. Gegenüber einem Paritätscode, der auch genau einen
Fehler erkennen kann, ist also beim 3N-Code ein weiteres Bit nötig. Dieser zusätzliche Aufwand macht sich dann bezahlt, wenn nicht nur eine fehlerfafte Datenübertragung erkannt, sondern auch die korrekte Funktion von
Funktionseinheiten überwacht werden soll. In Teil 3 dieser Serie wird noch ein weiteres algebraisches Verfahren zur Fehlererkennung erläutert. Selbsttaktende Codes Wenn zwei räumlich voneinander getrennte
Komponenten miteinander kommunizieren, müssen ihre Tätigkeiten aufeinander abgestimmt, das heißt synchronisiert werden. Bei synchroner Datenübertragung wird hierfür ein gemeinsamer Takt über eine gesonderte Leitung an
die beteiligten Komponenten geführt. Wegen Ungenauigkeiten im Taktgenerator, unterschiedlichen Laufzeiten, Gatterverzögerungen oder Störungen kann das synchrone Arbeiten beeinträchtigt sein, was eine korrekte
Kommunikation unmöglich macht und zu Fehlersitutationen führt. Um diese Fehler zu vermeiden, werden selbsttaktende Codes eingesetzt. Diese sind so ausgelegt, daß für jedes übertragene Bit ein Signalwechsel bei der
Übertragung erfolgt. So kann sich der Empfänger mit jedem Bit wieder aufs Neue mit dem Sender synchronisieren. Beispiele solcher Codes sind der RZ (return to zero)- und der Manchester-II-Code, die in Bild 3 dargestellt
werden. Bild 3: RZ-Code und Manchester-II-Code Neben diesen fehlervermeidenden Eigenschaften haben diese Codes auch die Fähigkeit, Fehler zu entdecken. Weil beispielsweise beim Manchester-II-Code jeder Wechsel
des Bitwerts im Datenstrom zwei Zustandswechsel des Signals bewirkt, können Störungen sehr gut erkannt werden. Zum Beispiel kann man Ständig-0/1-Fehler einfach erkennen, da auch bei einer Übertragung, die sich über eine
längere Zeit nur aus Nullen oder Einsen zusammensetzt, ein Signalübergang je Datenbit erfolgen muß und ein ständig gleichbleibender Spannungspegel deshalb keine gültige Signalfolge darstellt. Zusammenfassung
In diesem Abschnitt wurden die am weitesten verbreiteten Codierverfahren zur Fehlererkennung besprochen. Die Auswahl des geeigneten Verfahrens bedarf einer genauen Analyse des Rechensystems und der möglichen
Fehlerzustände. Will man einen funktionellen Fehler durch einen geeigneten Code erkennen, so kommt es darauf an, einen solchen Code zu verwenden, bei dem der Abstand d(y,y') zwischen dem korrekten Wert y und dem
gestörten Wert y' möglichst gleich der Anzahl der technischen Einzelfehler ist, die erforderlich sind, um den funktionellen Fehler hervorzurufen. Beeinflussen beispielsweise Einzelfehler nur ein Bit des Resultats, so
ist der Einsatz von Paritätsprüfcodes mit Hamming-Abstand d=2 sinnvoll. Diese Aussage ist abbhängig von den zu erkennenden Fehlern und von der Definition, welche Fehler als Einzelfehler anzusehen sind. Um den
Systembetrieb durch die Fehlererkennungsmaßnahmen nicht unnötig zu belasten, ist es sinnvoll die notwendige En- und Decodierung von einer dedizierten Hardware vornehmen zu lassen, da eine Codierung durch vorhandene
Systemkomponenten oder durch Software in der Regel zu einer Verschlechterung des Systemdurchsatzes führt. Alle Verfahren benötigen für die eigentliche Verarbeitung mehr oder weniger redundante Informationen, was in
jedem Fall erhöhte Kosten mit sich bringt, etwa in Form von zusätzlichen Leitungen oder zusätzlicher Übertragungszeit. Es ist ein Kompromiß zwischen nötigem Aufwand und der verbleibenden Restfehlerwahrscheinlichkeit zu
schließen. Dies gilt auch für die Methoden der Duplizierung, die im nächsten Teil dieser Serie besprochen werden. Literatur
Autor improve Erschienen in Datacom 10/91, Seiten 122 - 126
|
||