In Vorheriger Artikel habe ich herausgefunden, auf welchem Framework die Quantenfehlerkorrektur basiert. Jetzt, da wir die Aussicht auf verschiedene andere Quantenfehlerkorrekturen als den Shor-Code haben, fragen wir uns, welche anderen Methoden verfügbar sind. Zuvor scheint es jedoch notwendig zu sein, den "klassischen linearen Code" zu verstehen. Es wird gesagt, dass das Wissen über klassische lineare Codes als Grundlage für die Entwicklung verschiedener Methoden zur Quantenfehlerkorrektur verwendet wird. Dieses Mal werden wir also klassische lineare Codes untersuchen. Nachdem ich das Ganze verstanden habe, möchte ich die Funktionsweise des klassischen linearen Codes durch ein Python-Programm bestätigen.
Lassen Sie mich zunächst sagen, was ich in den folgenden Abschnitten zu erklären versuche. Dieser Artikel ist grob in die Teile "Erklärung der Theorie" und "Simulation" unterteilt. In "Erklärung der Theorie" sind nach der Erläuterung von "Erzeugungsmatrix", "Paritätsprüfmatrix" und "Vorzeichenabstand", die die Grundkonzepte des klassischen linearen Codes sind, "Hamming-Code" und "horizontale / vertikale Parität" konkrete Beispiele für Codierungsmethoden. Werfen wir einen Blick auf "Zeichen". Darüber hinaus werden wir die etwas fortgeschritteneren Themen "Die Grenzen von Gilbert-Varshamov" und "Doppelzeichen" behandeln. "Simulation" simuliert das Verhalten des Hamming-Codes. Stellen Sie beim Betrachten des Implementierungsbeispiels und des Verarbeitungsergebnisses in Python sicher, dass der Fehler behoben ist.
Die folgenden Dokumente wurden als Referenz verwendet.
Beginnen wir mit einer einfachen Geschichte. Eine sehr primitive Version des klassischen linearen Codes ist eine Codierungsmethode, die einfach die ursprüngliche Information wiederholt (im Folgenden als "Wiederholungscode" bezeichnet). Zum Beispiel jedes Bit einer binären Bitreihe,
\begin{align}
0 \rightarrow 000 \\
1 \rightarrow 111 \tag{1}
\end{align}
Es wird mit dreifacher Redundanz wie übertragen. Informationen, die ursprünglich 0 waren, werden zu 000. Selbst wenn beispielsweise eines der Bits in 0 in 010 invertiert wird, liegt dies daran, dass eines von 000 eine Bitinversion hatte und ursprünglich 0 war. Sie können sich vorstellen, dass dies der Fall war (dh Sie können den Fehler korrigieren). Wenn Sie 2 Bits invertieren, wird dies versehentlich korrigiert, aber wenn die Wahrscheinlichkeit gering ist, ist es besser, als nichts zu tun, nicht wahr? Im Allgemeinen besteht der Fehlerkorrekturcode im Wesentlichen darin, die ursprünglichen Bitinformationen redundant zu machen und zu erweitern. Das Redundieren und Erweitern wird als "Codierung" bezeichnet. Es gibt verschiedene Codierungsmethoden.
Um es ein wenig mathematisch zu abstrahieren, eine Bitfolge, die aus $ k $ $ \ {0,1 \} $ besteht, ist eine Menge von $ \ {0,1 \} ^ {k} $. Es kann gesagt werden, dass es ein Element von ist. In ähnlicher Weise sind $ n $ Bitsequenzen Elemente der Menge $ \ {0,1 \} ^ {n} $. Daher ist die Codierung ein $ k $ -Dimensionsvektor $ x \ in \ {0,1 \} ^ {k} $ zu einem $ n $ -Dimensionsvektor $ y \ in \ {0,1 \ Entspricht der Zuordnung zu } ^ {n} $. Der Code, der diese Zuordnung auf die lineare Transformation beschränkt, wird als "linearer Code" [^ 1] bezeichnet. Außerdem wird der aus dem Code nach der linearen Konvertierung zusammengesetzte Raum als "Code-Raum" bezeichnet.
[^ 1]: Um den Kontrast zum Quanten zu verdeutlichen, lautet der Titel dieses Artikels "klassischer linearer Code", aber da er im Text problematisch ist, werde ich ihn einfach "linearer Code" nennen.
Zum Beispiel ist die Codierung, die 1 Bit auf 3 Bit redundant macht,
G =
\begin{pmatrix}
1\\
1\\
1
\end{pmatrix} \tag{2}
Man kann sagen, dass es sich um eine lineare Transformation handelt, die durch die Matrix definiert wird. Anwenden der Transformationsmatrix $ G $ auf $ x = (0), x = (1) $
G
\begin{pmatrix}
0
\end{pmatrix} =
\begin{pmatrix}
1\\
1\\
1
\end{pmatrix}
\begin{pmatrix}
0
\end{pmatrix}
=
\begin{pmatrix}
0\\
0\\
0
\end{pmatrix}, \space
G
\begin{pmatrix}
1
\end{pmatrix}
=
\begin{pmatrix}
1\\
1\\
1
\end{pmatrix}
\begin{pmatrix}
1
\end{pmatrix}
=
\begin{pmatrix}
1\\
1\\
1
\end{pmatrix} \tag{3}
Und Sie können sehen, dass es dasselbe tut wie Gleichung (1). Der Wiederholungscode ist also ein linearer Code. Dieses $ G $ wird als "Generatormatrix" in dem Sinne bezeichnet, dass es eine Matrix ist, die aus den ursprünglichen Informationen einen Code generiert. Seitdem werden verschiedene lineare Operationen angezeigt, aber alle algebraischen Operationen werden mit 2 als Methode ausgeführt. Andernfalls passt nicht jedes Bit in $ \ {0,1 \} $ [^ 2].
[^ 2]: Übrigens beschäftigen wir uns in diesem Artikel nur mit Codes, die auf Binärzahlen basieren, aber in der allgemeinen linearen Codetheorie ist die Theorie so konstruiert, dass sie auf einer beliebigen Zahl basieren kann und auf q-ary Zahlen basiert. Es scheint, dass der Code, auf den gesetzt ist, speziell als "linearer Code für q Elemente" bezeichnet wird.
Hier ist ein Beispiel. Welche Art von Codierungsoperation repräsentiert die folgende Generationsmatrix $ G $?
\begin{pmatrix}
1 & 0 \\
1 & 0 \\
1 & 0 \\
0 & 1 \\
0 & 1 \\
0 & 1
\end{pmatrix} \tag{4}
Es ist einfach.
\begin{align}
(0,0)^T \rightarrow (0,0,0,0,0,0)^T \\
(0,1)^T \rightarrow (0,0,0,1,1,1)^T \\
(1,0)^T \rightarrow (1,1,1,0,0,0)^T \\
(1,1)^T \rightarrow (1,1,1,1,1,1)^T \tag{5}
\end{align}
Es ist die Kodierung. Früher haben wir 1 Bit auf 3 Bit redundant gemacht, aber diesmal haben wir 2 Bit auf 6 Bit redundant gemacht. Im Allgemeinen wird der Code, der k Bits in n Bits codiert, als [n, k] Code bezeichnet. Das erste Beispiel ist der [3,1] -Code, und dieses Beispiel ist der [6,2] -Code. Wie Sie leicht sehen können, ist die [n, k] -Codegenerierungsmatrix die $ n \ times k $ -Matrix [^ 3].
[^ 3]: Es gibt einige Literaturen und Texte, die die Codierungsoperation als $ xG $ beschreiben, wobei die Generierungsmatrix $ G $ die Matrix $ k \ times n $ und das Vorzeichen $ x $ der horizontale Vektor ist. Im Teil "Erklärung der Theorie" dieses Artikels ist laut Neilsen, Chan der Code $ x $ der vertikale Vektor und die Generierungsmatrix ist $ n. Schreiben wir als \ times k $ -Matrix die Codierungsoperation als $ Gx $. Wie ich später erklären werde, werde ich es im Teil "Simulation" der Einfachheit halber umkehren. Stellen Sie sich die Originalinformationen und das Zeichen vorerst als vertikalen Vektor vor.
Sie haben vielleicht gedacht, dass Sie jeden linearen Code frei erstellen können, wenn Sie die Generierungsmatrix entsprechend einstellen, aber das ist nicht der Fall. Damit die Matrix $ G $ eine Generierungsmatrix ist, muss jeder Spaltenvektor $ \ {g_1, g_2, \ cdots, g_k \} $, aus dem die Generierungsmatrix besteht, linear unabhängig sein. Bei linearer Abhängigkeit können unterschiedliche Informationen $ x $ und $ x ^ {\ prime} $ auf dasselbe Vorzeichen $ y $ abgebildet werden.
Was meinst du? Dies wird unten erklärt.
Das Zeichen $ y $ stammt aus der ursprünglichen Information $ x $
y = Gx = \sum_{i=0}^{k} g_{i} x_{i} \tag{6}
Es wird durch Anwenden der Generierungsmatrix $ G $ wie in generiert. Nun $ x ^ {\ prime} $, was sich von $ x $ unterscheidet,
y^{\prime} = Gx^{\prime} = \sum_{i=0}^{k} g_{i} x_{i}^{\prime} \tag{7}
Angenommen, es wird wie folgt generiert. Wenn $ \ {g_i \} $ linear unabhängig ist, dann ist Gleichung (7) minus Gleichung (6),
y^{\prime} - y = \sum_{i=0}^{k} g_{i} (x_{i}^{\prime} - x_{i}) \tag{8}
In ist die linke Seite nur dann $ 0 $, wenn $ x_ {i} ^ {\ prime} --x_ {i} = 0 $ für alle $ i $ (aus der Definition der linearen Unabhängigkeit). Das heißt, $ y $ und $ y ^ {\ prime} $ sind nur dann gleich, wenn $ x $ und $ x ^ {\ prime} $ gleich sind. Wenn umgekehrt die Vektoren $ x $ und $ x ^ {\ prime} $ unterschiedlich sind, sind $ y $ und $ y ^ {\ prime} $ immer unterschiedlich.
Überlegen Sie sich andererseits, was passiert, wenn $ \ {g_i \} $ linear abhängig ist. Zum Beispiel der Einfachheit halber
g_1 = g_2 + g_3 \tag{9}
Angenommen, die Beziehung ist hergestellt. Dies ist linear abhängig [^ 4]. Dann ist Gleichung (6)
[^ 4]: Jetzt bringe ich zufällig das 2. und 3. $ g_i $ ein und setze die Summe genau auf das 1. $ g_i $, aber selbst wenn es nicht so ist ( (Auch wenn Sie eine Kombination mitbringen), gilt die folgende Diskussion.
\begin{align}
y &= G x = \sum_{i=0}^{k} g_{i} x_{i} \\
&= (g_2 + g_3) x_1 + g_2 x_2 + g_3 x_3 + \cdots + g_k x_k \\
&= g_2 (x_1 + x_2) + g_3 (x_1 + x_3) + g_4 x_4 + \cdots + g_k x_k \tag{10}
\end{align}
Und $ x = (x_1, x_2, x_3, x_4, \ cdots, x_k) ^ T $ und $ x ^ {\ prime} = (\ bar {x_1}, \ bar {x_2}, \ bar {x_3}, x_4, \ cdots, x_k) ^ T $ erzeugt dasselbe Vorzeichen (wobei $ \ bar {x_i} $ die Bitinversion von $ x_i $ ist). Daher muss jeder Spaltenvektor, aus dem die generierte Matrix besteht, linear unabhängig sein [^ 5].
[^ 5]: Damit ist "Übungsübung 10.15" von Neilsen, Chan (wahrscheinlich) abgeschlossen.
Da es möglich war, durch Anwenden der Generierungsmatrix auf die Originalinformationen zu codieren, betrachten wir als nächstes das dem Code hinzugefügte Rauschen. Zunächst wird ein konkretes Beispiel gezeigt. Die erste gezeigte [3,1] Wiederholungscode-Erzeugungsmatrix war Gleichung (2). Für den generierten Code
H =
\begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 1
\end{pmatrix} \tag{11}
Was passiert, wenn Sie die Matrix anwenden? Nur wenn das Vorzeichen $ x $ $ (0,0,0) ^ T $ und $ (1,1,1) ^ {T} $ ist (dh nur, wenn keine Fehler vorliegen),
H x = 0 \tag{12}
Wird sein. Davon abgesehen wird es nicht $ 0 $ sein. Daher kann festgestellt werden, dass ein Fehler aufgetreten ist. Welches Bit einen Fehler aufweist, wird abhängig von der Codierungsmethode von einem anderen Algorithmus bestimmt. In diesem Beispiel ist, wenn $ Hx $ $ (1,0) ^ {T} $ ist, das erste Bit, wenn $ (1,1) ^ {T} $, das zweite Bit, $ ( Im Fall von 0,1) ^ {T} $ kann festgestellt werden, dass im dritten Bit ein Fehler aufgetreten ist. Die Matrix $ H $, die konstruiert wurde, um auf diese Weise auf Fehler zu prüfen, wird als "Paritätsprüfungsmatrix" bezeichnet und als die Beziehung in Gleichung (12) erfüllend definiert. In diesem Beispiel ist es, da es sich um einen sich wiederholenden Code handelt, möglich, eine Beurteilung zu treffen, indem alle 3 Bits eine Mehrheitsentscheidung getroffen wird. Um jedoch verschiedenen linearen Codes zu entsprechen, ist es allgemeiner, das Ergebnis durch lineare Operation zu überprüfen. Es wird eine Art zu sagen sein.
Das nächste Beispiel für die [6,2] Wiederholungscode-Generierungsmatrix war Gleichung (4). Was ist die Paritätsprüfungsmatrix dafür? Warte 1 Minute.
Wie ist das? Hast du verstanden?
Sagen wir jetzt die Antwort (obwohl ich denke, dass Sie es sehen konnten).
\begin{pmatrix}
1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 1
\end{pmatrix} \tag{13}
Das stimmt [^ 6]. Ich denke, es ist leicht zu erkennen, dass dies der Fall ist. Das Konvertieren des 6-dimensionalen Vektors auf der rechten Seite von Gleichung (5) mit der obigen Matrix führt zu allen $ 0 $, aber wenn in einem Bit ein Fehler vorliegt, ist dies nicht $ 0 $. Nach den gleichen Regeln wie zuvor kann festgestellt werden, welches Bit falsch war. Und während die [n, k] -Codegenerierungsmatrix die $ n \ times k $ -Matrix war, ist die entsprechende Paritätsprüfungsmatrix die $ (n-k) \ times n $ -Matrix.
Sagen wir es etwas allgemeiner. Angenommen, dem codierten $ y $ wird Rauschen hinzugefügt, und es ändert sich wie $ y ^ {\ prime} = y + e $. Multipliziert man dies mit der Paritätsprüfungsmatrix, erhält man $ Hy ^ {\ prime} = Hy + He = He $, wobei nur der Beitrag zu den durch das Rauschen hinzugefügten Fehlerinformationen übrig bleibt. Dieses $ Hy ^ {\ prime} $ wird "Fehlersyndrom" genannt. Basierend auf dem Berechnungsergebnis dieses Fehlersyndroms wird der Fehler dann konkret korrigiert. Wenn ein Fehler im $ j $ -ten Bit auftritt, ist $ e $ ein Vektor mit der $ j $ -ten Komponente in $ 1 $ und dem Rest in $ 0 $. Daher ist das Berechnungsergebnis von $ Hy ^ {\ prime} $ genau gleich dem Spaltenvektor der Spalte $ j $ von $ H $. Wenn Sie also bestimmen, welcher Spalte in $ H $ das Fehlersyndrom entspricht, wissen Sie, welches Bit falsch ist. Wenn Sie dieses Bit invertieren, haben Sie den Fehler korrigiert.
[^ 6]: Dies ist die Antwort auf "Übung 10.17" von Neilsen, Chan.
Wäre es nicht schön, die Paritätsprüfungsmatrix aus der generierten Matrix zu finden, die Sie erstellt haben, oder umgekehrt die generierte Matrix aus der angegebenen Paritätsprüfungsmatrix zu finden? (Bitte denken Sie nach!) Tatsächlich können Sie dies folgendermaßen tun.
Um die Paritätsprüfungsmatrix aus der generierten Matrix zu erhalten, wählen Sie $ nk $ lineare unabhängige Vektoren $ y_1, y_2, \ cdots, y_ {nk} $, die orthogonal zur Spalte $ G $ sind, und die Zeile $ H $ ist $ Setzen Sie auf y_ {1}, y_ {2}, \ cdots, y_ {nk} $. Um umgekehrt die erzeugte Matrix aus der Paritätsprüfungsmatrix zu finden, wählen Sie $ k $ linear unabhängige Vektoren $ y_1, y_2, \ cdots, y_k $ aus, deren Kern $ H $ und $ G $ $ y_1 ist. Stellen Sie die Spalten y_2, \ cdots, y_k $ ein.
Hmm? Es kann so sein, also kauen Sie es ein wenig.
Wenn Sie $ G $ auf die Originalinformationen $ x $ anwenden, diese codieren und dann $ H $ unverändert anwenden (ohne Fehler), beträgt der Wert $ 0 $. Es ist $ 0 $ für jedes $ x $, also
HG = 0 \tag{14}
Die Beziehung gilt [^ 7]. Wenn Sie $ H $ aus dem gegebenen $ G $ finden möchten, müssen Sie Gleichung (14) erfüllen, also alle Spaltenvektoren, aus denen $ G $ besteht, und alle Zeilenvektoren, aus denen $ H $ besteht. Das innere Produkt muss alle $ 0 $ sein. Mit anderen Worten, es muss orthogonal sein. Der gesamte Codebereich hat die Dimension $ n $, und die Spaltenvektoren, aus denen $ G $ besteht, sind $ k $. Wenn Sie einen linear unabhängigen Vektor wählen, der orthogonal dazu ist, handelt es sich zwangsläufig um $ n-k $ Stücke. Ich denke, Sie haben ein Bild davon, wie Sie $ H $ von $ G $ erhalten. Als nächstes, wenn Sie $ G $ aus dem angegebenen $ H $ finden möchten. Betrachten Sie zunächst den Raum, in dem sich der "Kern" von $ H $ befindet. Der Kern des linearen Operators $ A $ ist der Unterraum des gesamten Vektors $ x $, so dass $ Ax = 0 $ ist. In diesem Fall ist der Raum, der $ H $ berechnet, um $ 0 $ zu werden, der von $ G $ erzeugte Code-Raum. Wenn Sie also einen linear unabhängigen Vektor finden, der den Kern von $ H $ bildet, ist dies der Code. Es ist ein linearer unabhängiger Vektor, der den Raum ausdehnt. Da $ H $ eine $ n-k $ -Zeile für einen Raum mit einer Gesamtdimension von $ n $ ist, können wir lineare unabhängige Vektoren $ k $ erhalten [^ 8]. Dann setzen Sie es als Spaltenvektor für $ G $ und Sie sind mit $ G $ fertig. Ich habe bereits erwähnt, dass die Paritätsprüfungsmatrix eine $ (n-k) \ times n $ -Matrix ist, aber ich denke, Sie können sehen, warum dies so ist.
[^ 7]: Dies ist "Übungsübung 10.18" von Neilsen, Chan. Ich denke, das geht aus der Definition der Paritätsprüfungsmatrix hervor.
[^ 8]: Es ist möglicherweise einfacher zu verstehen, wenn Sie sich $ Hx = 0 $ als simultane Gleichung vorstellen, die aus $ n-k $ Gleichungen mit $ n $ Variablen besteht. Da die $ n $ -Dimension der Freiheit $ n-k $ Bindungsbedingungen hat, ist der Nettofreiheitsgrad schließlich die $ k $ -Dimension.
Es ist in Ordnung, diesen Abschnitt zu beenden, aber es gibt noch eine wichtige Sache bei Paritätsprüfungsmatrizen. Das heißt, die Paritätsprüfungsmatrix kann jederzeit in die "Standardform" umgeschrieben werden, wobei ihre Wirkung erhalten bleibt. Der Standardtyp ist
H = (A|I_{n-k}) \tag{15}
Es ist eine Matrix der Form. Wobei $ A $ eine $ (n-k) \ mal k $ -Matrix darstellt und $ I_ {n-k} $ eine $ n-k $ -Dimensionseinheitsmatrix darstellt. Gleichung (15) ist eine Matrix, die aussieht, als wären sie nebeneinander angeordnet und zusammengeführt. Wenn $ H $ eine Paritätsprüfmatrix ist, gilt $ H x = 0 $ für den Vektor $ x $ im Codebereich. Wenn Sie dies als eine simultane Gleichung von $ n-k $ betrachten, die aus $ n $ Variablen besteht, können Sie sehen, warum sie in Form von Gleichung (15) umgeschrieben werden kann. Denken Sie daran, Junior High School Mathematik. Wenn ich die simultanen Gleichungen löse, denke ich, dass ich, während ich auf jede Gleichung starre, beide Seiten mit etwas multipliziere und addiere oder subtrahiere (das heißt, es ist eine Additions- oder Subtraktionsmethode), allmählich zu einer einfachen Form wurde, aber ich stelle mir dieselbe Operation vor Bitte. Da jedoch die Anzahl der Gleichungen im Vergleich zur Anzahl der Variablen gering ist, kann die genaue Lösung nicht erhalten werden. Die Antwort besteht darin, jede der $ n-k $ -Variablen als lineare Summe der anderen $ k $ -Variablen darzustellen. Genau das ist Gleichung (15) $ Hx = 0 $ zugeordnet.
Wenn die Paritätsprüfungsmatrix auf diese Weise standardisiert ist, kann die Erzeugungsmatrix direkt von hier erhalten werden. Verwenden von $ I_k $ als Einheitsmatrix der Dimension $ k $
G =
\begin{pmatrix}
I_k \\
-A
\end{pmatrix} \tag{16}
Mach einfach. Da $ HG = 0 $ ist, ist dies sicherlich eine Generierungsmatrix für die Paritätsprüfmatrix in Gleichung (15] [^ 9]. Wie ist das? Es ist einfach. Früher habe ich den Kern des Operators, die lineare Unabhängigkeit usw. erklärt, aber dies ist ein Moment!
[^ 9]: $ -A $ in Gleichung (16) kann durch Entfernen des Minus durch $ A $ ersetzt werden, wenn es auf einer Binärzahl wie dieser basiert, dh wenn Sie einen binären linearen Code betrachten. Alle Berechnungen basieren auf 2.
Unter Verwendung der auf diese Weise erstellten generierten Matrix sind die ursprünglichen Informationen die ersten $ k $ Teile des codierten $ n $ -Dimensionsvektors selbst. Wenn Sie den Fehler im vorherigen Verfahren beheben konnten, können Sie die ursprünglichen Informationen wiederherstellen, indem Sie einfach das erste $ k $ extrahieren (einfach!).
Nachdem wir die Generierungsmatrix und die Paritätsprüfungsmatrix erklärt haben, werden wir nun ein weiteres wichtiges Konzept erläutern, "Vorzeichenabstand".
Definieren Sie den Abstand $ d (y, y ^ {\ prime}) $ in den beiden Vektoren $ y, y ^ {\ prime} $ im Codebereich $ \ {0,1 \} ^ {n} $ tun können. Vergleichen Sie jedes Element von $ y $ und $ y ^ {\ prime} $ und verwenden Sie die Summe der verschiedenen Dinge als Abstand (die Summe wird jedoch normal berechnet, nicht die Berechnung basierend auf 2). Die so definierte Distanz wird als "Hamming-Distanz" bezeichnet. Außerdem wird das "Hamming-Gewicht" $ wt (y) $ mit dem Vorzeichen $ y $ als $ wt (y) \ äquiv. D (y, 0) $ als Abstand vom Vektor $ 0 $ definiert.
Unter Verwendung dieser Hamming-Distanz wird die "Vorzeichen-Distanz" $ d (C) $ des Code-Raums $ C $, die durch die durch $ y = G x $ spezifizierte Codierung erhalten wird, wie folgt definiert.
d(C) = \min_{x,y \in C, x \neq y} d(x,y) \tag{17}
Mit anderen Worten, der Mindestwert des Hamming-Abstands zwischen zwei willkürlich ausgewählten Codes ist der Codeabstand (daher wird er auch als "Mindestabstand" des Codes bezeichnet). Da $ d (x, y) = wt (x + y) $ gilt, [^ 10] ist Gleichung (17)
[^ 10]: $ d (x, y) $ war die Summe der verschiedenen Elemente von $ x, y $. Dies entspricht dem Ausführen von $ x + y (mod \ space 2) $ und dem anschließenden Zählen der Anzahl von $ 1 $, die als Element enthalten sind. Andererseits ist $ wt (x + y) $ per Definition genau die Anzahl von $ 1 $, die als Element enthalten ist. Daher gilt $ d (x + y) = wx (x + y) $.
d(C) = \min_{x \in C, x \neq 0} wt(x) \tag{18}
Es ist das gleiche, auch wenn es umgeschrieben wird als.
Da der Codeabstand eine sehr wichtige Merkmalsgröße ist, die die Eigenschaften des Coderaums darstellt, ist der [n, k] -Code, dessen Codedistanz $ d = d (C) $ ist, insbesondere [n, k, d]. Es wird oft in beschrieben.
Einer der Gründe, warum es so wichtig ist, ist, dass es zeigt, wie viele Fehlerkorrekturbits möglich sind. [3,1] Unter Hinweis auf den sich wiederholenden Code beträgt der Abstand dieses Codes nach der aktuellen Definition 3. Da es sich verdreifacht, können Sie, wenn Sie den Fehler durch Mehrheitsentscheidung korrigieren, definitiv bis zu 1-Bit-Fehler behandeln. [5,1] Im Fall eines sich wiederholenden Codes beträgt der Abstand 5, und wenn der Fehler durch das Mehrheitsentscheidungsverfahren korrigiert wird, kann bis zu einem 2-Bit-Fehler behandelt werden. Wenn der Code-Abstand $ 2t + 1 $ beträgt, können Sie den Fehler im $ t $ -Bit definitiv korrigieren. Daher hängt der Codeabstand eng mit der Anzahl der fehlerkorrigierbaren Bits zusammen. Im Allgemeinen ein eindeutiges Zeichen $, das $ d (y, y ^ {\ prime}) \ leq t $ mit dem verdorbenen Zeichen $ y ^ {\ prime} $ durch ein Zeichen in einem Abstand von $ 2t + 1 $ füllt. Durch einfaches Entschlüsseln als y $ können Fehler bis zum $ t $ -Bit korrigiert werden.
In Bezug auf die Entfernung des Zeichens gibt es zwei weitere wichtige Dinge zu sagen, die ich der Reihe nach erläutern werde.
Zuerst der erste.
Es gibt eine Möglichkeit, den Codeabstand von einem bestimmten [n, k] Code zu schätzen. Angenommen, die Auswahl von $ d-1 $ -Stücken aus den Spaltenvektoren, aus denen die Paritätsprüfungsmatrix besteht, ist immer linear unabhängig, und die Auswahl von $ d $ -Stücken kann zu einer linearen Abhängigkeit führen. Zu diesem Zeitpunkt ist der Codeabstand gleich $ d $ [^ 11]. Lass es uns beweisen.
[^ 11]: Dies ist "Übungsübung 10.20" von Neilsen, Chan.
[Beweis]
Sei $ H $ eine Paritätsprüfungsmatrix mit dem Vorzeichen [n, k], und seien die Spaltenvektoren, aus denen dies besteht, $ \ {h_1, h_2, \ cdots, h_n \} $. Wenn ein Zeichen im Codebereich C $ x $ ist, dann ist $ H x = 0 $
h_1 x_1 + h_2 x_2 + \cdots + h_n x_n = 0 \tag{19}
Ist festgelegt. Nun zu einer positiven ganzen Zahl $ s (\ leq n) $
\begin{align}
& x_{i_1}, x_{i_2}, \cdots , x_{i_s} \neq 0 \\
& x_{i_{s+1}}, x_{i_{s+2}}, \cdots , x_{i_n} = 0 \tag{20}
\end{align}
Und setzen Sie $ x $
x = (x_{i_1}, x_{i_2}, \cdots , x_{i_s}, \cdots , x_{i_n})^{T} \tag{21}
Entscheide dich so. Wenn $ x $ ein Code im Codebereich ist, ersetzen Sie ihn in Gleichung (19) und
h_1 x_1 + h_2 x_2 + \cdots + h_s x_s = 0 \tag{22}
Muss halten. Unter der Annahme muss $ s $ größer als $ d-1 $ sein, da jedes $ d-1 $ von $ {h_i} $ linear unabhängig ist. Denn wenn $ s $ kleiner als $ d-1 $ ist, müssen $ x_1, x_2, \ cdots, x_s $ alle $ 0 $ von der Definition der linearen Unabhängigkeit sein. Wir wissen also, dass es $ s \ geq d $ sein sollte. Da $ s $ die Anzahl von $ 1 $ ist, die im Zeichen enthalten ist (dh das Hamming-Gewicht), muss es größer oder gleich $ d $ sein, dh der Abstand $ d (C) $ dieses Zeichens ist Muss $ d (C) \ geq d $ erfüllen.
Nun, da wir $ d (C) = d $ beweisen wollen, müssen wir nur zeigen, dass es mindestens ein Zeichen $ x $ mit einem Hamming-Gewicht von $ wt (x) = d $ gibt. Die Annahme ist, dass es $ d $ Spaltenvektoren gibt, die in den Spaltenvektoren, aus denen $ H $ besteht, linear abhängig sind, also $ h_ {i_1}, h_ {i_2}, \ cdots, h_ { Sagen wir i_d} $. Dann
a_{i_1} h_{i_1} + a_{i_2} h_{i_2} + \cdots + a_{i_d} h_{i_d} = 0 \tag{23}
Es wird $ a_ {i_1}, a_ {i_2}, \ cdots, a_ {i_d} \ neq 0 $ geben (aus der Definition der linearen Abhängigkeit). Mit diesem $ a_ {i_1}, a_ {i_2}, \ cdots, a_ {i_d} $,
x = (0, \cdots , 0, a_{i_1}, 0, \cdots , 0, a_{i_2}, 0, \cdots , 0, a_{i_d}, 0 , \cdots , 0) \tag{24}
Durch die Definition erfüllt dieses $ x $ $ Hx = 0 $, sodass gesagt werden kann, dass es ein Element des Codebereichs ist, den wir betrachten. Und das Hamming-Gewicht $ wt (x) $ dieses $ x $ ist $ d $. Sie haben jetzt $ d (C) = d $ bewiesen. (Ende der Zertifizierung)
Als nächstes kommt die zweite wichtige Sache.
Das Vorzeichen [n, k, d] muss die Beziehung $ n-k \ geq d-1 $ erfüllen. Mit anderen Worten, sobald $ n $ und $ k $ bestimmt sind, wird der mögliche $ d $ -Bereich automatisch bestimmt. Alternativ können Sie $ k $ und $ d $ festlegen und der mögliche $ n $ -Bereich wird automatisch bestimmt. Dieser relationale Ausdruck wird "Singleton-Grenze" genannt [^ 12]. Lass es uns beweisen.
[^ 12]: Dies ist "Übungsübung 10.21" von Neilsen, Chan.
[Beweis]
Da die Paritätsprüfungsmatrix von [n, k] Code eine $ (n-k) \ mal n $ -Matrix ist, ist ihr Rang
rank(H) \leq n-k \tag{25}
muss sein. Und der Rang ist die maximale Anzahl von Spaltenvektoren (oder Zeilenvektoren), aus denen die Matrix besteht, die linear unabhängig sind [^ 13]. Dies bedeutet, dass wenn Sie $ rank (H) + 1 $ Spaltenvektoren aus $ H $ auswählen, diese immer linear abhängig sind. Nach dem, was wir gerade bewiesen haben, entspricht der maximale Vorzeichenabstand der maximalen Anzahl linear unabhängiger Spaltenvektoren in $ H $ plus $ 1 $ [^ 14]. Das ist,
d \leq rank(H) + 1 \tag{26}
ist. Eliminieren von $ rank (H) $ aus den Gleichungen (25) und (26)
n-k \geq d-1 \tag{27}
Ist festgelegt. (Ende der Zertifizierung)
[^ 13]: Hmm? Wenn Sie das glauben, lesen Sie bitte das Buch der geeigneten linearen Algebra.
[^ 14]: Es kann schwierig sein, diesen Bereich zu lesen. Einschließlich der Bedeutung der zuvor bewiesenen Vorbedingung: "Wenn Sie $ d-1 $ auswählen, ist es immer linear unabhängig, und wenn Sie $ d $ auswählen, kann es linear abhängig werden." Bitte schauen Sie genauer hin. "Wenn Sie $ d-1 $ -Stücke auswählen, sind diese immer linear unabhängig" unterscheidet sich von der Tatsache, dass sie bei Auswahl von $ d $ -Stücken immer linear abhängig sind. Dies bedeutet, dass der Maximalwert von $ d-1 $ durch die maximale Anzahl linear unabhängiger Vektoren in $ H $ (dh $ rank (H) $) begrenzt ist.
Nachdem wir nun eine grundlegende Erklärung haben, möchte ich zwei spezifische Beispiele für Codierungsmethoden vorstellen. Einer ist der "Hamming-Code" und der andere ist der "horizontale und vertikale Paritätscode".
Der Hamming-Code ist ein $ [2 ^ {r} -1, 2 ^ {r} -r-1] $ -Code, der durch die Ganzzahl $ r \ geq 2 $ gekennzeichnet ist. Die Paritätsprüfungsmatrix $ H $ bei $ r = 3 $ ist unten dargestellt.
H =
\begin{pmatrix}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1
\end{pmatrix} \tag{28}
Es mag wie $ 0,1 $ zufällig ohne Regelmäßigkeit aussehen, ist es aber nicht. Wenn Sie die Spaltenvektoren in der Reihenfolge von links betrachten, sieht es aus wie eine Ganzzahl von $ 1 $ bis $ 8 $, die in eine 3-Bit-Binärzahl konvertiert wird. Die Paritätsprüfungsmatrix für den [n, k] -Code war die Matrix $ (n-k) \ times n $, daher ist die Paritätsprüfungsmatrix für den Hamming-Code die Matrix $ r \ times (2 ^ {r} -1) $. Wenn $ r = 3 $ ist, ist es eine $ 3 \ mal 7 $ Matrix, also ist Gleichung (28) sicherlich so.
Lassen Sie uns dies auf das Standardformular korrigieren. Sie müssen lediglich die Spaltenvektoren austauschen [^ 15].
[^ 15]: Entspricht der Änderung der Definition der Reihenfolge der Codes.
H =
\begin{pmatrix}
0 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 1
\end{pmatrix} \tag{29}
Es wird sein. In dieser Form kann die entsprechende Generierungsmatrix $ G $ sofort gefunden werden.
G =
\begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1
\end{pmatrix} \tag{30}
Es wird sein.
Wie ich zuvor erklärt habe, kann der Codeabstand aus der Paritätsprüfungsmatrix ermittelt werden. Die Form von Gleichung (28) ist leichter zu verstehen, schauen Sie also dort hin. Die Auswahl von zwei beliebigen Spaltenvektoren ist immer linear unabhängig. Beispielsweise ist die Auswahl der ersten und zweiten Spalte linear unabhängig (und der beiden anderen Spalten, die Sie auswählen). Wenn Sie jedoch die nächste dritte Spalte auswählen, ist diese linear abhängig. Der Abstand dieses [7,3] -Hamming-Codes beträgt also 3 [^ 16].
[^ 16]: Dies ist "Übungsübung 10.22" von Neilsen, Chan.
Die maximale Anzahl von Bits, die mit diesem Code korrigiert werden können, beträgt $ 3 = 2t + 1 $, was $ t $ entspricht. Sie können also sehen, dass jeder 1-Bit-Fehler korrigiert werden kann.
Durch Codieren mit der Standardgleichung (30), Berechnen des Fehlersyndroms mit Gleichung (29) und Vergleichen mit den Spaltenvektoren des Paritätsprüfcodes können Sie sehen, in welchem Bit der Fehler aufgetreten ist. Es ist also etwas invertiert [^ 17].
[^ 17]: Es ist möglicherweise besser, das Fehlersyndrom unter Verwendung von Gleichung (28) anstelle der Standardform zu berechnen. Es scheint einfach zu implementieren zu sein, da die Zahl, die durch Konvertieren der Binärsequenz des Fehlersyndroms in eine Dezimalzahl erhalten wird, gleich der Bitnummer ist, bei der der Fehler aufgetreten ist. Bei der Berechnung des Fehlersyndroms unter Verwendung des Standardformulars muss jedes Mal die Anzahl der Spalten in der Paritätsprüfungsmatrix bestimmt werden. Sie mögen denken, aber ich denke, es ist praktisch, eine Nachschlagetabelle im Voraus zu erstellen (obwohl die Implementierung etwas umständlich ist).
Die Entschlüsselung wurde in der Standardform berücksichtigt, sodass die ursprünglichen Informationen durch Extrahieren der ersten 4 Bits wiederhergestellt werden können.
Der horizontal-vertikale Paritätsprüfcode ist eine Codierungsmethode, die die ursprünglichen Informationen blockiert und die Parität beibehält. Wenn in der $ \ {0,1 \} $ -Serie die Anzahl von $ 1 $ gerade ist, wird die Parität als $ 0 $ (oder gerade Parität) definiert, und wenn sie ungerade ist, wird die Parität als $ 1 $ (oder ungerade Parität) definiert. Machen. Diese Parität wird getrennt von den ursprünglichen Informationsdaten beibehalten. Angenommen, die ursprüngliche Information ist eine 6-stellige $ \ {0,1 \} $ -Serie. Ordnen Sie die Informationen zu diesem Zeitpunkt in einem Block von $ 2 \ times 3 $ an. Zum Beispiel
1 0 1
0 1 1
Wird besorgt. Schauen Sie sich nun die vertikalen und horizontalen Sequenzen an, berechnen Sie die Parität der einzelnen Sequenzen und ordnen Sie sie rechts oder unten an. Dann
1 0 1 | 0
0 1 1 | 0
-------
1 1 0
Es wird sein. Diese Summe von 10 $ \ {0,1 \} $ wird als eindimensionale Reihe übertragen. Wenn Sie die Originalinformationen von links oben nach rechts unten scannen und dann den Zeilenparitätsteil und den Spaltenparitätsteil zusammen senden, beträgt die gesamte Codesequenz $ (1,0,1,0,1, Es wird 1,0,0,1,1,0) ^ {T} $ sein, was der [10,6] -Code ist.
Wenn ein Bit in der Originalinformation falsch ist, stimmt es nicht mit dem Paritätsteil überein. Wenn beispielsweise das Bit ganz rechts invertiert ist,
1 0 1 | 0
0 1 0 | 0
-------
1 1 0
Es wird in einem solchen Zustand sein. In diesem Fall stimmen die Paritätsberechnung in der zweiten Zeile und die Paritätsberechnung in der dritten Spalte nicht überein. An den nicht übereinstimmenden Zeilen und Spalten können Sie erkennen, wo der Fehler auftritt. Angenommen, im Paritätsteil tritt ein Fehler auf und der Paritätswert in der ersten Zeile wird invertiert.
1 0 1 | 1
0 0 0 | 0
-------
1 0 1
Es wird so sein. Dann ist die Paritätsberechnung der Spalte korrekt, aber nur die Parität der ersten Zeile hat einen seltsamen Wert. In diesem Fall kann festgestellt werden, dass die Parität selbst in der ersten Zeile invertiert ist.
Der Code ist auf diese Weise aufgebaut, aber es ist auch eine Art linearer Code.
Betrachten Sie zunächst die Generierungsmatrix.
Erzeugt einen Code, in dem die ursprüngliche Information $ (1,0,1,0,0,0) ^ {T} $ ist und der Paritätsteil $ (1,0,1,0,1) $ mit diesem zusammengeführt wird. TU es einfach. Da sich der ursprüngliche Informationsteil nicht so ändert, wie er ist, ist es ausreichend, eine Einheitsmatrix zu platzieren. Der Paritätsteil basiert auf den Originalinformationen
A =
\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 1
\end{pmatrix} \tag{31}
Sie können es durch Multiplizieren dieser Matrix generieren (natürlich ist die Berechnung Mod 2, nur für den Fall). Die erste Zeile von $ A $ ist die Paritätsberechnung der ersten Zeile des ursprünglichen Informationsblocks, die zweite Zeile von $ A $ ist die Paritätsberechnung der zweiten Zeile des ursprünglichen Informationsblocks und in der folgenden Reihenfolge die Parität der ersten Spalte Es dient zur Berechnung, Paritätsberechnung in der zweiten Spalte und Paritätsberechnung in der dritten Spalte. Daher ist die Generierungsmatrix $ G $ eine Kombination aus der Einheitsmatrix und diesem $ A $.
G =
\begin{pmatrix}
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 1
\end{pmatrix} \tag{32}
Es bedeutet das. Die Paritätsprüfungsmatrix ist einfach, da sie in der Standardform vorliegt.
H =
\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1
\end{pmatrix} \tag{33}
Wird sein.
Durch Berechnen des Fehlersyndroms unter Verwendung dieses $ H $ und Erkennen, welcher Spalte von $ H $ das Ergebnis entspricht, kann das Fehlerbit identifiziert werden, wenn dieses Bit also invertiert wird. Sie können Fehler korrigieren. Danach können Sie die ursprünglichen Informationen wiederherstellen, indem Sie die ersten 6 Bits extrahieren.
Nachdem Sie nun ein grundlegendes Verständnis der linearen Codes einschließlich konkreter Beispiele haben, wollen wir uns einem etwas fortgeschritteneren Thema widmen. Es gibt einen interessanten Satz namens "Gilbert-Varshamovs Grenzen", also werde ich ihn beweisen [^ 18].
[^ 18]: Neilsen, Chan "Übungsübung 10.23" (Der Wortlaut wurde jedoch in Bezug auf andere Dokumente geändert.) .. Es heißt: "Der Beweis ist einfach, also lasse ich ihn in der Übung", aber es ist überhaupt nicht einfach. Ich stoße oft darauf, wenn ich ein Mathematikbuch lese. Glauben Sie nicht den Worten "leicht zu verstehen" oder "offensichtlich".
[Satz: Grenzen von Gilbert-Varshamov]
Wenn für $ 0 \ leq \ delta \ leq \ frac {1} {2} $ eine ausreichend große Codelänge $ n $ verwendet wird, ist der Codeabstand $ d = \ delta n $ die Codierungsrate $ R \ geq 1 - Das Vorzeichen von H (\ delta) $ existiert. Wobei $ H $ eine binäre Entropie ist, definiert durch $ H (x) \ äquiv -x \ log (x) - (1-x) \ log (1-x) $.
Mit anderen Worten, dieser Satz realisiert den gegebenen Vorzeichenabstand $ d = \ delta n $ und die Codierungsrate beträgt $ 1-H (\ delta) $ oder mehr, wenn ein ausreichend großes $ n $ genommen wird. Dies bedeutet, dass der Code immer vorhanden ist. Lass es uns beweisen.
[Beweis des Satzes]
Nachdem ich eine "Hamming-Sphäre" definiert habe, werde ich zunächst zwei ergänzende Themen beweisen, die damit zusammenhängen.
Definition: Hammmng Sphere
Für $ x \ in \ {0,1 \} ^ {n} $ und die reelle Zahl $ r $ ist die auf $ x $ zentrierte "Hamming-Kugel" $ B (x, r) $
B(x,r) = \{y \in \{ 0,1 \}^{n}: d(x,y) \leq r \} \tag{34}
Es wird definiert in. Hier ist $ d (x, y) $ der Hamming-Abstand, also ist $ B (x, r) $ Kurz gesagt, die Differenz zwischen jedem Element ist kleiner als $ r $, zentriert auf $ x $. Betrachten Sie es als eine Versammlung. Wenn Sie zählen, wie viele dieser Punkte es gibt, ist es das Volumen der Hamming-Kugel. Das Volumen der Hamming-Kugel ist tatsächlich gleich, unabhängig davon, wo sich das Zentrum $ x $ befindet, solange der Radius $ r $ bestimmt wird. Hmm? Sie können denken, dass unabhängig vom Wert von $ x $ die Anzahl der Hamming-Kugeln, wenn höchstens $ r $ aus der Gesamtzahl der $ n $ -Elemente herausgenommen und invertiert wird, die Hamming-Kugel ist. Sie können sehen, dass es gleich dem Volumen von ist. Sein Volumen $ Vol (n, r) $ ist
Vol(n,r) = \sum_{j=0}^{r}
\begin{pmatrix}
n \\
j
\end{pmatrix} \tag{35}
Es kann mit berechnet werden.
Ergänzender Titel (1)
Für $ n $ ist $ 0 \ leq p \ leq \ frac {1} {2} $ groß genug
Vol(n,pn) \leq 2^{H(p)n} \tag{36}
Ist festgelegt.
Nachweis des ergänzenden Titels (1)
\begin{align}
\frac{Vol(n,pn)}{2^{H(p)n}} &= \frac{\sum_{j=0}^{pn} \begin{pmatrix} n \\ j \end{pmatrix}}{p^{-pn} \cdot (1-p)^{-(1-p)n}} \\
&= \sum_{j=0}^{pn} \begin{pmatrix} n \\ j \end{pmatrix} p^{pn} (1-p)^{(1-p)n} \\
&= \sum_{j=0}^{pn} \begin{pmatrix} n \\ j \end{pmatrix} (1-p)^{n} (\frac{p}{1-p})^{pn} \tag{37}
\end{align}
Hier ist $ p \ leq \ frac {1} {2} $ $ \ frac {p} {1-p} \ leq 1 $, also
\begin{align}
\frac{Vol(n,pn)}{2^{H(p)n}} &\leq \sum_{j=0}^{pn} \begin{pmatrix} n \\ j \end{pmatrix} (1-p)^{n} (\frac{p}{1-p})^{j} \\
&= \sum_{j=0}^{pn} \begin{pmatrix} n \\ j \end{pmatrix} (1-p)^{n-j} p^{j} \\
&= ((1-p)+p)^{n} = 1^{n} = 1 \tag{38}
\end{align}
Daraus kann Gleichung (36) abgeleitet werden. (Ende des Nachweises des ergänzenden Titels (1))
Ergänzender Titel (2)
|C| \geq \frac{2^{n}}{Vol(n,d-1)} \tag{39}
Ist festgelegt. Hier,
Nachweis des ergänzenden Titels (2)
Für jedes $ x \ in \ {0,1 \} ^ {n} $, das nicht in $ C $ enthalten ist, gibt es mindestens ein Zeichen $ c_x \ in C $.
d(x,c_x) \leq d-1 \tag{40}
Ist festgelegt. Dies liegt daran, dass es in Ordnung ist, $ x $ in den Codebereich $ C $ aufzunehmen (da der Abstand unveränderlich ist), wenn dies nicht zutrifft, was der Annahme widerspricht.
Dann ist die gesamte Menge $ \ {0,1 \} ^ {n} $ gleich der Summe aller Kugeln mit einem Radius von $ d-1 $, zentriert auf $ c \ in C $. .. Das ist,
\{ 0,1 \}^{n} = \bigcup_{c \in C} B(c,d-1) \tag{41}
Deshalb,
\begin{align}
2^{n} &= | \{ 0,1 \}^{n} | = | \bigcup_{c \in C} B(c,d-1)| \\
&\leq \bigcup_{c \in C} | B(c,d-1) | \\
&= |C| \sum_{j=0}^{d-1} \begin{pmatrix} n \\ j \end{pmatrix} \\
&= |C| Vol(n,d-1) \tag{42}
\end{align}
Nächster,
|C| \geq \frac{2^{n}}{Vol(n,d-1)} \tag{39}
Sie können sehen, dass dies zutrifft. (Ende des Nachweises des ergänzenden Titels (2))
Lassen Sie uns nun den Hauptteil zertifizieren. Es ist ein Moment, in dem du hierher kommst. Unter Verwendung der Untertitel (1) und (2), wobei die Codierungsrate $ R $, $ d = \ delta n $ und die binäre Entropie $ H (\ cdot) $ beträgt,
\begin{align}
R &= \frac{\log |C|}{n} \geq \frac{n - \log Vol(n,d-1)}{n} \\
&\geq \frac{n - H(\delta - 1/n)n}{n} \\
&= 1 - H(\delta - \frac{1}{n}) \\
&\geq 1 - H(\delta) \tag{43}
\end{align}
Ist festgelegt. (Ende des Beweises des Satzes)
Dieser Satz kann auch wie folgt umformuliert werden.
Wenn Sie $ k $ für ein ausreichend großes $ n $ wählen,
\frac{k}{n} \geq 1 - H(\frac{2t}{n}) \tag{44}
Es gibt einen [n, k] Fehlercode, der vor $ t $ Bitfehlern schützt, die [^ 19] erfüllen. Sie können aus der Beziehung von $ d = 2t + 1 $ zwischen dem Vorzeichenabstand $ d $ und der Anzahl der fehleranfälligen Bits $ t $ ersehen.
[^ 19]: Neilsen, Chan wird auf diese Weise erklärt.
Als Abschluss der theoretischen Erklärung werde ich erklären, was als "dualer Code" bezeichnet wird. Es ist ein wichtiges Schlüsselkonzept bei der Erstellung eines Quantencodes namens CSS-Code.
Angenommen, $ C $ ist ein [n, k] -Zeichen mit einer Generierungsmatrix $ G $ und einer Paritätsprüfungsmatrix $ H $. Zu diesem Zeitpunkt hat $ C $ ein duales [n, nk] -Zeichen $ C ^ {\ perp} $, eine Generierungsmatrix $ H ^ {T} $ und eine Paritätsprüfungsmatrix $ G ^ {T} $. Als eine Sache definiert. Das heißt, das Dual von $ C $ besteht aus Codes, die orthogonal zu allen in $ C $ enthaltenen Codes sind. Wenn $ C \ subseteq C ^ {\ perp} $, wird das Vorzeichen $ C $ als "schwaches Selbst-Dual" bezeichnet, und wenn $ C = C ^ {\ perp} $, wird es als "streng selbst-dual" bezeichnet.
Hier werde ich zwei Eigenschaften erklären, die in Bezug auf den dualen Code gelten.
Erstens ist das erste.
Ein Vorzeichen mit einer Generationsmatrix $ G $ kann nur dann als schwaches Selbst-Dual bezeichnet werden, wenn $ G ^ {T} G = 0 $ [^ 20]. Das ist,
G^{T}G = 0 \Leftrightarrow C \subseteq C^{\perp} \tag{45}
Ist festgelegt. Lass es uns beweisen.
[^ 20]: Dies ist "Übungsübung 10.24" von Neilsen, Chan.
[Beweis]
Wenn Sie $ y = Gx $ für alle $ x \ in \ {0,1 \} ^ {k} $ ausführen, werden alle $ y \ in C $ ausnahmslos generiert. Wenn Sie $ y \ in C $ auswählen und die Paritätsprüfungsmatrix von $ C ^ {T} $ anwenden, erhalten Sie $ G ^ {T} y = G ^ {T} Gx $. Da $ G ^ {T} G = 0 $ angenommen wurde, ist $ G ^ {T} y = 0 $. Dann ist das willkürlich ausgewählte $ y $ auch ein Element von $ C ^ {\ perp} $. Daher gilt $ C \ subseteq C ^ {\ perp} $.
Wenn es $ y \ in C $ ist, ist es auch $ y \ in C ^ {\ perp} $. Wenn Sie daher die Paritätsprüfungsmatrix von $ C ^ {\ perp} $ auf $ y $ anwenden, ist dies $ 0 $. Das heißt, $ G ^ {T} y = 0 $. Da $ y = Gx $, $ G ^ {T} Gx = 0 $, was für jedes $ x $ gelten muss, ist $ G ^ {T} G = 0 $.
(Ende der Zertifizierung)
Als nächstes kommt der zweite.
Für das lineare Vorzeichen $ C $
\begin{align}
x \in C^{\perp} &\Rightarrow \sum_{y \in C} (-1)^{xy} = |C| \\
x \notin C^{\perp} &\Rightarrow \sum_{y \in C} (-1)^{xy} = 0 \tag{46}
\end{align}
Ist etabliert [^ 21]. Lass es uns beweisen.
[^ 21]: Dies ist "Übungsübung 10.25" von Neilsen, Chan. Wo $ xy $ geschrieben ist, ist das innere Produkt von $ x $ und $ y $. Sie sollten also wirklich $ x ^ {T} y $ schreiben, aber $ T $ weglassen.
[Beweis]
Erstens die erste Hälfte.
Die $ C $ -Erzeugungs- und Paritätsprüfmatrizen seien $ G, H $, und die $ C ^ {\ perp} $ -Erzeugungs- und Paritätsprüfmatrizen seien $ H ^ {T}, G ^ {T} $. Informationen vor der Zuordnung zu $ y \ in C $ vor der Zuordnung zu $ a \ in \ {0,1 \} ^ {k} $, $ x \ in C ^ {\ perp} $ Die Informationen seien $ b \ in \ {0,1 \} ^ {nk} $. Zu diesem Zeitpunkt ist $ x = H ^ {T} b, y = Ga $ und $ xy = b ^ {T} HG a = 0 $, also
x \in C^{\perp} \Rightarrow \sum_{y \in C} (-1)^{xy} = \sum_{y \in C} 1 = |C| \tag{47}
Ist festgelegt.
Als nächstes kommt die zweite Hälfte.
Jedes $ y \ in C $ kann als $ y = Ga $ unter Verwendung der $ a \ in \ {0,1 \} ^ {k} $ - und $ C $ -Erzeugungsmatrix $ G $ geschrieben werden. Ich kann. Hier $ a $
a = (a_1, a_2, \cdots , a_k)^{T} \tag{48}
Ausgedrückt durch seine Komponenten wie G,
G = (g_1, g_2, \cdots , g_k) \tag{49}
Verwenden wir die Spaltenvektoren $ g_1, g_2, \ cdots, g_k $ wie in. Dann ist das innere Produkt von $ x \ notin C ^ {\ perp} $ und $ y $
xy = xGa = a_1 (x g_1) + a_2 (x g_2) + \cdots + a_k (x g_k) \tag{50}
Kann geschrieben werden. Hier ist mindestens eines von $ (x g_ {i}) $ immer $ 1 $. Dies liegt daran, dass, wenn sie alle $ 0 $ sind, $ x $ und $ y $ orthogonal sind und die Annahme von $ x \ notin C ^ {\ perp} $ abgelehnt wird. Angenommen, $ (x g_1) $ ist $ 1 $ (unabhängig davon, welches $ (x g_ {i}) $ 1 ist, gilt das folgende Argument). Dann
xy = xGa = a_1 + a_2 (x g_2) + \cdots + a_k (x g_k) \tag{51}
Nächster,
\begin{align}
\sum_{y \in C} (-1)^{xy}
&= \sum_{a_1, a_2, \cdots , a_k = 0,1} (-1)^{a_1} (-1)^{a_2 (xg_2) + \cdots + a_k (xg_k)} \\
&= \sum_{a_2, \cdots , a_k = 0,1} (1+(-1)) (-1)^{a_2 (xg_2) + \cdots + a_k (xg_k)} \\
&= 0 \tag{52}
\end{align}
(Ende der Zertifizierung)
Die Erklärung der Theorie ist ziemlich lang geworden, aber jetzt, da sie vollständig ist, wollen wir die Funktionsweise des linearen Codes mit einem Python-Programm überprüfen. Ich hätte die drei Codes "Wiederholungscode", "Hamming-Code" und "horizontaler und vertikaler Code" verstehen sollen, also würde ich gerne alle ausprobieren, aber ich werde müde, also mache ich nur einen. Alles war in Ordnung, aber irgendwie habe ich versucht, "Hamming-Code" zu verwenden.
Es generiert zufällig Informationsdaten, codiert sie mit einem Hamming-Code und invertiert ein zufällig ausgewähltes Bit. Korrigieren Sie es und entschlüsseln Sie es, um sicherzustellen, dass der Fehler korrekt ist. Der gesamte Python-Code ist unten.
import numpy as np
def decimal_to_binlist(decimal, digits): # ex) 6,3 --> [1,1,0]
bin_str = "{:0{digits}b}".format(decimal, digits=digits)
return [int(s) for s in list(bin_str)]
def binlist_to_decimal(bin_list): # ex) [0,1,1] --> 3
return int("".join([str(i) for i in bin_list]), 2)
def make_hamming_matrix(r):
# parity check matrix (H)
A = []
for x in range(1,2**r):
bin_list = decimal_to_binlist(x, r)
if sum(bin_list) == 1: continue
A.append(bin_list)
A = np.array(A)
I_H = np.eye(r, dtype=int)
H = np.concatenate([A, I_H])
# represent integer each row of H matrix (for error correction algorithm)
H_int = [binlist_to_decimal(row) for row in H]
# generator matrix (G)
I_G = np.eye(2**r-r-1, dtype=int)
G = np.concatenate([I_G, A], 1)
return G, H, H_int
def generate_data(k, N): # random k-bits data
for _ in range(N):
yield np.random.randint(2, size=k)
def add_noise(d_in): # bit flip to one bit (select randomly)
idx = np.random.randint(len(d_in))
err = np.array([1 if i == idx else 0 for i in range(len(d_in))])
d_out = (d_in + err) % 2
return d_out
def correct_error(d_in, H_int):
d_out = d_in.copy()
p = (d_out @ H) % 2
x = binlist_to_decimal(p)
err_idx = H_int.index(x)
d_out[err_idx] = (d_out[err_idx] + 1) % 2 # bit flip (recover)
return d_out
if __name__ == '__main__':
r = 3
n = 2**r - 1
k = 2**r - r - 1
N = 10
G, H, H_int = make_hamming_matrix(r)
print("* input(random) -> encode -> add noise(random 1-bit flip) -> correct -> decode:")
err_count = 0
for x in generate_data(k, N):
y = (x @ G)%2
y_error = add_noise(y)
y_correct = correct_error(y_error, H_int)
x_correct = y_correct[0:k] # decode (= extract 1st to k-th elements)
print("{0:} -> {1:} -> {2:} -> {3:} -> {4:}".format(x,y,y_error,y_correct,x_correct))
if sum((x+x_correct)%2) == 1: # if x != x_correct --> 1
err_count += 1
err_rate = err_count / N
print("* error rate = {0:} (count:{1:} / total:{2:})".format(err_rate, err_count, N))
Ich werde erklären, was Sie tun. Schauen Sie sich den Hauptverarbeitungsabschnitt an.
r = 3
n = 2**r - 1
k = 2**r - r - 1
N = 10
Stellen Sie die Parameter mit ein. Wenn Sie den Wert von r einstellen (3 im obigen Beispiel, aber Sie können ihn beliebig ändern), werden die Vorzeichen n und k [n, k] automatisch bestimmt. Geben Sie an, wie viele Daten zufällig mit N generiert werden sollen.
G, H, H_int = make_hamming_matrix(r)
Berechnen Sie dann die Hamming-Code-Generierungsmatrix G und die Paritätsprüfmatrix H. Hier ist eine Anmerkung. In der obigen theoretischen Erklärung ist die [n, k] -Codegenerierungsmatrix die $ n \ times k $ -Matrix, die Paritätsprüfungsmatrix ist die $ (nk) \ times n $ -Matrix und die Codegenerierung ist $ Gx $. Ich habe geschrieben. Aufgrund der Bequemlichkeit des Programms wird jedoch jedes in eine Translokationsmatrix umgewandelt. Daher wird der Code durch Multiplizieren von der gegenüberliegenden Seite wie $ xG $ generiert. Wenn Sie numpy verwenden, ist es natürlicher, einen Vektor als horizontalen Vektor anstelle eines vertikalen Vektors zu schreiben, also habe ich dies getan. Es mag etwas verwirrend sein, aber bitte wechseln Sie (sorry).
H_int ist eine Liste des Bitarrays jeder Zeile der Paritätsprüfmatrix (jede Spalte in der Notation, wenn die Theorie erklärt wird), die in Dezimalzahlen umgewandelt wurde. Es ist einfacher, dies bei der Berechnung der Fehlerkorrektur zu haben, daher gebe ich es als Randnotiz aus.
Schauen Sie sich nun die Definition der Funktion make_hamming_matrix an.
# parity check matrix (H)
A = []
for x in range(1,2**r):
bin_list = decimal_to_binlist(x, r)
if sum(bin_list) == 1: continue
A.append(bin_list)
A = np.array(A)
I_H = np.eye(r, dtype=int)
H = np.concatenate([A, I_H])
Erstellen Sie eine Paritätsprüfungsmatrix in Standardform. Mit anderen Worten, erstellen Sie eine r-dimensionale Einheitsmatrix I_H und eine andere Matrix A und führen Sie sie vertikal mit der Verkettung von numpy zusammen. Jede Zeile der Hamming-Code-Paritätsprüfmatrix (jede Spalte in der Notation zum Zeitpunkt der theoretischen Erklärung) war eine binäre Spalte von ganzen Zahlen von 1 bis 2 ** r. Jetzt möchte ich es zu einer Standardform machen, also nehme ich nur die anderen Ganzzahlen als die der Einheitsmatrix entsprechende heraus, mache es zu einer binären Zeichenfolge und ordne es vertikal an, um eine Matrix A zu bilden. Ich mache das in der for-Schleife oben. Berechnen Sie eine Binärzeichenfolge aus dezimalem x mit binlist = decimal_to_binlist (x, r) und weisen Sie sie binlist zu. Informationen zur Verarbeitung mit decimal_to_binlist finden Sie in der Funktionsdefinition. Wenn die for-Schleife fertig ist, machen Sie sie zu einer Numpy-Matrix und führen Sie sie mit der von Numpys Auge erstellten Einheitsmatrix zusammen, um die Paritätsprüfungsmatrix H zu erstellen.
# represent integer each row of H matrix (for error correction algorithm)
H_int = [binlist_to_decimal(row) for row in H]
Hier berechnen wir die Liste der Dezimalzahlen für jede Zeile von H. Die Funktion binlist_to_decimal ist eine Funktion, die eine Binärzeichenfolge in eine Dezimalzeichenfolge konvertiert. Informationen zur internen Verarbeitung finden Sie in der Funktionsdefinition.
# generator matrix (G)
I_G = np.eye(2**r-r-1, dtype=int)
G = np.concatenate([I_G, A], 1)
Erstellen Sie dann die Generierungsmatrix G. Es ist ein Standardtyp, also einfach. Sie müssen lediglich die Matrix A und die Einheitsmatrix horizontal zusammenführen.
Kehren wir nun zum Hauptverarbeitungsabschnitt zurück.
err_count = 0
for x in generate_data(k, N):
...
Initialisieren Sie dann den Fehlerzähler err_count auf 0 und geben Sie die for-Schleife ein. Mit generate_data (k, N) werden N Teile von k-Bit-Daten zufällig generiert. Weisen Sie x jedes der Daten zu und führen Sie die Verarbeitung in der Schleife aus. Informationen zum Verarbeitungsinhalt der Funktion generator_data finden Sie in der Funktionsdefinition.
Unten ist der Inhalt der Schleife.
y = (x @ G)%2
Dann lasse x auf die Erzeugungsmatrix G einwirken, um das Vorzeichen y zu erzeugen. Da ich jedoch Mod 2 berechnen muss, setze ich es auf '% 2'.
y_error = add_noise(y)
Fügen Sie dann zufällig Rauschen zu y hinzu, um y_error zu erzeugen. Insbesondere werden die Bits zufällig ausgewählt und invertiert. Informationen zum Verarbeitungsinhalt von add_noise finden Sie in der Funktionsdefinition.
y_correct = correct_error(y_error, H_int)
Führt eine Fehlerkorrektur durch. Schauen wir uns den Inhalt der Funktionrect_error an.
d_out = d_in.copy()
p = (d_out @ H) % 2
x = binlist_to_decimal(p)
err_idx = H_int.index(x)
d_out[err_idx] = (d_out[err_idx] + 1) % 2 # bit flip (recover)
return d_out
Die erste Zeile kopiert die Eingabedaten d_in nach d_out. Die Paritätsprüfungsmatrix wird in der zweiten Zeile angewendet. Das Ergebnis ist eine binäre Sequenz. Bestimmt, welcher Zeile der Paritätsprüfungsmatrix dies entspricht. Verwenden Sie daher binlist_to_decimal in der 3. Zeile, um es in eine Dezimalzahl umzuwandeln, und verwenden Sie dann die Indexmethode, um herauszufinden, welcher Spalte von H_int es in der 4. Zeile entspricht. Weisen Sie es err_idx zu. Zeile 5 invertiert das err_idxth-Bit von d_out. Schließlich wird d_out zurückgegeben (ich suche jedes Mal mit der Indexmethode, aber ich denke, es ist besser, LUT zu verwenden. Es ist problematisch, daher habe ich die Implementierung weggelassen).
Kehren wir nun zum Hauptverarbeitungsabschnitt zurück.
x_correct = y_correct[0:k] # decode (= extract 1st to k-th elements)
Entschlüsselt die Originalinformationen aus dem fehlerkorrigierten Code y_correct. Es ist ein Standardtyp, also einfach. Nehmen Sie einfach das k-te Bit von Anfang an heraus. Nachdem die Verarbeitungsserie abgeschlossen ist,
print("{0:} -> {1:} -> {2:} -> {3:} -> {4:}".format(x,y,y_error,y_correct,x_correct))
Anzeigen der Daten jeder Stufe.
if sum((x+x_correct)%2) == 1: # if x != x_correct --> 1
err_count += 1
Wenn der Fehler nicht behoben wurde, addieren Sie 1 zur Fehleranzahl.
Schließlich,
err_rate = err_count / N
print("* error rate = {0:} (count:{1:} / total:{2:})".format(err_rate, err_count, N))
Anzeige der Fehlerrate.
Lassen Sie uns nun das Ergebnis der Ausführung des obigen Codes sehen.
* input(random) -> encode -> add noise(random 1-bit flip) -> correct -> decode:
[1 0 1 1] -> [1 0 1 1 0 1 0] -> [1 0 1 1 1 1 0] -> [1 0 1 1 0 1 0] -> [1 0 1 1]
[1 0 1 1] -> [1 0 1 1 0 1 0] -> [1 1 1 1 0 1 0] -> [1 0 1 1 0 1 0] -> [1 0 1 1]
[0 1 0 1] -> [0 1 0 1 0 1 0] -> [1 1 0 1 0 1 0] -> [0 1 0 1 0 1 0] -> [0 1 0 1]
[0 1 0 1] -> [0 1 0 1 0 1 0] -> [1 1 0 1 0 1 0] -> [0 1 0 1 0 1 0] -> [0 1 0 1]
[1 0 1 0] -> [1 0 1 0 1 0 1] -> [1 0 1 1 1 0 1] -> [1 0 1 0 1 0 1] -> [1 0 1 0]
[0 1 1 1] -> [0 1 1 1 1 0 0] -> [0 1 1 1 1 0 1] -> [0 1 1 1 1 0 0] -> [0 1 1 1]
[0 1 1 1] -> [0 1 1 1 1 0 0] -> [0 1 1 1 0 0 0] -> [0 1 1 1 1 0 0] -> [0 1 1 1]
[0 1 1 1] -> [0 1 1 1 1 0 0] -> [1 1 1 1 1 0 0] -> [0 1 1 1 1 0 0] -> [0 1 1 1]
[1 1 1 1] -> [1 1 1 1 1 1 1] -> [0 1 1 1 1 1 1] -> [1 1 1 1 1 1 1] -> [1 1 1 1]
[0 0 1 0] -> [0 0 1 0 1 1 0] -> [0 0 1 1 1 1 0] -> [0 0 1 0 1 1 0] -> [0 0 1 0]
* error rate = 0.0 (count:0 / total:10)
Da die ursprünglichen Informationen zufällig generiert wurden und das Rauschen auch zufällig war, änderten sich die Eingabe- / Ausgabedaten jedes Mal, wenn sie ausgeführt wurden, aber der Fehler wurde immer vollständig korrigiert. Glückwunsch Glückwunsch.
Basierend auf Neilsen, Chan habe ich versucht, den Raum zwischen den Zeilen sorgfältig auszufüllen, während ich mich auf andere Dokumente bezog, sodass es ein ziemlich langer Satz wurde. Es ist weg. Als ich die Übungen von [Neilsen, Chan] bemerkte (https://www.ohmsha.co.jp/book/9784274200090/), hatte ich fast alle erobert (ob sie jedoch richtig antworteten). .. Dadurch hat sich mein Verständnis der Grundlagen erheblich verbessert. Dies ist jedoch eine "klassische" Fehlerkorrekturgeschichte. Die darauf basierende Geschichte von "Quantum" ist (wahrscheinlich) noch tiefer und umfassender. Es ist immer noch launisch und in meinem eigenen Tempo, aber ich werde mein Bestes geben.
das ist alles
Recommended Posts