Systematic correction codes. Linearly group code

In this publication, we will consider the linear group code as one of the representatives of systematic correction codes and its implementation in C ++ is proposed.

What is the correction code? Correction code - a code aimed at detecting and correcting errors. A systematic codes - These are the codes in which the control and information bits are placed on a particular system. One such example is the Hamming Code or the linear group codes themselves.
Linear group code consists of information bits and control. For example, for an initial combination of 4 characters, the linear group code would look like this:

|1100|110| 

Where the first 4 characters are our original combination, and the last 3 characters are control bits.

The total length of the linear group code is 7 characters. If the number of bits of the original combination is known to us, then to calculate the number of check bits, you need to use the formula:
')

$$

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

Where n is the number of information bits, that is, the length of the original combination, and log at the base 2. And the total length N of the code will be calculated by the formula:

$$

$$N = n + d$$

Suppose the original combination will be 10 bits.

$$

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

$$

$$d = 3,867$$

d is always rounded up and d = 4.

And the total length of the code will be 14 bits.

Having dealt with the length of the code, we need to create a generating and testing matrix.

A generating matrix of dimension N by n, where N is the length of the linear group code, and n is the length of the information part of the linear group code. In fact, the generating matrix is ​​two matrices: the unit of dimension m by m, and the matrix of control bits of dimension d by n. If the unit matrix is ​​compiled by placing the units along the main diagonal, then the compilation of the “control” part of the matrix has some rules. Easier to explain with an example. We will take the combination of 10 information bits already known to us, but add redundancy to the code and add the 5th control bit to it. The matrix will have a dimension of 15 to 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 

The “control” part is composed according to the scheme of reducing the binary number and observing the minimum code distance between the lines: in our case, this is 11111, 11110, 11101 ...
The minimum code distance for the combination will be calculated by the formula:

 Wp=r+s 

Where r is the rank of the detected error, and s is the rank of the error to be fixed.
In our case, the rank of the corrected and detectable error is 1.
It is also necessary to make a check matrix. It is composed by transposing the “control” part and after it the unitary matrix of dimension d is added by 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 

Having made matrices, we can already write a linearly group code by summing the rows of the generating matrix with the numbers of nonzero bits of the original message.

Consider this step on the example of the original message 1001101010.

Linearly group code: 100110101011100

Immediately we will designate that check digits in LGK are determined by the parity rules of the sum of the corresponding indices, in our case, these sums are: 5,3,3,4,4. Therefore, the control part of the code looks like: 11100.

As a result, we have compiled a linear group code. However, as mentioned earlier, a linearly grouped code has a correcting ability; in our case, it is able to detect and correct a single error.

Suppose our code was sent with an error in the 6th digit. To determine the errors in the code, the previously generated check matrix serves

In order to determine in which particular discharge an error occurred, we need to find out the “error syndrome”. Error syndrome is calculated by checking for non-zero positions of the checking matrix for parity. In our case, there are five of these checks, and we conduct our received message through all of these checks.

$$

$$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$$

Having obtained a binary number, we compare it with the columns of the check matrix. As soon as we find the corresponding "syndrome", we determine its index, and perform the inverse of the bit according to the obtained index.

In our case, the syndrome is: 01111, which corresponds to the 6th category in LGC. We invert the bit and get the correct linear group code.

Decoding of the corrected LHC is done by simply removing the control bits. After deleting the LGK control bits, we get the original combination that was sent to the encoding.

In conclusion, we can say that such correction codes as linear group codes, the Hamming Code are already quite outdated, and in their effectiveness will definitely give way to their modern alternatives. However, they quite cope with the task of becoming familiar with the process of coding binary codes and the method of correcting errors as a result of the effect of interference on a communication channel.

Implementation of working with LGK on 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 - a file archive of students [Electronic resource] studfiles.net/preview/4514583/page : 2 /.

2. Task book on information theory and coding [Text] / V.P. Tsymbal. - Ed. united "Vishcha school", 1976. - 276 p.

3. Tennikov, F.E. Theoretical foundations of information technology / F.E. Tennikov. - M .: Energy, 1971. - 424 p.