Fehlererkennungs- und Korrekturcodes
Wir wissen, dass die Bits 0 und 1 zwei verschiedenen analogen Spannungsbereichen entsprechen. Während der Übertragung von Binärdaten von einem System zum anderen kann also auch das Rauschen hinzugefügt werden. Aus diesem Grund können Fehler in den empfangenen Daten auf einem anderen System auftreten.
Das bedeutet, dass sich ein Bit 0 in 1 oder ein Bit 1 in 0 ändern kann. Wir können die Störung durch Rauschen nicht vermeiden. Wir können jedoch zuerst die Originaldaten zurückerhalten, indem wir feststellen, ob Fehler vorliegen, und diese Fehler dann korrigieren. Zu diesem Zweck können wir die folgenden Codes verwenden.
- Fehlererkennungscodes
- Fehlerkorrekturcodes
Error detection codes- werden verwendet, um die in den empfangenen Daten vorhandenen Fehler (Bitstrom) zu erkennen. Diese Codes enthalten einige Bits, die im ursprünglichen Bitstrom enthalten (angehängt) sind. Diese Codes erkennen den Fehler, wenn er während der Übertragung der Originaldaten (Bitstrom) auftritt.Example - Paritätscode, Hamming-Code.
Error correction codes- werden verwendet, um die in den empfangenen Daten (Bitstrom) vorhandenen Fehler zu korrigieren, damit wir die Originaldaten erhalten. Fehlerkorrekturcodes verwenden ebenfalls die ähnliche Strategie von Fehlererkennungscodes.Example - Hamming-Code.
Um die Fehler zu erkennen und zu korrigieren, werden daher zum Zeitpunkt der Übertragung zusätzliche Bits an die Datenbits angehängt.
Paritätscode
Es ist einfach, ein Paritätsbit entweder links von MSB oder rechts von LSB des ursprünglichen Bitstroms einzufügen (anzuhängen). Es gibt zwei Arten von Paritätscodes, nämlich geraden Paritätscode und ungeraden Paritätscode, basierend auf dem gewählten Paritätstyp.
Sogar Paritätscode
Der Wert des geraden Paritätsbits sollte Null sein, wenn im Binärcode eine gerade Anzahl von Einsen vorhanden ist. Ansonsten sollte es einer sein. Damit sind auch nur wenige anwesendeven parity code. Ein gerader Paritätscode enthält die Datenbits und ein gerades Paritätsbit.
Die folgende Tabelle zeigt die even parity codesentsprechend jedem 3-Bit-Binärcode. Hier ist das gerade Paritätsbit rechts vom LSB des Binärcodes enthalten.
| Binärcode | Sogar Paritätsbit | Sogar Paritätscode |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Hier beträgt die Anzahl der in den geraden Paritätscodes vorhandenen Bits 4. Die mögliche gerade Anzahl von Bits in diesen geraden Paritätscodes beträgt also 0, 2 und 4.
Wenn das andere System einen dieser geraden Paritätscodes empfängt, liegt kein Fehler in den empfangenen Daten vor. Die anderen Bits als das gerade Paritätsbit sind die gleichen wie die des Binärcodes.
Wenn das andere System andere als gerade Paritätscodes empfängt, gibt es einen Fehler in den empfangenen Daten. In diesem Fall können wir den ursprünglichen Binärcode nicht vorhersagen, da wir die Bitposition (en) des Fehlers nicht kennen.
Daher ist ein gerades Paritätsbit nur zur Erkennung eines Fehlers im empfangenen Paritätscode nützlich. Es reicht jedoch nicht aus, den Fehler zu korrigieren.
Ungerader Paritätscode
Der Wert des ungeraden Paritätsbits sollte Null sein, wenn eine ungerade Anzahl von Einsen im Binärcode vorhanden ist. Ansonsten sollte es einer sein. Damit ist eine ungerade Anzahl von Personen vorhandenodd parity code. Der ungerade Paritätscode enthält die Datenbits und das ungerade Paritätsbit.
Die folgende Tabelle zeigt die odd parity codesentsprechend jedem 3-Bit-Binärcode. Hier ist das ungerade Paritätsbit rechts vom LSB des Binärcodes enthalten.
| Binärcode | Ungerades Paritätsbit | Ungerader Paritätscode |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Hier beträgt die Anzahl der in den ungeraden Paritätscodes vorhandenen Bits 4. Die mögliche ungerade Anzahl von Einsen in diesen ungeraden Paritätscodes beträgt also 1 und 3.
Wenn das andere System einen dieser ungeraden Paritätscodes empfängt, liegt kein Fehler in den empfangenen Daten vor. Die anderen Bits als das ungerade Paritätsbit sind die gleichen wie die des Binärcodes.
Wenn das andere System andere als ungerade Paritätscodes empfängt, liegen Fehler in den empfangenen Daten vor. In diesem Fall können wir den ursprünglichen Binärcode nicht vorhersagen, da wir die Bitposition (en) des Fehlers nicht kennen.
Daher ist ein ungerades Paritätsbit nur zur Erkennung eines Fehlers im empfangenen Paritätscode nützlich. Es reicht jedoch nicht aus, den Fehler zu korrigieren.
Hamming Code
Der Hamming-Code ist sowohl zur Erkennung als auch zur Korrektur von Fehlern in den empfangenen Daten nützlich. Dieser Code verwendet mehrere Paritätsbits und wir müssen diese Paritätsbits an den Stellen der Potenzen von 2 platzieren.
Das minimum value of 'k' für die die folgende Beziehung korrekt (gültig) ist, ist nichts anderes als die erforderliche Anzahl von Paritätsbits.
$$ 2 ^ k \ geq n + k + 1 $$
Wo,
'n' ist die Anzahl der Bits im Binärcode (Information)
'k' ist die Anzahl der Paritätsbits
Daher ist die Anzahl der Bits im Hamming-Code gleich n + k.
Lassen Sie die Hamming codeist $ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ & Paritätsbits $ p_ {k}, p_ {k-1}, .... p_ {1} $. Wir können die 'k'-Paritätsbits nur in Potenzen von 2 Positionen platzieren. An den verbleibenden Bitpositionen können wir die 'n' Bits des Binärcodes platzieren.
Je nach Anforderung können wir beim Erstellen eines Hamming-Codes entweder gerade oder ungerade Parität verwenden. Es sollte jedoch dieselbe Paritätstechnik verwendet werden, um festzustellen, ob in den empfangenen Daten ein Fehler vorliegt.
Befolgen Sie diese Prozedur, um zu finden parity bits.
Finden Sie den Wert von p1, basierend auf der Anzahl von Einsen, die in den Bitpositionen b 3 , b 5 , b 7 usw. vorhanden sind. Alle diese Bitpositionen (Suffixe) in ihrer äquivalenten Binärdatei haben '1' im Stellenwert von 2 0 .
Finden Sie den Wert von p2, basierend auf der Anzahl von Einsen, die in den Bitpositionen b 3 , b 6 , b 7 usw. vorhanden sind. Alle diese Bitpositionen (Suffixe) in ihrer äquivalenten Binärdatei haben '1' im Stellenwert von 2 1 .
Finden Sie den Wert von p3, basierend auf der Anzahl von Einsen, die in den Bitpositionen b 5 , b 6 , b 7 usw. vorhanden sind. Alle diese Bitpositionen (Suffixe) in ihrer äquivalenten Binärdatei haben '1' im Stellenwert von 2 2 .
In ähnlicher Weise finden Sie andere Werte von Paritätsbits.
Befolgen Sie diese Prozedur, um zu finden check bits.
Finden Sie den Wert von c 1 basierend auf der Anzahl der an den Bitpositionen b 1 , b 3 , b 5 , b 7 usw. vorhandenen Einsen . Alle diese Bitpositionen (Suffixe) in ihrer äquivalenten Binärdatei haben '1' im Stellenwert von 2 0 .
Finden Sie den Wert von c 2 basierend auf der Anzahl der an den Bitpositionen b 2 , b 3 , b 6 , b 7 usw. vorhandenen Einsen . Alle diese Bitpositionen (Suffixe) in ihrer äquivalenten Binärdatei haben '1' im Stellenwert von 2 1 .
Finden Sie den Wert von c 3 basierend auf der Anzahl der an den Bitpositionen b 4 , b 5 , b 6 , b 7 usw. vorhandenen Einsen . Alle diese Bitpositionen (Suffixe) in ihrer äquivalenten Binärdatei haben '1' im Stellenwert von 2 2 .
Suchen Sie in ähnlicher Weise andere Werte von Prüfbits.
Das Dezimaläquivalent der Prüfbits in den empfangenen Daten gibt den Wert der Bitposition an, an der der Fehler vorliegt. Ergänzen Sie einfach den an dieser Bitposition vorhandenen Wert. Daher erhalten wir den ursprünglichen Binärcode nach dem Entfernen von Paritätsbits.
Beispiel 1
Finden wir den Hamming-Code für den Binärcode, d 4 d 3 d 2 d 1 = 1000. Betrachten Sie gerade Paritätsbits.
Die Anzahl der Bits im angegebenen Binärcode beträgt n = 4.
Wir können die erforderliche Anzahl von Paritätsbits unter Verwendung der folgenden mathematischen Beziehung finden.
$$ 2 ^ k \ geq n + k + 1 $$
Ersetzen Sie in der obigen mathematischen Beziehung n = 4.
$$ \ Rightarrow 2 ^ k \ geq 4 + k + 1 $$
$$ \ Rightarrow 2 ^ k \ geq 5 + k $$
Der Minimalwert von k, der die obige Beziehung erfüllt, ist 3. Daher benötigen wir 3 Paritätsbits p 1 , p 2 und p 3 . Daher beträgt die Anzahl der Bits im Hamming-Code 7, da der Binärcode 4 Bits und 3 Paritätsbits enthält. Wir müssen die Paritätsbits und Bits des Binärcodes wie unten gezeigt in den Hamming-Code einfügen.
Das 7-bit Hamming code ist $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} d_ {1 } p_ {2} bp_ {1} $
Durch Ersetzen der Bits des Binärcodes lautet der Hamming-Code $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2 } p_ {1} $. Lassen Sie uns nun die Paritätsbits finden.
$$ p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1 $$
Durch Ersetzen dieser Paritätsbits wird die Hamming code wird $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $ sein.
Beispiel 2
Im obigen Beispiel haben wir den Hamming-Code als $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $ erhalten. Lassen Sie uns nun die Fehlerposition finden, wenn der empfangene Code $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111 $ ist.
Lassen Sie uns nun die Prüfbits finden.
$$ c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0 $$
Der Dezimalwert der Prüfbits gibt die Fehlerposition im empfangenen Hamming-Code an.
$$ c_ {3} c_ {2} c_ {1} = \ left (011 \ right) _ {2} = \ left (3 \ right) _ {10} $$
Daher ist der Fehler im dritten Bit (b 3 ) des Hamming-Codes vorhanden. Ergänzen Sie einfach den in diesem Bit vorhandenen Wert und entfernen Sie Paritätsbits, um den ursprünglichen Binärcode zu erhalten.