Fehlererkennung und -korrektur - Error detection and correction

Um Übertragungsfehler zu beseitigen, die durch die Erdatmosphäre (links) verursacht wurden, wendeten Goddard-Wissenschaftler die Reed-Solomon-Fehlerkorrektur (rechts) an, die häufig bei CDs und DVDs verwendet wird. Typische Fehler sind fehlende Pixel (weiß) und falsche Signale (schwarz). Der weiße Streifen zeigt einen kurzen Zeitraum an, in dem die Übertragung unterbrochen wurde.

In der Informationstheorie und Codierungstheorie mit Anwendungen in der Informatik und Telekommunikation , Fehlererkennung und Korrektur oder Fehlerkontrolle sind Techniken , die ermöglichen , zuverlässige Lieferung von digitalen Daten über unzuverlässige Kommunikationskanäle . Viele Kommunikationskanäle unterliegen Kanalrauschen , und daher können während der Übertragung von der Quelle zu einem Empfänger Fehler eingeführt werden. Fehlererkennungstechniken ermöglichen die Erkennung solcher Fehler, während die Fehlerkorrektur in vielen Fällen die Rekonstruktion der Originaldaten ermöglicht.

Definitionen

Fehlererkennung ist die Erkennung von Fehlern, die durch Rauschen oder andere Beeinträchtigungen während der Übertragung vom Sender zum Empfänger verursacht werden.

Fehlerkorrektur ist die Erkennung von Fehlern und die Rekonstruktion der ursprünglichen, fehlerfreien Daten.

Geschichte

In der klassischen Antike wurden Kopisten der hebräischen Bibel für ihre Arbeit nach der Anzahl der Stiche (Verszeilen) bezahlt . Da die Prosabücher der Bibel kaum in Stichen geschrieben waren, mussten die Kopisten, um den Arbeitsaufwand abzuschätzen, die Buchstaben zählen. Dies trug auch dazu bei, die Genauigkeit bei der Übertragung des Textes bei der Herstellung nachfolgender Kopien sicherzustellen. Zwischen dem 7. und 10. Jahrhundert n. Chr. formalisierte und erweiterte eine Gruppe jüdischer Schreiber dies, um die Numerische Masorah zu schaffen , um eine genaue Wiedergabe des heiligen Textes zu gewährleisten. Es umfasste Zählungen der Anzahl von Wörtern in einer Zeile, einem Abschnitt, einem Buch und einer Gruppe von Büchern, wobei der mittlere Stich eines Buches, Wortverwendungsstatistiken und Kommentare notiert wurden. Die Standards wurden so, dass eine Abweichung auch nur eines einzigen Buchstabens in einer Torarolle als inakzeptabel angesehen wurde. Die Wirksamkeit ihrer Fehlerkorrekturmethode wurde durch die Genauigkeit des Kopierens im Laufe der Jahrhunderte bestätigt, die durch die Entdeckung der Schriftrollen vom Toten Meer in den Jahren 1947-1956 aus der Zeit um 150 v.

Die moderne Entwicklung des Fehlerkorrekturcodes wird gutgeschrieben Richard Hamming 1947. Eine Beschreibung des Hamming Code erschien in Claude Shannon ‚s A Mathematical Theory of Communication und wurde von schnell verallgemeinert Marcel JE Golay .

Einführung

Alle Fehlererkennungs- und -korrekturschemata fügen einer Nachricht eine gewisse Redundanz (dh einige zusätzliche Daten) hinzu, die Empfänger verwenden können, um die Konsistenz der gelieferten Nachricht zu überprüfen und Daten wiederherzustellen, die als beschädigt erkannt wurden. Fehlererkennungs- und -korrekturschemata können entweder systematisch oder nicht-systematisch sein. In einem systematischen Schema sendet der Sender die Originaldaten und fügt eine feste Anzahl von Prüfbits (oder Paritätsdaten ) hinzu, die durch einen deterministischen Algorithmus aus den Datenbits abgeleitet werden . Wenn nur eine Fehlererkennung erforderlich ist, kann ein Empfänger einfach denselben Algorithmus auf die empfangenen Datenbits anwenden und seine Ausgabe mit den empfangenen Prüfbits vergleichen; Stimmen die Werte nicht überein, ist irgendwann während der Übertragung ein Fehler aufgetreten. In einem System, das einen nicht-systematischen Code verwendet, wird die Originalnachricht in eine codierte Nachricht umgewandelt, die die gleichen Informationen trägt und mindestens so viele Bits wie die Originalnachricht hat.

Eine gute Fehlerkontrollleistung erfordert, dass das Schema basierend auf den Eigenschaften des Kommunikationskanals ausgewählt wird. Gängige Kanalmodelle umfassen speicherlose Modelle, bei denen Fehler zufällig und mit einer bestimmten Wahrscheinlichkeit auftreten, und dynamische Modelle, bei denen Fehler hauptsächlich in Bursts auftreten . Folglich können Fehlererkennungs- und Fehlerkorrekturcodes allgemein zwischen Zufallsfehlererkennung/-korrigieren und Burst-Fehlererkennung/-korrigieren unterschieden werden . Einige Codes können auch für eine Mischung aus Zufallsfehlern und Burstfehlern geeignet sein.

Wenn die Kanaleigenschaften nicht bestimmt werden können oder sehr variabel sind, kann ein Fehlererkennungsschema mit einem System zur erneuten Übertragung fehlerhafter Daten kombiniert werden. Dies ist als Automatic Repeat Request (ARQ) bekannt und wird vor allem im Internet verwendet. Ein alternativer Ansatz zur Fehlerkontrolle ist die hybride automatische Wiederholungsanforderung (HARQ), die eine Kombination aus ARQ und Fehlerkorrekturcodierung ist.

Arten der Fehlerkorrektur

Es gibt drei Hauptarten der Fehlerkorrektur.

Automatische Wiederholungsanfrage (ARQ)

Automatic Repeat reQuest (ARQ) ist ein Fehlerkontrollverfahren für die Datenübertragung, das Fehlererkennungscodes, Bestätigungs- und/oder negative Bestätigungsnachrichten sowie Zeitüberschreitungen verwendet , um eine zuverlässige Datenübertragung zu erreichen. Eine Bestätigung ist eine Nachricht , die durch den Empfänger gesendet , um anzuzeigen , dass sie korrekt empfangen haben einen Datenrahmen .

Wenn der Sender die Bestätigung nicht empfängt, bevor die Zeitüberschreitung auftritt (dh innerhalb einer angemessenen Zeit nach dem Senden des Datenrahmens), sendet er den Rahmen normalerweise erneut, bis er entweder korrekt empfangen wird oder der Fehler über eine vorbestimmte Anzahl von erneuten Übertragungen hinaus besteht .

Drei Arten von ARQ-Protokollen sind Stop-and-wait ARQ , Go-Back-N ARQ und Selective Repeat ARQ .

ARQ ist geeignet, wenn der Kommunikationskanal unterschiedliche oder unbekannte Kapazitäten hat , wie dies im Internet der Fall ist. ARQ erfordert jedoch die Verfügbarkeit eines Rückkanals , führt möglicherweise zu erhöhter Latenz aufgrund von erneuten Übertragungen und erfordert die Wartung von Puffern und Timern für erneute Übertragungen, was im Falle einer Netzwerküberlastung den Server und die gesamte Netzwerkkapazität belasten kann.

ARQ wird beispielsweise auf Kurzwellen-Funkdatenverbindungen in Form von ARQ-E verwendet oder mit Multiplexing als ARQ-M kombiniert .

Vorwärtsfehlerkorrektur

Vorwärtsfehlerkorrektur (FEC) ist ein Verfahren des Hinzufügens von redundanten Daten wie beispielsweise ein Fehlerkorrekturcode (ECC) zu einer Nachricht , so dass es auch von einem Empfänger wiedergewonnen werden , wenn eine Anzahl von Fehlern (bis zu der Fähigkeit des Codes Wesens verwendet) wurden entweder während des Übermittlungsprozesses oder bei der Lagerung eingeführt. Da der Empfänger den Sender nicht um eine erneute Übertragung der Daten bitten muss, wird bei der Vorwärtsfehlerkorrektur kein Rückkanal benötigt und ist daher für Simplex-Kommunikation wie etwa Rundfunk geeignet . Fehlerkorrekturcodes werden häufig in der Kommunikation auf unteren Ebenen sowie zur zuverlässigen Speicherung in Medien wie CDs , DVDs , Festplatten und RAM verwendet .

Fehlerkorrekturcodes werden normalerweise zwischen Faltungscodes und Blockcodes unterschieden :

Das Theorem von Shannon ist ein wichtiges Theorem in der Vorwärtsfehlerkorrektur und beschreibt die maximale Informationsrate, mit der eine zuverlässige Kommunikation über einen Kanal möglich ist, der eine bestimmte Fehlerwahrscheinlichkeit oder ein Signal-Rausch-Verhältnis (SNR) aufweist. Diese strikte Obergrenze wird durch die Kanalkapazität ausgedrückt . Genauer gesagt besagt das Theorem, dass Codes existieren, so dass mit zunehmender Codierungslänge die Fehlerwahrscheinlichkeit auf einem diskreten speicherlosen Kanal beliebig klein gemacht werden kann, vorausgesetzt, dass die Coderate kleiner als die Kanalkapazität ist. Die Coderate ist definiert als der Bruchteil k/n von k Quellsymbolen und n codierten Symbolen.

Die tatsächlich maximal zulässige Coderate hängt vom verwendeten Fehlerkorrekturcode ab und kann niedriger sein. Dies liegt daran, dass Shannons Beweis nur existenzieller Natur war und nicht zeigte, wie man Codes konstruiert, die sowohl optimal sind als auch effiziente Kodierungs- und Dekodierungsalgorithmen aufweisen.

Hybride Systeme

Hybrid-ARQ ist eine Kombination aus ARQ und Vorwärtsfehlerkorrektur. Es gibt zwei grundlegende Ansätze:

  • Nachrichten werden immer mit FEC-Paritätsdaten (und Fehlererkennungsredundanz) übertragen. Ein Empfänger decodiert eine Nachricht unter Verwendung der Paritätsinformationen und fordert eine erneute Übertragung unter Verwendung von ARQ nur dann an, wenn die Paritätsdaten für eine erfolgreiche Decodierung nicht ausreichend waren (durch eine fehlgeschlagene Integritätsprüfung identifiziert).
  • Nachrichten werden ohne Paritätsdaten übertragen (nur mit Fehlererkennungsinformationen). Wenn ein Empfänger einen Fehler erkennt, fordert er mit ARQ FEC-Informationen vom Sender an und verwendet sie, um die ursprüngliche Nachricht zu rekonstruieren.

Der letztere Ansatz ist auf einem Löschkanal besonders attraktiv , wenn ein ratenloser Löschcode verwendet wird .


Fehlererkennungsschemata

Die Fehlererkennung wird am häufigsten unter Verwendung einer geeigneten Hash-Funktion (oder insbesondere einer Prüfsumme , einer zyklischen Redundanzprüfung oder eines anderen Algorithmus) realisiert. Eine Hash-Funktion fügt einer Nachricht ein Tag fester Länge hinzu , das es Empfängern ermöglicht, die zugestellte Nachricht zu überprüfen, indem das Tag neu berechnet und mit dem bereitgestellten verglichen wird.

Es gibt eine große Vielfalt an verschiedenen Hash-Funktions-Designs. Einige sind jedoch aufgrund ihrer Einfachheit oder ihrer Eignung zum Erfassen bestimmter Arten von Fehlern (z. B. der Leistung der zyklischen Redundanzprüfung beim Erfassen von Burstfehlern ) von besonders weit verbreiteter Verwendung .

Mindestabstandscodierung

Ein Zufallsfehler-korrigierender Code, der auf einer Minimalabstandscodierung basiert, kann eine strikte Garantie für die Anzahl der erkennbaren Fehler bieten, aber er kann möglicherweise nicht vor einem Preimage-Angriff schützen .

Wiederholungscodes

Ein Wiederholungscode ist ein Codierungsschema, das die Bits über einen Kanal wiederholt, um eine fehlerfreie Kommunikation zu erreichen. Bei einem zu übertragenden Datenstrom werden die Daten in Bitblöcke unterteilt. Jeder Block wird eine vorbestimmte Anzahl von Malen übertragen. Um beispielsweise das Bitmuster "1011" zu senden, kann der Vier-Bit-Block dreimal wiederholt werden, wodurch "1011 1011 1011" erzeugt wird. Wenn dieses Zwölf-Bit-Muster als "1010 1011 1011" empfangen wurde – wobei der erste Block von den anderen beiden verschieden ist – ist ein Fehler aufgetreten.

Ein Wiederholungscode ist sehr ineffizient und kann anfällig für Probleme sein, wenn der Fehler für jede Gruppe an genau derselben Stelle auftritt (zB "1010 1010 1010" im vorherigen Beispiel würde als richtig erkannt). Der Vorteil von Wiederholungscodes besteht darin, dass sie extrem einfach sind und tatsächlich bei einigen Übertragungen von Nummernstationen verwendet werden .

Paritätsbit

Ein Paritätsbit ist ein Bit, das zu einer Gruppe von Quellbits hinzugefügt wird, um sicherzustellen, dass die Anzahl der gesetzten Bits (dh Bits mit dem Wert 1) im Ergebnis gerade oder ungerade ist. Es ist ein sehr einfaches Schema, das verwendet werden kann, um einzelne oder jede andere ungerade Anzahl (dh drei, fünf usw.) von Fehlern in der Ausgabe zu erkennen. Eine gerade Anzahl umgedrehter Bits lässt das Paritätsbit korrekt erscheinen, selbst wenn die Daten fehlerhaft sind.

Paritätsbits, die jedem gesendeten "Wort" hinzugefügt werden, werden Querredundanzprüfungen genannt , während diejenigen, die am Ende eines Stroms von "Wörtern" hinzugefügt werden, Längsredundanzprüfungen genannt werden . Wenn beispielsweise jedem einer Reihe von m-Bit-"Worten" ein Paritätsbit hinzugefügt ist, das anzeigt, ob es eine ungerade oder gerade Anzahl von Einsen in diesem Wort gab, wird jedes Wort mit einem einzelnen Fehler darin erkannt. Es wird jedoch nicht bekannt sein, wo im Wort der Fehler liegt. Wenn zusätzlich nach jedem Strom von n Wörtern eine Paritätssumme gesendet wird, deren jedes Bit anzeigt, ob an dieser Bitposition in der letzten Gruppe eine ungerade oder gerade Anzahl von Einsen gesendet wurde, wird die genaue Position des Fehlers festgestellt und der Fehler korrigiert werden kann. Dieses Verfahren ist jedoch nur dann garantiert effektiv, wenn in jeder Gruppe von n Wörtern nicht mehr als 1 Fehler vorhanden sind. Mit mehr Fehlerkorrekturbits können mehr Fehler erkannt und in einigen Fällen korrigiert werden.

Es gibt auch andere Bitgruppierungstechniken.

Prüfsumme

Eine Prüfsumme einer Nachricht ist eine modulare arithmetische Summe von Nachrichtencodewörtern einer festen Wortlänge (zB Byte-Werte). Die Summe kann mit Hilfe einer Einer-Komplement- Operation vor der Übertragung negiert werden , um unbeabsichtigte Nur -Null-Nachrichten zu erkennen.

Prüfsummenschemata umfassen Paritätsbits, Prüfziffern und Längsredundanzprüfungen . Einige Prüfsummenschemata, wie der Damm-Algorithmus , der Luhn-Algorithmus und der Verhoeff-Algorithmus , wurden speziell entwickelt, um Fehler zu erkennen, die häufig von Menschen beim Aufschreiben oder Merken von Identifikationsnummern eingeführt werden.

Zyklische Redundanzprüfung

Eine zyklische Redundanzprüfung (CRC) ist eine unsichere Hash-Funktion , mit der versehentliche Änderungen an digitalen Daten in Computernetzwerken erkannt werden sollen. Es ist nicht geeignet, böswillig eingebrachte Fehler zu erkennen. Es zeichnet sich durch die Angabe eines Generatorpolynoms aus , das als Divisor bei einer polynomialen langen Division über einen endlichen Körper verwendet wird , wobei die Eingabedaten als Dividenden verwendet werden . Der Rest wird das Ergebnis.

Ein CRC hat Eigenschaften, die ihn für die Erkennung von Burst-Fehlern gut geeignet machen . CRCs sind besonders einfach in Hardware zu implementieren und werden daher häufig in Computernetzwerken und Speichergeräten wie Festplatten verwendet .

Das Paritätsbit kann als Sonderfall 1-Bit-CRC angesehen werden.

Kryptografische Hash-Funktion

Die Ausgabe einer kryptografischen Hash-Funktion , auch als Message Digest bekannt , kann starke Zusicherungen über die Datenintegrität liefern , unabhängig davon, ob Änderungen der Daten versehentlich (zB aufgrund von Übertragungsfehlern) oder böswillig eingeführt wurden. Jede Änderung der Daten wird wahrscheinlich durch einen nicht übereinstimmenden Hash-Wert erkannt. Darüber hinaus ist es bei einem bestimmten Hash-Wert normalerweise nicht möglich, Eingabedaten (andere als die angegebenen) zu finden, die denselben Hash-Wert liefern. Wenn ein Angreifer nicht nur die Nachricht, sondern auch den Hash-Wert ändern kann, kann für zusätzliche Sicherheit ein verschlüsselter Hash oder ein Message Authentication Code (MAC) verwendet werden. Ohne den Schlüssel zu kennen, ist es dem Angreifer nicht möglich, den korrekt verschlüsselten Hash-Wert für eine modifizierte Nachricht einfach und bequem zu berechnen.

Fehlerkorrekturcode

Zur Fehlererkennung kann jeder fehlerkorrigierende Code verwendet werden. Ein Code mit minimalem Hamming - Abstand , d , kann bis detektieren d 1 Fehler in einem Codewort -. Die Verwendung von auf einem Mindestabstand basierenden Fehlerkorrekturcodes zur Fehlererkennung kann geeignet sein, wenn eine strikte Begrenzung der minimalen Anzahl von zu erkennenden Fehlern gewünscht wird.

Codes mit minimalem Hamming-Abstand d = 2 sind entartete Fälle von fehlerkorrigierenden Codes und können verwendet werden, um Einzelfehler zu erkennen. Das Paritätsbit ist ein Beispiel für einen Einzelfehlererkennungscode.

Anwendungen

Anwendungen, die eine geringe Latenz erfordern (z. B. Telefongespräche), können keine automatische Wiederholungsanforderung (ARQ) verwenden; sie müssen eine Vorwärtsfehlerkorrektur (FEC) verwenden. Wenn ein ARQ-System einen Fehler entdeckt und diesen erneut überträgt, kommen die erneut gesendeten Daten zu spät an, um verwendet werden zu können.

Anwendungen, bei denen der Sender die Informationen sofort vergisst, sobald sie gesendet werden (wie die meisten Fernsehkameras), können ARQ nicht verwenden; sie müssen FEC verwenden, da im Fehlerfall die Originaldaten nicht mehr verfügbar sind.

Anwendungen, die ARQ verwenden, müssen einen Rückkanal haben ; Anwendungen ohne Rückkanal können ARQ nicht verwenden.

Anwendungen, die extrem niedrige Fehlerraten erfordern (z. B. digitale Geldüberweisungen), müssen ARQ verwenden, da bei FEC nicht korrigierbare Fehler auftreten können.

Auch die Zuverlässigkeits- und Prüftechnik nutzt die Theorie der fehlerkorrigierenden Codes.

Internet

In einem typischen TCP/IP- Stack wird die Fehlerkontrolle auf mehreren Ebenen durchgeführt:

  • Jeder Ethernet-Frame verwendet CRC-32- Fehlererkennung. Frames mit erkannten Fehlern werden von der Empfängerhardware verworfen.
  • Der IPv4- Header enthält eine Prüfsumme , die den Inhalt des Headers schützt. Pakete mit falschen Prüfsummen werden im Netzwerk oder beim Empfänger verworfen.
  • Die Prüfsumme wurde im IPv6- Header weggelassen , um den Verarbeitungsaufwand beim Netzwerk-Routing zu minimieren und weil von der aktuellen Link-Layer- Technologie ausgegangen wird, dass sie eine ausreichende Fehlererkennung bietet (siehe auch RFC 3819).
  • UDP verfügt über eine optionale Prüfsumme, die die Nutzlast- und Adressierungsinformationen in den UDP- und IP-Headern abdeckt. Pakete mit falschen Prüfsummen werden vom Netzwerkstack verworfen . Die Prüfsumme ist unter IPv4 optional und unter IPv6 erforderlich. Wenn es weggelassen wird, wird davon ausgegangen, dass die Sicherungsschicht das gewünschte Maß an Fehlerschutz bietet.
  • TCP stellt eine Prüfsumme zum Schutz der Nutzlast und der Adressierungsinformationen in den TCP- und IP-Headern bereit. Pakete mit falschen Prüfsummen werden vom Netzwerkstapel verworfen und schließlich mithilfe von ARQ erneut übertragen, entweder explizit (z. B. durch Drei-Wege-Handshake ) oder implizit aufgrund eines Timeouts .

Telekommunikation im Weltraum

Die Entwicklung von Fehlerkorrekturcodes war aufgrund der extremen Verdünnung der Signalleistung über interplanetare Distanzen und der begrenzten Verfügbarkeit von Energie an Bord von Raumsonden eng mit der Geschichte der Weltraummissionen verbunden. Während frühe Missionen ihre Daten ab 1968 unverschlüsselt sendeten, wurde die digitale Fehlerkorrektur in Form von (suboptimal decodierten) Faltungscodes und Reed-Muller-Codes implementiert . Der Reed-Muller-Code war gut für den Lärm geeignet, dem das Raumfahrzeug ausgesetzt war (entspricht ungefähr einer Glockenkurve ), und wurde für das Mariner-Raumschiff implementiert und zwischen 1969 und 1977 bei Missionen verwendet.

Die Missionen Voyager 1 und Voyager 2 , die 1977 begannen, wurden entwickelt, um Farbbilder und wissenschaftliche Informationen von Jupiter und Saturn zu liefern . Dies führte zu erhöhten Codierungsanforderungen, und somit wurden die Raumfahrzeuge durch (optimal Viterbi-decodierte ) Faltungscodes unterstützt, die mit einem äußeren Golay (24,12,8)-Code verkettet werden konnten . Das Schiff Voyager 2 unterstützte zusätzlich eine Implementierung eines Reed-Solomon-Codes . Der verkettete Reed-Solomon-Viterbi (RSV)-Code ermöglichte eine sehr leistungsfähige Fehlerkorrektur und ermöglichte die ausgedehnte Reise der Raumsonde zu Uranus und Neptun . Nach den Upgrades des ECC-Systems im Jahr 1989 verwendeten beide Fahrzeuge die V2-RSV-Codierung.

Der Beratende Ausschuss für Weltraumdatensysteme empfiehlt derzeit die Verwendung von Fehlerkorrekturcodes mit einer Leistung, die mindestens der des Voyager 2-RSV-Codes ähnelt. Verkettete Codes geraten bei Weltraummissionen zunehmend in Ungnade und werden durch leistungsfähigere Codes wie Turbo-Codes oder LDPC-Codes ersetzt .

Die verschiedenen Arten von Weltraum- und Orbitalmissionen, die durchgeführt werden, deuten darauf hin, dass der Versuch, ein universelles Fehlerkorrektursystem zu finden, ein anhaltendes Problem sein wird. Bei erdnahen Missionen unterscheidet sich die Art des Rauschens im Kommunikationskanal von dem, was ein Raumfahrzeug bei einer interplanetaren Mission erfährt. Wenn ein Raumfahrzeug seinen Abstand von der Erde vergrößert, wird außerdem das Problem der Rauschkorrektur schwieriger.

Satellitenübertragung

Die Nachfrage nach Bandbreite von Satelliten- Transpondern wächst weiter, angetrieben durch den Wunsch, Fernsehen (einschließlich neuer Kanäle und hochauflösendes Fernsehen ) und IP-Daten bereitzustellen. Transponderverfügbarkeit und Bandbreitenbeschränkungen haben dieses Wachstum begrenzt. Die Transponderkapazität wird durch das gewählte Modulationsschema und den von FEC verbrauchten Kapazitätsanteil bestimmt.

Datenspeicher

Fehlererkennungs- und Korrekturcodes werden häufig verwendet, um die Zuverlässigkeit von Datenspeichermedien zu verbessern. Eine Paritätsspur, die Einzelbitfehler erkennen kann, war 1951 auf dem ersten Magnetbanddatenspeicher vorhanden . Der in gruppencodierten Aufzeichnungsbändern verwendete optimale Rechteckcode erkennt nicht nur Einzelbitfehler, sondern korrigiert sie auch. Einige Dateiformate , insbesondere Archivformate , enthalten eine Prüfsumme (meistens CRC32 ), um Beschädigungen und Kürzungen zu erkennen, und können Redundanz- oder Paritätsdateien verwenden , um Teile beschädigter Daten wiederherzustellen. Reed-Solomon-Codes werden in CDs verwendet , um durch Kratzer verursachte Fehler zu korrigieren.

Moderne Festplatten verwenden Reed-Solomon-Codes, um kleinere Fehler beim Lesen von Sektoren zu erkennen und beschädigte Daten aus fehlerhaften Sektoren wiederherzustellen und diese Daten in den Ersatzsektoren zu speichern. RAID- Systeme verwenden eine Vielzahl von Fehlerkorrekturtechniken, um Daten wiederherzustellen, wenn eine Festplatte vollständig ausfällt. Dateisysteme wie ZFS oder Btrfs sowie einige RAID- Implementierungen unterstützen Data Scrubbing und Resilvering, wodurch fehlerhafte Blöcke erkannt und (hoffentlich) wiederhergestellt werden können, bevor sie verwendet werden. Die wiederhergestellten Daten können an genau den gleichen physikalischen Ort neu geschrieben werden, um an anderer Stelle auf derselben Hardware Ersatzblöcke zu speichern, oder die Daten können auf Ersatzhardware neu geschrieben werden.

Fehlerkorrigierender Speicher

Dynamischer Direktzugriffsspeicher (DRAM) kann einen stärkeren Schutz gegen weiche Fehler bieten , indem er sich auf fehlerkorrigierende Codes verlässt. Ein solcher fehlerkorrigierender Speicher, der als ECC- oder EDAC-geschützter Speicher bekannt ist, ist aufgrund der erhöhten Strahlung im Weltraum insbesondere für missionskritische Anwendungen wie wissenschaftliche Berechnungen, Finanzen, Medizin usw. sowie für außerirdische Anwendungen wünschenswert .

Fehlerkorrigierende Speichercontroller verwenden traditionell Hamming-Codes , obwohl einige dreifache modulare Redundanz verwenden . Die Verschachtelung ermöglicht die Verteilung der Wirkung eines einzelnen kosmischen Strahls, der möglicherweise mehrere physikalisch benachbarte Bits über mehrere Wörter hinweg stört, indem benachbarte Bits verschiedenen Wörtern zugeordnet werden. Solange ein Single-Event-Upset (SEU) die Fehlerschwelle (zB ein einzelner Fehler) in einem bestimmten Wort zwischen den Zugriffen nicht überschreitet, kann es korrigiert werden (zB durch einen Ein-Bit-Fehlerkorrekturcode) und die Illusion eines fehlerfreien Speichersystems kann aufrechterhalten werden.

Zusätzlich zur Hardware, die die für den Betrieb des ECC-Speichers erforderlichen Funktionen bereitstellt, enthalten Betriebssysteme normalerweise zugehörige Berichtsfunktionen, die verwendet werden, um Benachrichtigungen bereitzustellen, wenn Soft Errors transparent behoben werden. Ein Beispiel ist der Linux - Kernel ist EDAC - Subsystem (früher bekannt als Bluesmoke ), die die Daten von Fehlerprüfungs aktiviert sammelt Komponenten innerhalb eines Computersystems; Neben dem Sammeln und Zurückmelden der Ereignisse im Zusammenhang mit dem ECC-Speicher unterstützt es auch andere Prüfsummenfehler, einschließlich der auf dem PCI-Bus erkannten . Einige Systeme unterstützen auch Memory Scrubbing , um Fehler frühzeitig zu erkennen und zu korrigieren, bevor sie nicht mehr behebbar werden.

Siehe auch

Verweise

Weiterlesen

Externe Links