Hamming-Code: Fehlererkennung und -korrektur mit Beispielen

Was ist ein Fehler?

Übertragene Daten können während der Kommunikation beschädigt werden. Es ist wahrscheinlich, dass es durch externe Geräusche oder andere physische Fehler beeinträchtigt wird. In einer solchen Situation können die Eingabedaten nicht mit den Ausgabedaten identisch sein. Diese Nichtübereinstimmung wird als „Fehler“ bezeichnet.

Die Datenfehler können zum Verlust wichtiger oder sicherer Daten führen. Der Großteil der Datenübertragung in digitalen Systemen erfolgt in Form einer „Bitübertragung“. Schon eine kleine Änderung kann die Leistung des gesamten Systems beeinträchtigen. Wenn in einer Datensequenz 1 in 0 oder 0 in 1 geändert wird, spricht man von einem „Bitfehler“.

Arten von Fehlern

Bei der Datenübertragung vom Sender zum Empfänger treten im Wesentlichen drei Arten von Bitfehlern auf.

• Einzelbitfehler
• Mehrere Bitfehler
• Burst-Fehler

Einzelbitfehler

Die Änderung eines Bits in der gesamten Datensequenz wird als „Einzelbitfehler“ bezeichnet. Das Auftreten eines Einzelbitfehlers ist jedoch nicht so häufig. Darüber hinaus tritt dieser Fehler nur in einem parallelen Kommunikationssystem auf, da die Daten bitweise in einer einzigen Leitung übertragen werden. Daher besteht eine größere Wahrscheinlichkeit, dass eine einzelne Leitung verrauscht sein kann.

Mehrere Bitfehler

Wenn sich in der Datensequenz zwei oder mehr Bits einer Datensequenz vom Sender zum Empfänger ändern, spricht man von „Mehrbitfehlern“.

Diese Art von Fehler tritt meist sowohl in seriellen als auch in parallelen Datenkommunikationsnetzwerken auf.

Burst-Fehler

Die Änderung des Bitsatzes in der Datensequenz wird als „Burst-Fehler“ bezeichnet. Diese Art von Datenfehler wird von der ersten Bitänderung bis zur letzten Bitänderung berechnet.

Was ist Fehlererkennung und Fehlerkorrektur?

In digitalen Kommunikationssystemen werden Fehler von einem Kommunikationssystem auf ein anderes übertragen. Werden diese Fehler nicht erkannt und behoben, gehen die Daten verloren. Für eine effektive Kommunikation sollten Systemdaten mit hoher Genauigkeit übertragen werden. Dies geschieht, indem zunächst die Fehler identifiziert und behoben werden.

Die Fehlererkennung ist eine Methode zur Erkennung von Fehlern, die in den von einem Sender an einen Empfänger in einem Datenkommunikationssystem übertragenen Daten vorhanden sind.

Hier können Sie Redundanzcodes verwenden, um diese Fehler zu finden, indem Sie sie bei der Übertragung von der Quelle zu den Daten hinzufügen. Diese Codes werden als „Fehlererkennungscodes“ bezeichnet.

Drei 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 verfügt über einen kostengünstigen Mechanismus zur Fehlererkennung.
• Bei dieser Technik wird das redundante Bit als Paritätsbit bezeichnet. Es wird für jede Dateneinheit angehängt. Die Gesamtzahl der Einsen in der Einheit sollte gerade werden, was als Paritätsbit bezeichnet wird.

Längsredundanzprüfung

Bei dieser Fehlererkennungstechnik wird ein Bitblock im Tabellenformat organisiert. Mit der LRC-Methode können Sie das Paritätsbit für jede Spalte berechnen. Der Satz dieser Parität wird auch zusammen mit den Originaldaten gesendet. Der Paritätsblock hilft Ihnen, die Redundanz zu überprüfen.

Zyklische Redundanzprüfung

Die zyklische Redundanzprüfung ist eine Redundanzsequenz, die am Ende der Einheit angehängt werden muss. Deshalb sollte die resultierende Dateneinheit durch eine zweite, vorgegebene Binärzahl teilbar werden.

Am Ziel müssen die eingehenden Daten durch dieselbe Zahl geteilt werden. Wenn kein Rest übrig bleibt, wird davon ausgegangen, dass die Dateneinheit korrekt ist und akzeptiert wird. Andernfalls weist dies darauf hin, dass die Dateneinheit bei der Übertragung beschädigt wurde und daher abgelehnt werden muss.

Im Hamming-Code kodiert die Quelle die Nachricht, indem sie redundante Bits in die Nachricht einfügt. Diese redundanten Bits werden meist an bestimmten Positionen in der Nachricht eingefügt und generiert, um einen Fehlererkennungs- und -korrekturprozess durchzuführen.

Geschichte des Hamming-Codes

• Hamming-Code ist eine von RWHamming entwickelte Technik zur Fehlererkennung.
• Hamming-Code sollte auf Dateneinheiten beliebiger Länge angewendet werden und nutzt die Beziehung zwischen Daten und Redundanzbits.
• Er arbeitete am Problem der Fehlerkorrekturmethode und entwickelte eine zunehmend leistungsfähigere Reihe von Algorithmen, die als Hamming-Codes bezeichnet werden.
• 1950 veröffentlichte er den Hamming-Code, der heute in Anwendungen wie dem ECC-Speicher weit verbreitet ist.

Anwendung von Hamming-Code

Hier sind einige häufige Anwendungen der Verwendung von Hamming-Code:

• Satelliten
• Computerspeicher
• Modem
• PlasmaCAM
• Offene Anschlüsse
• Abschirmdraht
• Eingebetteter Prozessor

Vorteile von Hamming-Code

• Die Hamming-Code-Methode ist in Netzwerken effektiv, in denen die Datenströme für Einzelbitfehler angegeben sind.
• Hamming-Code ermöglicht nicht nur die Erkennung eines Bitfehlers, sondern hilft Ihnen auch dabei, fehlerhaltige Bits einzurücken, damit sie korrigiert werden können.
• Aufgrund ihrer Benutzerfreundlichkeit eignen sich Hamming-Codes am besten für den Einsatz im Computerspeicher und für die Einzelfehlerkorrektur.

Nachteile von Hamming-Code

• Code zur Erkennung und Korrektur von Einzelbitfehlern. Wenn jedoch mehrere Bits fehlerhaft sind, kann das Ergebnis dazu führen, dass ein anderes Bit geändert wird, das korrekt sein sollte. Dies kann dazu führen, dass die Daten noch fehlerhafter werden.
• Der Hamming-Code-Algorithmus kann nur Einzelbitprobleme lösen.

So kodieren Sie eine Nachricht im Hamming-Code

Der vom Absender verwendete Prozess zum Verschlüsseln der Nachricht umfasst die folgenden drei Schritte:

• Berechnung der Gesamtzahl redundanter Bits.
• Überprüfung der Position der redundanten Bits.
• Zuletzt berechnen wir die Werte dieser redundanten Bits.

Wenn die oben genannten redundanten Bits in die Nachricht eingebettet sind, wird sie an den Benutzer gesendet.

Schritt 1) Berechnung der Gesamtzahl der redundanten Bits.

Nehmen wir an, dass die Nachricht Folgendes enthält:

• n– Anzahl der Datenbits
• p – Anzahl der redundanten Bits, die hinzugefügt werden, damit np mindestens (n ​​+ p + 1) verschiedene Zustände anzeigen kann.

Hier stellt (n + p) die Position eines Fehlers in jeder der (n + p) Bitpositionen dar und ein zusätzlicher Zustand zeigt an, dass kein Fehler vorliegt. Da p Bits 2 anzeigen können^p Staaten, 2^p muss mindestens gleich (n + p + 1) sein.

Schritt 2) Platzieren Sie die redundanten Bits an der richtigen Position.

Die p redundanten Bits sollten an Bitpositionen mit Zweierpotenzen platziert werden, zum Beispiel 2, 1, 2, 4, 8 usw. Sie werden als p bezeichnet₁ (an Position 1), S₂ (an Position 2), S₃ (an Position 4) usw.

Schritt 3) Berechnung der Werte des redundanten Bits.

Die redundanten Bits sollten Paritätsbits sein, wodurch die Anzahl der Einsen entweder gerade oder ungerade ist.

Die beiden Arten der Parität sind ?

• Wenn die Gesamtzahl der Bits in der Nachricht gleich ist, nennt man das gerade Parität.
• Die ungerade Gesamtzahl der Bits in der Nachricht wird als ungerade Parität bezeichnet.

Hier muss das gesamte redundante Bit p1 als Parität berechnet werden. Es sollte alle Bitpositionen abdecken, deren binäre Darstellung eine 1 an der 1. Position enthalten sollte, mit Ausnahme der Position von p1.

P1 ist das Paritätsbit für alle Datenbits an Positionen, deren binäre Darstellung eine 1 an der weniger wichtigen Position ohne 1 enthält, z. B. (3, 5, 7, 9, …).

P2 ist das Paritätsbit für alle Datenbits an Positionen, deren binäre Darstellung 1 an der Position 2 von rechts enthält, ohne 2 wie (3, 6, 7, 10, 11,…)

P3 ist das Paritätsbit für jedes Bit an Positionen, deren binäre Darstellung eine 1 an der Position 3 von rechts enthält, ohne 4 wie (5-7, 12-15,…).

Entschlüsseln einer Nachricht im Hamming-Code

Der Empfänger empfängt eingehende Nachrichten, die Neuberechnungen durchführen müssen, um Fehler zu finden und zu korrigieren.

Der Neuberechnungsprozess erfolgt in folgenden Schritten:

• Zählen der Anzahl redundanter Bits.
• Korrekte Positionierung aller redundanten Bits.
• Paritätsprüfung

Schritt 1) Zählen der Anzahl redundanter Bits

Sie können dieselbe Formel zum Codieren verwenden, nämlich die Anzahl der redundanten Bits

2^p ? n + p + 1

Dabei ist die Anzahl der Datenbits und p die Anzahl der redundanten Bits.

Schritt 2) Alle redundanten Bits richtig platzieren

Hier ist p ein redundantes Bit, das sich an Bitpositionen mit Zweierpotenzen befindet, zum Beispiel 2, 1, 2, 4 usw.

Schritt 3) Paritätsprüfung

Paritätsbits müssen basierend auf Datenbits und den redundanten Bits berechnet werden.

p1 = Parität (1, 3, 5, 7, 9, 11…)

p2 = Parität(2, 3, 6, 7, 10, 11…)

p3 = Parität (4-7, 12-15, 20-23…)

Zusammenfassung

• Übertragene Daten können während der Kommunikation beschädigt werden
• Drei Arten von Bitfehlern sind 1) Einzelbitfehler, 2) Mehrfachbitfehler und 3) Burst-Bitfehler
• Die Änderung eines Bits in der gesamten Datensequenz wird als „Einzelbitfehler“ bezeichnet.
• Wenn sich in der Datensequenz zwei oder mehr Bits einer Datensequenz vom Sender zum Empfänger ändern, spricht man von „Mehrbitfehlern“.
• Die Änderung des Bitsatzes in der Datensequenz wird als „Burst-Fehler“ bezeichnet.
• Die Fehlererkennung ist eine Methode zur Erkennung von Fehlern, die in den von einem Sender an einen Empfänger in einem Datenkommunikationssystem übertragenen Daten vorhanden sind
• Drei Arten von Fehlererkennungscodes sind 1) Paritätsprüfung, 2) zyklische Redundanzprüfung (CRC), 3) longitudinale Redundanzprüfung (LRC).
• Hamming-Code ist ein Liner-Code, der zur Fehlererkennung von bis zu zwei unmittelbaren Bitfehlern nützlich ist. Es ist zu Einzelbitfehlern fähig.
• Hamming-Code ist eine von RWHamming entwickelte Technik zur Fehlererkennung.
• Häufige Anwendungen für die Verwendung von Hamming-Code sind Computerspeicher von Satelliten, Modems, eingebettete Prozessoren usw.
• Der größte Vorteil der Hamming-Code-Methode ist in Netzwerken wirksam, in denen die Datenströme für Einzelbitfehler angegeben sind.
• Der größte Nachteil der Hamming-Code-Methode besteht darin, dass sie nur Einzelbitprobleme lösen kann.
• Wir können den Prozess der Verschlüsselung und Dekodierung der Nachricht mithilfe von Hamming-Code durchführen.