🛏️ 🕗 🧛🏽 Korrektur mehrerer Fehler beim Codieren von Nachrichten 🤶🏿 🧑🏻 🕊️

In Informationssystemen geht der Austausch von Nachrichten in Kommunikations- oder Computernetzwerken mit störenden Einflüssen der Umgebung oder eines Eindringlings einher, was zum Auftreten von Signalverzerrungen und zu Symbolfehlern bei der digitalen Übertragung führt. Der Kampf gegen dieses Phänomen wird mit Korrekturcodes durchgeführt. Zuvor habe ich den Hamming-Code beschrieben und gezeigt, wie ein einzelner Fehler in einem Codewort behoben werden kann. Natürlich stellte sich die Frage nach Situationen mit einer großen Anzahl von Fehlern. Heute betrachten wir den Fall von zwei Fehlern in einem Codewort (Mehrfachfehler). Einerseits ist theoretisch alles mehr oder weniger einfach und verständlich, andererseits ist es überhaupt nicht offensichtlich. Die Präsentation des Materials basiert auf den Arbeiten von E. Berlekamp.

Theoretische Bestimmungen

Die Idee, organisierte Redundanz in Nachrichten zu verwenden, führte R. Hamming zur Konstruktion des hier beschriebenen Korrekturcodes . Ein linearer Korrekturcode (n, k) ist durch eine Prüfmatrix (m × n) H gekennzeichnet. Die Anforderungen an die Matrix sind einfach: Die Anzahl der Zeilen stimmt mit der Anzahl der Prüfsymbole überein, ihre Spalten müssen von Null verschieden sein und alle sind unterschiedlich. Darüber hinaus beschreiben die Spaltenwerte die Positionsnummern, die im Codewort durch Wortzeichen belegt sind, die Elemente des letzten Feldes sind.

Oft verwendet der Decodierer die Berechnung des für dieses Wort berechneten Syndroms, um zu bestimmen, ob ein übertragenes Wort fehlerhaft ist. Das Syndrom ist gleich der Summe der Spalten dieser Matrix multipliziert mit den Komponenten des Fehlervektors. Wenn H m Zeilen enthält und der Code die Korrektur einzelner Fehler ermöglicht, überschreitet die Länge des Blocks (Codewort) nicht

n \leq 2^{m} - 1

$n≤2^m-1$ ... Wichtig ist auch die Machbarkeit des erforderlichen Abstands der Codewörter voneinander.

Hamming-Codes erreichen diese Grenze. Jede Position des Hamming-Codeworts kann mit einem Binärvektor nummeriert werden, der mit der entsprechenden Spalte der Matrix H übereinstimmt. In diesem Fall fällt das Syndrom direkt mit der Positionsnummer zusammen, an der der Fehler aufgetreten ist (wenn nur ein Fehler vorliegt) oder mit der binären Summe von Zahlen (wenn mehrere Fehler vorliegen).

Vektornummerierung ist eine sehr fruchtbare Idee. Weiter werden wir annehmen

n \leq 2^{m} - 1

$n≤2^m-1$ und dass die i-te Position des Wortes i nummeriert ist.

Die binäre Nummerierung (d. H. Eine solche Darstellung) wird als Positionsortung bezeichnet. Angenommen, Sie möchten alle doppelten und einfachen Fehler beheben. Anscheinend erfordert dies eine große Code-Redundanz, d.h. Matrix H muss mehr Zeilen haben (doppelt so viele). Daher bilden wir eine Matrix H mit 2m Zeilen und mit

n \leq 2^{m} - 1

$n≤2^m-1$ Spalten, und es ist ratsam, verschiedene Spalten auszuwählen. Für die ersten m Zeilen nehmen wir die vorherige Matrix des Hamming-Codes. Dies sind die Basiswortvektoren des Wortraums.

Beispiel 1

Es sei m = 5 und n = 31. Es wäre wünschenswert, einen (n, k) -Code zu erhalten, der doppelte Fehler korrigiert, mit einer Paritätsprüfmatrix H in der Form:

Für die in der Matrix angegebenen Funktionen fj (ξ) ist es wünschenswert, eine Funktion zu haben, die abgebildet wird Satz von 5-dimensionalen Vektoren in sich. Die letzten 5 Zeilen der Matrix definieren den Hamming-Code genau dann, wenn die Funktion f eine Bijektion (Permutation) ist.

Wenn Sie in den ersten 5 Zeilen und in den letzten 5 Zeilen einzelne Fehler separat korrigieren können, können Sie möglicherweise zusammen zwei Fehler korrigieren.

Wir müssen lernen, binäre 5-dimensionale Vektoren zu addieren, zu subtrahieren, zu multiplizieren und zu dividieren und sie durch Polynome mit einem Grad von höchstens 4 darzustellen, um die erforderliche Funktion fj (ξ) zu finden.

Beispiel 2

00000 ← → 0

00010 ← → 1

00011 ← → x

...

11011 \leftarrow\to х^{4} + х^{3} + х + 1

$11011 ←→ ^4 +^3++1$

Die Summe und Differenz solcher Polynome entspricht der Summe und Differenz der Vektoren:

0 ± 0 = 0, 0 ± 1 = 1, 1 ± 0 = 1, 1 ± 1 = 0, die Vorzeichen von ± haben im binären Fall die gleiche Bedeutung. Nicht so bei der Multiplikation kann der Exponent des Ergebnisses der Multiplikation 4 überschreiten.

Beispiel 3

(х^{3} + х + 1) х^{4} + х^{3} + х + 1) = х^{7} + х^{6} + х^{5} + 3 х^{4} + 2 х^{3} + х^{2} + 2 х + 1 =

$(^3++1)^4+^3++1)=^7+^6+^5+3^4+2^3+^2+2+1=$

= х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1

$=^7+^6+^5+^4+^2+1$ ...

Ein Verfahren zum Verringern von Graden größer als 4

ist erforderlich. Es wird (Reduktion) der Konstruktion von Resten modulo eines irreduziblen Polynoms M (x) von Grad 5 genannt; Die Methode besteht im Übergang von den Polynomen der Produkte zu ihren Resten nach Division durch

M (x) = x^{5} + x^{2} + 1

$M(x)=x^5+x^2 + 1$

Damit

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 = (х^{2} + х + 1) (х^{5} + х^{2} + 1) + х^{3} + х^{2} + х

$^7+^6+^5+^4+^2+1 =(^2+ + 1)(^5 +^2 +1) +^3 +^2 +$ oder

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 \equiv (х^{3} + х^{2} + x) m o d (х^{5} + х^{2} + 1) .

$^7+^6+^5+^4+^2+1 ≡(^3+^2 + x)mod(^5 +^2 +1).$

Das Symbol ≡ lautet "vergleichbar mit".

Im Allgemeinen ist A (x) ≡a (x) mod M (x)

genau dann, wenn ein Polynom C (x) existiert, so dass

A (x) = M (x) C (x) + a (x) Die Koeffizienten der Polynome sind modulo zwei reduziert:

A (x) ≡ a (x) mod (2, M (x)).

Wichtige Eigenschaften von Vergleichen

Wenn a (x) ≤ A (x) mod M (x) und b (x) ≤ B (x) mod M (x), dann ist

a (x) ± b (x) ≤ A (x) ± B (x ) mod M (x) und a

(x) b (x) ≤ (x) B (x) mod M (x).

Wenn darüber hinaus die Grade der Polynome a (x) und A (x) kleiner als der Grad von M (x) sind,

folgt aus der Formel a (x) ≡ A (x) mod (2, M (x)), dass a (x) = A (x).

Es gibt 2 verschiedene Rückstandsklassen in Grad degM (x) - das heißt, so viele wie es verschiedene Polynome mit einem Grad kleiner als m gibt, d.h. wie viele verschiedene Teilungsreste können sein. Die Teilung ist noch schwieriger.

Divisionsalgorithmus

Für Zahlen.

Für gegebenes a und M gibt es eindeutig definierte Zahlen q und A, so dass a = qM + A, 0 ≤ A ≤ M,

für Polynome mit Koeffizienten aus einem gegebenen Feld.

Für gegebenes a (x) und M (x) gibt es eindeutig definierte Polynome q (x) und A (x), so dass a (x) = q (x) M (x) + A (x), degA (x) ) <Grad M (x).

Die Möglichkeit, Polynome zu teilen, bietet der euklidische Algorithmus.

Für Zahlen wird hier ein Beispiel für eine erweiterte GCD beschrieben .

Für ein gegebenes a und b gibt es Zahlen A und B, so dass aA + bB = (a, b) ist, wobei (a, b) die GCD der Zahlen a und b ist.

Für Polynome mit Koeffizienten aus einem bestimmten Feld.

Für gegebenes a (x) und b (x) existieren Polynome A (x) und B (x), so dass

a (x) A (x) + b (x) B (x) = (a (x), b (x)),

wobei (a (x), b (x)) der normalisierte gemeinsame Teiler von a (x) und b (x) von größtem Grad ist.

Wenn a (x) und M (x) einen gemeinsamen Teiler d (x) ≠ 1 haben, ist eine Division durch einen (x) mod M (x) nicht immer möglich.

Es ist offensichtlich, dass die Division durch a (x) der Multiplikation mit A (x) entspricht.

Da wenn (a (x), b (x)) = 1 = GCD ist, gibt es nach dem Euklid-Algorithmus A (x) und B (x), so dass a (x) A (x) + b (x) B (x) = 1, so dass a (x) A (x) ≤ 1 mod b (x). Überprüfen, ob ein binäres Polynom über das Feld GF irreduzibel ist (

2^{5}

$2^5$ ) wird durch direkte Division durch alle möglichen Teiler mit Grad kleiner als Grad M (x) durchgeführt.

Beispiel 4 .

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ geteilt durch x und (x + 1)

durch lineare Teiler. Das Teilungsergebnis ist nicht Null. Teilen Sie durch quadratische Teiler

х^{2}, х^{2} + х = х (х + 1), х^{2} + 1, х^{2} + 2 х + 1 = (х + 1)^{2}, х^{2} + х + 1.

$^2 , ^2 +=( +1),^2 +1, ^2 +2 +1= ( +1)^2, ^2 + + 1.$ ... Sie geben Guthaben ungleich Null aus. Teiler vom Grad ≥ 3 existieren nicht, da ihr Produkt den Grad ≥ 6 ergibt.

Somit können Polynome addiert, subtrahiert, multipliziert und modulo geteilt werden

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ ...

Wir wenden uns der Suche nach einer Funktion für die Paritätsprüfmatrix H zu, die einen doppelten Fehlerkorrekturcode mit einer Blocklänge von 31 und einer Rate von 21/31 definiert. 31-21 = 10 = 2t - Prüfsymbole = 10. Eine solche Funktion muss die Anzahl der fehlerhaften Positionen im Codewort, d.h. Wenn Positionsnummern in diese Funktion eingesetzt werden, wird sie auf Null gesetzt.

Suchfunktion

Angenommen, β1 und β2 sind die Zahlen der verzerrten Zeichen (Positionen) des Wortes. Unter Verwendung der binären Notation der Zahlen β1 und β2 können diese Zahlen als Restklassen modulo M (x) dargestellt werden, d.h. Stellen Sie die Entsprechung βi → β ⁽ⁱ⁾ (x) - binäre Polynome vom Grad <5 her.

Die ersten 5 Testbedingungen bestimmen β1 + β2 ; Der zweite Satz von Testgleichungen muss f (β1) + f (β2) bestimmen .

Der Decoder muss β1 und β2 gemäß dem gegebenen System bestimmen:

Was sollte die Funktion f (x) sein ?

Die einfachste Funktion ist die Multiplikation mit einer Konstanten f (β) ≡ αβ () modM (x) .

Aber dann ist ξ2 = αξ1 , d.h. Die Gleichungen des Systems sind abhängig. Die neuen fünf Testbedingungen geben dem Decoder nichts Neues.

In ähnlicher Weise ändert die Funktion f (β) = β + α die Situation nicht, da ξ2 = ξ1 ist .

Power-Funktionen ausprobieren: zuerst nehmen

f (β) = β^{2}

$f(β) = β^2$ ... Darüber hinaus sind

diese Gleichungen auch abhängig, da

ξ 1^{2} = (β 1 + β 2)^{2} = β 1^{2} + 2 β 1 β 2 + β 2^{2} = β 1^{2} + β 2^{2} = ξ 2

$ξ1^2 =(β1 + β2)^2=β1^2 + 2β1β2 + β2^2 = β1^2 + β2^2 =ξ2$

Die zweite Gleichung ist also das Quadrat der ersten.

Ich versuche es

f (β) = β^{3}

$f(β) = β^3$ ... Form der

Decodergleichung ändern: Position

ξ 2 = β 1^{3} + β 2^{3} = (β 1 + β 2) (β 1^{2} - β 1 β 2 + β 2^{2}) = ξ 1 (β 1 β 2 - ξ 1^{2}) .

$ξ2 =β1^3 + β2^3=(β1 + β2)(β1^2 -β1β2+ β2^2)=ξ1(β1β2-ξ1^2).$

Für ξ1 ≠ 0 gilt

also: β1 und β2 erfüllen die Gleichung

. Wenn also genau zwei Fehler aufgetreten sind, erfüllen ihre Lokalisierer diese Gleichung.

Da diese Gleichung genau 2 Wurzeln im Bereich der binären Polynome modulo M (x) hat , kann der Decodierer immer die zwei erforderlichen Lokalisierer finden.

Wenn nur ein Fehler auftritt, ist β1 = ξ1 und $β1^2 = ξ2$ ... Daher erfüllt in diesem Fall der einzige Fehler die Gleichung β + ξ1 = 0 oder 1+ ξ1β ^-1 = 0 .

Schließlich führt der Decodierer immer eine Decodierung durch, wenn keine Fehler aufgetreten sind, in diesem Fall ξ1 + ξ2 = 0 .

In der Praxis ist es bequemer, nicht direkt mit einem Polynom zu arbeiten, dessen Wurzeln Fehlerlokalisierer sind, sondern mit einem Polynom, dessen Wurzeln mit den Lokalisierern wechselseitig sind. jene. sind multiplikative Kehrwerte zu ihnen.

Es ist klar, dass der Decoder mit nicht mehr als zwei Fehlern die Fehlernummern bestimmen kann. Wenn drei oder mehr Symbole verzerrt sind, tritt ein Decodierungsfehler oder ein Decodierungsfehler auf.

Also die Funktion

f (x) = x^{3}

$f(x) = x^3$ geeignet zum Konstruieren der unteren fünf Zeilen der Prüfmatrix H eines Binärcodes mit einer Codewortlänge von 31 und 10 Prüfsymbolen, um alle doppelten Fehler zu korrigieren.

Die ersten fünf Prüfungen geben die Summe der Fehlernummern (S1) an; Die zweiten fünf Prüfungen sind die Summe der Fehlernummernwürfel (S3).

Das Dekodierungsverfahren besteht aus drei Hauptschritten:

Jedes empfangene Codewort wird überprüft und S1 und S3 werden berechnet.
finde das Fehlerlokalisierungspolynom in σ (z);
Die Gegenwerte für die Wurzeln σ (z) werden berechnet und die Symbole an den entsprechenden Positionen des resultierenden Wortes geändert.

Korrektur mehrerer Fehler beim Codieren von Nachrichten

Theoretische Bestimmungen

Wichtige Eigenschaften von Vergleichen

Divisionsalgorithmus

Suchfunktion

More articles: