Codes correctifs systématiques. Code de groupe linéaire

Cette publication considérera un code de groupe linéaire comme l'un des représentants des codes correctifs systématiques et sa mise en œuvre en C ++ est proposée.

Qu'est-ce qu'un code correctif? Le code correctif est un code destiné à détecter et corriger les erreurs. A codes systématiques - Ce sont des codes dans lesquels les bits de commande et d'information sont placés sur un système spécifique. Un tel exemple est le code de Hamming ou les codes de groupe réellement linéaires.
Le code de groupe linéaire se compose de bits d'information et de bits de contrôle. Par exemple, pour une combinaison initiale de 4 caractères, un code groupé linéairement ressemblerait à ceci:

|1100|110| 

Où les 4 premiers caractères sont notre combinaison d'origine et les 3 derniers caractères sont des bits de contrôle.

La longueur totale du code de groupe linéaire est de 7 caractères. Si nous connaissons le nombre de bits de la combinaison d'origine, alors pour calculer le nombre de bits de contrôle, vous devez utiliser la formule:

$$

$$d = log (n + 1 + log (n + 1))$$

Où n est le nombre de bits d'information, c'est-à-dire la longueur de la combinaison d'origine, et log est la base 2. Et la longueur totale N du code sera calculée par la formule:

$$

$$N = n + d$$

Supposons que la combinaison d'origine soit de 10 bits.

$$

$$d = log (10 + 1 + log (10 + 1))$$

$$

$$d = 3 867$$

d est toujours arrondi et d = 4.

Et la longueur totale du code sera de 14 bits.

Après avoir compris la longueur du code, nous devons composer une matrice de production et de vérification.

La matrice de génération, dimension N par n, où N est la longueur du code de groupe linéaire et n est la longueur de la partie information du code de groupe linéaire. En effet, la matrice génératrice est constituée de deux matrices: une dimension unitaire m par m, et une matrice de bits de contrôle de dimension d par n. Si la matrice d'identité est compilée en disposant les unités sur la diagonale principale, alors la compilation de la partie «contrôle» de la matrice a quelques règles. Plus facile à expliquer par l'exemple. Nous prenons la combinaison de 10 bits d'information que nous connaissons déjà, mais ajoutons une redondance au code et lui ajoutons le 5e bit de contrôle. La matrice aura une dimension de 15 sur 10.

 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 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 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 

La partie «contrôle» est compilée selon le schéma de réduction du nombre binaire et d'observation de la distance minimale de code entre les lignes: dans notre cas c'est 11111, 11110, 11101 ...
La distance minimale du code pour la combinaison sera calculée par la formule:

 Wp=r+s 

Où r est le rang de l'erreur détectée et s est le rang de l'erreur corrigée.
Dans notre cas, le rang de l'erreur corrigeable et détectable est 1.
Il est également nécessaire d'établir une matrice de vérification. Il est compilé en transposant la partie «contrôle» et après cela une matrice unitaire de dimension d par d est ajoutée.

 1 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 0 1 

Après avoir compilé les matrices, nous pouvons déjà écrire un code de groupe linéaire en sommant les lignes de la matrice génératrice sous le nombre de bits non nuls du message d'origine.

Considérez cette étape comme un exemple du message d'origine 1001101010.

Code de groupe linéaire: 100110101011100

On constate immédiatement que les bits de contrôle dans le LGK sont déterminés selon les règles de parité de la somme des indices correspondants, dans notre cas, ces montants sont: 5,3,3,4,4. Par conséquent, la partie contrôle du code ressemble à: 11100.

En conséquence, nous avons compilé un code de groupe linéaire. Cependant, comme mentionné précédemment, un code de groupe linéaire a une capacité de correction, dans notre cas, il est capable de détecter et de corriger une seule erreur.

Disons que notre code a été envoyé avec une erreur dans la 6ème catégorie. Pour déterminer les erreurs dans le code, une matrice de vérification précédemment compilée est utilisée.

Afin de déterminer dans quelle catégorie particulière une erreur s'est produite, nous devons connaître le «syndrome d'erreur». Le syndrome d'erreur est calculé par la méthode de contrôle des positions non nulles de la matrice de contrôle de parité. Dans notre cas, il y a cinq de ces chèques, et nous publions notre message reçu à travers tous ces chèques.

$$

$$S1 = n1 + n2 + n3 + n4 + n5 + n7 + n8 + n9 + n11$$

$$

$$S2 = n1 + n2 + n3 + n4 + n6 + n7 + n8 + n10 + n12$$

$$

$$S3 = n1 + n2 + n3 + n5 + n6 + n7 + n13$$

$$

$$S4 = n1 + n2 + n4 + n5 + n6 + n9 + n10 + n14$$

$$

$$S5 = n1 + n3 + n4 + n5 + n6 + n8 + n9 + n10 + n15$$

Ayant reçu un nombre binaire, nous le comparons avec les colonnes de la matrice de vérification. Dès que nous trouvons le "syndrome" correspondant, nous déterminons son indice, et effectuons l'inverse du bit en fonction de l'indice obtenu.

Dans notre cas, le syndrome est: 01111, ce qui correspond à la 6ème catégorie en LGA. Nous inversons le bit et obtenons le code de groupe linéaire correct.

Le décodage de la LGK corrigée se produit en supprimant simplement les bits de commande. Après avoir supprimé les bits de contrôle du LGK, nous obtenons la combinaison d'origine, qui a été envoyée pour l'encodage.

En conclusion, nous pouvons dire que des codes correctifs tels que les codes de groupe linéaires, le code de Hamming sont déjà assez obsolètes et, dans leur efficacité, ils céderont certainement à leurs alternatives modernes. Cependant, ils font tout à fait face à la tâche de se familiariser avec le processus de codage des codes binaires et la méthode de correction des erreurs résultant de l'effet des interférences sur le canal de communication.

Implémentation du travail avec LGK en C ++:

 #include <iostream> #include <vector> #include <string> #include <cstdlib> #include <ctime> #include <algorithm> #include <iterator> #include <cctype> #include <cmath> using namespace std; int main() { setlocale(LC_ALL, "Russian"); cout<<" :"<<endl; int matr [10][15]={{1,0,0,0,0,0,0,0,0,0,1,1,1,1,1},{0,1,0,0,0,0,0,0,0,0,1,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,0,0,0,0,1,1,0,1,1},{0,0,0,0,1,0,0,0,0,0,1,0,1,1,1}, {0,0,0,0,0,1,0,0,0,0,0,1,1,1,1},{0,0,0,0,0,0,1,0,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,1,0,0,1,1,0,0,1},{0,0,0,0,0,0,0,0,1,0,1,0,0,1,1},{0,0,0,0,0,0,0,0,0,1,0,1,0,1,1}}; for(int i=0;i<10;i++) { for(int j=0;j<15;j++) { cout<<matr[i][j]<<' '; } cout<<endl; } cout<<" :"<<endl; int matr_2 [5][15]={{1,1,1,1,1,0,1,1,1,0,1,0,0,0,0},{1,1,1,1,0,1,1,1,0,1,0,1,0,0,0},{1,1,1,0,1,1,1,0,0,0,0,0,1,0,0},{1,1,0,1,1,1,0,0,1,1,0,0,0,1,0},{1,0,1,1,1,1,0,1,1,1,0,0,0,0,1}}; for(int i=0;i<5;i++) { for(int j=0;j<15;j++) { cout<<matr_2[i][j]<<' '; } cout<<endl; } cout<<" : "<<endl; string str; bool flag=false; while(flag!=true) { cin>>str; if(str.size()!=10) { cout<<"  !"<<endl; flag=false; } else flag=true; } vector <int> arr; for(int i=0;i<str.size();i++) { if(str[i]=='1') arr.push_back(1); else if(str[i]=='0') arr.push_back(0); } cout<<" : "; for(int i=0;i<arr.size();i++) cout<<arr[i]; cout<<endl; vector <int> S; vector <vector<int>> R; for(int i=0;i<10;i++) { if(arr[i]==1) { vector <int> T; for(int j=0;j<15;j++) { T.push_back(matr[i][j]); } R.push_back(T); } } cout<<endl; cout<<"     : "<<endl; for(vector <vector<int>>::iterator it=R.begin();it!=R.end();it++) { copy((*it).begin(),(*it).end(),ostream_iterator<int>(cout,"\t")); cout<<"\n"; } cout<<endl; vector <int> P; for(int i=0; i<15;i++) { int PT=0; for(int j=0; j<R.size();j++) { PT+=R[j][i]; } P.push_back(PT); } for(int i=10; i<15;i++) { if(P[i]%2==0) P[i]=0; else if(P[i]%2!=0) P[i]=1; } cout<<endl<<"  : "<<endl; for(int i=0; i<P.size();i++) { cout<<P[i]<<' '; } int rand_i; rand_i=5; cout<<endl<<"   : "; if(P[rand_i]==0) P[rand_i]=1; else if(P[rand_i]==1) P[rand_i]=0; for(int i=0; i<P.size();i++) { cout<<P[i]<<' '; } int S1, S2, S3, S4, S5; //   S1=P[0]+P[1]+P[2]+P[3]+P[4]+P[6]+P[7]+P[8]+P[10]; S2=P[0]+P[1]+P[2]+P[3]+P[5]+P[6]+P[7]+P[9]+P[11]; S3=P[0]+P[1]+P[2]+P[4]+P[5]+P[6]+P[12]; S4=P[0]+P[1]+P[3]+P[4]+P[5]+P[8]+P[9]+P[13]; S5=P[0]+P[2]+P[3]+P[4]+P[5]+P[7]+P[8]+P[9]+P[14]; //  if(S1%2==0) { S1=0; } else if(S1%2!=0) { S1=1; } if(S2%2==0) { S2=0; } else if(S2%2!=0) { S2=1; } if(S3%2==0) { S3=0; } else if(S3%2!=0) { S3=1; } if(S4%2==0) { S4=0; } else if(S4%2!=0) { S4=1; } if(S5%2==0) { S5=0; } else if(S5%2!=0) { S5=1; } cout<<endl<<" : "<<S1<<S2<<S3<<S4<<S5<<endl; int mas_s[5]={S1,S2,S3,S4,S5}; int index_j=0; bool flag_s=false; for(int i=0;i<15;i++) { if((matr_2[0][i]==mas_s[0])&&(matr_2[1][i]==mas_s[1])&&(matr_2[2][i]==mas_s[2])&&(matr_2[3][i]==mas_s[3])&&(matr_2[4][i]==mas_s[4])) { index_j=i; } } cout<<endl<<" : "<<index_j+1<<endl; if(P[index_j]==0) P[index_j]=1; else if(P[index_j]==1) P[index_j]=0; cout<<" : "; for(int i=0; i<P.size();i++) { cout<<P[i]<<' '; } cout<<endl; P.erase(P.begin()+14); P.erase(P.begin()+13); P.erase(P.begin()+12); P.erase(P.begin()+11); P.erase(P.begin()+10); cout<<" : "; for(int i=0; i<P.size();i++) { cout<<P[i]<<' '; } cout<<endl; return 0; } 

Sources:

1. StudFiles - archive de fichiers des étudiants [Ressource électronique] studfiles.net/preview/4514583/page : 2 /.

2. Zadachnik sur la théorie de l'information et le codage [Texte] / V.P. Tsymbal. - Ed. unis «École Vishka», 1976. - 276 p.

3. Tennikov, F.E. Fondements théoriques des technologies de l'information / F.E. Tennikov. - M.: Énergie, 1971. - 424 p.