Dans Article précédent, j'ai découvert sur quel type de cadre la correction d'erreur quantique est basée. Maintenant que nous avons la perspective de diverses corrections d'erreurs quantiques autres que le code Shor, nous nous demandons quelles autres méthodes sont disponibles. Mais avant cela, il semble nécessaire de comprendre le «code linéaire classique». On dit que la connaissance des codes linéaires classiques est utilisée comme base pour le développement de diverses méthodes de correction d'erreur quantique. Donc, cette fois, nous étudierons les codes linéaires classiques. Après avoir tout compris, je voudrais confirmer le fonctionnement du code linéaire classique par un programme Python.
Permettez-moi d'abord de dire ce que j'essaie d'expliquer dans les sections qui suivent. Cet article est grossièrement divisé en parties «explication de la théorie» et «simulation». Dans «Explication de la théorie», après avoir expliqué «matrice de génération», «matrice d'inspection de parité» et «distance de code» qui sont les concepts de base du code linéaire classique, «code de Hamming» et «parité horizontale / verticale» sont des exemples concrets de méthodes de codage. Jetons un coup d'œil aux «signes». De plus, nous aborderons les thèmes un peu plus avancés de "les limites de Gilbert-Varshamov" et du "double signe". "Simulation" simule le comportement du code de Hamming. Tout en regardant l'exemple d'implémentation et le résultat du traitement en Python, assurez-vous que l'erreur est corrigée.
Les documents suivants ont été utilisés comme références.
Commençons par une histoire simple. Une version très primitive du code linéaire classique est une méthode de codage qui répète simplement les informations d'origine (ci-après dénommé «code de répétition»). Par exemple, chaque bit d'une série de bits binaires,
\begin{align}
0 \rightarrow 000 \\
1 \rightarrow 111 \tag{1}
\end{align}
Il est transmis avec une triple redondance comme. Les informations qui étaient à l'origine 0 deviennent 000, donc par exemple, même si l'un des bits de ceci est inversé à 010, c'est parce que l'un des 000 avait une inversion de bits, et il était à l'origine 0. Vous pouvez deviner que c'était (c'est-à-dire que vous pouvez corriger l'erreur). Si vous inversez 2 bits, cela sera corrigé par erreur, mais si la probabilité est faible, c'est mieux que de ne rien faire, n'est-ce pas? En général, le code de correction d'erreur consiste essentiellement à rendre les informations de bit d'origine redondantes et à les étendre. Le rendre redondant et en expansion s'appelle «encodage». Il existe différentes méthodes de codage.
Pour le dire un peu mathématiquement abstrait, une séquence de bits constituée de $ k $ $ \ {0,1 \} $ est un ensemble de $ \ {0,1 \} ^ {k} $. On peut dire que c'est un élément de. De même, les séquences $ n $ bits sont des éléments de l'ensemble $ \ {0,1 \} ^ {n} $. Par conséquent, le codage est un vecteur de dimension $ k $ $ x \ in \ {0,1 \} ^ {k} $ vers un vecteur de dimension $ n $ $ y \ in \ {0,1 \ Correspond à un mappage vers } ^ {n} $. Le code qui limite ce mappage à la transformation linéaire est appelé le "code linéaire" [^ 1]. De plus, l'espace composé du code après conversion linéaire est appelé "espace de code".
[^ 1]: Afin de clarifier le contraste avec le quantum, le titre de cet article est "code linéaire classique", mais comme il est gênant dans le texte, je l'appellerai simplement "code linéaire".
Par exemple, le codage qui rend 1 bit redondant sur 3 bits est
G =
\begin{pmatrix}
1\\
1\\
1
\end{pmatrix} \tag{2}
On peut dire qu'il s'agit d'une transformation linéaire définie par la matrice. Application de la matrice de transformation $ G $ à $ 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}
Et vous pouvez voir qu'il fait la même chose que l'équation (1). Le code de répétition est donc un code linéaire. Cette $ G $ est appelée "matrice génératrice" dans le sens où c'est une matrice qui génère un code à partir des informations d'origine. Depuis lors, diverses opérations linéaires apparaîtront, mais toutes les opérations algébriques seront effectuées avec 2 comme méthode. Sinon, chaque bit ne rentrera pas dans $ \ {0,1 \} $ [^ 2].
[^ 2]: Au fait, dans cet article, nous ne traitons que des codes basés sur des nombres binaires, mais en théorie générale des codes linéaires, la théorie est construite de manière à pouvoir être basée sur n'importe quel nombre, et elle est basée sur des nombres q-aires. Il semble que le code défini sur s'appelle spécialement "code linéaire d'élément q".
Alors, voici un exemple. Quel type d'opération de codage représente la matrice de génération suivante $ G $?
\begin{pmatrix}
1 & 0 \\
1 & 0 \\
1 & 0 \\
0 & 1 \\
0 & 1 \\
0 & 1
\end{pmatrix} \tag{4}
C'est facile.
\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}
C'est l'encodage. Auparavant, nous avons rendu 1 bit redondant sur 3 bits, mais cette fois nous avons rendu 2 bits redondants sur 6 bits. Généralement, le code qui code k bits en n bits est appelé code [n, k]. Le premier exemple est le code [3,1], et cet exemple est le code [6,2]. Comme vous pouvez le voir facilement, la matrice de génération de code [n, k] est la matrice $ n \ times k $ [^ 3].
[^ 3]: Il existe des littératures et des textes qui décrivent l'opération de codage comme $ xG $, avec la matrice de génération $ G $ comme matrice $ k \ times n $ et le signe $ x $ comme vecteur horizontal. Dans la partie "Explication de la théorie" de cet article, selon Neilsen, Chan, le code $ x $ est le vecteur vertical et la matrice de génération est $ n. En tant que matrice \ times k $, écrivons l'opération de codage comme $ Gx $. Comme je l'expliquerai plus tard, dans la partie "simulation", il est inversé pour plus de commodité. Mais pour le moment, pensez aux informations d'origine et au signe comme un vecteur vertical.
Vous pourriez avoir pensé que vous pouviez créer librement n'importe quel code linéaire en définissant la matrice de génération de manière appropriée comme ceci, mais ce n'est pas le cas. Pour que la matrice $ G $ soit une matrice de génération, chaque vecteur de colonne $ \ {g_1, g_2, \ cdots, g_k \} $ qui compose la matrice de génération doit être linéairement indépendant. Étant donné la dépendance linéaire, différentes informations $ x $ et $ x ^ {\ prime} $ peuvent être mappées sur le même signe $ y $.
Que voulez-vous dire? Ceci est expliqué ci-dessous.
Le signe $ y $ provient des informations originales $ x $
y = Gx = \sum_{i=0}^{k} g_{i} x_{i} \tag{6}
Il est généré en appliquant la matrice de génération $ G $ comme dans. Maintenant, $ x ^ {\ prime} $, qui est différent de $ x $,
y^{\prime} = Gx^{\prime} = \sum_{i=0}^{k} g_{i} x_{i}^{\prime} \tag{7}
Supposons qu'il soit généré comme suit. Si $ \ {g_i \} $ est linéairement indépendant, alors Eq. (7) moins Eq. (6),
y^{\prime} - y = \sum_{i=0}^{k} g_{i} (x_{i}^{\prime} - x_{i}) \tag{8}
Dans, le côté gauche n'est $ 0 $ que lorsque $ x_ {i} ^ {\ prime} --x_ {i} = 0 $ pour tout $ i $ (d'après la définition de l'indépendance linéaire). Autrement dit, $ y $ et $ y ^ {\ prime} $ ne sont égaux que lorsque $ x $ et $ x ^ {\ prime} $ sont égaux. Inversement, si les vecteurs $ x $ et $ x ^ {\ prime} $ sont différents, alors $ y $ et $ y ^ {\ prime} $ seront toujours différents.
D'un autre côté, considérez ce qui se passe si $ \ {g_i \} $ est linéairement dépendant. Par exemple, pour plus de simplicité
g_1 = g_2 + g_3 \tag{9}
Supposons que la relation soit établie. Ceci est linéairement dépendant [^ 4]. Ensuite, l'équation (6)
[^ 4]: Il m'arrive maintenant d'apporter les 2e et 3e $ g_i $ et d'en mettre la somme exactement égale au 1er $ g_i $, mais même si ce n'est pas le cas ( (Même si vous apportez une combinaison), la discussion suivante tient.
\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}
Et $ x = (x_1, x_2, x_3, x_4, \ cdots, x_k) ^ T $ et $ x ^ {\ prime} = (\ bar {x_1}, \ bar {x_2}, \ bar {x_3}, x_4, \ cdots, x_k) ^ T $ générera le même signe (où $ \ bar {x_i} $ est l'inversion de bits de $ x_i $). Ainsi, chaque vecteur de colonne qui compose la matrice générée doit être linéairement indépendant [^ 5].
[^ 5]: Ceci complète "Exercice pratique 10.15" de Neilsen, Chan (probablement).
Puisqu'il était possible d'encoder en appliquant la matrice de génération aux informations d'origine, considérons ensuite la détection du bruit ajouté au code. Tout d'abord, un exemple concret est montré. La première matrice de génération de code de répétition [3,1] montrée était l'équation (2). Pour le code généré
H =
\begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 1
\end{pmatrix} \tag{11}
Que se passe-t-il si vous appliquez la matrice? Uniquement lorsque le signe $ x $ est $ (0,0,0) ^ T $ et $ (1,1,1) ^ {T} $ (c'est-à-dire seulement s'il n'y a pas d'erreur),
H x = 0 \tag{12}
Sera. À part cela, ce ne sera pas 0 $. Par conséquent, il peut être déterminé qu'il y a eu une erreur. Le bit ayant une erreur est déterminé par un algorithme différent en fonction de la méthode de codage. Dans le cas de cet exemple, si $ Hx $ est $ (1,0) ^ {T} $, le premier bit, si $ (1,1) ^ {T} $, le deuxième bit, $ ( Dans le cas de 0,1) ^ {T} $, il peut être déterminé qu'il y a eu une erreur dans le troisième bit. La matrice $ H $ construite pour vérifier les erreurs de cette manière est appelée "matrice de contrôle de parité" et est définie comme satisfaisant la relation dans l'équation (12). Dans le cas de cet exemple, puisqu'il s'agit d'un code répétitif, il est possible de faire un jugement en prenant une décision majoritaire tous les 3 bits, mais pour correspondre à différents codes linéaires, il est plus général de vérifier le résultat par opération linéaire. Ce sera une façon de dire.
L'exemple suivant de la matrice de génération de code de répétition [6,2] était l'équation (4). Quelle est la matrice de contrôle de parité pour cela? Attendez 1 minute.
Comment c'est? Avez-vous compris?
Maintenant, disons la réponse (même si je pense que vous pouvez la voir).
\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}
C'est vrai [^ 6]. Je pense qu'il est facile de voir que c'est le cas. La conversion du vecteur à 6 dimensions sur le côté droit de l'équation (5) avec la matrice ci-dessus se traduira par $ 0 $, mais s'il y a une erreur dans un bit, ce ne sera pas $ 0 $. Il est possible de déterminer quel bit était incorrect par les mêmes règles qu'auparavant. Et la matrice de génération du code [n, k] était $ n \ times k $ matrix, mais la matrice de contrôle de parité correspondante est $ (n-k) \ times n $ matrix.
Disons-le un peu plus général. Supposons que du bruit soit ajouté au $ y $ encodé et qu'il change comme $ y ^ {\ prime} = y + e $. En multipliant cela par la matrice de contrôle de parité, on obtient $ Hy ^ {\ prime} = Hy + He = He $, ne laissant que la contribution à l'information d'erreur ajoutée par le bruit. Ce $ Hy ^ {\ prime} $ est appelé "syndrome d'erreur". Ensuite, sur la base du résultat du calcul de ce syndrome d'erreur, l'erreur est corrigée concrètement. Si une erreur se produit dans le bit $ j $ th, $ e $ est un vecteur avec le composant $ j $ th dans $ 1 $ et le reste dans $ 0 $. Par conséquent, le résultat du calcul de $ Hy ^ {\ prime} $ est exactement égal au vecteur de colonne de la colonne $ j $ de $ H $. Par conséquent, si vous déterminez à quelle colonne de $ H $ le syndrome d'erreur est égal, vous saurez quel bit est incorrect. Si vous inversez ce bit, vous avez corrigé l'erreur.
[^ 6]: C'est la réponse à "Exercice pratique 10.17" de Neilsen, Chan.
Maintenant, ne serait-il pas bien de trouver la matrice de contrôle de parité à partir de la matrice générée que vous avez créée, ou inversement, de trouver la matrice générée à partir de la matrice de contrôle de parité donnée? (Veuillez réfléchir!) En fait, vous pouvez le faire de la manière suivante.
Pour obtenir la matrice de contrôle de parité à partir de la matrice générée, choisissez $ nk $ vecteurs linéaires indépendants $ y_1, y_2, \ cdots, y_ {nk} $ orthogonaux à la colonne $ G $, et la ligne $ H $ est $ Défini sur y_ {1}, y_ {2}, \ cdots, y_ {nk} $. Inversement, pour trouver la matrice générée à partir de la matrice de contrôle de parité, sélectionnez $ k $ vecteurs linéairement indépendants $ y_1, y_2, \ cdots, y_k $ ce noyau $ H $, et $ G $ est $ y_1, Défini pour avoir les colonnes y_2, \ cdots, y_k $.
Hmm? Cela peut se sentir comme ça, alors mâchez-le un peu.
Si vous appliquez $ G $ aux informations d'origine $ x $, les encodez, puis appliquez $ H $ tel quel (sans erreur), ce sera $ 0 $. C'est 0 $ pour tout $ x $, donc
HG = 0 \tag{14}
La relation tient [^ 7]. Si vous voulez trouver $ H $ à partir du $ G $ donné, vous devez satisfaire l'équation (14), donc de tous les vecteurs colonnes qui composent $ G $ et tous les vecteurs lignes qui composent $ H $. Le produit intérieur doit être tout à 0 $. En d'autres termes, il doit être orthogonal. L'espace de code entier est de dimension $ n $, et les vecteurs de colonne qui composent $ G $ sont $ k $. Si vous choisissez un vecteur linéairement indépendant orthogonal à cela, ce sera inévitablement $ n-k $ pièces. Donc, je pense que vous avez une image de $ H $ de $ G $. Ensuite, si vous voulez trouver $ G $ à partir du $ H $ donné. Tout d'abord, considérons l'espace où le "noyau" de $ H $ est placé. Le noyau de l'opérateur linéaire $ A $ est le sous-espace du vecteur entier $ x $ tel que $ Ax = 0 $. Dans ce cas, l'espace qui calcule $ H $ pour devenir $ 0 $ est l'espace de code créé par $ G $, donc si vous trouvez un vecteur linéairement indépendant qui pose le noyau de $ H $, c'est le code. C'est un vecteur linéaire indépendant qui étire l'espace. Puisque $ H $ est une ligne $ n-k $ pour un espace de dimension $ n $ dans son ensemble, nous pouvons obtenir des vecteurs indépendants linéaires $ k $ [^ 8]. Ensuite, définissez-le comme vecteur de colonne pour $ G $ et vous avez terminé avec $ G $. Plus tôt, j'ai mentionné que la matrice de contrôle de parité est une matrice $ (n-k) \ times n $, mais je pense que vous pouvez voir pourquoi il en est ainsi.
[^ 7]: Ceci est "Exercice pratique 10.18" de Neilsen, Chan. Je pense que cela ressort clairement de la définition de la matrice de contrôle de parité.
[^ 8]: Cela peut être plus facile à comprendre si vous pensez à $ Hx = 0 $ comme une équation simultanée composée de $ n-k $ équations avec des variables $ n $. Puisque la dimension $ n $ de la liberté a des conditions de liaison $ n-k $, le degré net de liberté est après tout la dimension $ k $.
Ce n'est pas grave pour terminer cette section, mais il y a une autre chose importante concernant les matrices de contrôle de parité. Autrement dit, la matrice de contrôle de parité peut être réécrite à tout moment dans le "formulaire standard", en préservant son effet. Le type standard est
H = (A|I_{n-k}) \tag{15}
C'est une matrice de la forme. Où $ A $ représente une matrice d'unité de dimension $ (n-k) \ times k $ et $ I_ {n-k} $. L'équation (15) est une matrice qui semble être disposée côte à côte et fusionnée. Si $ H $ est une matrice de contrôle de parité, alors $ H x = 0 $ est valable pour le vecteur $ x $ sur l'espace de code. Si vous regardez cela comme une équation simultanée de $ n-k $ constituée de $ n $ variables, vous pouvez voir pourquoi elle peut être réécrite sous la forme de l'équation (15). Rappelez-vous les mathématiques du premier cycle du secondaire. Lors de la résolution des équations simultanées, je pense qu'en regardant chaque équation, en multipliant les deux côtés par quelque chose et en ajoutant ou en soustrayant (c'est-à-dire qu'il s'agit d'une méthode d'addition ou de soustraction), je pense que cela est progressivement devenu une forme simple, mais j'imagine la même opération S'il vous plaît. Cependant, comme le nombre d'équations est petit par rapport au nombre de variables, la solution exacte ne peut être obtenue. La réponse est de représenter chacune des variables $ n-k $ comme la somme linéaire des autres variables $ k $. C'est exactement ce que l'équation (15) est assignée à $ Hx = 0 $.
Lorsque la matrice de contrôle de parité est normalisée de cette manière, la matrice de génération peut être obtenue directement à partir d'ici. Utilisation de $ I_k $ comme matrice unitaire de dimension $ k $
G =
\begin{pmatrix}
I_k \\
-A
\end{pmatrix} \tag{16}
Fais juste. Puisque $ HG = 0 $, c'est certainement la matrice générée pour la matrice de contrôle de parité dans l'équation (15] [^ 9]. Comment c'est? C'est facile. Plus tôt, j'ai expliqué le noyau de l'opérateur, l'indépendance linéaire, etc., mais c'est un moment!
[^ 9]: $ -A $ dans l'équation (16) peut être remplacé par $ A $ en supprimant le moins s'il est basé sur un nombre binaire comme cette fois, c'est-à-dire si vous considérez un code linéaire binaire. Tous les calculs sont basés sur 2.
Ensuite, en utilisant la matrice générée créée de cette manière, les informations d'origine sont les premiers éléments $ k $ du vecteur de dimension $ n $ encodé lui-même. Si vous avez pu corriger l'erreur dans la procédure précédente, vous pouvez restaurer les informations d'origine en extrayant simplement le premier $ k $ (facile!).
Maintenant que nous avons expliqué la matrice de génération et la matrice de contrôle de parité, nous allons maintenant expliquer un autre concept important, la «distance de signe».
Définissez la distance $ d (y, y ^ {\ prime}) $ dans les deux vecteurs $ y, y ^ {\ prime} $ sur l'espace de code $ \ {0,1 \} ^ {n} $ peut faire. Comparez chaque élément de $ y $ et $ y ^ {\ prime} $ et utilisez la somme des différentes choses comme distance (cependant, la somme est calculée normalement, pas le calcul basé sur 2). La distance ainsi définie est appelée "distance de Hamming". De plus, le "poids de Hamming" $ wt (y) $ avec le signe $ y $ est défini comme $ wt (y) \ equiv d (y, 0) $ comme la distance du vecteur $ 0 $.
En utilisant cette distance de Hamming, nous définissons la "distance de signe" $ d (C) $ de l'espace de code $ C $ obtenu par le codage spécifié par $ y = G x $ comme suit.
d(C) = \min_{x,y \in C, x \neq y} d(x,y) \tag{17}
En d'autres termes, la valeur minimale de la distance de Hamming entre deux codes choisis arbitrairement est la distance de code (elle est donc également appelée «distance minimale» du code). Puisque $ d (x, y) = wt (x + y) $ tient, [^ 10], l'équation (17) est
[^ 10]: $ d (x, y) $ était la somme des différents éléments de $ x, y $. Cela équivaut à faire $ x + y (mod \ space 2) $ puis à compter le nombre de $ 1 $ inclus comme élément. D'autre part, $ wt (x + y) $ est, par définition, exactement le nombre de $ 1 $ inclus comme son élément. Par conséquent, $ d (x + y) = wx (x + y) $ est valable.
d(C) = \min_{x \in C, x \neq 0} wt(x) \tag{18}
C'est la même chose même s'il est réécrit sous la forme.
Puisque la distance de code est une quantité de caractéristiques très importante qui représente les caractéristiques de l'espace de code, le code [n, k] dont la distance de code est $ d = d (C) $ est surtout [n, k, d]. Il est souvent décrit dans.
L'une des raisons pour lesquelles il est si important est qu'il montre combien de bits de correction d'erreur sont possibles. [3,1] En rappelant le code répétitif, la distance de ce code est de 3 selon la définition courante. Puisqu'il est triplé, si vous corrigez l'erreur par décision majoritaire, vous pouvez certainement gérer une erreur allant jusqu'à 1 bit. [5,1] Dans le cas d'un code de répétition, la distance est de 5, et si l'erreur est corrigée par la méthode de décision majoritaire, jusqu'à une erreur de 2 bits peut être gérée. En étendant cela, si la distance de code est de 2t $ + 1 $, vous pouvez certainement corriger l'erreur dans le bit $ t $. Par conséquent, la distance de code est étroitement liée au nombre de bits corrigibles d'erreurs. En général, un signe unique $ qui remplit $ d (y, y ^ {\ prime}) \ leq t $ avec le signe gâté $ y ^ {\ prime} $ par un signe à une distance de $ 2t + 1 $. Décrypter simplement comme y $ peut corriger les erreurs jusqu'au bit $ t $.
Il y a deux choses plus importantes à dire concernant la distance du signe, que je vais expliquer dans l'ordre.
Premièrement, le premier.
Il existe un moyen d'estimer la distance du code à partir d'un code [n, k] donné. Supposons que la sélection de toute pièce $ d-1 $ à partir des vecteurs de colonne qui composent la matrice de contrôle de parité soit toujours linéairement indépendante, et la sélection de $ d $ pièces peut entraîner une dépendance linéaire. À ce stade, la distance de code est égale à $ d $ [^ 11]. Prouvons-le.
[^ 11]: Ceci est "Exercice pratique 10.20" de Neilsen, Chan.
[Preuve]
Soit $ H $ une matrice de contrôle de parité avec le signe [n, k], et que les vecteurs colonnes qui la composent soient $ \ {h_1, h_2, \ cdots, h_n \} $. Si un signe sur l'espace de code C est $ x $, alors $ H x = 0 $, donc
h_1 x_1 + h_2 x_2 + \cdots + h_n x_n = 0 \tag{19}
Est établi. Maintenant pour un entier positif $ 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}
Et mettez $ x $
x = (x_{i_1}, x_{i_2}, \cdots , x_{i_s}, \cdots , x_{i_n})^{T} \tag{21}
Décidez comme ça. Si $ x $ est un code sur l'espace de code, remplacez-le dans l'équation (19) et
h_1 x_1 + h_2 x_2 + \cdots + h_s x_s = 0 \tag{22}
Doit tenir. Par hypothèse, $ s $ doit être supérieur à $ d-1 $ car tout $ d-1 $ de $ {h_i} $ est linéairement indépendant. Parce que si $ s $ est inférieur à $ d-1 $, $ x_1, x_2, \ cdots, x_s $ doit tous être $ 0 $ d'après la définition de l'indépendance linéaire. Nous savons donc que ce devrait être $ s \ geq d $. Puisque $ s $ est le nombre de $ 1 $ contenu dans le signe (c'est-à-dire le poids de Hamming), il doit être supérieur ou égal à $ d $, c'est-à-dire que la distance $ d (C) $ de ce signe est Doit rencontrer $ d (C) \ geq d $.
Maintenant que nous voulons prouver $ d (C) = d $, il suffit de montrer qu'il y a au moins un signe $ x $ avec un poids de Hamming $ wt (x) = d $. L'hypothèse est qu'il existe des vecteurs de colonne $ d $ qui sont linéairement dépendants dans les vecteurs de colonne qui composent $ H $, donc $ h_ {i_1}, h_ {i_2}, \ cdots, h_ { Disons i_d} $. Puis
a_{i_1} h_{i_1} + a_{i_2} h_{i_2} + \cdots + a_{i_d} h_{i_d} = 0 \tag{23}
Il y aura $ a_ {i_1}, a_ {i_2}, \ cdots, a_ {i_d} \ neq 0 $ (d'après la définition de la dépendance linéaire). En utilisant ce $ 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}
En définissant, ce $ x $ satisfait $ Hx = 0 $, donc on peut dire qu'il est un élément de l'espace de code que nous considérons. Et le poids de Hamming $ wt (x) $ de ce $ x $ est $ d $. Vous avez maintenant prouvé $ d (C) = d $. (Fin de la certification)
Vient ensuite la deuxième chose importante.
Le signe [n, k, d] doit satisfaire la relation $ n-k \ geq d-1 $. En d'autres termes, une fois que $ n $ et $ k $ sont déterminés, la plage $ d $ possible est automatiquement déterminée. Alternativement, vous pouvez décider de $ k $ et $ d $ et la plage $ n $ possible sera déterminée automatiquement. Cette expression relationnelle est appelée "limite de Singleton" [^ 12]. Prouvons-le.
[^ 12]: Ceci est "Exercice pratique 10.21" de Neilsen, Chan.
[Preuve]
Puisque la matrice de contrôle de parité du code [n, k] est une matrice $ (n-k) \ times n $, son rang est
rank(H) \leq n-k \tag{25}
doit être. Et le rang est le nombre maximum de vecteurs colonnes (ou vecteurs lignes) qui composent la matrice qui sont linéairement indépendants [^ 13]. Cela signifie que si vous choisissez les vecteurs de colonne $ rank (H) + 1 $ dans $ H $, ils seront toujours linéairement dépendants. D'après ce que nous venons de prouver, la distance maximale entre les signes est égale au nombre maximum de vecteurs colonnes linéairement indépendants contenus dans $ H $ plus $ 1 $ [^ 14]. C'est,
d \leq rank(H) + 1 \tag{26}
est. Élimination de $ rank (H) $ des équations (25) et (26)
n-k \geq d-1 \tag{27}
Est établi. (Fin de la certification)
[^ 13]: Hmm? Si vous pensez cela, veuillez vous référer au livre de l'algèbre linéaire appropriée.
[^ 14]: Cela peut être difficile à comprendre en lisant cette section. Y compris la signification de la précondition prouvée précédemment, "Si vous sélectionnez n'importe quel $ d-1 $, il sera toujours linéairement indépendant, et si vous sélectionnez $ d $, il peut être linéairement dépendant." Veuillez regarder de plus près. «Si vous sélectionnez des pièces $ d-1 $, elles seront toujours linéairement indépendantes» est différent du fait que si vous sélectionnez $ d $ pièces, elles seront toujours linéairement dépendantes. Cela signifie que la valeur maximale de $ d-1 $ est limitée par le nombre maximal de vecteurs linéairement indépendants dans $ H $ (c'est-à-dire $ rank (H) $).
Maintenant que nous avons une explication de base, je voudrais vous présenter deux exemples spécifiques de méthodes de codage. L'un est le "code de Hamming" et l'autre est le "code de parité horizontale et verticale".
Le code de Hamming est un code $ [2 ^ {r} -1, 2 ^ {r} -r-1] $ caractérisé par l'entier $ r \ geq 2 $. La matrice de contrôle de parité $ H $ lorsque $ r = 3 $ est présentée ci-dessous.
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}
Cela peut ressembler à 0,1 $ aléatoire sans régularité, mais ce n'est pas le cas. Si vous regardez les vecteurs de colonne dans l'ordre à partir de la gauche, cela ressemble à un entier de 1 $ à 8 $ $ converti en un nombre binaire de 3 bits. La matrice de contrôle de parité pour le code [n, k] était la matrice $ (n-k) \ times n $, donc la matrice de contrôle de parité pour le code de Hamming est la matrice $ r \ times (2 ^ {r} -1) $. Si $ r = 3 $, c'est une matrice $ 3 \ fois 7 $, donc l'équation (28) est certainement comme ça.
Corrigeons cela au formulaire standard. Tout ce que vous avez à faire est d'échanger les vecteurs de colonne [^ 15].
[^ 15]: correspond à la modification de la définition de l'ordre des 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}
Ce sera. Sous cette forme, la matrice de génération correspondante $ G $ peut être trouvée en un instant.
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}
Ce sera.
Comme je l'ai expliqué précédemment, la distance de code peut être trouvée à partir de la matrice de contrôle de parité. La forme de l'équation (28) est plus facile à comprendre, alors jetez-y un œil. Le choix de deux vecteurs de colonne est toujours linéairement indépendant. Par exemple, le choix des première et deuxième colonnes est linéairement indépendant (et les deux autres que vous choisissez). Cependant, si vous sélectionnez la troisième colonne suivante, elle sera linéairement dépendante. Ainsi, la distance de ce [7,3] -Code de Hamming est 3 [^ 16].
[^ 16]: Ceci est "Exercice pratique 10.22" de Neilsen, Chan.
Le nombre maximum de bits qui peuvent être corrigés avec ce code est de 3 $ = 2t + 1 $, soit $ t $, vous pouvez donc voir que toute erreur de 1 bit peut être corrigée.
En codant avec l'équation standard (30), en calculant le syndrome d'erreur avec l'équation (29) et en le comparant avec les vecteurs de colonne du code de contrôle de parité, vous pouvez voir quel bit l'erreur s'est produite. Donc, inversez-le [^ 17].
[^ 17]: Il peut être préférable de calculer le syndrome d'erreur en utilisant l'équation (28) au lieu de la forme standard. Cela semble facile à mettre en œuvre car le nombre obtenu en convertissant la séquence binaire du syndrome d'erreur en un nombre décimal est égal au nombre de bits où l'erreur s'est produite. Lors du calcul du syndrome d'erreur à l'aide du formulaire standard, il est nécessaire de déterminer à chaque fois le nombre de colonnes dans la matrice de contrôle de parité. Vous pourriez penser, mais je pense qu'il est pratique de créer une table de consultation à l'avance (même si c'est un peu lourd à mettre en œuvre).
Le décryptage a été pris en compte sous la forme standard, de sorte que les informations d'origine peuvent être restaurées en extrayant les 4 premiers bits.
Le code de contrôle de parité horizontal-vertical est une méthode de codage qui bloque les informations d'origine et conserve la parité. Dans la série $ \ {0,1 \} $, si le nombre de $ 1 $ est pair, la parité est définie comme $ 0 $ (ou parité paire), et si elle est impaire, la parité est définie comme $ 1 $ (ou parité impaire). Faire. Cette parité est conservée séparément des données d'information d'origine. Par exemple, supposons que les informations d'origine soient une série $ \ {0,1 \} $ à 6 chiffres. À ce stade, organisez les informations dans un bloc de 2 $ \ fois 3 $. Par exemple
1 0 1
0 1 1
ça ira. Maintenant, regardez les séquences verticales et horizontales, calculez la parité de chacune et organisez-les à droite ou en bas. Puis
1 0 1 | 0
0 1 1 | 0
-------
1 1 0
Ce sera. Ce total de 10 $ \ {0,1 \} $ est transmis sous forme de série unidimensionnelle. Si vous scannez les informations d'origine de haut à gauche en bas à droite, puis envoyez la partie de parité de ligne et la partie de parité de colonne ensemble, la séquence de code entière est $ (1,0,1,0,1, Ce sera 1,0,0,1,1,0) ^ {T} $, qui est le code [10,6].
Si un bit des informations d'origine est incorrect, il sera incompatible avec la partie parité. Par exemple, si le bit le plus à droite est inversé,
1 0 1 | 0
0 1 0 | 0
-------
1 1 0
Ce sera dans un tel état. Si vous le faites, le calcul de parité de la deuxième ligne et le calcul de parité de la troisième colonne ne correspondront pas. Vous pouvez voir où l'erreur se produit à partir des lignes et des colonnes qui ne correspondent pas. Supposons également qu'une erreur se produise dans la partie de parité et que la valeur de parité sur la première ligne soit inversée.
1 0 1 | 1
0 0 0 | 0
-------
1 0 1
Ce sera comme ça. Ensuite, le calcul de parité de la colonne est tout correct, mais seule la parité de la première ligne a une valeur étrange. Dans ce cas, il peut être déterminé que la parité elle-même sur la première ligne est inversée.
Le code est composé de cette manière, mais c'est aussi une sorte de code linéaire.
Tout d'abord, considérons la matrice de génération.
Génère un code dans lequel les informations d'origine sont $ (1,0,1,0,0,0) ^ {T} $ et la partie de parité $ (1,0,1,0,1) $ est fusionnée avec elle. Simplement fais-le. Puisque la partie informationnelle d'origine ne change pas telle quelle, il suffit de mettre une matrice unitaire. La partie parité est basée sur les informations d'origine
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}
Vous pouvez le générer en multipliant une telle matrice (bien sûr, le calcul est mod 2, juste au cas où). La première ligne de $ A $ est le calcul de parité de la première ligne du bloc d'informations d'origine, la deuxième ligne de $ A $ est le calcul de parité de la deuxième ligne du bloc d'informations d'origine, et dans l'ordre suivant, la parité de la première colonne C'est pour le calcul, le calcul de la parité dans la deuxième colonne et le calcul de la parité dans la troisième colonne. Par conséquent, la matrice de génération $ G $ est une combinaison de la matrice unitaire et de ce $ 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}
Cela signifie que. La matrice de contrôle de parité est facile car elle se présente sous la forme standard.
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}
Sera.
En calculant le syndrome d'erreur en utilisant ce $ H $ et en voyant à quelle colonne de $ H $ le résultat correspond, le bit d'erreur peut être identifié, donc si ce bit est inversé. Vous pouvez corriger les erreurs. Après cela, vous pouvez restaurer les informations d'origine en extrayant les 6 premiers bits.
Maintenant que vous avez une compréhension de base des codes linéaires, y compris des exemples concrets, abordons un sujet légèrement plus avancé. Il existe un théorème intéressant appelé "Les limites de Gilbert-Varshamov", donc je vais le prouver [^ 18].
[^ 18]: Neilsen, Chan "Exercice pratique 10.23" (Cependant, le libellé a été modifié par rapport à d'autres documents) .. Il dit: "La preuve est facile, je vais donc la laisser dans l'exercice", mais ce n'est pas du tout facile. Je le rencontre souvent en lisant un livre de mathématiques. Ne croyez pas les mots «facilement compréhensible» ou «évident».
[Théorème: Limites de Gilbert-Varshamov]
Pour $ 0 \ leq \ delta \ leq \ frac {1} {2} $, si une longueur de code suffisamment grande $ n $ est prise, la distance de code $ d = \ delta n $, le taux de codage $ R \ geq 1 --Le signe de H (\ delta) $ existe. Où $ H $ est une entropie binaire, définie par $ H (x) \ equiv -x \ log (x) - (1-x) \ log (1-x) $.
En d'autres termes, ce théorème réalise la distance de signe donnée $ d = \ delta n $ et le taux de codage est $ 1-H (\ delta) $ ou plus si un $ n $ suffisamment grand est pris. Cela signifie que le code existe toujours. Prouvons-le.
[Preuve du théorème]
Premièrement, après avoir défini une "sphère de Hamming", je vais prouver deux sujets supplémentaires qui y sont liés.
Définition: Sphère de Hammmng
Pour $ x \ in \ {0,1 \} ^ {n} $ et le nombre réel $ r $, la "sphère de Hamming" $ B (x, r) $ centrée sur $ x $ est
B(x,r) = \{y \in \{ 0,1 \}^{n}: d(x,y) \leq r \} \tag{34}
Il doit être défini dans. Ici, $ d (x, y) $ est la distance de Hamming, donc $ B (x, r) est $ En bref, la différence entre chaque élément est inférieure à $ r $ centrée sur $ x $. Pensez-y comme un rassemblement. Si vous comptez le nombre de ces points, c'est le volume de la sphère de Hamming. Le volume de la sphère de Hamming est en fait le même quel que soit le centre $ x $, tant que le rayon $ r $ est déterminé. Hmm? Vous pouvez penser que, quelle que soit la valeur de $ x $, le nombre de sphères de Hamming lorsque au plus $ r $ est retiré du nombre total d'éléments $ n $ et inversé est la sphère de Hamming. Vous pouvez voir qu'il est égal au volume de. Son volume $ Vol (n, r) $ est
Vol(n,r) = \sum_{j=0}^{r}
\begin{pmatrix}
n \\
j
\end{pmatrix} \tag{35}
Il peut être calculé avec.
Titre supplémentaire (1)
Pour $ n $, $ 0 \ leq p \ leq \ frac {1} {2} $ assez grand
Vol(n,pn) \leq 2^{H(p)n} \tag{36}
Est établi.
Preuve de titre supplémentaire (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}
Ici, $ p \ leq \ frac {1} {2} $ est $ \ frac {p} {1-p} \ leq 1 $, donc
\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}
De là, l'équation (36) peut être dérivée. (Fin de la preuve du titre supplémentaire (1))
Titre supplémentaire (2)
|C| \geq \frac{2^{n}}{Vol(n,d-1)} \tag{39}
Est établi. ici,
Preuve de titre supplémentaire (2)
Pour chaque $ x \ in \ {0,1 \} ^ {n} $ non inclus dans $ C $, il y a au moins un signe $ c_x \ dans C $,
d(x,c_x) \leq d-1 \tag{40}
Est établi. C'est parce que s'il ne tient pas, il est correct d'inclure $ x $ dans l'espace de code $ C $ (car la distance est invariante), ce qui contredit l'hypothèse.
Alors l'ensemble entier $ \ {0,1 \} ^ {n} $ est égal à la somme de toutes les sphères de rayon $ d-1 $ centrées sur $ c \ en C $. .. C'est,
\{ 0,1 \}^{n} = \bigcup_{c \in C} B(c,d-1) \tag{41}
Donc,
\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}
Suivant,
|C| \geq \frac{2^{n}}{Vol(n,d-1)} \tag{39}
Vous pouvez voir que c'est vrai. (Fin de la preuve du titre supplémentaire (2))
Maintenant, certifions le corps principal. C'est un moment où tu viens ici. En utilisant les sous-titres (1) et (2), où le taux d'encodage est $ R $, $ d = \ delta n $, et l'entropie binaire est $ H (\ cdot) $,
\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}
Est établi. (Fin de la preuve du théorème)
Ce théorème peut également être reformulé comme suit.
Si vous choisissez $ k $ pour un $ n $ suffisamment grand,
\frac{k}{n} \geq 1 - H(\frac{2t}{n}) \tag{44}
Il existe un code d'erreur [n, k] qui protège contre les erreurs $ t $ bit qui satisfont [^ 19]. Vous pouvez voir à partir de la relation de $ d = 2t + 1 $ entre la distance du signe $ d $ et le nombre de bits sujets aux erreurs $ t $.
[^ 19]: Neilsen, Chan est expliqué de cette manière.
En conclusion de l'explication théorique, j'expliquerai ce que l'on appelle un "code dual". C'est un concept clé important dans la construction d'un code quantique appelé code CSS.
Supposons que $ C $ soit un signe [n, k] avec une matrice de génération $ G $ et une matrice de contrôle de parité $ H $. A ce moment, $ C $ a un double signe [n, nk] $ C ^ {\ perp} $, une matrice de génération $ H ^ {T} $, et une matrice de contrôle de parité $ G ^ {T} $. Défini comme une chose. Autrement dit, le dual de $ C $ se compose de codes orthogonaux à tous les codes contenus dans $ C $. Si $ C \ subseteq C ^ {\ perp} $, le signe $ C $ est dit "self-dual faible", et si $ C = C ^ {\ perp} $, il est dit "strictement self-dual".
Ici, je vais expliquer deux propriétés qui sont valables par rapport au code dual.
Le premier est le premier.
Un signe avec une matrice de génération $ G $ peut être considéré comme un self-dual faible uniquement lorsque $ G ^ {T} G = 0 $ [^ 20]. C'est,
G^{T}G = 0 \Leftrightarrow C \subseteq C^{\perp} \tag{45}
Est établi. Prouvons-le.
[^ 20]: Ceci est "Exercice pratique 10.24" de Neilsen, Chan.
[Preuve]
En faisant $ y = Gx $ pour tout $ x \ in \ {0,1 \} ^ {k} $, tout $ y \ en C $ sera généré sans exception. Si vous choisissez n'importe quel $ y \ dans C $ et appliquez la matrice de contrôle de parité de $ C ^ {T} $, vous obtenez $ G ^ {T} y = G ^ {T} Gx $. Puisque $ G ^ {T} G = 0 $ a été supposé, $ G ^ {T} y = 0 $. Ensuite, le $ y $ choisi arbitrairement est aussi un élément de $ C ^ {\ perp} $. Par conséquent, $ C \ subseteq C ^ {\ perp} $ tient.
Si c'est $ y \ en C $, c'est aussi $ y \ en C ^ {\ perp} $. Par conséquent, si vous appliquez la matrice de contrôle de parité de $ C ^ {\ perp} $ à $ y $, ce sera $ 0 $. Autrement dit, $ G ^ {T} y = 0 $. Puisque $ y = Gx $, alors $ G ^ {T} Gx = 0 $, qui doit tenir pour tout $ x $, donc $ G ^ {T} G = 0 $.
(Fin de la certification)
Vient ensuite le second.
Pour le signe linéaire $ 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}
Est établi [^ 21]. Prouvons-le.
[^ 21]: Ceci est "Exercice pratique 10.25" de Neilsen, Chan. Où $ xy $ est écrit est le produit interne de $ x $ et $ y $. Vous devriez donc vraiment écrire $ x ^ {T} y $, mais omettre $ T $.
[Preuve]
Tout d'abord, la première moitié.
Soit les matrices de génération et de contrôle de parité $ C $ $ G, H $, et les matrices de génération et de contrôle de parité $ C ^ {\ perp} $ $ H ^ {T}, G ^ {T} $. Information avant d'être mappée à $ y \ en C $ avant d'être mappée à $ a \ in \ {0,1 \} ^ {k} $, $ x \ in C ^ {\ perp} $ Soit l'information $ b \ in \ {0,1 \} ^ {nk} $. A ce moment, $ x = H ^ {T} b, y = Ga $ et $ xy = b ^ {T} HG a = 0 $, donc
x \in C^{\perp} \Rightarrow \sum_{y \in C} (-1)^{xy} = \sum_{y \in C} 1 = |C| \tag{47}
Est établi.
Vient ensuite la seconde moitié.
Tout $ y \ dans C $ peut être écrit comme $ y = Ga $ en utilisant la matrice de génération $ a \ in \ {0,1 \} ^ {k} $ et $ C $ $ G $. Je peux. Ici, $ a $
a = (a_1, a_2, \cdots , a_k)^{T} \tag{48}
Exprimé par ses composants comme, G,
G = (g_1, g_2, \cdots , g_k) \tag{49}
Utilisons les vecteurs de colonne $ g_1, g_2, \ cdots, g_k $ comme dans. Ensuite, le produit interne de tout $ x \ notin C ^ {\ perp} $ et $ y $ sera
xy = xGa = a_1 (x g_1) + a_2 (x g_2) + \cdots + a_k (x g_k) \tag{50}
Peut être écrit. Ici, au moins un des $ (x g_ {i}) $ est toujours $ 1 $. C'est parce que s'ils sont tous $ 0 $, $ x $ et $ y $ seront orthogonaux, et l'hypothèse de $ x \ notin C ^ {\ perp} $ sera refusée. Supposons maintenant que $ (x g_1) $ est $ 1 $ (peu importe lequel $ (x g_ {i}) $ est 1, l'argument suivant est vrai). Puis
xy = xGa = a_1 + a_2 (x g_2) + \cdots + a_k (x g_k) \tag{51}
Suivant,
\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}
(Fin de la certification)
L'explication de la théorie est devenue assez longue, mais maintenant qu'elle est complète, vérifions le fonctionnement du code linéaire avec un programme Python. J'aurais dû comprendre les trois codes, «code de répétition», «code de Hamming» et «code horizontal et vertical», alors j'aimerais tous les essayer, mais je suis fatigué alors je n'en ferai qu'un. Tout allait bien, mais d'une manière ou d'une autre j'ai essayé d'utiliser le "code de Hamming".
Il génère de manière aléatoire des données d'information, les code avec un code de Hamming et inverse un bit sélectionné au hasard. Corrigez-le et décryptez-le pour vous assurer que l'erreur est correcte. Le code Python complet est ci-dessous.
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))
Je vais vous expliquer ce que vous faites. Regardez la section de traitement principale.
r = 3
n = 2**r - 1
k = 2**r - r - 1
N = 10
Réglez les paramètres avec. Si vous définissez la valeur de r (3 dans l'exemple ci-dessus, mais vous pouvez la modifier arbitrairement), le signe [n, k] n et k sont automatiquement déterminés. Spécifiez le nombre de données à générer aléatoirement avec N.
G, H, H_int = make_hamming_matrix(r)
Ensuite, calculez la matrice de génération de code de Hamming G et la matrice de contrôle de parité H. Voici une note. Dans l'explication théorique ci-dessus, la matrice de génération de code [n, k] est la matrice $ n \ times k $, la matrice de contrôle de parité est la matrice $ (nk) \ times n $ et la génération de code est $ Gx $. J'ai écrit. Cependant, en raison de la commodité du programme, chacun est transformé en une matrice de translocation. Par conséquent, le code est généré en multipliant par le côté opposé comme $ xG $. Lorsque vous utilisez numpy, il est plus naturel d'écrire un vecteur sous forme de vecteur horizontal au lieu d'un vecteur vertical, c'est pourquoi je l'ai fait. Cela peut être un peu déroutant, mais veuillez changer (désolé).
H_int est une liste du tableau de bits de chaque ligne de la matrice de contrôle de parité (chaque colonne de la notation lorsque la théorie est expliquée) convertie en nombres décimaux. Il est plus facile de l'avoir lors du calcul de la correction d'erreurs, donc je la publie en note d'accompagnement.
Regardez maintenant la définition de la fonction make_hamming_matrix.
# 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])
Créez une matrice de contrôle de parité sous forme standard. En d'autres termes, créez une matrice unitaire r-dimensionnelle I_H et une autre matrice A, et fusionnez-les verticalement avec la concaténation de numpy. Chaque ligne de la matrice de contrôle de parité de code de Hamming (chaque colonne de la notation au moment de l'explication théorique) était une colonne binaire d'entiers de 1 à 2 ** r. Maintenant, je veux en faire une forme standard, donc je ne prends que les entiers autres que celui correspondant à la matrice unitaire et en fait une chaîne binaire, et je l'arrange verticalement pour faire une matrice A. Je fais cela dans la boucle for ci-dessus. Calculez une chaîne binaire à partir du décimal x avec binlist = decimal_to_binlist (x, r) et affectez-la à binlist. Pour le traitement avec decimal_to_binlist, reportez-vous à la définition de la fonction. Lorsque la boucle for est terminée, faites-en une matrice numpy et fusionnez-la avec la matrice unitaire créée par l'œil de numpy pour créer la matrice de contrôle de parité H.
# represent integer each row of H matrix (for error correction algorithm)
H_int = [binlist_to_decimal(row) for row in H]
Ici, nous calculons la liste des nombres décimaux pour chaque ligne de H. La fonction binlist_to_decimal est une fonction qui convertit une chaîne binaire en une chaîne décimale. Pour le traitement interne, reportez-vous à la définition de la fonction.
# generator matrix (G)
I_G = np.eye(2**r-r-1, dtype=int)
G = np.concatenate([I_G, A], 1)
Ensuite, créez la matrice de génération G. C'est un type standard, donc c'est facile. Tout ce que vous avez à faire est de fusionner horizontalement la matrice A et la matrice unitaire.
Maintenant, revenons à la section de traitement principale.
err_count = 0
for x in generate_data(k, N):
...
Ensuite, initialisez le compteur d'erreur err_count à 0 et entrez la boucle for. Avec generate_data (k, N), N morceaux de données k bits sont générés aléatoirement. Affectez chacune des données à x et exécutez le traitement dans la boucle. Pour le contenu de traitement de la fonction generator_data, reportez-vous à la définition de la fonction.
Voici le contenu de la boucle.
y = (x @ G)%2
Ensuite, laissez x agir sur la matrice de génération G pour générer le signe y. Cependant, comme je dois calculer le mod 2, je le règle sur «% 2».
y_error = add_noise(y)
Ensuite, ajoutez du bruit à y au hasard pour faire y_error. Plus précisément, les bits sont sélectionnés de manière aléatoire et inversés. Pour le contenu de traitement de add_noise, reportez-vous à la définition de la fonction.
y_correct = correct_error(y_error, H_int)
Effectue une correction d'erreur. Jetons un coup d'œil au contenu de la fonction correct_error.
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
La première ligne copie les données d'entrée d_in dans d_out. La matrice de contrôle de parité est appliquée dans la deuxième ligne. Le résultat est une séquence binaire. Détermine à quelle ligne de la matrice de contrôle de parité cela correspond. Par conséquent, utilisez binlist_to_decimal sur la troisième ligne pour le convertir en nombre décimal, puis utilisez la méthode d'index pour savoir à quelle colonne de H_int correspond sur la quatrième ligne. Attribuez-le à err_idx. La ligne 5 inverse le bit err_idxth de d_out. Enfin, il retourne d_out (je recherche à chaque fois avec la méthode d'index, mais je pense qu'il vaut mieux utiliser LUT. C'est gênant, j'ai donc omis l'implémentation).
Revenons maintenant à la section de traitement principale.
x_correct = y_correct[0:k] # decode (= extract 1st to k-th elements)
Déchiffre les informations d'origine du code corrigé d'erreur y_correct. C'est un type standard, donc c'est facile. Retirez simplement le kième bit du début. Maintenant que la série de traitement est terminée,
print("{0:} -> {1:} -> {2:} -> {3:} -> {4:}".format(x,y,y_error,y_correct,x_correct))
Pour afficher les données de chaque étape.
if sum((x+x_correct)%2) == 1: # if x != x_correct --> 1
err_count += 1
Donc, si l'erreur n'a pas été corrigée, ajoutez 1 au nombre d'erreurs.
Finalement,
err_rate = err_count / N
print("* error rate = {0:} (count:{1:} / total:{2:})".format(err_rate, err_count, N))
Pour afficher le taux d'erreur.
Voyons maintenant le résultat de l'exécution du code ci-dessus.
* 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)
Comme les informations d'origine étaient générées de manière aléatoire et que le bruit était également aléatoire, les données d'entrée / sortie changeaient à chaque fois qu'elles étaient exécutées, mais l'erreur était toujours complètement corrigée. Félicitations, félicitations.
Sur la base de Neilsen, Chan, j'ai essayé de remplir soigneusement l'interligne tout en faisant référence à d'autres documents, c'est donc devenu une phrase assez longue. C'est parti. Quand j'ai remarqué les exercices de Neilsen, Chan, je les avais vaincus presque tous (s'ils répondaient correctement, cependant). .. Grâce à cela, ma compréhension des bases s'est considérablement améliorée. Cela dit, il s'agit d'une histoire de correction d'erreur "classique". L'histoire du «quantum» basé sur cela est encore plus profonde et plus large (probablement). C'est toujours capricieux et à mon rythme, mais je ferai de mon mieux.
c'est tout
Recommended Posts