Berger Code - Berger code

In der Telekommunikation ist ein Berger-Code ein unidirektionaler Fehlererkennungscode , der nach seinem Erfinder JM Berger benannt ist. Berger-Codes können alle unidirektionalen Fehler erkennen. Unidirektionale Fehler sind Fehler, bei denen nur Einsen in Nullen oder nur Nullen in Einsen umgewandelt werden, z. B. in asymmetrischen Kanälen. Die Prüfbits von Berger-Codes werden berechnet, indem alle Nullen im Informationswort gezählt und diese Zahl in natürlicher Binärzahl ausgedrückt werden. Wenn das Informationswort aus Bits besteht , benötigt der Berger-Code "Prüfbits", was einen Berger-Code der Länge k + n ergibt. (Mit anderen Worten, die Prüfbits reichen aus, um auf Informationsbits zu prüfen ). Berger-Codes können eine beliebige Anzahl von Eins-zu-Null-Bit-Flip-Fehlern erkennen, solange im gleichen Codewort keine Null-zu-Eins-Fehler aufgetreten sind. In ähnlicher Weise können Berger-Codes eine beliebige Anzahl von Null-zu-Eins-Bit-Flip-Fehlern erkennen, solange keine Eins-zu-Null-Bit-Flip-Fehler in demselben Codewort auftreten. Berger-Codes können keinen Fehler korrigieren.

Wie alle unidirektionalen Fehlererkennungscodes können Berger-Codes auch in verzögerungsunempfindlichen Schaltungen verwendet werden.

Unidirektionale Fehlererkennung

Wie oben angegeben, erkennen Berger-Codes eine beliebige Anzahl von unidirektionalen Fehlern. Wenn für ein bestimmtes Codewort die einzigen aufgetretenen Fehler darin bestehen, dass einige (oder alle) Bits mit dem Wert 1 auf den Wert 0 geändert wurden, wird diese Transformation von der Berger-Code-Implementierung erkannt. Um zu verstehen, warum, bedenken Sie, dass es drei solche Fälle gibt:

  1. Einige 1s-Bits im Informationsteil des Codeworts wurden in 0s geändert.
  2. Einige 1s-Bits im Prüf- (oder redundanten ) Teil des Codeworts haben sich in 0s geändert.
  3. Einige 1s-Bits sowohl im Informations- als auch im Prüfabschnitt wurden in 0s geändert.

Für Fall 1 erhöht sich die Anzahl der 0-Wert-Bits im Informationsabschnitt per Definition des Fehlers. Daher ist unser Berger-Prüfcode niedriger als die tatsächliche 0-Bit-Anzahl für die Daten, sodass die Prüfung fehlschlägt.

Für Fall 2 ist die Anzahl der 0-Wert-Bits im Informationsabschnitt gleich geblieben, aber der Wert der Prüfdaten hat sich geändert. Da wir wissen, dass einige Einsen zu Nullen geworden sind, aber keine Nullen zu Einsen geworden sind (so haben wir in diesem Fall das Fehlermodell definiert), sinkt der codierte Binärwert der Prüfdaten (z. B. von binär 1011 auf 1010 oder bis 1001 oder 0011). Da die Informationsdaten gleich geblieben sind, hat sie die gleiche Anzahl von Nullen wie zuvor, und dies stimmt nicht mehr mit dem mutierten Prüfwert überein.

Beachten Sie für Fall 3, in dem sich die Bits sowohl im Informations- als auch im Prüfabschnitt geändert haben, dass die Anzahl der Nullen im Informationsabschnitt gestiegen ist , wie für Fall 1 beschrieben, und der im Prüfabschnitt gespeicherte Binärwert gesunken ist. Wie für Fall 2 beschrieben, besteht daher keine Chance, dass die beiden so mutieren, dass sie zu einem anderen gültigen Codewort werden.

Eine ähnliche Analyse kann durchgeführt werden und ist vollkommen gültig, wenn die einzigen Fehler darin bestehen, dass sich einige 0-Wert-Bits auf 1 ändern. Wenn daher alle Fehler, die bei einem bestimmten Codewort auftreten, alle in derselben Richtung auftreten werden diese Fehler erkannt. Für das nächste übertragene Codewort (zum Beispiel) können die Fehler in die entgegengesetzte Richtung gehen, und sie werden weiterhin erkannt, solange sie alle in die gleiche Richtung gehen.

Unidirektionale Fehler sind in bestimmten Situationen häufig. Beispielsweise können im Flash-Speicher Bits leichter auf eine 0 programmiert werden als auf eine 1 zurückgesetzt werden.

Verweise

  • JM Berger (März 1961). "Ein Hinweis zu einem Fehlererkennungscode für asymmetrische Kanäle" . Information und Kontrolle . 4 (1): 68–73. doi : 10.1016 / S0019-9958 (61) 80037-5 .
  • Subhasish Mitra und Edward J. McCluskey, " Welches Schema zur gleichzeitigen Fehlererkennung soll gewählt werden? ", Center for Reliable Computing, Stanford University, 2000. CiteSeer x :  10.1.1.9.2021
  • Tom Verhoeff (März 1988). "Verzögerungsunempfindliche Codes - eine Übersicht] von" (PDF) . Verteiltes Rechnen . 3 (1): 1–8. doi : 10.1007 / BF01788562 .