Hamming CodeFehlererkennung und -korrektur mit Beispielen

Was ist ein Fehler?

TransmitDaten können während der Übertragung beschädigt werden. Sie können durch externe Störungen oder andere physikalische Defekte beeinträchtigt werden. In einem solchen Fall stimmen die Eingangsdaten nicht mit den Ausgangsdaten überein. Diese Diskrepanz wird als „Fehler“ bezeichnet.

Datenfehler können zum Verlust wichtiger oder vertraulicher Daten führen. Der Großteil der Datenübertragung in digitalen Systemen erfolgt als „Bitübertragung“, und selbst die geringfügige Änderung eines einzelnen Bits kann die Leistung des gesamten Systems beeinträchtigen. Wird in einer Datensequenz eine 1 in eine 0 oder eine 0 in eine 1 geändert, spricht man von einem „Bitfehler“.

Arten von Fehlern

Es gibt hauptsächlich drei Arten von Bitfehlern, die bei der Datenverarbeitung auftreten. transmitvom Sender zum Empfänger übertragen. Das folgende Diagramm veranschaulicht, wie sich die einzelnen Typen auf eine Datensequenz auswirken:

• Einzelbitfehler
• Mehrere Bitfehler
• Burst-Fehler

Einzelbitfehler

Eine Änderung an einem einzelnen Bit in der gesamten Datensequenz wird als „Einzelbitfehler“ bezeichnet. Einzelbitfehler treten nicht häufig auf. Sie kommen hauptsächlich in parallelen Kommunikationssystemen vor, da die Daten bitweise über separate Leitungen übertragen werden. Dadurch ist die Wahrscheinlichkeit höher, dass eine Leitung verrauscht wird, während die anderen fehlerfrei bleiben.

Mehrere Bitfehler

Wenn sich zwei oder mehr Bits einer Datensequenz zwischen den transmitWenn zwischen dem Empfänger und dem Empfänger ein Fehler auftritt, spricht man von einem „Mehrbitfehler“.

Dieser Fehlertyp tritt sowohl in seriellen als auch in parallelen Datenkommunikationsnetzen auf.

Burst-Fehler

Eine Änderung an einer Gruppe aufeinanderfolgender Bits in einer Datensequenz wird als „Burst-Fehler“ bezeichnet. Die Länge eines Burst-Fehlers wird vom ersten geänderten Bit bis zum letzten geänderten Bit gemessen.

Was versteht man unter Fehlererkennung und Fehlerkorrektur?

In digitalen Kommunikationssystemen können Fehler bei der Datenübertragung zwischen Geräten auftreten. Werden diese Fehler nicht erkannt und korrigiert, gehen die Daten verloren. Für eine effektive Kommunikation ist eine hohe Genauigkeit der Datenübertragung unerlässlich. Dies wird erreicht, indem Fehler zunächst identifiziert und anschließend korrigiert werden.

Fehlererkennung ist eine Methode, um die in den Daten vorhandenen Fehler zu finden. transmitted von einem transmitan einen Empfänger in einem Datenkommunikation System.

Redundanzcodes werden verwendet, um diese Fehler zu finden, indem den Daten zusätzliche Bits hinzugefügt werden, wenn sie transmitDiese zusätzlichen Bits werden von der Quelle übernommen und als „Fehlererkennungscodes“ bezeichnet. Die drei gebräuchlichsten Arten von Fehlererkennungscodes sind:

• Paritätsprüfung
• Zyklische Redundanzprüfung (CRC)
• Längsredundanzprüfung (LRC)

Paritätsprüfung

• Es wird auch als Paritätsprüfung bezeichnet.
• Es bietet einen kostengünstigen Mechanismus zur Fehlererkennung.
• Bei dieser Technik wird das jeder Dateneinheit hinzugefügte redundante Bit als Paritätsbit bezeichnet. Es wird so gesetzt, dass die Gesamtzahl der Einsen in der Einheit gerade (gerade Parität) oder ungerade (ungerade Parität) ist.

Längsredundanzprüfung

Bei diesem Fehlererkennungsverfahren wird ein Bitblock in einer Tabelle organisiert. Das LRC-Verfahren berechnet für jede Spalte ein Paritätsbit, und dieser Satz von Paritätsbits wird zusammen mit den Originaldaten gesendet. Der Paritätsbitblock hilft dem Empfänger, Redundanz zu prüfen und Fehler zu erkennen.

Zyklische Redundanzprüfung

Bei der zyklischen Redundanzprüfung wird eine Folge redundanter Bits an das Ende der Dateneinheit angehängt, sodass die resultierende Dateneinheit genau durch eine zweite, vorbestimmte Binärzahl teilbar ist.

Am Zielort werden die eingehenden Daten durch dieselbe Zahl geteilt. Ergibt sich kein Rest, gilt die Dateneinheit als korrekt und wird akzeptiert. Andernfalls deutet dies darauf hin, dass die Dateneinheit bei der Übertragung beschädigt wurde und verworfen werden muss.

Was ist ein Hamming? Code?

Der Hamming-Code ist ein linearer Code, der sich zur Erkennung von bis zu zwei aufeinanderfolgenden Bitfehlern und zur Korrektur von Einzelbitfehlern eignet. Die Fehlerkorrektur dieser Art erfolgt typischerweise auf der Sicherungsschicht (Data Link Layer), indem sie Daten rahmt und deren Integrität zwischen benachbarten Knoten überprüft.

Beim Hamming-Code wird die Nachricht durch Hinzufügen redundanter Bits codiert. Diese redundanten Bits werden an bestimmten Positionen in der Nachricht eingefügt und generiert, um Fehler zu erkennen und zu korrigieren.

Geschichte von Hamming Code

• Der Hamming-Code ist eine von R. W. Hamming entwickelte Technik zur Erkennung und Korrektur von Fehlern.
• Es kann auf Dateneinheiten beliebiger Länge angewendet werden und nutzt die Beziehung zwischen Datenbits und Redundanzbits.
• Hamming beschäftigte sich mit dem Problem der Fehlerkorrektur und entwickelte eine immer leistungsfähigere Reihe von Algorithmen.
• Im Jahr 1950 veröffentlichte er den Hamming-Code, der auch heute noch in Anwendungen wie ECC-Speicher weit verbreitet ist.

Anwendungen der Hamming-Methode Code

Hier einige gängige Anwendungsgebiete des Hamming-Codes:

• Satelliten
• Computerspeicher (ECC RAM)
• Modem
• PlasmaCAM
• Offene Anschlüsse
• Abgeschirmtes Kabel
• Eingebettete Prozessoren

Vorteile der Hamming-Methode Code

• Hamming-Code ist effektiv in Netzwerken, in denen Datenströme Einzelbitfehlern ausgesetzt sind.
• Es erkennt nicht nur Bitfehler, sondern hilft Ihnen auch dabei, das fehlerhafte Bit zu identifizieren, damit es korrigiert werden kann.
• Aufgrund ihrer einfachen Anwendbarkeit eignen sich Hamming-Codes hervorragend für Computerspeicher und die Korrektur einzelner Fehler.

Nachteile der Hamming-Methode Code

• Es handelt sich um einen Einzelbit-Fehlererkennungs- und -korrekturcode. Werden mehrere fehlerhafte Bits gefunden, kann das Ergebnis ein weiteres, eigentlich korrektes Bit umkehren und die Daten dadurch weiter verfälschen.
• Der Hamming-Code-Algorithmus kann nur Einzelbit-Probleme lösen.

Wie man eine Nachricht in Hamming kodiert Code

Der vom Absender verwendete Prozess zur Kodierung der Nachricht umfasst die folgenden drei Schritte:

• Berechnen Sie die Gesamtzahl der redundanten Bits.
• Ermitteln Sie die Position der redundanten Bits.
• Berechne den Wert jedes redundanten Bits.

Wenn die redundanten Bits in die Nachricht eingebettet sind, wird das vollständige Codewort an den Empfänger gesendet.

Schritt 1) ​​Berechnen Sie die Gesamtzahl der redundanten Bits.

Angenommen, die Nachricht enthält n Datenbits und p redundante Bits, hinzugefügt, so dass 2^p kann mindestens (n ​​+ p + 1) verschiedene Zustände anzeigen.

Hierbei berücksichtigt (n + p) die Position eines Fehlers an jeder der (n + p) Bitpositionen, und ein zusätzlicher Zustand bedeutet, dass kein Fehler vorliegt. Da p Paritätsbits 2ⁿ anzeigen können, …^p Staaten, 2^p muss mindestens gleich (n + p + 1) sein.

Schritt 2) Platzieren Sie die redundanten Bits an ihren richtigen Positionen.

Die p redundanten Bits werden an Bitpositionen platziert, die Zweierpotenzen sind – beispielsweise 1, 2, 4, 8 und 16. Sie werden als p bezeichnet.₁ (an Position 1), S₂ (an Position 2), S₃ (an Position 4) und so weiter.

Schritt 3) Berechne den Wert jedes redundanten Bits.

Jedes redundante Bit ist ein Paritätsbit, das die Anzahl der Einsen in seiner Gruppe entweder gerade oder ungerade macht. Es gibt zwei Arten von Paritätsbits:

• Gleichstellung: Die Gesamtzahl der Einsen in den abgedeckten Positionen wird ausgeglichen.
• Ungerade Parität: Die Gesamtzahl der Einsen in den abgedeckten Positionen ist ungerade.

Jedes Paritätsbit deckt einen bestimmten Satz von Positionen ab, der durch die Binärdarstellung der Positionsnummern bestimmt wird:

• p₁ Überprüft jede Position, deren Binärwert im niedrigstwertigen Bit eine 1 hat – Positionen 1, 3, 5, 7, 9, 11 usw.
• p₂ Überprüft jede Position, deren Binärwert im zweiten Bit von rechts eine 1 hat – Positionen 2, 3, 6, 7, 10, 11 usw.
• p₃ Überprüft jede Position, deren Binärwert im dritten Bit von rechts eine 1 hat – Positionen 4 bis 7, 12 bis 15 usw.

Durchgerechnetes Beispiel (7,4): Betrachten wir die vier Datenbits 1011Es werden drei Paritätsbits benötigt (2³ = 8 ≥ 4 + 3 + 1), was ein sieben Bit langes Codewort ergibt, das wie folgt aufgebaut ist: p₁ p₂ d₁ p₃ d₂ d₃ d₄Durch die Anordnung der Daten ergeben sich die Positionen 3, 5, 6, 7 = 1, 0, 1, 1. Bei Verwendung gerader Parität: p₁ deckt die Positionen 1, 3, 5, 7 ab (Bits 1, 0, 1 → p).₁ = 0); p₂ deckt 2, 3, 6, 7 ab (Bits 1, 1, 1 → p₂ = 1); p₃ deckt 4, 5, 6, 7 ab (Bits 0, 1, 1 → p₃ = 0). transmitDas Codewort lautet daher 0110011.

Wie man eine Nachricht in Hamming entschlüsselt Code

Der Empfänger nimmt die eingehende Nachricht entgegen und führt Neuberechnungen durch, um Fehler zu finden und zu korrigieren. Der Neuberechnungsprozess umfasst die folgenden Schritte:

• Zähle die Anzahl der redundanten Bits.
• Positionieren Sie alle redundanten Bits korrekt.
• Führen Sie die Paritätsprüfung durch.

Schritt 1) ​​Zählen Sie die Anzahl der redundanten Bits. Verwenden Sie dieselbe Formel wie für die Kodierung: 2^p ≥ n + p + 1, wobei n die Anzahl der Datenbits und p die Anzahl der redundanten Bits ist.

Schritt 2) Positionieren Sie alle redundanten Bits korrekt. Jedes redundante Bit befindet sich an einer Bitposition, die eine Zweierpotenz ist – zum Beispiel 1, 2, 4 und 8.

Schritt 3) Führen Sie die Paritätsprüfung durch. Die Paritätsbits werden aus den Datenbits und den empfangenen redundanten Bits neu berechnet:

• p₁ = Parität(1, 3, 5, 7, 9, 11, …)
• p₂ = Parität(2, 3, 6, 7, 10, 11, …)
• p₃ = Parität(4–7, 12–15, 20–23, …)

Die neu berechneten Paritätsbits bilden zusammen eine Binärzahl. Ist diese Zahl null, liegt kein Fehler vor; andernfalls gibt ihr Wert die genaue Position des einzelnen fehlerhaften Bits an, welches dann invertiert wird, um die Nachricht zu korrigieren.

Häufig gestellte Fragen