رمز تصحيح أخطاء الترتيب

في نظرية الترميز ، تُعدّ رموز الرتبة (وتُسمى أيضًا رموز غابيدولين ) رموزًا غير ثنائية ^{[ 1 ]} خطية لتصحيح الأخطاء، لا تعتمد على مقياس هامينغ ، بل على مقياس الرتبة . وقد وصفت هذه الرموز طريقة منهجية لبناء رموز قادرة على اكتشاف وتصحيح أخطاء الرتبة العشوائية المتعددة . من خلال إضافة التكرار بترميز كلمة من k رمزًا إلى كلمة من n رمزًا، يمكن لرمز الرتبة تصحيح أي خطأ في الرتبة حتى t = ⌊ ( d − 1) / 2 ⌋، حيث d هي مسافة الترميز. وباعتباره رمزًا للمحو ، فإنه يستطيع تصحيح ما يصل إلى d − 1 من عمليات المحو المعروفة.        

رمز الرتبة هو رمز خطي جبري على الحقل المنتهي${\displaystyle GF(q^{N})}$مشابه لرمز ريد-سولومون .

رتبة المتجه على${\displaystyle GF(q^{N})}$يمثل الحد الأقصى لعدد المكونات المستقلة خطيًا على${\displaystyle GF(q)}$المسافة الرتبية بين متجهين على${\displaystyle GF(q^{N})}$يمثل رتبة الفرق بين هذين المتجهين.

يقوم رمز الرتبة بتصحيح جميع الأخطاء التي لا تتجاوز رتبة متجه الخطأ فيها t . 

يترك${\displaystyle X^{n}}$ليكن فضاء متجهي ذو n بُعد على الحقل المنتهي${\displaystyle GF\left({q^{N}}\right)}$، أين${\displaystyle q}$هي قوة عدد أولي و${\displaystyle N}$هو عدد صحيح موجب . ليكن ${\displaystyle \left(u_{1},u_{2},\dots ,u_{N}\right)}$، مع${\displaystyle u_{i}\in GF(q^{N})}$كن قاعدة لـ${\displaystyle GF\left({q^{N}}\right)}$كفضاء متجهي على الحقل${\displaystyle GF\left({q}\right)}$.

كل عنصر${\displaystyle x_{i}\in GF\left({q^{N}}\right)}$يمكن تمثيلها على النحو التالي${\displaystyle x_{i}=a_{1i}u_{1}+a_{2i}u_{2}+\dots +a_{Ni}u_{N}}$وبالتالي، كل متجه${\displaystyle {\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)}$زيادة${\displaystyle GF\left({q^{N}}\right)}$يمكن كتابتها على شكل مصفوفة:

${\displaystyle {\vec {x}}=\left\|{\begin{array}{*{20}c}a_{1,1}&a_{1,2}&\ldots &a_{1,n}\\a_{2,1}&a_{2,2}&\ldots &a_{2,n}\\\ldots &\ldots &\ldots &\ldots \\a_{N,1}&a_{N,2}&\ldots &a_{N,n}\end{array}}\right\|}$

رتبة المتجه${\displaystyle {\vec {x}}}$في الملعب${\displaystyle GF\left({q^{N}}\right)}$يمثل رتبة المصفوفة المقابلة ${\displaystyle A\left({\vec {x}}\right)}$في الملعب${\displaystyle GF\left({q}\right)}$يرمز إليه بـ${\displaystyle r\left({{\vec {x}};q}\right)}$.

مجموعة جميع المتجهات${\displaystyle {\vec {x}}}$هو مساحة${\displaystyle X^{n}=A_{N}^{n}}$الخريطة${\displaystyle {\vec {x}}\to r\left({\vec {x}};q\right)}$) يُعرّف معيارًا على${\displaystyle X^{n}}$ومقياس الترتيب :

${\displaystyle d\left({{\vec {x}};{\vec {y}}}\right)=r\left({{\vec {x}}-{\vec {y}};q}\right)}$

مجموعة${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$من المتجهات من${\displaystyle X^{n}}$يُطلق عليه اسم رمز ذو مسافة رمزية ${\displaystyle d=\min d\left(x_{i},x_{j}\right)}$إذا كانت المجموعة تشكل أيضًا فضاءً جزئيًا من البعد k من${\displaystyle X^{n}}$عندئذٍ يُطلق عليه اسم رمز خطي ( ن ، ك ) مع مسافة${\displaystyle d}$. هذا النوع من رموز مقياس الرتبة الخطية يحقق دائمًا حد Singleton${\displaystyle d\leq n-k+1}$بالمساواة.

هناك العديد من البنى المعروفة لرموز الرتبة، وهي رموز مسافة الرتبة القصوى (أو MRD) مع d  = n − k + 1. أسهلها في البناء هو ما يُعرف برمز غابيدولين (المعمم)، وقد اكتشفه ديلسارت أولاً (الذي أطلق عليه اسم نظام Singleton ) ولاحقًا غابيدولين ^{[ 2 ]} (وكشيفتسكي ^{[ 3 ]} ).     

لنعرّف قوة فروبينيوس${\displaystyle [i]}$من العنصر${\displaystyle x\in GF(q^{N})}$مثل

${\displaystyle x^{[i]}=x^{q^{i\mod N}}.\,}$

ثم، كل متجه${\displaystyle {\vec {g}}=(g_{1},g_{2},\dots ,g_{n}),~g_{i}\in GF(q^{N}),~n\leq N}$، مستقلة خطيًا على${\displaystyle GF(q)}$، يحدد مصفوفة توليد لرمز MRD ( n , k , d  = n − k + 1).     

${\displaystyle G=\left\|{\begin{array}{*{20}c}g_{1}&g_{2}&\dots &g_{n}\\g_{1}^{[m]}&g_{2}^{[m]}&\dots &g_{n}^{[m]}\\g_{1}^{[2m]}&g_{2}^{[2m]}&\dots &g_{n}^{[2m]}\\\dots &\dots &\dots &\dots \\g_{1}^{[(k-1)m]}&g_{2}^{[(k-1)m]}&\dots &g_{n}^{[(k-1)m]}\end{array}}\right\|,}$

أين${\displaystyle \gcd(m,N)=1}$.

توجد عدة مقترحات لأنظمة التشفير بالمفتاح العام القائمة على رموز الرتبة. ومع ذلك، فقد ثبت أن معظمها غير آمن (انظر على سبيل المثال مجلة علم التشفير، أبريل 2008 ^{[ 4 ]} ).

تُعد رموز الرتب مفيدة أيضًا لتصحيح الأخطاء والمحو في ترميز الشبكة .

• الكود الخطي
• تصحيح الخطأ ريد-سولومون
• خوارزمية بيرلكامب-ماسي
• ترميز الشبكة

• جابيدولين، إرنست م. (1985)، "نظرية الرموز ذات أقصى مسافة رتبة" ، مشاكل نقل المعلومات ، 21 ( 1): 1-12
• كشيفتسكي، ألكسندر؛ غابيدولين، إرنست م. (4-9 سبتمبر 2005). "البناء الجديد لرموز الرتب". وقائع الندوة الدولية لنظرية المعلومات، 2005. ISIT 2005. ص 2105-2108 . doi : 10.1109/ISIT.2005.1523717 . ISBN  978-0-7803-9151-2. S2CID 11679865 . 
• جابيدولين، إرنست م.؛ بيليبتشوك، نينا إ. (29 يونيو - 4 يوليو 2003). "طريقة جديدة لتصحيح المحو باستخدام رموز الرتبة". وقائع ندوة IEEE الدولية لنظرية المعلومات، 2003. ص  423. doi : 10.1109/ISIT.2003.1228440 . ISBN 978-0-7803-7728-8. S2CID 122552232 . 

• تنفيذ برنامج ترميز مقياس الرتبة باستخدام MATLAB