🤽🏻 👨🏼‍🔬 🔘 Systematische Korrekturcodes. Linearer Gruppencode 🈯️ 💷 ♀️

In dieser Veröffentlichung wird ein linearer Gruppencode als einer der Vertreter systematischer Korrekturcodes betrachtet, und seine Implementierung in C ++ wird vorgeschlagen.

Was ist ein Korrekturcode? Korrekturcode ist ein Code, der darauf abzielt, Fehler zu erkennen und zu korrigieren. Ein systematischer Code - Dies sind Codes, in denen die Steuer- und Informationsbits auf einem bestimmten System platziert sind. Ein solches Beispiel ist der Hamming-Code oder der tatsächlich lineare Gruppencode.
Der lineare Gruppencode besteht aus Informationsbits und Steuerbits. Für eine anfängliche 4-stellige Kombination würde ein linear gruppierter Code beispielsweise folgendermaßen aussehen:

|1100|110|

Wobei die ersten 4 Zeichen unsere ursprüngliche Kombination sind und die letzten 3 Zeichen Steuerbits sind.

Die Gesamtlänge des linearen Gruppencodes beträgt 7 Zeichen. Wenn wir die Anzahl der Bits der ursprünglichen Kombination kennen, müssen Sie zur Berechnung der Anzahl der Prüfbits die folgende Formel verwenden:

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

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

Dabei ist n die Anzahl der Informationsbits, dh die Länge der ursprünglichen Kombination, und log ist die Basis 2. Die Gesamtlänge N des Codes wird nach folgender Formel berechnet:

N = n + d

$N = n + d$

Angenommen, die ursprüngliche Kombination beträgt 10 Bit.

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 wird immer aufgerundet und d = 4.

Die volle Codelänge beträgt 14 Bit.

Nachdem wir die Länge des Codes herausgefunden haben, müssen wir eine Produktions- und Verifizierungsmatrix erstellen.

Die Erzeugungsmatrix, Dimension N mal n, wobei N die Länge des linearen Gruppencodes und n die Länge des Informationsteils des linearen Gruppencodes ist. Tatsächlich besteht die erzeugende Matrix aus zwei Matrizen: einer Einheitsdimension m mal m und einer Matrix von Steuerbits der Dimension d mal n. Wenn die Identitätsmatrix durch Anordnen der Einheiten auf der Hauptdiagonale kompiliert wird, gelten für das Kompilieren des Kontrollteils der Matrix einige Regeln. Einfacher anhand eines Beispiels zu erklären. Wir nehmen die Kombination von 10 bereits bekannten Informationsbits, fügen dem Code jedoch Redundanz hinzu und fügen ihm das 5. Steuerbit hinzu. Die Matrix hat eine Dimension von 15 mal 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

Der "Steuer" -Teil wird nach dem Schema zur Reduzierung der Binärzahl und zur Einhaltung des minimalen Codeabstands zwischen den Zeilen kompiliert: In unserem Fall ist es 11111, 11110, 11101 ...
Der minimale Codeabstand für die Kombination wird nach folgender Formel berechnet:

 Wp=r+s

Dabei ist r der Rang des erkannten Fehlers und s der Rang des zu korrigierenden Fehlers.
In unserem Fall beträgt der Rang des korrigierbaren und erkennbaren Fehlers 1.
Es ist auch notwendig, eine Verifizierungsmatrix zu erstellen. Es wird durch Transponieren des "Steuer" -Teils kompiliert und danach wird eine Einheitsmatrix der Dimension d mal d hinzugefügt.

 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

Nachdem wir die Matrizen kompiliert haben, können wir bereits einen linearen Gruppencode schreiben, indem wir die Zeilen der generierenden Matrix unter der Anzahl der Nicht-Null-Bits der ursprünglichen Nachricht summieren.

Betrachten Sie diesen Schritt als Beispiel für die ursprüngliche Nachricht 1001101010.

Linearer Gruppencode: 100110101011100

Wir stellen sofort fest, dass die Steuerbits in der LGK gemäß den Paritätsregeln der Summe der entsprechenden Indizes bestimmt werden. In unserem Fall sind diese Beträge: 5,3,3,4,4. Daher sieht der Steuerteil des Codes wie folgt aus: 11100.

Als Ergebnis haben wir einen linearen Gruppencode kompiliert. Wie bereits erwähnt, hat ein linearer Gruppencode jedoch eine Korrekturfähigkeit. In unserem Fall kann er einen einzelnen Fehler erkennen und korrigieren.

Angenommen, unser Code wurde mit einem Fehler in der 6. Kategorie gesendet. Um Fehler im Code zu bestimmen, wird eine zuvor kompilierte Verifizierungsmatrix verwendet.

Um festzustellen, in welcher bestimmten Kategorie ein Fehler aufgetreten ist, müssen wir das „Fehlersyndrom“ kennen. Das Fehlersyndrom wird nach der Methode der Überprüfung auf Positionen ungleich Null der Paritätsprüfungsmatrix berechnet. In unserem Fall gibt es fünf dieser Prüfungen, und wir senden unsere empfangene Nachricht über alle diese Prüfungen.

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$

Nachdem wir eine Binärzahl erhalten haben, vergleichen wir sie mit den Spalten der Verifizierungsmatrix. Sobald wir das entsprechende "Syndrom" finden, bestimmen wir seinen Index und führen die Umkehrung des Bits gemäß dem erhaltenen Index durch.

In unserem Fall ist das Syndrom: 01111, was der 6. Kategorie in LGA entspricht. Wir invertieren das Bit und erhalten den richtigen linearen Gruppencode.

Die Decodierung der korrigierten LGK erfolgt durch einfaches Entfernen der Steuerbits. Nach dem Entfernen der Steuerbits des LGK erhalten wir die ursprüngliche Kombination, die zur Codierung gesendet wurde.

Zusammenfassend können wir sagen, dass solche Korrekturcodes wie lineare Gruppencodes, der Hamming-Code, bereits ziemlich veraltet sind und in ihrer Wirksamkeit definitiv ihren modernen Alternativen nachgeben werden. Sie haben jedoch die Aufgabe, sich mit dem Codierungsprozess von Binärcodes und der Methode zur Korrektur von Fehlern infolge der Auswirkung von Interferenzen auf den Kommunikationskanal vertraut zu machen.

Implementierung der Arbeit mit LGK in 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; }

Quellen:

1. StudFiles - Dateiarchiv der Studenten [Elektronische Ressource] studfiles.net/preview/4514583/page : 2 /.

2. Zadachnik über Informationstheorie und Kodierung [Text] / V.P. Tsymbal. - Ed. vereint "Vishka Schule", 1976. - 276 p.

3. Tennikov, F.E. Theoretische Grundlagen der Informationstechnologie / F.E. Tennikov. - M.: Energy, 1971. - 424 p.

Systematische Korrekturcodes. Linearer Gruppencode

More articles: