الرمز المعجمي

الموسوعة الحرة

الرموز المعجمية أو المعاجم هي رموز تصحيح أخطاء تُولّد بطريقة جشعة ، وتتميز بخصائص جيدة للغاية. وقد طُوّرت بشكل مستقل من قِبل فلاديمير ليفنشتاين [ 1 ] وجون هورتون كونواي ونيل سلون [ 2 ] . الرموز المعجمية الثنائية هي رموز خطية ، وتشمل رموز هامينغ ورموز غولاي الثنائية [ 2 ] .

بناء

يُنشأ رمز معجمي بطول n ومسافة دنيا d على حقل منتهٍ بالبدء بمتجه جميع عناصره أصفار، ثم إضافة المتجه التالي ( بالترتيب المعجمي ) ذي مسافة هامينغ الدنيا d بشكل متكرر من المتجهات المضافة حتى الآن. على سبيل المثال، يتكون الرمز المعجمي ذو الطول 3 والمسافة الدنيا 2 من المتجهات المميزة بعلامة "X" في المثال التالي:

متجهفي الكود؟
٠٠٠X
001
010
011X
100
101X
110X
111

فيما يلي جدول يوضح جميع رموز المعجم ذات n بت، مع حساب الحد الأدنى لمسافة هامينغ لكل منها، مما ينتج عنه قاموس رموز بحد أقصى 2m كلمة . على سبيل المثال، يُظهر رمز F4 ( n=4، d=2، m=3)، ورمز هامينغ الموسع (n=8، d=4، m=4)، وخاصة رمز غولاي (n=24، d=8، m=12) تماسكًا استثنائيًا مقارنةً بالرموز المجاورة.

اختصار الثاني123456789101112131415161718
11
221
3321
44311
554211
6653211
77643111
887442111
9985422111
1010965321111
111110764321111
1212118744221111
13131298543211111
1414131096543211111
151514111076542211111
1616151111875522111111
17171612119865322111111
181817131299763322111111
1919181413109874322111111
20201915141110985432211111
212120161512111095533221111
2222211716121211106543221111
2323221817131212116654222111
2424231918141312127655322211
2525242019151412128765332211
2626252120161512129876432221
2727262221171613129977543222
28282723221817131310987553322
292928242319181413111088654322
303029252419191514121198665422
3131302625201916151212109666532
32323126262120161613121110766633
33...32...26...21...16...13...11...7...6...3

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

بما أن المعاجم خطية، فإنه يمكن أيضًا بناؤها عن طريق أساسها . [ 3 ]

تطبيق

بعد ذلك، يتم إنشاء رمز معجمي وتعيين المعلمات لرمز غولاي (N=24، D=8).

#include <stdio.h> #include <stdlib.h> int main () { /* توليد كود GOLAY */ int i , j , k ; int _pc [ 1 << 16 ] = { 0 }; // ماكرو PopCount for ( i = 0 ; i < ( 1 << 16 ); i ++ ) for ( j = 0 ; j < 16 ; j ++ ) _pc [ i ] += ( i >> j ) & 1 ; #define pc(X) (_pc[(X)&0xffff] + _pc[((X)>>16)&0xffff]) #define N 24 // N بت #define D 8 // مسافة D بت unsigned int * z = malloc ( 1 << 29 ); for ( i = j = 0 ; i < ( 1 << N ); i ++ ) { // مسح جميع الرموز المعجمية السابقة for ( k = j - 1 ; k >= 0 ; k-- ) // if ( pc ( z [ k ] ^ i ) < D ) // التحقق العكسي break ; // أسرع بكثير... if ( k == -1 ) { // إضافة رمز معجمي جديد for ( k = 0 ; k < N ; k ++ ) // وطباعته printf ( "%d" , ( i >> k ) & 1 ); printf ( ": %d \n " , j ); z [ j ++ ] = i; } } }

نظرية الألعاب التوافقية

ترتبط نظرية الرموز المعجمية ارتباطًا وثيقًا بنظرية الألعاب التوافقية . وعلى وجه الخصوص، تُشفّر الكلمات المشفرة في رمز معجمي ثنائي بمسافة d مواقع الفوز في أحد أنواع لعبة غروندي ، التي تُلعب على مجموعة من أكوام الحجارة، حيث تتكون كل حركة من استبدال أي كومة بما لا يزيد عن d − 1 كومة أصغر منها، والهدف هو أخذ الحجر الأخير. [ 2 ]

ملحوظات

  1. ^ Levenšteĭn، VI (1960)، “Об одном классе систематических кодов” [ فئة من الرموز المنهجية ] ، Doklady Akademii Nauk SSSR (بالروسية)، 131 (5): 1011–1014 ، MR 0122629 ; الترجمة الإنجليزية في مجلة الرياضيات السوفيتية، العدد 1 (1960)، الصفحات 368-371
  2. 1 2 3 كونواي، جون هـ .؛ سلون، ن. ج. أ. (1986)، "الرموز المعجمية: رموز تصحيح الأخطاء من نظرية الألعاب"، معاملات IEEE في نظرية المعلومات ، 32 (3): 337-348 ، CiteSeerX 10.1.1.392.795 ، doi : 10.1109/TIT.1986.1057187 ، MR 0838197  
  3. ↑ تراختنبرغ، آري (2002)، "تصميم رموز معجمية ذات تعقيد شبكي معين"، معاملات IEEE في نظرية المعلومات ، 48 (1): 89-100 ، doi : 10.1109/18.971740 ، MR 1866958