Esta publicação considerará um código de grupo linearmente como um dos representantes dos códigos corretivos sistemáticos e sua implementação em C ++ é proposta.
O que é um código corretivo? Código corretivo é um código destinado a detectar e corrigir erros. A códigos sistemáticos - são códigos nos quais os bits de controle e informação são colocados em um sistema específico. Um exemplo é o código de Hamming ou os códigos de grupo realmente lineares.
O código de grupo linearmente consiste em bits de informação e bits de controle. Por exemplo, para uma combinação inicial de 4 caracteres, um código agrupado linearmente seria assim:
|1100|110|
Onde os 4 primeiros caracteres são nossa combinação original e os 3 últimos são bits de controle.
O comprimento total do código do grupo linear é de 7 caracteres. Se soubermos o número de bits da combinação original, para calcular o número de bits de verificação, você precisará usar a fórmula:
d=log(n+1+log(n+1))
Onde n é o número de bits de informação, ou seja, o comprimento da combinação original e o log é a base 2. E o comprimento total N do código será calculado pela fórmula:
N=n+d
Suponha que a combinação original seja 10 bits.
d=log(10+1+log(10+1))
d=$3.86
d é sempre arredondado para cima ed = 4.
E o comprimento total do código será
14 bits.
Depois de descobrir o comprimento do código, precisamos compor uma matriz de produção e verificação.
A matriz geradora, dimensão N por n, em que N é o comprimento do código do grupo linearmente en é o comprimento da parte da informação do código do grupo linearmente. De fato, a matriz produtora consiste em duas matrizes: uma dimensão unitária m por me uma matriz de bits de controle da dimensão d por n. Se a matriz de identidade é compilada organizando as unidades na diagonal principal, a compilação da parte "controle" da matriz possui algumas regras. Mais fácil de explicar pelo exemplo. Tomamos a combinação de 10 bits de informação que já conhecemos, mas adicionamos redundância ao código e adicionamos o quinto bit de controle a ele. A matriz terá uma dimensão 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
A parte "controle" é compilada de acordo com o esquema para reduzir o número binário e observar a distância mínima do código entre as linhas: no nosso caso, são 11111, 11110, 11101 ...
A distância mínima do código para a combinação será calculada pela fórmula:
Wp=r+s
Onde r é a classificação do erro que está sendo detectado es é a classificação do erro que está sendo corrigido.
No nosso caso, a classificação do erro corrigível e detectável é 1.
Também é necessário elaborar uma matriz de verificação. Ele é compilado através da transposição da parte de "controle" e depois é adicionada uma matriz unitária da dimensão 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
Após compilar as matrizes, já podemos escrever um código de grupo linearmente, somando as linhas da matriz geradora sob o número de bits diferentes de zero da mensagem original.
Considere esta etapa como um exemplo da mensagem original 1001101010.
Código do grupo linear: 100110101011100
Notamos imediatamente que os bits de controle no LGK são determinados de acordo com as regras de paridade da soma dos índices correspondentes; no nosso caso, esses valores são: 5,3,3,4,4. Portanto, a parte de controle do código parece: 11100.
Como resultado, compilamos um código de grupo linearmente. No entanto, como mencionado anteriormente, um código de grupo linearmente possui uma capacidade corretiva; no nosso caso, é capaz de detectar e corrigir um único erro.
Digamos que nosso código foi enviado com um erro na 6ª categoria. Para determinar erros no código, uma matriz de verificação compilada anteriormente é usada.
Para determinar em qual categoria específica ocorreu um erro, precisamos conhecer a "síndrome do erro". A síndrome do erro é calculada pelo método de verificação de posições diferentes de zero da matriz de verificação de paridade. No nosso caso, existem cinco dessas verificações e postamos nossa mensagem recebida em todas essas verificações.
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
Depois de receber um número binário, comparamos com as colunas da matriz de verificação. Assim que encontramos a "síndrome" correspondente, determinamos seu índice e executamos o inverso do bit de acordo com o índice obtido.
No nosso caso, a síndrome é: 01111, que corresponde à 6ª categoria no LGA. Invertemos o bit e obtemos o código de grupo linear correto.
A decodificação do LGK corrigido ocorre simplesmente removendo os bits de controle. Após remover os bits de controle do LGK, obtemos a combinação original, que foi enviada para codificação.
Em conclusão, podemos dizer que códigos corretivos, como códigos de grupos lineares, o código de Hamming já estão bastante desatualizados e, em sua eficácia, eles definitivamente renderão suas alternativas modernas. No entanto, eles lidam bastante com a tarefa de familiarizar-se com o processo de codificação de códigos binários e com o método de correção de erros como resultado do efeito da interferência no canal de comunicação.
Implementação do trabalho com LGK em 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; }
Fontes:
1. StudFiles - arquivo dos alunos [Recurso eletrônico]
studfiles.net/preview/4514583/page : 2 /.
2. O livro de problemas sobre teoria da informação e codificação [Texto] / V.P. Tsymbal. - Ed. unidos "Escola Vishka", 1976. - 276 p.
3. Tennikov, F.E. Fundamentos teóricos da tecnologia da informação / F.E. Tennikov. - M .: Energy, 1971. - 424 p.