Fehlererkennung und -korrektur (Sicherungsschicht)

Fehlererkennung und -korrektur fügen sorgfältig berechnete redundante Bits zu übertragenen Daten hinzu, sodass ein Empfänger Bitfehler, die durch eine verrauschte Kommunikationsverbindung entstehen, erkennen und manchmal auch korrigieren kann.

Definition

Fehlererkennung und -korrektur sind Kodierungstechniken, die redundante Prüfbits, die aus den Daten berechnet werden, anhängen, sodass ein Empfänger feststellen kann, ob Bits während der Übertragung beschädigt wurden (Erkennung) und, mit stärkeren Codes, die Originaldaten rekonstruieren kann (Korrektur).

Scope

Dieses Thema behandelt die Kodierungstechniken, die auf der Sicherungsschicht verwendet werden, um Bitfehler zu bewältigen: einfache Paritätsprüfungen, zweidimensionale Parität, Internet-Prüfsummen und zyklische Redundanzprüfungen (CRC) zur Erkennung sowie Vorwärtsfehlerkorrekturcodes wie Hamming-Codes zur Korrektur. Es behandelt den Kompromiss zwischen Redundanz-Overhead und der Stärke der Erkennung oder Korrektur und wo jede Technik eingesetzt wird. Es schließt die auf höheren Schichten aufgebaute, auf Neuübertragung basierende Zuverlässigkeit aus, die die Kodierung ergänzt, anstatt sie zu ersetzen.

Core questions

• Wie ermöglichen redundante Prüfbits einem Empfänger, zu erkennen, dass eine Übertragung beschädigt wurde?
• Wie unterscheiden sich Parität, Prüfsummen und zyklische Redundanzprüfungen in Stärke und Kosten?
• Wie korrigieren Vorwärtsfehlerkorrekturcodes wie Hamming-Codes Fehler ohne Neuübertragung?
• Welchen Kompromiss gibt es zwischen Kodierungs-Overhead und Fehlerbehandlungsfähigkeit?
• Wann ist Fehlerkorrektur der Erkennung plus Neuübertragung vorzuziehen?

Key concepts

• Paritätsprüfung
• zweidimensionale Parität
• Internet-Prüfsumme
• zyklische Redundanzprüfung (CRC)
• Generatorpolynom
• Vorwärtsfehlerkorrektur
• Hamming-Codes
• Bündelfehler
• Kodierungs-Overhead

Key theories

Redundanz zur Fehlererkennung

Durch die Übertragung zusätzlicher Bits, die aus den Daten berechnet werden – ein Paritätsbit, eine Prüfsumme oder ein CRC-Rest – kann ein Empfänger diese neu berechnen und vergleichen, um Beschädigungen zu erkennen; CRCs, die auf Polynomarithmetik basieren, erfassen alle Bündelfehler bis zum Grad des Generatorpolynoms.

Vorwärtsfehlerkorrektur

Fehlerkorrekturcodes wie Hamming-Codes fügen genügend strukturierte Redundanz hinzu, sodass der Empfänger nicht nur eine begrenzte Anzahl von Bitfehlern erkennen, sondern auch lokalisieren und beheben kann, wodurch eine Neuübertragung auf Kosten eines höheren Overheads vermieden wird.

Kanalkapazität und zuverlässige Kommunikation

Die Informationstheorie besagt, dass jeder verrauschte Kanal eine Kapazität hat, unterhalb derer eine beliebig zuverlässige Kommunikation mit geeigneter Kodierung möglich ist, was die fundamentalen Grenzen umreißt, denen sich praktische Fehlerkontrollcodes annähern.

Clinical relevance

Fehlerkontrolle ist unsichtbar, aber allgegenwärtig: CRCs schützen Ethernet- und Wi-Fi-Frames, Prüfsummen sichern IP- und Transportschicht-Header, und Vorwärtsfehlerkorrektur ist unerlässlich, wo Neuübertragung kostspielig oder unmöglich ist, wie bei Deep-Space-Verbindungen, Speichermedien und Streaming über verlustbehaftete drahtlose Verbindungen. Das richtige Gleichgewicht zwischen Erkennung und Korrektur prägt die Zuverlässigkeit und Effizienz in Kommunikations- und Speichersystemen.

History

Claude Shannons Informationstheorie von 1948 etablierte die Existenz zuverlässiger Kodierung bis zur Kanalkapazität, und Richard Hammings Codes von 1950 lieferten das erste praktische Einzelfehlerkorrekturverfahren. Zyklische Redundanzprüfungen und stärkere Codes folgten und wurden zum Standard in der Sicherungsschicht-Rahmenbildung, und das Feld hat seitdem leistungsstarke Codes (wie Turbo- und LDPC-Codes) hervorgebracht, die Shannons Grenze nahekommen.

Key figures

• Claude Shannon
• Richard Hamming

Seminal works

• shannon1948
• hamming1950
• kurose2021

Frequently asked questions

Was ist der Unterschied zwischen Fehlererkennung und Fehlerkorrektur?

Fehlererkennung teilt dem Empfänger lediglich mit, dass Daten beschädigt wurden, woraufhin er die Daten verwerfen oder eine Neuübertragung anfordern kann. Fehlerkorrektur fügt genügend Redundanz hinzu, sodass der Empfänger die Originaldaten auch ohne erneute Anforderung rekonstruieren kann, was wertvoll ist, wenn eine Neuübertragung langsam oder unmöglich ist.

Warum verwenden Netzwerke CRCs anstelle einfacher Parität?

Ein einzelnes Paritätsbit übersieht jede gerade Anzahl von Bitfehlern, während eine zyklische Redundanzprüfung, basierend auf Polynomdivision, alle Einzelbitfehler, alle Doppelbitfehler und alle Bündelfehler, die kürzer als die Prüfung sind, erkennt, was sie für die Arten von Fehlern, die Verbindungen tatsächlich erzeugen, wesentlich stärker macht.