व्यवस्थित सुधारात्मक कोड। रैखिक समूह कोड

यह प्रकाशन एक रैखिक समूह कोड को सुधारात्मक सुधारात्मक कोड के प्रतिनिधियों में से एक के रूप में मानेगा और C ++ में इसका कार्यान्वयन प्रस्तावित है।

सुधारात्मक कोड क्या है? सुधारात्मक कोड त्रुटियों का पता लगाने और सही करने के उद्देश्य से एक कोड है। एक व्यवस्थित कोड - ये ऐसे कोड होते हैं जिनमें नियंत्रण और सूचना बिट्स को एक विशिष्ट सिस्टम पर रखा जाता है। ऐसा ही एक उदाहरण हैमिंग कोड या वास्तव में रैखिक समूह कोड है।
रैखिक समूह कोड में जानकारी बिट्स और नियंत्रण बिट्स होते हैं। उदाहरण के लिए, प्रारंभिक 4-वर्ण संयोजन के लिए, एक रेखीय रूप से समूहीकृत कोड इस तरह दिखेगा:

|1100|110| 

जहां पहले 4 अक्षर हमारा मूल संयोजन है, और अंतिम 3 वर्ण नियंत्रण बिट्स हैं।

रैखिक समूह कोड की कुल लंबाई 7 वर्ण है। यदि हम मूल संयोजन के बिट्स की संख्या जानते हैं, तो चेक बिट्स की संख्या की गणना करने के लिए, आपको सूत्र का उपयोग करने की आवश्यकता है:

$$

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

जहाँ n सूचना बिट्स की संख्या है, अर्थात, मूल संयोजन की लंबाई, और लॉग बेस 2 है। और कोड की कुल लंबाई N की गणना सूत्र द्वारा की जाएगी:

$$

$$एन = एन + डी$$

मान लीजिए कि मूल संयोजन 10 बिट्स है।

$$

$$d = log (10 + 1 + लॉग (10 + 1))$$

$$

$$d = $ 3,86$$

d हमेशा गोल होता है, और d = 4।

और पूर्ण कोड की लंबाई 14 बिट होगी।

कोड की लंबाई का पता लगाने के बाद, हमें उत्पादन और सत्यापन मैट्रिक्स की रचना करने की आवश्यकता है।

उत्पन्न करने वाला मैट्रिक्स, आयाम एन द्वारा एन, जहां एन रैखिक रूप से समूह कोड की लंबाई है, और एन रेखीय समूह कोड के सूचना भाग की लंबाई है। वास्तव में, उत्पन्न करने वाले मैट्रिक्स में दो मैट्रिक्स होते हैं: एक इकाई आयाम m, और n द्वारा d के आयाम के नियंत्रण बिट्स का एक मैट्रिक्स। यदि पहचान मैट्रिक्स को मुख्य विकर्ण पर इकाइयों की व्यवस्था करके संकलित किया जाता है, तो मैट्रिक्स का "नियंत्रण" भाग कुछ नियमों को संकलित करता है। उदाहरण द्वारा समझाने में आसान। हम 10 सूचना बिट्स का संयोजन लेते हैं जिन्हें हम पहले से जानते हैं, लेकिन कोड में अतिरेक जोड़ें और इसमें 5 वां नियंत्रण बिट जोड़ें। मैट्रिक्स में 15 से 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 

बाइनरी संख्या को कम करने और लाइनों के बीच न्यूनतम कोड दूरी का पालन करने के लिए योजना के अनुसार "नियंत्रण" भाग संकलित किया गया है: हमारे मामले में यह 11111, 11110, 11101 है ...
संयोजन के लिए न्यूनतम कोड दूरी की गणना सूत्र द्वारा की जाएगी:

 Wp=r+s 

जहाँ r त्रुटि का पता लगाया जा रहा है, और s त्रुटि की रैंक तय की जा रही है।
हमारे मामले में, सुधारात्मक और पता लगाने योग्य त्रुटि का रैंक 1 है।
एक सत्यापन मैट्रिक्स तैयार करना भी आवश्यक है। इसे "नियंत्रण" भाग को ट्रांसफ़ॉर्म करके संकलित किया जाता है और इसके बाद d द्वारा 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 

मैट्रिसेस को संकलित करने के बाद, हम पहले से ही मूल संदेश के नॉनज़रो बिट्स की संख्या के तहत उत्पन्न मैट्रिक्स की पंक्तियों को संक्षेप में एक रैखिक समूह कोड लिख सकते हैं।

इस कदम को मूल संदेश 1001101010 के उदाहरण के रूप में देखें।

रैखिक समूह कोड: 100110101011100

हम तुरंत ध्यान देते हैं कि एलजीके में नियंत्रण बिट्स को संबंधित सूचकांकों की राशि के समता नियमों द्वारा निर्धारित किया जाता है, हमारे मामले में, ये मात्राएं हैं: 5,3,3,4,4। इसलिए, कोड का नियंत्रण भाग दिखता है: 11100।

नतीजतन, हमने एक रैखिक समूह कोड संकलित किया। हालांकि, जैसा कि पहले उल्लेख किया गया है, एक रैखिक समूह कोड में एक सुधारात्मक क्षमता होती है, हमारे मामले में, यह एकल त्रुटि का पता लगाने और सही करने में सक्षम है।

मान लीजिए कि हमारा कोड 6 वीं श्रेणी में त्रुटि के साथ भेजा गया था। कोड में त्रुटियों को निर्धारित करने के लिए, पहले से संकलित सत्यापन मैट्रिक्स का उपयोग किया जाता है।

यह निर्धारित करने के लिए कि किस विशेष श्रेणी में त्रुटि हुई है, हमें "त्रुटि सिंड्रोम" जानने की आवश्यकता है। त्रुटि सिंड्रोम की गणना पैरिटी चेक मैट्रिक्स के नॉनजरो पदों के लिए जाँच की विधि द्वारा की जाती है। हमारे मामले में, इनमें से पांच चेक हैं, और हम इन सभी चेक के माध्यम से अपना संदेश प्राप्त करते हैं।

$$

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

एक बाइनरी नंबर प्राप्त करने के बाद, हम इसकी तुलना सत्यापन मैट्रिक्स के कॉलम से करते हैं। जैसे ही हम संबंधित "सिंड्रोम" पाते हैं, हम इसके सूचकांक का निर्धारण करते हैं, और प्राप्त सूचकांक के अनुसार बिट का व्युत्क्रम करते हैं।

हमारे मामले में, सिंड्रोम है: 01111, जो एलजीए में 6 वीं श्रेणी से मेल खाती है। हम बिट को उल्टा करते हैं और सही रैखिक समूह कोड प्राप्त करते हैं।

सही LGK का डिकोडिंग केवल नियंत्रण बिट्स को हटाने के द्वारा होता है। LGK के नियंत्रण बिट्स को हटाने के बाद, हमें मूल संयोजन मिलता है, जिसे एन्कोडिंग के लिए भेजा गया था।

अंत में, हम यह कह सकते हैं कि ऐसे सुधारात्मक कोड जैसे कि रैखिक समूह कोड, हैमिंग कोड पहले से ही काफी पुराने हैं, और उनकी प्रभावशीलता में वे निश्चित रूप से अपने आधुनिक विकल्पों के लिए उपजेंगे। हालांकि, वे द्विआधारी कोड को एन्कोडिंग करने की प्रक्रिया और संचार चैनल पर हस्तक्षेप के प्रभाव के परिणामस्वरूप त्रुटियों को सही करने की विधि से परिचित होने के कार्य के साथ काफी सामना करते हैं।

C ++ में LGK के साथ कार्य का कार्यान्वयन:

 #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; } 

सूत्रों का कहना है:

1. StudFiles - छात्रों का फ़ाइल संग्रह [इलेक्ट्रॉनिक संसाधन] studfiles.net/preview/4514583/page : 2 /।

2. सूचना सिद्धांत और कोडिंग पर जादचनिक [पाठ] / वी.पी. Tsymbal। - एड। संयुक्त करें। "विशाका स्कूल", 1976. - 276 पी।

3. टेनीकोव, एफ.ई. सूचना प्रौद्योगिकी के सैद्धांतिक आधार / एफ.ई. Tenniken। - एम .: ऊर्जा, 1971. - 424 पी।