📗 🌜 👍🏾 Códigos correctivos sistemáticos. Código de grupo lineal 🙆🏿 🗣️ 🤶🏻

Esta publicación considerará un código de grupo lineal como uno de los representantes de los códigos correctivos sistemáticos y se propone su implementación en C ++.

¿Qué es un código correctivo? El código correctivo es un código destinado a detectar y corregir errores. A códigos sistemáticos: son códigos en los que los bits de control e información se colocan en un sistema específico. Un ejemplo de ello es el código de Hamming o los códigos de grupo realmente lineales.
El código de grupo lineal consta de bits de información y bits de control. Por ejemplo, para una combinación inicial de 4 caracteres, un código agrupado linealmente se vería así:

|1100|110|

Donde los primeros 4 caracteres es nuestra combinación original, y los últimos 3 caracteres son bits de control.

La longitud total del código de grupo lineal es de 7 caracteres. Si conocemos el número de bits de la combinación original, para calcular el número de bits de verificación, debe usar la fórmula:

d = l o g (n + 1 + l o g (n + 1))

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

Donde n es el número de bits de información, es decir, la longitud de la combinación original y el registro es base 2. Y la longitud total N del código se calculará mediante la fórmula:

N = n + d

$N = n + d$

Supongamos que la combinación original es de 10 bits.

d = l o g (10 + 1 + l o g (10 + 1))

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

d = $ 3, 86

$d = $ 3,86$

d siempre se redondea hacia arriba y d = 4.

Y la longitud total del código será de 14 bits.

Habiendo descubierto la longitud del código, necesitamos componer una matriz de producción y verificación.

La matriz generadora, dimensión N por n, donde N es la longitud del código de grupo lineal yn es la longitud de la parte de información del código de grupo lineal. De hecho, la matriz productora consta de dos matrices: una unidad de dimensión m por m, y una matriz de bits de control de dimensión d por n. Si la matriz de identidad se compila organizando las unidades en la diagonal principal, compilar la parte de "control" de la matriz tiene algunas reglas. Más fácil de explicar con el ejemplo. Tomamos la combinación de 10 bits de información que ya conocemos, pero agregamos redundancia al código y le agregamos el quinto bit de control. La matriz tendrá una dimensión de 15 por 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 parte de "control" se compila de acuerdo con el esquema para reducir el número binario y observar la distancia mínima de código entre las líneas: en nuestro caso es 11111, 11110, 11101 ...
La distancia mínima de código para la combinación se calculará mediante la fórmula:

 Wp=r+s

Donde r es el rango del error que se detecta y s es el rango del error que se corrige.
En nuestro caso, el rango del error corregible y detectable es 1.
También es necesario elaborar una matriz de verificación. Se compila transponiendo la parte de "control" y luego se agrega una matriz de unidad de dimensión d por d.

 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

Una vez compiladas las matrices, ya podemos escribir un código de grupo lineal sumando las filas de la matriz generadora bajo los números de bits distintos de cero del mensaje original.

Considere este paso como un ejemplo del mensaje original 1001101010.

Código de grupo lineal: 100110101011100

Notamos de inmediato que los bits de control en el LGK se determinan de acuerdo con las reglas de paridad de la suma de los índices correspondientes, en nuestro caso, estas cantidades son: 5,3,3,4,4. Por lo tanto, la parte de control del código se ve: 11100.

Como resultado, compilamos un código de grupo lineal. Sin embargo, como se mencionó anteriormente, un código de grupo lineal tiene una capacidad correctiva, en nuestro caso, es capaz de detectar y corregir un solo error.

Digamos que nuestro código se envió con un error en la sexta categoría. Para determinar los errores en el código, se utiliza una matriz de verificación compilada previamente.

Para determinar en qué categoría en particular ocurrió un error, necesitamos conocer el "síndrome de error". El síndrome de error se calcula mediante el método de verificación de las posiciones distintas de cero de la matriz de verificación de paridad. En nuestro caso, hay cinco de estos controles, y publicamos nuestro mensaje recibido a través de todos estos controles.

S 1 = n 1 + n 2 + n 3 + n 4 + n 5 + n 7 + n 8 + n 9 + n 11

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

S 2 = n 1 + n 2 + n 3 + n 4 + n 6 + n 7 + n 8 + n 10 + n 12

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

S 3 = n 1 + n 2 + n 3 + n 5 + n 6 + n 7 + n 13

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

S 4 = n 1 + n 2 + n 4 + n 5 + n 6 + n 9 + n 10 + n 14

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

S 5 = n 1 + n 3 + n 4 + n 5 + n 6 + n 8 + n 9 + n 10 + n 15

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

Habiendo recibido un número binario, lo comparamos con las columnas de la matriz de verificación. Tan pronto como encontramos el "síndrome" correspondiente, determinamos su índice y realizamos la inversa del bit de acuerdo con el índice obtenido.

En nuestro caso, el síndrome es: 01111, que corresponde a la sexta categoría en LGA. Invertimos el bit y obtenemos el código de grupo lineal correcto.

La decodificación de la LGK corregida ocurre simplemente quitando los bits de control. Después de eliminar los bits de control del LGK, obtenemos la combinación original, que se envió para su codificación.

En conclusión, podemos decir que códigos de corrección como los códigos de grupo lineal, el código de Hamming ya están bastante desactualizados, y en su efectividad definitivamente cederán ante sus alternativas modernas. Sin embargo, hacen frente a la tarea de familiarizarse con el proceso de codificación de códigos binarios y el método de corrección de errores como resultado del efecto de la interferencia en el canal de comunicación.

Implementación de trabajo con 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; }

Fuentes:

1. StudFiles - archivo de estudiantes [recurso electrónico] studfiles.net/preview/4514583/page : 2 /.

2. Zadachnik sobre teoría de la información y codificación [Texto] / V.P. Tsymbal - Ed. unidos "Escuela Vishka", 1976. - 276 p.

3. Tennikov, F.E. Fundamentos teóricos de la tecnología de la información / F.E. Tennikov - M .: Energía, 1971. - 424 p.

Códigos correctivos sistemáticos. Código de grupo lineal

More articles: