Fehlererkennung und Korrektur

Nicht zu verwechseln mit Fehlerbehandlung.
In diesem Artikel geht es um Computer. Für Wissen siehe Fakten Überprüfung und Probleme lösen.
Um Übertragungsfehler zu beseitigen, die durch die Erdatmosphäre (links) eingeführt wurden, haben die Goddard -Wissenschaftler die Reed -Solomon -Fehlerkorrektur (rechts) angewendet, die üblicherweise in CDs und DVDs verwendet wird. Typische Fehler sind fehlende Pixel (weiß) und falsche Signale (schwarz). Der weiße Streifen zeigt eine kurze Zeit an, wenn die Übertragung unterbrochen wurde.

Im Informationstheorie und Codierungstheorie mit Anwendungen in Informatik und Telekommunikation, Fehlererkennung und Korrektur (EDAC) oder Fehlersteuerung sind Techniken, die ermöglichen zuverlässige Lieferung von Digitale Daten über unzuverlässig Kommunikationskanäle. Viele Kommunikationskanäle unterliegen Kanalrauschenund somit können Fehler während der Übertragung von der Quelle auf einen Empfänger eingeführt werden. Fehlererkennungstechniken ermöglichen das Erkennen solcher Fehler, während die Fehlerkorrektur in vielen Fällen die Rekonstruktion der ursprünglichen Daten 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.

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

Geschichte

In der klassischen Antike,, Kopisten des Hebräische Bibel wurden für ihre Arbeit gemäß der Anzahl der Stichs (Verse -Linien) bezahlt. Da die Prosa -Bücher der Bibel kaum in Stichs geschrieben wurden, mussten die Kopisten, um die Arbeit zu schätzen, die Briefe zählen.[1] Dies trug auch dazu bei, die Genauigkeit bei der Übertragung des Textes mit der Herstellung nachfolgender Kopien zu gewährleisten.[2][3] Zwischen dem 7. und 10. Jahrhundert CE a Gruppe jüdischer Schriftgelehrten formalisiert und erweiterte dies, um die zu erstellen Numerische Masorah um eine genaue Reproduktion des heiligen Textes zu gewährleisten. Es enthielt Zählungen der Anzahl der Wörter in einer Zeile, einem Abschnitt, einem Buch und Gruppen von Büchern, wobei die mittlere Stich eines Buches, ein Wort verwenden Statistiken und Kommentare festgestellt wurden.[1] Standards wurden so, dass eine Abweichung in einem einzigen Buchstaben in einer Tora -Schriftrolle als inakzeptabel angesehen wurde.[4] Die Wirksamkeit ihrer Fehlerkorrekturmethode wurde durch die Genauigkeit des Kopierens durch die Jahrhunderte durch die Entdeckung der verifiziert Totmeer -Schriftrollen 1947–1956 stammt aus ca.150 v. Chr. 75 n. Chr.[5]

Die moderne Entwicklung von Fehlerkorrekturcodes wird zugeschrieben Richard Hamming 1947.[6] Eine Beschreibung von Hamming -Code erschien in Claude Shannon's Eine mathematische Kommunikationstheorie[7] und wurde schnell durch verallgemeinert von Marcel J. E. Golay.[8]

Einführung

Alle Fehlererkennungs- und Korrekturschemata fügen einige hinzu Redundanz (d. H. Einige zusätzliche Daten) an eine Nachricht, mit der Empfänger die Konsistenz der übermittelten Nachricht überprüfen und Daten wiederhergestellt wurden, die als beschädigt bestimmt wurden. Fehlererkennung und Korrekturschemata können entweder sein systematisch oder nicht systematisch. In einem systematischen Schema sendet der Sender die ursprünglichen Daten und fügt eine feste Anzahl von an. Bits überprüfen (oder Paritätsdaten), die von den Datenbits von einigen abgeleitet werden deterministischer Algorithmus. Wenn nur Fehlererkennung erforderlich ist, kann ein Empfänger einfach denselben Algorithmus auf die empfangenen Datenbits anwenden und seine Ausgabe mit den empfangenen Scheckbits vergleichen. Wenn die Werte nicht übereinstimmen, ist irgendwann während der Übertragung ein Fehler aufgetreten. In einem System, das einen nicht-systematischen Code verwendet, wird die ursprüngliche Nachricht in eine codierte Nachricht mit denselben Informationen umgewandelt und mindestens so viele Bits wie die ursprüngliche Nachricht enthält.

Eine gute Fehlersteuerungsleistung erfordert, dass das Schema basierend auf den Eigenschaften des Kommunikationskanals ausgewählt wird. Verbreitet Kanalmodelle enthalten erinnertlos Modelle, bei denen Fehler zufällig und mit einer bestimmten Wahrscheinlichkeit auftreten, und dynamische Modelle, bei denen in erster Linie Fehler auftreten Bursts. Folglich können Fehler zur Erkennung und Korrektur von Codes im Allgemeinen zwischen unterschieden werden zufällige Erkennung/Korrektur und Burst-Erkennung/Korrektur. Einige Codes können auch für eine Mischung aus Zufallsfehlern und Burst -Fehlern geeignet sein.

Wenn die Kanalmerkmale nicht bestimmt werden oder sehr unterschiedlich sind, kann ein Fehler zur Erkennung von Erkennung mit einem System zur Übermittlung fehlerhafter Daten kombiniert werden. Dies ist bekannt als als Automatische Wiederholungsanforderung (ARQ) und wird vor allem im Internet verwendet. Ein alternativer Ansatz für die Fehlersteuerung ist Hybrid automatische Wiederholungsanforderung (HARQ), eine Kombination aus ARQ und Fehlerkorrekturcodierung.

Arten der Fehlerkorrektur

Es gibt drei Haupttypen der Fehlerkorrektur.[9]

Automatische Wiederholungsanforderung

Automatische Wiederholungsanforderung . Zeitüberschreitungen zu einer zuverlässigen Datenübertragung. Ein Wissen ist eine vom Empfänger gesendete Nachricht, um anzuzeigen, dass er korrekt empfangen hat a Datenrahmen.

Wenn der Sender die Bestätigung nicht vor der Auszeitung nicht erhält (d. H. Innerhalb einer angemessenen Zeit nach dem Senden des Datenrahmens), übermittelt er den Rahmen, bis er entweder korrekt empfangen wird oder der Fehler über eine vorbestimmte Anzahl von Übertragungen hinausgeht .

Drei Arten von ARQ -Protokollen sind Stop-and-Wait Arq, Go-R-N-N arq, und Selektive Wiederholung ARQ.

ARQ ist angemessen, wenn der Kommunikationskanal unterschiedlich oder unbekannt ist Kapazität, wie im Internet der Fall. ARQ erfordert jedoch die Verfügbarkeit von a Rückkanal, führt zu möglicherweise erhöht Latenz aufgrund von Wiedervermutungen und erfordert die Wartung von Puffer und Timern für die Wiederholung, die im Fall von Netzüberlastung Kann den Server und die Gesamtnetzwerkkapazität belasten.[10]

Zum Beispiel wird ARQ in Shortwave -Funkdatenlinks in Form von verwendet Arq-eoder kombiniert mit Multiplexing als ARQ-M.

Vorwärtsfehlerkorrektur

Vorwärtsfehlerkorrektur (FEC) ist ein Additionsprozess überflüssige Daten wie ein Fehlerkorrekturcode (ECC) zu einer Nachricht, so dass sie von einem Empfänger wiederhergestellt werden kann, wenn eine Reihe von Fehlern (bis zur Fähigkeit des verwendeten Codes) entweder während des Übertragungsprozesses oder beim Speicher eingeführt werden. Da der Empfänger den Absender nicht um die Übermittlung der Daten bitten muss, a Rückkanal ist bei der Vorwärtsfehlerkorrektur nicht erforderlich. Fehlerkorrigierende Codes werden in verwendet untere Schicht Kommunikation wie Mobilfunk, schnelle Geschwindigkeit Faser-optische Kommunikation und W-lan,[11][12] sowie für zuverlässigen Speicher in Medien wie z. B. Flash-Speicher, Festplatte und RAM.[13]

Fehlerkorrigierende Codes werden normalerweise zwischen unterschieden Faltungscodes und Blockcodes:

Shannons Theorem ist ein wichtiger Satz bei der Vorwärtsfehlerkorrektur und beschreibt das Maximum Informationsrate auf welche zuverlässige Kommunikation über einen Kanal möglich ist, der eine bestimmte Fehlerwahrscheinlichkeit hat oder Signal-Rausch-Verhältnis (SNR). Diese strenge Obergrenze wird in Bezug auf die ausgedrückt Kanalkapazität. Insbesondere sagt der Satz, dass es Codes so gibt, dass die Wahrscheinlichkeit eines Fehlers auf a mit zunehmender Codierungslänge vorhanden ist Diskreter, speicherloser Kanal kann willkürlich klein gemacht werden, sofern die Coderate ist kleiner als die Kanalkapazität. Die Coderate ist definiert als der Fraktion k/n von k Quellensymbole und n codierte Symbole.

Die tatsächliche Maximum-Code-Rate hängt vom verwendeten fehlerkorrigierenden Code ab und kann niedriger sein. Dies liegt daran effizient Codierungs- und Dekodierungsalgorithmen.

Hybridschemata

Hauptartikel: Hybrid arq

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

  • Nachrichten werden immer mit FEC-Paritätsdaten (und Fehlerabbauaufnahme) übertragen. Ein Empfänger dekodiert eine Nachricht unter Verwendung der Paritätsinformationen und fordert die Neuübertragung nur mit ARQ an, wenn die Paritätsdaten für eine erfolgreiche Decodierung nicht ausreichen (identifiziert durch eine fehlgeschlagene Integritätsprüfung).
  • Nachrichten werden ohne Paritätsdaten übertragen (nur mit Fehlererkennungsinformationen). Wenn ein Empfänger einen Fehler erkennt, fordert er FEC -Informationen vom Sender mit ARQ an und rekonstruiert die ursprüngliche Nachricht.

Der letztere Ansatz ist besonders attraktiv für eine Löschungskanal Bei Verwendung a Ratloser Löschcode.

Fehlererkennungsschemata

Die Fehlererkennung wird am häufigsten mit einem geeigneten realisiert Hash-Funktion (oder speziell a Überprüfung, zyklische Redundanzprüfung oder ein anderer Algorithmus). Eine Hash-Funktion fügt eine feste Länge hinzu Schild zu einer Nachricht, mit der Empfänger die übertragbare Nachricht durch Neuzunahme des Tags überprüfen und mit dem bereitgestellten verglichen werden können.

Es gibt eine Vielzahl verschiedener Hash -Funktionsdesigns. Einige sind jedoch aufgrund ihrer Einfachheit oder ihrer Eignung für die Erkennung bestimmter Arten von Fehlern besonders weit verbreitet Burst -Fehler).

Mindestdistanzcodierung

Ein zufälliger Erreger-korrigierender Code basierend auf Mindestdistanzcodierung kann eine strikte Garantie für die Anzahl der nachweisbaren Fehler liefern, kann jedoch nicht vor a schützen Vorbereitungsangriff.

Wiederholungscodes

A Wiederholungscode ist ein Codierungsschema, das die Bits über einen Kanal wiederholt, um fehlerfreie Kommunikation zu erreichen. Bei einem Datenstrom werden die Daten in Bitblöcke unterteilt. Jeder Block wird einige vorgegebene Häufigkeit übertragen. Um 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 nicht von den anderen beiden ist-ist ein Fehler aufgetreten.

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

Paritätsbit

Hauptartikel: Paritätsbit

A Paritätsbit ist ein bisschen, das einer Gruppe von Quellbits hinzugefügt wird, um sicherzustellen, dass die Anzahl der festgelegten Bits (d. H. Bits mit Wert 1) im Ergebnis gerade oder ungerade ist. Es ist ein sehr einfaches Schema, das verwendet werden kann, um einzelne oder andere ungerade Zahl (d. H. Drei, fünf usw.) von Fehlern in der Ausgabe zu erkennen. Eine gleichmäßige Anzahl von umgedrehten Bits lässt das Paritätsbit korrekt erscheinen, obwohl die Daten fehlerhaft sind.

Zu jedem "Wort" hinzugefügten Paritätsbits werden aufgerufen Quer -Redundanzprüfungen, während diejenigen, die am Ende eines Stroms von "Wörtern" hinzugefügt wurden, genannt werden Längsreduktionsprüfungen. Wenn beispielsweise jede Reihe von M-Bit-Wörtern ein Paritätsbit hinzugefügt hat, wird gezeigt, ob es in diesem Wort eine ungerade oder sogar Anzahl derjenigen gab, ein Wort mit einem einzigen Fehler darin wird erkannt. Es wird jedoch nicht bekannt sein, wo im Wort der Fehler ist. Wenn zusätzlich nach jedem Strom von N-Wörtern eine Paritätsbetrag gesendet wird, von denen jeder zeigt, ob es eine ungerade oder sogar Anzahl derjenigen in dieser Bitposition in der jüngsten Gruppe zugesandt hat, die genaue Position des Fehlers Kann bestimmt und der Fehler korrigiert werden. Diese Methode ist jedoch nur garantiert, ob es in jeder Gruppe von N -Wörtern nicht mehr als 1 Fehler gibt. Bei mehr Fehlerkorrekturbits können mehr Fehler erkannt und in einigen Fällen korrigiert werden.

Es gibt auch andere Bitgruppentechniken.

Überprüfung

Hauptartikel: Überprüfung

A Überprüfung einer Nachricht ist a Modulararithmetik Summe von Nachrichtencodewörtern einer festen Wortlänge (z. B. Bytewerte). Die Summe kann mittels a negiert werden Einen eine Komplementierung Betrieb vor der Übertragung zur Erkennung unbeabsichtigter All-Null-Nachrichten.

Prüfsummenschemata umfassen Paritätsbits, Ziffern überprüfen, und Längsreduktionsprüfungen. Einige Prüfsummenschemata wie die DAMM -Algorithmus, das Luhn -Algorithmus, und die Verhoeff -Algorithmus, sind speziell entwickelt, um Fehler zu erkennen, die häufig vom Menschen beim Aufschreiben oder Erinnern von Identifikationsnummern eingeführt werden.

Zyklische Redundanzprüfung

Hauptartikel: Zyklische Redundanzprüfung

A zyklische Redundanzprüfung (CRC) ist eine Nichtsicherheit Hash-Funktion Entwickelt, um zufällige Änderungen an digitalen Daten in Computernetzwerken zu erkennen. Es ist nicht geeignet, böswillig eingeführte Fehler zu erkennen. Es ist durch Spezifikation von a gekennzeichnet Generator Polynom, was als die verwendet wird Divisor in einem Polynom lange Division über ein endliches Felddie Eingabedaten als die als die Dividende. Das Rest wird das Ergebnis.

Ein CRC hat Eigenschaften, die es gut zum Erkennen eignen Burst -Fehler. CRCs sind besonders einfach in Hardware zu implementieren und werden daher häufig in verwendet Computernetzwerke und Speichergeräte wie z. Festplattenfahrten.

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

Kryptografische Hash -Funktion

Hauptartikel: Kryptografische Hash -Funktion

Die Ausgabe von a Kryptografische Hash -Funktion, auch bekannt als a Nachrichtendigest, kann starke Zusicherungen über liefern Datenintegrität, ob Änderungen der Daten zufällig sind (z. B. aufgrund von Übertragungsfehlern) oder böswillig eingeführt. Jede Änderung an den Daten wird wahrscheinlich durch einen nicht übereinstimmenden Hash -Wert erkannt. Darüber hinaus ist es angesichts eines gewissen Hash -Wertes in der Regel nicht durchführbar, einige Eingabedaten (außer der angegebenen) zu finden, die den gleichen Hash -Wert liefern. Wenn ein Angreifer nicht nur die Nachricht, sondern auch den Hash -Wert ändern kann, dann ist a Keyed Hash oder Nachrichtenauthentifizierungscode (MAC) kann für zusätzliche Sicherheit verwendet werden. Ohne den Schlüssel zu kennen, ist es nicht möglich, dass der Angreifer den korrekten Keyled -Hash -Wert für eine geänderte Nachricht einfach oder bequem berechnet.

Fehlerkorrekturcode

Hauptartikel: Fehlerkorrekturcode

Jeder fehlerkorrigierende Code kann zur Fehlererkennung verwendet werden. Ein Code mit Minimum Hamming -Entfernung, d, kann zu erkennen d - 1 Fehler in einem Codewort. Die Verwendung von Mindeststörungs-basierten fehlerkorrigierenden Codes zur Fehlererkennung kann geeignet sein, wenn eine strenge Grenze für die minimale Anzahl der zu erkennenden Fehler gewünscht wird.

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

Anwendungen

Anwendungen, die eine geringe Latenz erfordern (z. B. Telefongespräche), können nicht verwendet werden Automatische Wiederholungsanforderung (ARQ); Sie müssen verwenden Vorwärtsfehlerkorrektur (FEC). Wenn ein ARQ-System einen Fehler entdeckt und erneut überträgt, werden die Wiederversanddaten zu spät eintreffen, um verwendbar zu sein.

Anwendungen, bei denen der Sender die Informationen sofort vergisst, sobald er gesendet wird (z. B. die meisten Fernsehkameras), können ARQ nicht verwenden. Sie müssen FEC verwenden, da bei einem Fehler die ursprünglichen Daten nicht mehr verfügbar sind.

Anwendungen, die ARQ verwenden Rückkehrkanal; Anwendungen mit kein Rückgabekanal können ARQ nicht verwenden.

Anwendungen, die extrem niedrige Fehlerraten (z. B. Digitalgeldtransfers) erfordern, müssen ARQ aufgrund der Möglichkeit unkorrigierbarer Fehler mit FEC verwenden.

Zuverlässigkeits- und Inspektionsingenieurwesen nutzen auch die Theorie der fehlerkorrigierenden Codes.[16]

Internet

In einem typischen TCP/IP Stack, Fehlersteuerung wird auf mehreren Ebenen durchgeführt:

  • Jeder Ethernet -Frame Verwendet CRC-32 Fehlererkennung. Frames mit erkannten Fehlern werden von der Empfängerhardware verworfen.
  • Das IPv4 Header enthält a Überprüfung Schutz des Inhalts des Headers. Pakete Mit falschen Prüfsummen werden im Netzwerk oder am Empfänger fallen gelassen.
  • Die Prüfsumme wurde aus dem weggelassen IPv6 Header, um die Verarbeitungskosten in zu minimieren Netzwerkrouting Und weil Strom Verbindungsschicht Es wird angenommen, dass Technologie eine ausreichende Fehlererkennung liefert (siehe auch RFC 3819).
  • UDP hat eine optionale Prüfsumme, die die Nutzlast und die Adressierung von Informationen in den UDP- und IP -Headern abdeckt. Pakete mit falschen Prüfsummen werden von der verworfen Netzwerkstapel. Die Prüfsumme ist unter IPv4 optional und unter IPv6 erforderlich. Bei Auslassung wird angenommen, dass die Datenverbindungsschicht den gewünschten Fehlerschutzniveau bietet.
  • TCP Bietet eine Prüfsumme zum Schutz der Nutzlast und der Adressierung von Informationen in den TCP- und IP -Headern. Pakete mit falschen Prüfsummen werden vom Netzwerkstapel verworfen und werden schließlich mit ARQ erneut übertragen (wie bis zum Beispiel Drei-Wege-Handschlag) oder implizit aufgrund von a Auszeit.

Tiefstände Telekommunikation

Die Entwicklung von Fehlerkorrekturcodes war aufgrund der extremen Verdünnung der Signalleistung über interplanetarische Entfernungen und der begrenzten Stromverfügbarkeit an den Raumsonden der Signalleistung eng mit der Vorgeschichte von Tiefenmissionen gekoppelt. Während frühe Missionen ihre Daten ab 1968 unkodiert sandten, wurde die digitale Fehlerkorrektur in Form von (suboptimal dekodiert) implementiert, um zu korrigieren. Faltungscodes und Reed -Müller -Codes.[17] Der Reed -Müller -Code war gut für das Geräusch geeignet, dem das Raumschiff ausgesetzt war (ungefähr a entspricht a Glockenkurve) und wurde für das Mariner -Raumschiff implementiert und zwischen 1969 und 1977 für Missionen verwendet.

Das Voyager 1 und Voyager 2 Missionen, die 1977 begannen, wurden entwickelt, um Farbbildgebung und wissenschaftliche Informationen aus zu liefern Jupiter und Saturn.[18] Dies führte zu erhöhten Codierungsanforderungen, und daher wurde das Raumschiff unterstützt (optimal Viterbi-dekodiert) Faltungscodes, die sein könnten verkettet mit einer äußeren Golay (24,12,8) Code. Das Handwerk von Voyager 2 unterstützte zusätzlich eine Implementierung von a Reed -Solomon -Code. Der verkettete Reed -Solomon -Viterbi -Code (RSV) ermöglichte eine sehr leistungsstarke Fehlerkorrektur und ermöglichte die erweiterte Reise des Raumfahrzeugs Uranus und Neptun. Nach den Upgrades von ECC -Systemen im Jahr 1989 verwendeten beide die V2 -RSV -Codierung.

Das Beratungsausschuss für Weltraumdatensysteme Derzeit empfiehlt die Verwendung von Fehlerkorrekturcodes mit einer ähnlichen Leistung, die dem Voyager 2 RSV -Code minimal ähnlich ist. Verkettete Codes fallen mit Weltraummissionen zunehmend in Ungnade und werden durch leistungsstärkere Codes ersetzt wie Turbocodes oder LDPC -Codes.

Die verschiedenen Arten von Raum- und Orbitalmissionen, die durchgeführt werden, deuten darauf hin, dass der Versuch, ein einheitliches Fehlerkorrektursystem zu finden, ein fortlaufendes Problem darstellt. Für Missionen in der Nähe der Erde die Natur der Lärm in dem Kommunikationskanal unterscheidet sich von dem, was ein Raumschiff auf einer interplanetären Missionserfahrung. Wenn ein Raumschiff seinen Abstand von der Erde erhöht, wird das Problem der Korrektur von Rauschen außerdem schwieriger.

Satellitenübertragung

Die Nachfrage nach Satelliten Transponder Die Bandbreite wächst weiter, befördert vom Wunsch, Fernsehen zu liefern (einschließlich neuer Kanäle und Hochdefinitionsfernseher) und IP -Daten. Transponderverfügbarkeit und Bandbreitenbeschränkungen haben dieses Wachstum eingeschränkt. Die Transponderkapazität wird durch die ausgewählten bestimmt Modulation Schema und der Anteil der von FEC konsumierten Kapazität.

Datenspeicher

Fehlererkennungs- und Korrekturcodes werden häufig verwendet, um die Zuverlässigkeit von Datenspeichermedien zu verbessern.[19] Eine Paritätsspur, die in der Lage ist, Einzelbit-Fehler zu erkennen, war am ersten vorhanden Datenspeicherung von Magnetbanddaten 1951. Die optimaler rechteckiger Code benutzt in Gruppencodierte Aufzeichnung Bänder erkennt nicht nur, sondern korrigiert auch Einzelbitfehler. Etwas Dateiformate, im Speziellen ArchivformateFügen Sie eine Prüfsumme (am häufigsten CRC32) Korruption und Kürzung zu erkennen und Redundanz einsetzen kann oder Paritätsdateien Teile der beschädigten Daten wiederherstellen. Reed-Solomon-Codes werden in verwendet CDs Fehler durch Kratzer zu korrigieren.

Moderne Festplatten verwenden Reed -Solomon -Codes, um kleinere Fehler in den Sektor -Lesevorgängen zu erkennen und zu korrigieren, und um beschädigte Daten aus fehlgeschlagenen Sektoren wiederherzustellen und diese Daten in den Ersatzsektoren zu speichern.[20] ÜBERFALLEN Systeme verwenden eine Vielzahl von Fehlerkorrektechniken, um Daten wiederherzustellen, wenn eine Festplatte vollständig fehlschlägt. Dateisysteme wie ZFS oder Btrfssowie einige ÜBERFALLEN Implementierungen, Unterstützung Datenschrubben und Widerstand, wodurch schlechte Blöcke erkannt und (hoffentlich) erholt werden, bevor sie verwendet werden.[21] Die wiederhergestellten Daten können genau an den gleichen physischen Standort geschrieben werden, um Blöcke an anderer Stelle auf derselben Hardware zu verschaffen, oder die Daten können auf Ersatzhardware umgeschrieben werden.

Fehlerkorrigierender Speicher

Hauptartikel: ECC -Speicher

Dynamischer Direktzugriffsspeicher (DRAM) kann einen stärkeren Schutz gegen weiche Fehler Durch die Stütze auf fehlerkorrigierende Codes. Solcher fehlerkorrigierender Speicher, bekannt als ECC oder EDAC-geschützt Gedächtnis ist besonders wünschenswert für missionskritische Anwendungen wie wissenschaftliches Computer, finanzielle, medizinische usw. sowie außerirdische Anwendungen aufgrund des erhöhten Anstiegs Strahlung im Weltraum.

Fehlerkorrigierende Speichercontroller verwenden traditionell Hamming -Codes, obwohl einige benutzen dreifache modulare Redundanz. Verschachtung 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 mit verschiedenen Wörtern verknüpft werden. Solange ein Einberufung verärgert (SEU) überschreitet den Fehlerschwellenwert (z. B. ein einzelner Fehler) in einem bestimmten Wort zwischen Zugriffern nicht (z. B. durch einen einzelbit-Fehlerkorrekturcode) und die Illusion eines fehlerfreien Speichers System kann beibehalten werden.[22]

Neben der Hardware, die für den Betrieb des ECC -Speichers Funktionen bietet, ist auch Funktionen Betriebssysteme Normalerweise enthalten verwandte Berichterstattungsmöglichkeiten, mit denen Benachrichtigungen vorgestellt werden, wenn weiche Fehler transparent wiederhergestellt werden. Ein Beispiel ist das Linux Kernel's EDAC Subsystem (zuvor bekannt als Bluesmoke), das die Daten von fehlerübergreifenden Komponenten in einem Computersystem sammelt; Neben dem Sammeln und Berichten der Ereignisse im Zusammenhang mit dem ECC -Speicher unterstützt es auch andere Überprüfungsfehler, einschließlich derjenigen, die auf dem erkannt wurden PCI -Bus.[23][24][25] Ein paar Systeme[angeben] auch Unterstützung Memory Scrubbing Fehler zu fangen und zu korrigieren, bevor sie nicht wiederherstellbar werden.

Siehe auch

Verweise

  1. ^ a b "Masorah". Jüdische Enzyklopädie.
  2. ^ Pratico, Gary D.; Pelt, Miles V. Van (2009). Grundlagen der biblischen hebräischen Grammatik: zweite Ausgabe. Zondervan. ISBN 978-0-310-55882-8.
  3. ^ Mounce, William D. (2007). Griechisch für den Rest von uns: Verwendung griechischer Werkzeuge ohne Beherrschung biblischer Sprachen. Zondervan. p. 289. ISBN 978-0-310-28289-1.
  4. ^ Mischneh Tora, Tefillin, Mezuzah und Sefer Tora, 1: 2. Beispiel Englische Übersetzung: Eliyahu Tuger. Die Mischneh -Tora des Rambams. Moznaim Publishing Corporation.
  5. ^ Brian M. Fagan (5. Dezember 1996). "Scrollen des Toten Meeres". Der Oxford -Begleiter der Archäologie. Oxford University Press. ISBN 0195076184.
  6. ^ Thompson, Thomas M. (1983), Von fehlerkorrigierenden Codes über Kugelpakete bis hin zu einfachen Gruppen, The Carus Mathematical Monographs (#21), The Mathematical Association of America, p. vii, ISBN 0-88385-023-0
  7. ^ Shannon, C. E. (1948), "Eine mathematische Kommunikationstheorie", Glockensystem Technisches Journal, 27 (3): 379–423, doi:10.1002/j.1538-7305.1948.tb01338.x, HDL:10338.DMLCZ/101429, PMID 9230594
  8. ^ Golay, Marcel J. E. (1949), "Notizen zur digitalen Codierung", Proc.I.R.E. (D.h.e.e.e.), 37: 657
  9. ^ Gupta, Vikas; Verma, Chanderkant (November 2012). "Fehlererkennung und Korrektur: Eine Einführung". Internationales Journal of Advanced Research in Informatik und Software -Engineering. 2 (11). S2CID 17499858.
  10. ^ a b A. J. McAuley, Zuverlässige Breitbandkommunikation unter Verwendung eines Burst -Löschungs -Korrekturcode, ACM Sigcomm, 1990.
  11. ^ Shah, Pradeep M.; Vyavahare, Prakash D.; Jain, Anjana (September 2015). "Moderne Fehlerkorrekturcodes für 4G und darüber hinaus: Turbocodes und LDPC -Codes". 2015 Radio- und Antennen Tage des Indischen Ozeans (Radio): 1–2. doi:10.1109/radio.2015.7323369. ISBN 978-9-9903-7339-4. S2CID 28885076. Abgerufen 22. Mai 2022.
  12. ^ "IEEE SA - IEEE 802.11AC -2013". IEEE Standards Association.
  13. ^ "Übergang zum fortgeschrittenen Format 4K -Sektor Festplatten | Seagate US". Seagate.com. Abgerufen 22. Mai 2022.
  14. ^ Frank Van Gerwen. "Zahlen (und andere mysteriöse) Stationen". Abgerufen 12. März 2012.
  15. ^ Gary Cutlack (25. August 2010). "Mysterious Russian 'Nummern Station' ändert nach 20 Jahren ausgestrahlt". Gizmodo. Abgerufen 12. März 2012.
  16. ^ Ben-Gal.; Herer Y.; Raz T. (2003). "Selbstkorrekturinspektionsverfahren unter Inspektionsfehlern" (PDF). Iie Transaktionen. Iie Transaktionen zu Qualität und Zuverlässigkeit, 34 (6), S. 529-540. Archiviert von das Original (PDF) Am 2013-10-13. Abgerufen 2014-01-10.
  17. ^ K. Andrews et al., Die Entwicklung von Turbo- und LDPC-Codes für Tiefenanwendungen, Proceedings of the IEEE, Vol. 95, Nr. 11, November 2007.
  18. ^ Huffman, William Cary; Pless, Vera S. (2003). Grundlagen der fehlerkorrigierenden Codes. Cambridge University Press. ISBN 978-0-521-78280-7.
  19. ^ Kurtas, Erozan M.; Vasic, Bane (2018-10-03). Erweiterte Fehlersteuerungstechniken für Datenspeichersysteme. CRC Press. ISBN 978-1-4200-3649-7.[Permanent Dead Link]
  20. ^ Scott A. Moulton. "Meine Festplatte ist gestorben". Archiviert von das Original am 2008-02-02.
  21. ^ Qiao, Zhi; Fu, Lied; Chen, Hsing-Bung; Settlemyer, Bradley (2019). "Aufbau zuverlässiger Hochleistungsspeichersysteme: eine empirische und analytische Studie". 2019 IEEE International Conference on Cluster Computing (Cluster): 1–10. doi:10.1109/cluster.2019.8891006. ISBN 978-1-7281-4734-5. S2CID 207951690.
  22. ^ "Mit Strongarm SA-1110 im On-Bord-Computer von Nanosatelliten". Tsinghua Space Center, Tsinghua Universität, Peking. Archiviert von das Original Am 2011-10-02. Abgerufen 2009-02-16.
  23. ^ Jeff Layton. "Fehlererkennung und Korrektur". Linux Magazine. Abgerufen 2014-08-12.
  24. ^ "EDAC -Projekt". Bluesmoke.SourceForge.net. Abgerufen 2014-08-12.
  25. ^ "Dokumentation/edac.txt". Linux -Kernel -Dokumentation. kernel.org. 2014-06-16. Archiviert von das Original am 2009-09-05. Abgerufen 2014-08-12.

Weitere Lektüre

Externe Links