Hamming-Code: Beispiele für Fehlerkorrekturen

Inhaltsverzeichnis:

Anonim

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 größte Teil der Datenübertragung in digitalen Systemen erfolgt in Form einer "Bitübertragung". Schon kleine Änderungen können die Leistung des gesamten Systems beeinträchtigen. Wenn in einer Datensequenz 1 in 0 oder 0 in 1 geändert wird, wird dies als "Bitfehler" bezeichnet.

In diesem Hamming-Code-Tutorial lernen Sie:

  • Was ist ein Fehler?
  • Arten von Fehlern
  • Was ist Fehlererkennung und -korrektur?
  • Was ist ein Hamming-Code?
  • Geschichte des Hamming-Codes
  • Anwendung des Hemming-Codes:
  • Vorteile des Hamming-Codes
  • Nachteile des Hamming-Codes
  • Prozess der Codierung einer Nachricht mit Hamming-Code
  • Prozess zum Entschlüsseln einer Nachricht im Hamming-Code

Arten von Fehlern

Es gibt hauptsächlich drei Arten von Bitfehlern, die bei der Datenübertragung vom Sender zum Empfänger auftreten.

  • Einzelbitfehler
  • Mehrbitfehler
  • Burst-Fehler

Einzelbitfehler

Die in einem Bit in der gesamten Datensequenz vorgenommene Änderung 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 Daten bitweise in einer einzelnen Zeile übertragen werden. Daher besteht eine größere Wahrscheinlichkeit, dass eine einzelne Leitung verrauscht.

Mehrfachbitfehler

Wenn sich in der Datensequenz zwei oder mehr Bits einer Datensequenz eines Senders zum Empfänger ändern, spricht man von "Mehrfachbitfehlern".

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

Burst-Fehler

Die Änderung des Satzes von Bits in der Datensequenz ist als "Burst-Fehler" bekannt. Diese Art von Datenfehler wird von der Änderung des ersten Bits bis zur Änderung des letzten Bits berechnet.

Was ist Fehlererkennung und -korrektur?

In einem digitalen Kommunikationssystem werden Fehler von einem Kommunikationssystem in ein anderes übertragen. Wenn diese Fehler nicht erkannt und behoben werden, gehen die Daten verloren. Für eine effektive Kommunikation sollten Systemdaten mit hoher Genauigkeit übertragen werden. Dies erfolgt, indem zuerst die Fehler identifiziert und korrigiert werden.

Die Fehlererkennung ist ein Verfahren zum Erkennen der Fehler, die in den von einem Sender zum Empfänger übertragenen Daten in einem Datenkommunikationssystem vorhanden sind.

Hier können Sie Redundanzcodes verwenden, um diese Fehler zu finden, indem Sie die Daten hinzufügen, wenn sie von der Quelle übertragen werden. Diese Codes werden als "Fehlererkennungscodes" bezeichnet.

Drei Arten von Fehlererkennungscodes sind:

  • Paritätsprüfung
  • Cyclic Redundancy Check (CRC)
  • Longitudinal Redundancy Check (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 ist das redundante Bit als Paritätsbit bekannt. 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 ist 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 Folge von Redundanz, die an das Ende des Geräts 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 Nummer geteilt werden. Falls kein Rest vorhanden ist, wird die Dateneinheit als korrekt angenommen und akzeptiert. Andernfalls wird angezeigt, dass die Dateneinheit bei der Übertragung beschädigt wurde und daher zurückgewiesen werden muss.

Was ist ein Hamming-Code?

Hamming-Code ist ein Liner-Code, der zur Fehlererkennung von bis zu zwei unmittelbaren Bitfehlern nützlich ist. Es kann Einzelbitfehler verursachen.

Im Hamming-Code codiert die Quelle die Nachricht durch Hinzufügen redundanter Bits zur Nachricht. Diese redundanten Bits werden meistens an bestimmten Stellen in der Nachricht eingefügt und erzeugt, um einen Fehlererkennungs- und Korrekturprozess durchzuführen.

Geschichte des Hamming-Codes

  • Hamming-Code ist eine Technik, die von RWHamming entwickelt wurde, um Fehler zu erkennen.
  • Hamming-Code sollte auf Dateneinheiten beliebiger Länge angewendet werden und verwendet die Beziehung zwischen Daten und Redundanzbits.
  • Er arbeitete am Problem der Fehlerkorrekturmethode und entwickelte eine immer leistungsfähigere Reihe von Algorithmen namens Hamming-Code.
  • 1950 veröffentlichte er den Hamming-Code, der heute in Anwendungen wie dem ECC-Speicher weit verbreitet ist.

Anwendung des Hamming-Codes

Hier sind einige gängige Anwendungen für die Verwendung von Hemming-Code:

  • Satelliten
  • Computerspeicher
  • Modems
  • PlasmaCAM
  • Stecker öffnen
  • Abschirmdraht
  • Eingebetteter Prozessor

Vorteile des Hamming-Codes

  • Die Hamming-Code-Methode ist in Netzwerken wirksam, in denen die Datenströme für die 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.
  • Die einfache Verwendung von Hamming-Codes macht sie am besten für die Verwendung im Computerspeicher und zur Korrektur einzelner Fehler geeignet.

Nachteile des Hamming-Codes

  • Einzelbit-Fehlererkennungs- und Korrekturcode. Wenn jedoch mehrere Bits als Fehler begründet sind, kann das Ergebnis zu einem anderen Bit führen, das korrekt sein sollte, um geändert zu werden. Dies kann dazu führen, dass die Daten weiter fehlerhaft sind.
  • Der Hamming-Code-Algorithmus kann nur Einzelbitprobleme lösen.

Prozess der Codierung einer Nachricht mit Hamming-Code

Der vom Absender zum Codieren der Nachricht verwendete Prozess umfasst die folgenden drei Schritte:

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

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.

Angenommen, die Nachricht enthält:

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

Hier zeigt (n + p) den Ort eines Fehlers in jeder der (n + p) Bitpositionen und ein zusätzlicher Zustand zeigt keinen Fehler an. Als p Bits 2 zeigt , kann p Zustände, 2 p hat mindestens gleich (n + p + 1).

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

Die p redundanten Bits sollten an Bitpositionen mit Potenzen von 2 platziert werden. Zum Beispiel 1, 2, 4, 8, 16 usw. Sie werden als p 1 (an Position 1), p 2 (an Position 2) bezeichnet. , p 3 (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 wird.

Die zwei Arten der Parität sind -

  • Die Gesamtzahl der Bits in der Nachricht, die gerade gemacht wird, wird als gerade Parität bezeichnet.
  • Die Gesamtzahl der ungeraden 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 mit Ausnahme der Position von p1 enthalten sollte.

P1 ist das Paritätsbit für jedes Datenbit an Positionen, deren binäre Darstellung eine 1 an der weniger wichtigen Position ohne 1 Like (3, 5, 7, 9,

…. )

P2 ist das Paritätsbit für jedes Datenbit an Positionen, deren binäre Darstellung 1 an der Position 2 von rechts enthält, ohne 2 Like (3, 6, 7, 10, 11,

…)

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

…)

Prozess zum Entschlüsseln einer Nachricht im Hamming-Code

Der Empfänger erhält eingehende Nachrichten, die neu berechnet werden müssen, um Fehler zu finden und zu korrigieren.

Der Neuberechnungsprozess erfolgt in den folgenden Schritten:

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

Schritt 1) Zählen der Anzahl redundanter Bits

Sie können dieselbe Formel für die Codierung verwenden, die Anzahl der redundanten Bits

2 p ≥ n + p + 1

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

Schritt 2) Alle redundanten Bits richtig positionieren

Hier ist p ein redundantes Bit, das sich an Bitpositionen mit Potenzen von 2 befindet, zum Beispiel 1, 2, 4, 8 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 3) Burst-Bitfehler
  • Die in einem Bit in der gesamten Datensequenz vorgenommene Änderung wird als "Einzelbitfehler" bezeichnet.
  • Wenn sich in der Datensequenz zwei oder mehr Bits einer Datensequenz eines Senders zum Empfänger ändern, spricht man von "Mehrfachbitfehlern".
  • Die Änderung des Satzes von Bits in der Datensequenz ist als "Burst-Fehler" bekannt.
  • Die Fehlererkennung ist ein Verfahren zum Erkennen der Fehler, die in den von einem Sender zum Empfänger übertragenen Daten in einem Datenkommunikationssystem vorhanden sind
  • Drei Arten von Fehlererkennungscodes sind: 1) Paritätsprüfung 2) Zyklische Redundanzprüfung (CRC) 3) Längsredundanzprüfung (LRC)
  • Hamming-Code ist ein Liner-Code, der zur Fehlererkennung von bis zu zwei unmittelbaren Bitfehlern nützlich ist. Es kann Einzelbitfehler verursachen.
  • Hamming-Code ist eine Technik, die von RWHamming entwickelt wurde, um Fehler zu erkennen.
  • Häufige Anwendungen für die Verwendung von Hemming-Code sind Satelliten-Computerspeicher, Modems, eingebetteter Prozessor usw.
  • Der größte Vorteil der Hamming-Code-Methode besteht in Netzwerken, in denen die Datenströme für die Einzelbitfehler angegeben werden.
  • Der größte Nachteil der Hamming-Code-Methode besteht darin, dass nur Einzelbit-Probleme gelöst werden können.
  • Wir können den Prozess des Verschlüsselns und Entschlüsselns der Nachricht mit Hilfe von Hamming-Code durchführen.