الكود الخطي

في نظرية الترميز ، يُعرف الترميز الخطي بأنه ترميز تصحيح الأخطاء، حيث يُعتبر أي تركيب خطي من الكلمات المشفرة كلمة مشفرة. تُصنف الترميزات الخطية تقليديًا إلى ترميزات كتلية وترميزات التفافية ، مع العلم أن الترميزات التوربينية تُعتبر مزيجًا من هذين النوعين. ^{[ 1 ]} تتيح الترميزات الخطية خوارزميات ترميز وفك ترميز أكثر كفاءة من الترميزات الأخرى (انظر فك ترميز المتلازمة ).

تُستخدم الرموز الخطية في تصحيح الأخطاء الأمامية ، وتُطبّق في طرق إرسال الرموز (مثل البتات ) عبر قناة اتصال ، بحيث يُمكن للمُستقبِل تصحيح أو اكتشاف بعض الأخطاء في حال حدوثها. تتكون الكلمات المشفرة في رمز الكتلة الخطي من كتل من الرموز المُشفّرة باستخدام عدد من الرموز يفوق القيمة الأصلية المُراد إرسالها. ^{[ 2 ]} يُرسل رمز خطي بطول n كتلًا تحتوي على n رمزًا. على سبيل المثال، رمز هامينغ [7,4,3] هو رمز ثنائي خطي يُمثّل رسائل من 4 بتات باستخدام كلمات مشفرة من 7 بتات. تختلف كلمتان مشفرتان مختلفتان في ثلاثة بتات على الأقل. ونتيجةً لذلك، يُمكن اكتشاف ما يصل إلى خطأين لكل كلمة مشفرة، بينما يُمكن تصحيح خطأ واحد فقط. ^{[ 3 ]} يحتوي هذا الرمز على 2 ^{^4}  =  16 كلمة مشفرة.

الرمز الخطي ذو الطول n والبعد k هو فضاء جزئي خطي C ذو بعد k من الفضاء المتجهي${\displaystyle \mathbb {F} _{q}^{n}}$أين${\displaystyle \mathbb {F} _{q}}$هو الحقل المنتهي الذي يحتوي على q عنصرًا. يُسمى هذا النوع من الشفرة شفرة q -ary. إذا كانت q  =  2 أو q  =  3، تُوصف الشفرة بأنها شفرة ثنائية أو شفرة ثلاثية على التوالي. تُسمى المتجهات في C كلمات الشفرة . حجم الشفرة هو عدد كلمات الشفرة ويساوي qk ^.

وزن كلمة التشفير هو عدد عناصرها غير الصفرية، والمسافة بين كلمتي تشفير متجاورتين هي مسافة هامينغ بينهما، أي عدد العناصر التي تختلفان فيها. المسافة d للرمز الخطي هي أقل وزن لكلمات التشفير غير الصفرية، أو بعبارة أخرى، أقل مسافة بين كلمات تشفير مختلفة. يُطلق على الرمز الخطي ذي الطول n والبعد k والمسافة d اسم رمز [ n , k , d ] ( أو بتعبير أدق ،${\displaystyle [n,k,d]_{q}}$شفرة).

نريد أن نعطي${\displaystyle \mathbb {F} _{q}^{n}}$الأساس القياسي هو أن كل إحداثية تمثل "بت" يتم إرساله عبر "قناة مشوشة" ​​باحتمالية ضئيلة لحدوث خطأ في الإرسال ( قناة ثنائية متناظرة ). إذا تم استخدام أساس آخر، فلن يكون هذا النموذج قابلاً للتطبيق، ولن يقيس مقياس هامينغ عدد أخطاء الإرسال كما هو مطلوب.

كفضاء فرعي خطي من${\displaystyle \mathbb {F} _{q}^{n}}$يمكن تمثيل الكود C بأكمله (الذي قد يكون كبيرًا جدًا) على أنه مدى مجموعة من${\displaystyle k}$الكلمات المشفرة (المعروفة بالأساس في الجبر الخطي ). غالبًا ما تُجمع هذه الكلمات المشفرة الأساسية في صفوف مصفوفة G تُعرف باسم مصفوفة التوليد للرمز C. عندما تكون G على شكل مصفوفة كتلية${\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}$، أين${\displaystyle I_{k}}$يشير إلى${\displaystyle k\times k}$مصفوفة الوحدة و P هي شيء ما${\displaystyle k\times (nk)}$إذا كانت المصفوفة في الصورة القياسية، فإننا نقول إن G في الصورة القياسية .

مصفوفة H تمثل دالة خطية${\displaystyle \phi$ المصفوفة \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{nk} التينواتها C تُسمى مصفوفة التحقق لـ C (أو أحيانًا مصفوفة التحقق من التكافؤ). وبالمثل، H هي مصفوفة فضاءها الصفري هو C. إذا كانت C رمزًا بمصفوفة توليد G في الصورة القياسية،${\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}$، ثم${\displaystyle {\boldsymbol {H}}=[-P^{T}\mid I_{nk}]}$هي مصفوفة فحص لـ C. يُطلق على الكود المُولّد بواسطة H اسم الكود الثنائي لـ C. يمكن التحقق من أن G هي${\displaystyle k\times n}$مصفوفة، بينما H عبارة عن${\displaystyle (nk)\times n}$مصفوفة.

_{تضمن خاصية الخطية أن تكون} أقصر مسافة هامينغ d بين كلمة رمزية c₀ وأي كلمة رمزية أخرى c ≠ c₀ مستقلة عن _c₀ . وينتج هذا من خاصية أن الفرق c − c₀ بين كلمتين رمزيتين في C هو أيضًا كلمة رمزية (أي عنصر من الفضاء الجزئي C ) ، ومن خاصية أن d ( c , c₀ ₎ = d ( c − c₀ _{, 0 )} . وتستلزم هذه الخصائص أن          

${\displaystyle \min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,\ c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,\ c\neq 0}d(c,0)=d.}$

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

المسافة d للرمز الخطي C تساوي أيضًا الحد الأدنى لعدد الأعمدة المرتبطة خطيًا في مصفوفة التحقق H.

الدليل: لأن ${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}}$وهو ما يعادل${\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}}$، أين${\displaystyle {\boldsymbol {H_{i}}}}$هو${\displaystyle i^{th}}$عمود من${\displaystyle {\boldsymbol {H}}}$قم بإزالة تلك العناصر باستخدام${\displaystyle c_{i}=0}$، أولئك${\displaystyle {\boldsymbol {H_{i}}}}$مع${\displaystyle c_{i}\neq 0}$هي مرتبطة خطيًا. لذلك،${\displaystyle d}$هو على الأقل الحد الأدنى لعدد الأعمدة المرتبطة خطيًا. من ناحية أخرى، ضع في اعتبارك الحد الأدنى لمجموعة الأعمدة المرتبطة خطيًا${\displaystyle \{{\boldsymbol {H_{j}}}\mid j\in S\}}$أين${\displaystyle S}$هي مجموعة فهرس العمود. ${\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}}$والآن، لننظر إلى المتجه${\displaystyle {\boldsymbol {c'}}}$بحيث${\displaystyle c_{j}'=0}$لو${\displaystyle j\notin S}$. ملحوظة${\displaystyle {\boldsymbol {c'}}\in C}$لأن${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}}$لذلك، لدينا${\displaystyle d\leq wt({\boldsymbol {c'}})}$، وهو الحد الأدنى لعدد الأعمدة المرتبطة خطيًا في${\displaystyle {\boldsymbol {H}}}$وبذلك، تكون الملكية المطالب بها قد ثبتت.

باعتبارها أول فئة من الرموز الخطية التي طُوّرت لأغراض تصحيح الأخطاء، فقد استُخدمت رموز هامينغ على نطاق واسع في أنظمة الاتصالات الرقمية. لأي عدد صحيح موجب${\displaystyle r\geq 2}$يوجد${\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2}}$شفرة هامينغ. منذ${\displaystyle d=3}$، يمكن لرمز هامينغ هذا تصحيح خطأ بت واحد.

مثال  : رمز الكتلة الخطي ذو مصفوفة المولد ومصفوفة فحص التكافؤ التاليين هو${\displaystyle [7,4,3]_{2}}$شفرة هامينغ.

${\displaystyle {\boldsymbol {G}}={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&0&1&1\\0&0&1&0&1&1&1\\0&0&0&1&1&0&1\end{pmatrix}},}$${\displaystyle {\boldsymbol {H}}={\begin{pmatrix}1&0&1&1&1&0&0\\1&1&\ 1&0&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}}$

كود هادامارد هو${\displaystyle [2^{r},r,2^{r-1}]_{2}}$يتميز كود هادامارد بأنه خطي وقادر على تصحيح العديد من الأخطاء. ويمكن بناء كود هادامارد عمودًا تلو الآخر  .${\displaystyle i^{th}}$العمود هو بتات التمثيل الثنائي للعدد الصحيح${\displaystyle i}$كما هو موضح في المثال التالي. يتميز رمز هادامارد بأقصر مسافة${\displaystyle 2^{r-1}}$وبالتالي يمكنه التصحيح${\displaystyle 2^{r-2}-1}$أخطاء.

مثال: رمز الكتلة الخطي ذو مصفوفة المولد التالية هو${\displaystyle [8,3,4]_{2}}$رمز هادامارد: ${\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }={\begin{pmatrix}0&0&0&0&1&\ 1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{pmatrix}}}$.

يُعدّ رمز هادامارد حالة خاصة من رمز ريد-مولر . إذا أزلنا العمود الأول (العمود الذي يحتوي على جميع القيم الصفرية) من${\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }}$، نحصل${\displaystyle [7,3,4]_{2}}$رمز سيمبلكس ، وهو الرمز المزدوج لرمز هامينغ.

يرتبط المعامل d ارتباطًا وثيقًا بقدرة الكود على تصحيح الأخطاء. يوضح البناء/الخوارزمية التالية ذلك (وتسمى خوارزمية فك التشفير لأقرب جار):

المدخلات: متجه مستلم v في${\displaystyle \mathbb {F} _{q}^{n}.}$

الناتج: كلمة سرية${\displaystyle w}$في${\displaystyle C}$الأقرب إلى${\displaystyle v}$، إن وجدت.

• بدءاً من${\displaystyle t=0}$كرر الخطوتين التاليتين.
• عدد عناصر الكرة ذات نصف قطر (هامينغ)${\displaystyle t}$حول الكلمة المستلمة${\displaystyle v}$، المشار إليه${\displaystyle B_{t}(v)}$.
  • لكل${\displaystyle w}$في${\displaystyle B_{t}(v)}$تحقق مما إذا${\displaystyle w}$في${\displaystyle C}$إذا كان الأمر كذلك، فقم بالعودة${\displaystyle w}$كحل.
• زيادة${\displaystyle t}$الفشل فقط عندما${\displaystyle t>(d-1)/2}$إذن، اكتملت عملية التعداد ولم يتم العثور على أي حل.

نقول إن الخطية${\displaystyle C}$يكون${\displaystyle t}$- تصحيح الأخطاء إذا كان هناك كلمة رمزية واحدة على الأكثر في${\displaystyle B_{t}(v)}$لكل${\displaystyle v}$في${\displaystyle \mathbb {F} _{q}^{n}}$.

يُرمز للرموز عمومًا بالحرف C ، ويُشار عادةً إلى الرمز ذي الطول n والرتبة k (أي الذي يحتوي على n كلمة رمزية في أساسه و k صفًا في مصفوفة توليده ) باسم رمز ( n , k ). أما رموز الكتل الخطية، فيُرمز لها غالبًا برموز [ n , k , d ] ، حيث يشير d إلى أقصر مسافة هامينغ بين أي كلمتين رمزيتين.   

( لا ينبغي الخلط بين الترميز [ n , k , d ] والترميز ( n , M , d ) المستخدم للدلالة على رمز غير خطي بطول n وحجم M (أي يحتوي على M كلمة رمزية) وأدنى مسافة هامينغ d .)    

اللمة ( الحد الأحادي ): كل رمز خطي من النوع [ n , k , d ] C يحقق ما يلي:${\displaystyle k+d\leq n+1}$.

يُطلق على الكود C الذي تحقق معاييره الشرط k  + d  = n + 1 اسم الكود القابل للفصل بأقصى مسافة أو MDS . وتُعد هذه الأكواد، عند وجودها، من أفضل الأكواد الممكنة من بعض النواحي.   

إذا كان _C1 و C2 رمزين بطول n، _وإذا وُجد تبديل p في المجموعة المتناظرة Sn بحيث يكون ( c1 , ..., _{cn )} في C1 إذا وفقط إذا كان ( _cp ( 1 _{) ,} ..., cp _{( n ) )} في _C2 ، فإننا نقول _إن C1 _و C2 متكافئان تبديليًا _. وبشكل أعم، إذا وُجد${\displaystyle n\times n}$مصفوفة أحادية الحد${\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}$والذي يرسل C ₁ بشكل متماثل إلى C _2، ثم نقول أن C ₁ و C ₂ متكافئان .

اللمة : أي رمز خطي هو مكافئ تبديليًا لرمز موجود في الشكل القياسي.

يُعرَّف الرمز بأنه متساوي المسافات إذا وفقط إذا وُجد ثابت d بحيث تكون المسافة بين أي كلمتين مختلفتين من كلمات الرمز مساوية لـ d . ^{[ 4 ]} في عام 1984، حدد أريغو بونيسولي بنية الرموز الخطية ذات الوزن الواحد على الحقول المنتهية، وأثبت أن كل رمز خطي متساوي المسافات هو سلسلة من رموز هامينغ الثنائية . ^{[ 5 ]}

تتضمن بعض الأمثلة على الرموز الخطية ما يلي:

تم أيضًا دراسة فضاءات هامينغ على أبجديات غير حقلية، لا سيما على الحلقات المنتهية ، وأبرزها حلقات غالوا على Z⁴ _. ينتج عن ذلك وحدات نمطية بدلًا من فضاءات متجهة، ورموز خطية حلقية (مُعرَّفة بوحدات نمطية فرعية ) بدلًا من الرموز الخطية. المقياس النموذجي المستخدم في هذه الحالة هو مسافة لي . يوجد تماثل غراي بين${\displaystyle \mathbb {Z} _{2}^{2m}}$(أي GF(2 ^{2 m} )) مع مسافة هامينغ و${\displaystyle \mathbb {Z} _{4}^{m}}$(يُشار إليه أيضًا بـ GR(4,m)) مع مسافة لي؛ جاذبيته الرئيسية تكمن في أنه يُنشئ تطابقًا بين بعض الرموز "الجيدة" غير الخطية على${\displaystyle \mathbb {Z} _{2}^{2m}}$كصور لرموز خطية حلقية من${\displaystyle \mathbb {Z} _{4}^{m}}$[ ^{6 ] [ 7 ] [ 8 ]​}

وقد أشار بعض المؤلفين إلى هذه الرموز على الحلقات ببساطة على أنها رموز خطية أيضًا. ^{[ 9 ]}

• أساليب فك التشفير

• برنامج مولد الشفرة q
• جداول الأكواد: حدود المعلمات لأنواع مختلفة من الأكواد ، IAKS، Fakultät für Informatik، Universität Karlsruhe (TH)] . على الإنترنت، جدول محدث للرموز الثنائية المثالية، يتضمن رموزًا غير ثنائية.
• قاعدة بيانات رموز Z4 على الإنترنت، قاعدة بيانات محدثة لرموز Z4 المثلى.