🈴 💘 📴 الرموز التصحيحية المنهجية. رمز المجموعة الخطية 💱 🧖🏾 👨🏾‍🎓

سوف يعتبر هذا المنشور رمز المجموعة الخطي كأحد ممثلي الرموز التصحيحية المنهجية ويقترح تنفيذه في C ++.

ما هو الكود التصحيحي؟ الكود التصحيحي هو كود يهدف إلى اكتشاف الأخطاء وتصحيحها. أكواد منهجية - هذه هي الرموز التي توضع فيها وحدات التحكم والمعلومات في نظام معين. أحد الأمثلة على ذلك هو رمز Hamming أو رموز المجموعة الخطية بالفعل.
يتكون رمز المجموعة الخطي من بتات المعلومات وبتات التحكم. على سبيل المثال ، بالنسبة لتكوين أولي يتكون من 4 أحرف ، سيبدو رمز المجموعة خطيًا كما يلي:

|1100|110|

حيث تكون الأحرف الأربعة الأولى هي مجموعتنا الأصلية ، والأحرف الثلاثة الأخيرة عبارة عن بتات تحكم.

الطول الكلي لرمز المجموعة الخطية هو 7 أحرف. إذا علمنا عدد وحدات بت المجموعة الأصلية ، ثم لحساب عدد وحدات التحقق ، تحتاج إلى استخدام الصيغة:

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

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

حيث n هو عدد وحدات البت في المعلومات ، أي أن طول المجموعة الأصلية وسجلها هو الأساس 2. وسيتم احتساب الطول الإجمالي N للرمز بواسطة الصيغة:

N = n + d

$N = n + d$

افترض أن المجموعة الأصلية هي 10 بتات.

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

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

d = 3 ، 867

$d = 3،867$

يتم تقريب d دائمًا ، و d = 4.

وسيكون طول الكود الكامل 14 بت.

بعد معرفة طول الكود ، نحتاج إلى إنشاء مصفوفة إنتاج وتحقق.

مصفوفة التوليد ، البعد N بواسطة n ، حيث N هو طول رمز المجموعة الخطية ، و n هو طول جزء المعلومات من كود المجموعة الخطية. في الواقع ، تتكون المصفوفة المنتجة من مصففتين: أبعاد الوحدة m بواسطة m ، ومصفوفة بتات التحكم في البعد d بواسطة n. إذا تم تجميع مصفوفة الهوية عن طريق ترتيب الوحدات على القطر الرئيسي ، فإن تجميع جزء "التحكم" في المصفوفة يتضمن بعض القواعد. أسهل لشرح بالقدوة. نحن نأخذ مجموعة من 10 بتات من المعلومات نعرفها بالفعل ، لكننا نضيف التكرار إلى الكود ونضيف إليه عنصر التحكم الخامس. سيكون للمصفوفة بعد 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

نلاحظ على الفور أن وحدات التحكم في LGK يتم تحديدها وفقًا لقواعد التكافؤ لمجموع المؤشرات المقابلة ، في حالتنا ، هذه المبالغ هي: 5،3،3،4،4. لذلك ، يبدو جزء التحكم في التعليمات البرمجية: 11100.

نتيجة لذلك ، قمنا بتجميع رمز مجموعة خطي. ومع ذلك ، كما ذكرنا سابقًا ، تتمتع شفرة المجموعة الخطية بقدرة تصحيحية ، في حالتنا ، يمكنها اكتشاف وتصحيح خطأ واحد.

لنفترض أنه تم إرسال الكود الخاص بنا مع وجود خطأ في الفئة السادسة. لتحديد الأخطاء في التعليمات البرمجية ، يتم استخدام مصفوفة تحقق مترجمة مسبقًا.

لتحديد الفئة التي حدث فيها خطأ ما ، نحتاج إلى معرفة "متلازمة الخطأ". يتم حساب متلازمة الخطأ عن طريق طريقة التحقق من المواقف غير الصفرية لمصفوفة فحص التكافؤ. في حالتنا ، هناك خمسة من هذه الشيكات ، وننشر رسالتنا المستلمة من خلال كل هذه الشيكات.

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$

بعد تلقي رقم ثنائي ، قمنا بمقارنته بأعمدة مصفوفة التحقق. بمجرد العثور على "المتلازمة" المقابلة ، نحدد الفهرس الخاص بها ، ونقوم بعكس البت وفقًا للفهرس الذي تم الحصول عليه.

في حالتنا ، فإن المتلازمة هي: 01111 ، والتي تتوافق مع الفئة السادسة في LGA. نقلب القطعة ونحصل على رمز المجموعة الخطية الصحيح.

يحدث فك تشفير LGK المصحح من خلال إزالة وحدات التحكم فقط. بعد إزالة وحدات التحكم في LGK ، نحصل على المجموعة الأصلية التي تم إرسالها للتشفير.

في الختام ، يمكننا أن نقول أن رموز التصحيح مثل رموز المجموعة الخطية ، رمز هامينغ قد عفا عليها الزمن بالفعل ، وفي فعاليتها ستخضع بالتأكيد لبدائلها الحديثة. ومع ذلك ، فهم يتعاملون تمامًا مع مهمة التعرف على عملية ترميز الرموز الثنائية وطريقة تصحيح الأخطاء نتيجة لتأثير التداخل على قناة الاتصال.

تنفيذ العمل مع LGK في 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; }

مصادر:

1. StudFiles - أرشيف ملفات الطلاب [مورد إلكتروني] studfiles.net/preview/4514583/page : 2 /.

2. Zadachnik على نظرية المعلومات والترميز [النص] / V.P. Tsymbal. - إد. الجمع. "مدرسة فيشكا" ، 1976. - 276 صفحة.

3. تينيكوف ، إ. الأسس النظرية لتكنولوجيا المعلومات / F.E. Tenniken. - م: الطاقة ، 1971. - 424 ص.

الرموز التصحيحية المنهجية. رمز المجموعة الخطية

More articles: