رمز بي سي إتش

في نظرية الترميز ، تُشكل رموز بوز - تشودري - هوكينغيم ( رموز BCH ) فئةً من رموز تصحيح الأخطاء الدورية ، والتي تُبنى باستخدام كثيرات الحدود على حقل منتهٍ (يُسمى أيضًا حقل غالوا ). اخترع رموز BCH عالم الرياضيات الفرنسي ألكسيس هوكينغيم عام 1959 ، وبشكل مستقل عام 1960، اخترعها راج تشاندرا بوز ودي كي راي-تشودري . ^[¹^]^[²^]^[³^] اسم بوز - تشودري - هوكينغيم (والاختصار BCH ) مشتق من الأحرف الأولى لألقاب المخترعين (خطأً، في حالة راي-تشودري).

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

تُستخدم رموز BCH في تطبيقات مثل الاتصالات عبر الأقمار الصناعية، ^{[ 4 ]} ومشغلات الأقراص المدمجة ، وأقراص DVD ، ومحركات الأقراص ، ومحركات أقراص USB المحمولة ، ومحركات الأقراص الصلبة ، ^{[ 5 ]} والرموز الشريطية ثنائية الأبعاد .

التعريف والتوضيح

رموز BCH البدائية ذات المعنى الضيق

بالنظر إلى عدد أولي $q$ وقوة أولية $q m$ مع أعداد صحيحة موجبة $m$ و $d$ بحيث $d \leq q m - 1$ ، يتم إنشاء رمز BCH بدائي ضيق المعنى على الحقل المنتهي (أو حقل Galois) $GF(q)$ بطول رمز $n = q m - 1$ ومسافة لا تقل عن d $بالطريقة$ التالية.

ليكن $α$ عنصرًا أوليًا في حقل $غالوا$ $GF(q, m)$ . لأي عدد صحيح موجب $i$ ، ليكن mᵢ $(x) متعدد$ الحدود الأدنى بمعاملات αᵢ في $حقل غالوا$ $GF$ ( $q) .$ يُعرَّف متعدد الحدود المولد لرمز BCH بأنه المضاعف المشترك الأصغر $g$ $($ $x$ $) = lcm($ $m₁$ $($ $x$ $), ...,$ $mᵢ₋₁$ $($ $x$ $))$ . يتضح أن $g$ $($ $x$ $)$ متعدد حدود بمعاملات في حقل $غالوا$ $GF$ $($ $q$ $)$ ويقسم $xⁿ⁻¹$ . بالتالي، فإن $رمز$ $متعدد$ الحدود $المُعرَّف$ بواسطة $g$ $($ $x$ $)$ هو رمز دوري.

مثال

لنفترض أن $q = 2$ و $m = 4$ (وبالتالي $n = 15$ ). سندرس قيمًا مختلفة لـ $d$ في $GF(16) = GF(2 4)$ بناءً على متعددة الحدود المختزلة $z 4 + z + 1$ ، باستخدام العنصر الأولي $α (z) = z$ . توجد أربعة عشر متعددة حدود دنيا $m i (x)$ بمعاملات في $GF(2)$ تحقق ما يلي:

m_{i}\left(\alpha ^{i}\right){\bmod {\left(z^{4}+z+1\right)}}=0.

كثيرات الحدود الدنيا هي

{\begin{aligned}m_{1}(x)&=m_{2}(x)=m_{4}(x)=m_{8}(x)=x^{4}+x+1,\\m_{3}(x)&=m_{6}(x)=m_{9}(x)=m_{12}(x)=x^{4}+x^{3}+x^{2}+x+1,\\m_{5}(x)&=m_{10}(x)=x^{2}+x+1,\\m_{7}(x)&=m_{11}(x)=m_{13}(x)=m_{14}(x)=x^{4}+x^{3}+1.\end{aligned}}

رمز BCH مع $d=2,3$ له متعدد الحدود المولد

g(x)={\rm {lcm}}(m_{1}(x),m_{2}(x))=m_{1}(x)=x^{4}+x+1.\,

يتميز هذا الكود بمسافة هامينغ دنيا لا تقل عن 3، ويصحح خطأً واحدًا كحد أقصى. وبما أن متعدد الحدود المولد من الدرجة الرابعة، فإن هذا الكود يحتوي على 11 بتًا للبيانات و4 بتات للتحقق من المجموع. ويُشار إليه أيضًا بالرمز: كود (15، 11) BCH .

رمز BCH مع $d=4,5$ له متعدد الحدود المولد

{\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x))=m_{1}(x)m_{3}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)=x^{8}+x^{7}+x^{6}+x^{4}+1.\end{aligned}}

يتميز هذا الكود بمسافة هامينغ دنيا لا تقل عن 5، ويصحح حتى خطأين. وبما أن متعدد الحدود المولد من الدرجة 8، فإن هذا الكود يحتوي على 7 بتات للبيانات و8 بتات للتحقق من المجموع. ويُشار إليه أيضًا بالرمز: (15، 7) كود BCH .

رمز BCH مع $d=6,7$ له متعدد الحدود المولد

\displaystyle \begin{aligned}g(x)&=\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x),m_{5}(x),m_{6}(x))=m_{1}(x)m_{3}(x)m_{5}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1.\end{aligned}}}

يتميز هذا الرمز بمسافة هامينغ دنيا لا تقل عن 7، ويصحح حتى ثلاثة أخطاء. ولأن متعدد الحدود المولد من الدرجة 10، فإن هذا الرمز يحتوي على 5 بتات للبيانات و10 بتات للتحقق من المجموع. ويُشار إليه أيضًا بالرمز: (15، 5) BCH code. (يُستخدم متعدد الحدود المولد هذا في تطبيقات عملية، ضمن "معلومات التنسيق" لرمز الاستجابة السريعة ).

رمز BCH مع $d=8$ ويكون للمولد متعدد الحدود أعلى من ذلك

\displaystyle \begin{aligned}g(x)&=\rm {lcm}}(m_{1}(x),m_{2}(x),...,m_{14}(x))=m_{1}(x)m_{3}(x)m_{5}(x)m_{7}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)\left(x^{4}+x^{3}+1\right)=x^{14}+x^{13}+x^{12}+\cdots +x^{2}+x+1.\end{aligned}}}

يتميز هذا الرمز بمسافة هامينغ دنيا تبلغ 15، ويصحح 7 أخطاء. يتكون من بت بيانات واحد و14 بت للتحقق من المجموع الاختباري. ويُشار إليه أيضًا بالرمز: (15, 1) رمز BCH . في الواقع، يتكون هذا الرمز من كلمتين فقط: 000000000000000 و111111111111111 ( رمز تكرار بسيط ).

رموز BCH العامة

تختلف رموز BCH العامة عن رموز BCH البدائية ذات المعنى الضيق في جانبين.

أولاً، الشرط الذي $\alpha$ أن يكون عنصرًا بدائيًا من $\mathrm {GF} (q^{m})$ يمكن تخفيف هذا الشرط. بتخفيف هذا الشرط، يتغير طول الكود من $q^{m}-1$ ل $\mathrm {ord} (\alpha ),$ ترتيب العنصر $\alpha .$

ثانيًا، قد تمتد الجذور المتتالية لكثير الحدود المولد من $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ بدلاً من $\alpha ,\ldots ,\alpha ^{d-1}.$

التعريف. تثبيت حقل منتهٍ $GF(q),$ أين $q$ هي قوة أولية. اختر أعدادًا صحيحة موجبة $m,n,d,c$ بحيث $2\leq d\leq n,$ ${\rm {gcd}}(n,q)=1,$ و $m$ هو الترتيب الضربي لـ $q$ modulo $n.$

كما في السابق، دع $\alpha$ كن بدائيًا $n$ الجذر النوني للوحدة في $GF(q^{m}),$ ودع $m_{i}(x)$ ليكن متعدد الحدود الأدنى على $GF(q)$ ل $\alpha ^{i}$ للجميع $i.$ تُعرَّف متعددة الحدود المولدة لرمز BCH بأنها المضاعف المشترك الأصغر $g(x)={\rm {lcm}}(m_{c}(x),\ldots ,m_{c+d-2}(x)).$

ملاحظة: إذا $n=q^{m}-1$ كما في التعريف المبسط، إذن ${\rm {gcd}}(n,q)$ هو 1، وترتيب $q$ modulo $n$ يكون $m.$ لذلك، فإن التعريف المبسط هو في الواقع حالة خاصة من التعريف العام.

حالات خاصة

رمز BCH مع $c=1$ يُطلق عليه اسم رمز BCH بالمعنى الضيق .
رمز BCH مع $n=q^{m}-1$ يُطلق عليه اسم بدائي .

كثير الحدود المولد $g(x)$ يحتوي رمز BCH على معاملات من $\mathrm {GF} (ف).$ بشكل عام، الكود الدوري على $\mathrm {GF} (q^{p})$ مع $g(x)$ يُطلق على كثير الحدود المولد اسم رمز BCH على $\mathrm {GF} (q^{p}).$ رمز BCH $\mathrm {GF} (q^{m})$ ومولد متعدد الحدود $g(x)$ مع صلاحيات متتالية لـ $\alpha$ تُعدّ جذور أحد أنواع شفرة ريد-سولومون حيث تكون أبجدية المُفكِّك (المتلازمات) هي نفسها أبجدية القناة (البيانات ومتعددة الحدود المولدة)، وجميع عناصر $\mathrm {GF} (q^{m})$ [ ⁶^] النوع الآخر من رموز ريد سولومون هو ^رمز ريد سولومون الأصلي الذي ليس رمز BCH.

ملكيات

تكون درجة متعددة الحدود المولدة لرمز BCH على الأكثر $(d-1)m$ علاوة على ذلك، إذا $q=2$ و $c=1$ ، يكون لكثير الحدود المولد درجة على الأكثر $dm/2$ .

دليل

كل متعددة حدود دنيا $m_{i}(x)$ حاصل على درجة علمية على الأكثر $m$ لذلك، فإن المضاعف المشترك الأصغر لـ $d-1$ لا يحمل أي منهم شهادة جامعية على الأكثر $(d-1)m$ علاوة على ذلك، إذا $q=2,$ ثم $m_{i}(x)=m_{2i}(x)$ للجميع $i$ . لذلك، $g(x)$ هو المضاعف المشترك الأصغر لـ على الأكثر $d/2$ كثيرات الحدود الدنيا $m_{i}(x)$ للفهارس الفردية $i,$ كل درجة على الأكثر $m$ .

يتميز رمز BCH بمسافة هامينغ دنيا على الأقل $d$ .

دليل

لنفترض أن $p(x)$ هي كلمة رمزية تحتوي على أقل من $d$ الحدود غير الصفرية. ثم

p(x)=b_{1}x^{k_{1}}+\cdots +b_{d-1}x^{k_{d-1}},{\text{ where }}k_{1}<k_{2}<\cdots <k_{d-1}.

تذكر أن $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ هي جذور $g(x),$ ومن ثم من $p(x)$ وهذا يعني أن $b_{1},\ldots ,b_{d-1}$ تحقق المعادلات التالية، لكل منها $i\in \{c,\dotsc ,c+d-2\}$ :

p(\alpha ^{i})=b_{1}\alpha ^{ik_{1}}+b_{2}\alpha ^{ik_{2}}+\cdots +b_{d-1}\alpha ^{ik_{d-1}}=0.

في شكل المصفوفة، لدينا

{\begin{bmatrix}\alpha ^{ck_{1}}&\alpha ^{ck_{2}}&\cdots &\alpha ^{ck_{d-1}}\\\alpha ^{(c+1)k_{1}}&\alpha ^{(c+1)k_{2}}&\cdots &\alpha ^{(c+1)k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(c+d-2)k_{1}}&\alpha ^{(c+d-2)k_{2}}&\cdots &\alpha ^{(c+d-2)k_{d-1}}\\\end{bmatrix}}{\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{d-1}\end{bmatrix}}={\begin{bmatrix}0\\0\\\vdots \\0\end{bmatrix}}.

محدد هذه المصفوفة يساوي

\left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det {\begin{pmatrix}1&1&\cdots &1\\\alpha ^{k_{1}}&\alpha ^{k_{2}}&\cdots &\alpha ^{k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(d-2)k_{1}}&\alpha ^{(d-2)k_{2}}&\cdots &\alpha ^{(d-2)k_{d-1}}\\\end{pmatrix}}=\left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det(V).

المصفوفة $V$ يُلاحظ أنها مصفوفة فانديرموند ، ومحددها هو

\det(V)=\prod _{1\leq i<j\leq d-1}\left(\alpha ^{k_{j}}-\alpha ^{k_{i}}\right),

وهو ليس صفراً. وبالتالي، يترتب على ذلك أن $b_{1},\ldots ,b_{d-1}=0,$ لذلك $p(x)=0.$

رمز BCH دوري.

دليل

رمز متعدد الحدود بطول $n$ تكون الدالة دورية إذا وفقط إذا كان متعدد الحدود المولد لها يقسم $x^{n}-1.$ منذ $g(x)$ هي متعددة الحدود الدنيا ذات الجذور $\alpha ^{c},\ldots ,\alpha ^{c+d-2},$ يكفي التحقق من أن كل واحد من $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ هو جذر $x^{n}-1.$ ويترتب على ذلك مباشرة حقيقة أن $\alpha$ هو، بحكم التعريف، $n$ الجذر النوني للوحدة.

التشفير

لأن أي متعدد حدود يكون مضاعفًا لمتعدد حدود المولد هو كلمة رمزية صالحة في BCH، فإن ترميز BCH هو مجرد عملية إيجاد متعدد حدود يكون المولد أحد عوامله.

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

التشفير غير المنهجي: الرسالة كعامل

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

s(x)=p(x)g(x)

كمثال على ذلك، ضع في اعتبارك متعدد الحدود المولد $g(x)=x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1$ تم اختيارها للاستخدام في رمز BCH الثنائي (31، 21) المستخدم في POCSAG وغيرها. لترميز الرسالة المكونة من 21 بت {101101110111101111101}، نقوم أولاً بتمثيلها كمتعددة حدود على $GF(2)$ :

p(x)=x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1

ثم احسب (أيضًا على $GF(2)$ ):

{\begin{aligned}s(x)&=p(x)g(x)\\&=\left(x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1\right)\left(x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1\right)\\&=x^{30}+x^{29}+x^{26}+x^{25}+x^{24}+x^{22}+x^{19}+x^{17}+x^{16}+x^{15}+x^{14}+x^{12}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{2}+1\end{aligned}}

وبالتالي، فإن كلمة الترميز المرسلة هي {1100111010010111101011101110101}.

يمكن للمستقبل استخدام هذه البتات كمعاملات في $s(x)$ وبعد تصحيح الأخطاء لضمان صحة كلمة المرور، يمكن إعادة حسابها. $p(x)=s(x)/g(x)$

التشفير المنهجي: الرسالة كبادئة

الشفرة المنهجية هي تلك التي تظهر فيها الرسالة حرفيًا في مكان ما ضمن كلمة الشفرة. لذلك، تتضمن عملية ترميز BCH المنهجية أولًا تضمين متعددة حدود الرسالة داخل متعددة حدود كلمة الشفرة، ثم تعديل معاملات الحدود المتبقية (غير المتعلقة بالرسالة) لضمان ذلك. $s(x)$ يقبل القسمة على $g(x)$ .

تستفيد طريقة التشفير هذه من حقيقة أن طرح الباقي من المقسوم ينتج عنه مضاعف للمقسوم عليه. وبالتالي، إذا أخذنا متعددة حدود الرسالة الخاصة بنا $p(x)$ كما في السابق، واضربه في $x^{n-k}$ (لإزاحة الرسالة بعيدًا عن طريق الباقي)، يمكننا بعد ذلك استخدام القسمة الإقليدية لكثيرات الحدود لنحصل على:

p(x)x^{n-k}=q(x)g(x)+r(x)

هنا، نرى أن $q(x)g(x)$ كلمة مرور صالحة. $r(x)$ تكون دائماً من درجة أقل من $n-k$ (وهي درجة $g(x)$ يمكننا طرحه بأمان من $p(x)x^{n-k}$ دون تغيير أي من معاملات الرسالة، وبالتالي لدينا $s(x)$ مثل

s(x)=q(x)g(x)=p(x)x^{n-k}-r(x)

زيادة $GF(2)$ (أي مع رموز BCH الثنائية)، لا يمكن تمييز هذه العملية عن إضافة فحص التكرار الدوري ، وإذا تم استخدام رمز BCH الثنائي المنهجي فقط لأغراض اكتشاف الأخطاء، فإننا نرى أن رموز BCH هي مجرد تعميم لرياضيات فحوصات التكرار الدوري .

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

فك التشفير

توجد العديد من الخوارزميات لفك تشفير رموز BCH. وتتبع أكثرها شيوعًا هذا المخطط العام:

احسب المتلازمات s _j للمتجه المستلم
حدد عدد الأخطاء t ومتعددة حدود تحديد موقع الخطأ Λ(x) من المتلازمات
احسب جذور متعددة حدود موقع الخطأ لإيجاد مواقع الخطأ X _i
احسب قيم الخطأ Y _i عند مواقع الخطأ تلك
صحح الأخطاء

خلال بعض هذه الخطوات، قد يكتشف خوارزمية فك التشفير أن المتجه المُستقبَل يحتوي على أخطاء كثيرة جدًا بحيث لا يمكن تصحيحها. على سبيل المثال، إذا لم يتم العثور على قيمة مناسبة لـ t ، فسيفشل التصحيح. في الشفرة المقتطعة (غير الأولية)، قد يكون موقع الخطأ خارج النطاق. إذا احتوى المتجه المُستقبَل على أخطاء أكثر مما يمكن للشفرة تصحيحه، فقد يُنتج جهاز فك التشفير، دون علمه، رسالة تبدو صحيحة ولكنها ليست الرسالة المُرسَلة.

احسب المتلازمات

المتجه المستلم $R$ هو مجموع كلمة السر الصحيحة $C$ ومتجه خطأ غير معروف $E.$ يتم تكوين قيم المتلازمة من خلال النظر في $R$ كدالة متعددة الحدود وتقييمها عند $\alpha ^{c},\ldots ,\alpha ^{c+d-2}.$ وبالتالي فإن المتلازمات هي ^{[ 7 ]}

s_{j}=R\left(\alpha ^{j}\right)=C\left(\alpha ^{j}\right)+E\left(\alpha ^{j}\right)

ل $j=c$ ل $c+d-2.$

منذ $\alpha ^{j}$ أصفار $g(x),$ منها $C(x)$ هو عدد مضاعف، $C\left(\alpha ^{j}\right)=0.$ وبالتالي فإن فحص قيم المتلازمة يعزل متجه الخطأ بحيث يمكن للمرء أن يبدأ في حله.

إذا لم يكن هناك خطأ، $s_{j}=0$ للجميع $j.$ إذا كانت جميع المتلازمات صفرًا، فإن عملية فك التشفير قد اكتملت.

احسب متعدد الحدود لتحديد موقع الخطأ

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

إذا كان هناك خطأ واحد، فاكتبه كالتالي: $E(x)=e\,x^{i},$ أين $i$ هو موقع الخطأ و $e$ حجمها. ثم المتلازمتان الأوليان هما

{\begin{aligned}s_{c}&=e\,\alpha ^{c\,i}\\s_{c+1}&=e\,\alpha ^{(c+1)\,i}=\alpha ^{i}s_{c}\end{aligned}}

لذا فإنهما يسمحان لنا معاً بالحساب $e$ وقدّم بعض المعلومات حول $i$ (تحديدها بشكل كامل في حالة رموز ريد-سولومون).

إذا كان هناك خطأين أو أكثر،

E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots \,

ليس من الواضح على الفور كيفية البدء في حل المتلازمات الناتجة عن المجاهيل $e_{k}$ و $i_{k}.$

تتمثل الخطوة الأولى في إيجاد حل يتوافق مع المتلازمات المحسوبة وبأقل قدر ممكن من العوامل المؤثرة. $t,$ متعدد الحدود المحدد:

\Lambda (x)=\prod _{j=1}^{t}\left(x\alpha ^{i_{j}}-1\right)

ثلاث خوارزميات شائعة لهذه المهمة هي:

خوارزمية بيترسون-جورنشتاين-زيرلر

تُعدّ خوارزمية بيترسون الخطوة الثانية من إجراء فك تشفير BCH المعمم. وتُستخدم خوارزمية بيترسون لحساب معاملات متعددة الحدود لتحديد موقع الخطأ. $\lambda _{1},\lambda _{2},\dots ,\lambda _{v}$ من متعدد الحدود

\Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}.

والآن، إليكم إجراء خوارزمية بيترسون-غورنشتاين-زيرلر. ^{[ 8 ]} نتوقع أن يكون لدينا على الأقل 2t متلازمات s c _، ...، s _{c + 2 t − 1.} لنفترض أن v = t .

ابدأ بإنشاء $S_{v\times v}$ مصفوفة تحتوي على عناصر تمثل قيم المتلازمة
$S_{v\times v}={\begin{bmatrix}s_{c}&s_{c+1}&\dots &s_{c+v-1}\\s_{c+1}&s_{c+2}&\dots &s_{c+v}\\\vdots &\vdots &\ddots &\vdots \\s_{c+v-1}&s_{c+v}&\dots &s_{c+2v-2}\end{bmatrix}}.$
إنشاء $c_{v\times 1}$ متجه ذو عناصر
$C_{v\times 1}={\begin{bmatrix}s_{c+v}\\s_{c+v+1}\\\vdots \\s_{c+2v-1}\end{bmatrix}}.$
يترك $\Lambda$ تشير إلى معاملات كثير الحدود المجهولة، والتي تُعطى بواسطة
$\Lambda _{v\times 1}={\begin{bmatrix}\lambda _{v}\\\lambda _{v-1}\\\vdots \\\lambda _{1}\end{bmatrix}}.$
قم بتكوين معادلة المصفوفة
$S_{v\times v}\Lambda _{v\times 1}=-C_{v\times 1\,}.$
إذا كان محدد المصفوفة $S_{v\times v}$ إذا كانت قيمة المصفوفة غير صفرية، فيمكننا إيجاد معكوس هذه المصفوفة وحل المعادلة لإيجاد قيم المجهول. $\Lambda$ قيم.
لو $\det \left(S_{v\times v}\right)=0,$ ثم اتبع إذا $v=0$ ثم قم بتعريف متعدد حدود لتحديد موقع الخطأ فارغًا. أوقف إجراء بيترسون. نهاية المجموعة $v\leftarrow v-1$ استمر من بداية عملية فك شفرة بيترسون عن طريق تصغيرها $S_{v\times v}$
بعد أن تحصل على قيم $\Lambda$ لديك متعددة الحدود لتحديد موقع الخطأ.
أوقفوا إجراء بيترسون.

متعدد الحدود لتحديد عامل الخطأ

الآن بعد أن حصلت على $\Lambda (x)$ متعددة الحدود، يمكن إيجاد جذورها في الشكل $\Lambda (x)=\left(\alpha ^{i_{1}}x-1\right)\left(\alpha ^{i_{2}}x-1\right)\cdots \left(\alpha ^{i_{v}}x-1\right)$ باستخدام القوة الغاشمة، على سبيل المثال باستخدام خوارزمية بحث تشين . القوى الأسية للعنصر الأولي $\alpha$ سيؤدي ذلك إلى تحديد المواضع التي تحدث فيها الأخطاء في الكلمة المستلمة؛ ومن هنا جاء اسم "محدد موقع الخطأ" متعدد الحدود.

أصفار Λ( x ) هي α ^{− i ₁} , ..., α ^{− i _v} .

حساب قيم الخطأ

بمجرد تحديد مواقع الأخطاء، تتمثل الخطوة التالية في تحديد قيم الأخطاء في تلك المواقع. ثم تُستخدم قيم الأخطاء لتصحيح القيم المستلمة في تلك المواقع لاستعادة كلمة المرور الأصلية.

في حالة BCH الثنائي (مع إمكانية قراءة جميع الأحرف)، يكون الأمر بسيطًا؛ يكفي قلب بتات الكلمة المستلمة في هذه المواضع، فنحصل على كلمة الترميز المصححة. أما في الحالة الأكثر عمومية، فتُستخدم أوزان الخطأ. $e_{j}$ يمكن تحديد ذلك عن طريق حل النظام الخطي

{\begin{aligned}s_{c}&=e_{1}\alpha ^{c\,i_{1}}+e_{2}\alpha ^{c\,i_{2}}+\cdots \\s_{c+1}&=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \\&{}\ \vdots \end{aligned}}

خوارزمية فورني

ومع ذلك، هناك طريقة أكثر كفاءة تُعرف باسم خوارزمية فورني .

يترك

S(x)=s_{c}+s_{c+1}x+s_{c+2}x^{2}+\cdots +s_{c+d-2}x^{d-2}.

v\leqslant d-1,\lambda _{0}\neq 0\qquad \Lambda (x)=\sum _{i=0}^{v}\lambda _{i}x^{i}=\lambda _{0}\prod _{k=0}^{v}\left(\alpha ^{-i_{k}}x-1\right).

ومتعدد الحدود لتقييم الخطأ ^{[ 9 ]}

\Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}

أخيراً:

\Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},

أين

i\cdot x:=\sum _{k=1}^{i}x.

بدلاً من ذلك، إذا أمكن تفسير المتلازمات بكلمة خطأ، والتي لا يمكن أن تكون قيمتها صفرًا إلا في المواضع المحددة. $i_{k}$ ثم تكون قيم الخطأ

e_{k}=-{\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right) \over \alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}.

بالنسبة لرموز BCH ذات المعنى الضيق، فإن c = 1، وبالتالي يتبسط التعبير إلى:

e_{k}=-{\Omega \left(\alpha ^{-i_{k}}\right) \over \Lambda '\left(\alpha ^{-i_{k}}\right)}.

شرح عملية حساب خوارزمية فورني

يعتمد ذلك على استيفاء لاغرانج وتقنيات توليد الدوال .

يعتبر $S(x)\Lambda (x),$ ولنفترض، من أجل التبسيط $\lambda _{k}=0$ ل $k>v,$ و $s_{k}=0$ ل $k>c+d-2.$ ثم

S(x)\Lambda (x)=\sum _{j=0}^{\infty }\sum _{i=0}^{j}s_{j-i+1}\lambda _{i}x^{j}.

{\begin{aligned}S(x)\Lambda (x)&=S(x)\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{i=0}^{d-2}\sum _{j=1}^{v}e_{j}\alpha ^{(c+i)\cdot i_{j}}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\sum _{i=0}^{d-2}\left(\alpha ^{i_{j}}\right)^{i}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\left(\left(x\alpha ^{i_{j}}\right)^{d-1}-1\right)\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right)\end{aligned}}

نريد حساب المجاهيل $e_{j},$ ويمكننا تبسيط السياق عن طريق إزالة $\left(x\alpha ^{i_{j}}\right)^{d-1}$ بنود. وهذا يؤدي إلى متعدد الحدود لتقييم الخطأ

\Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}.

شكراً لـ $v\leqslant d-1$ لدينا

\Omega (x)=-\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right).

شكراً لـ $\Lambda$ (حيلة لاغرانج للاستيفاء) يؤول المجموع إلى حد واحد فقط لـ $x=\alpha ^{-i_{k}}$

\Omega \left(\alpha ^{-i_{k}}\right)=-\lambda _{0}e_{k}\alpha ^{c\cdot i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).

للحصول على $e_{k}$ يجب علينا التخلص من حاصل الضرب. يمكننا حساب حاصل الضرب مباشرةً من الجذور المحسوبة مسبقًا. $\alpha ^{-i_{j}}$ ل $\Lambda ,$ لكن يمكننا استخدام صيغة أبسط.

كمشتق رسمي

\Lambda '(x)=\lambda _{0}\sum _{j=1}^{v}\alpha ^{i_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right),

نحصل مرة أخرى على أمر واحد فقط في

\Lambda '\left(\alpha ^{-i_{k}}\right)=\lambda _{0}\alpha ^{i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).

وأخيراً

e_{k}=-{\frac {\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right)}{\alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}}.

تُعد هذه الصيغة مفيدة عند حساب المشتقة الرسمية لـ $\Lambda$ استمارة

\Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}

ينتج عنه:

\Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},

أين

i\cdot x:=\sum _{k=1}^{i}x.

فك التشفير بناءً على خوارزمية إقليدية موسعة

تعتمد عملية بديلة لإيجاد كل من متعددة الحدود Λ ومتعددة حدود تحديد موقع الخطأ على تعديل ياسوو سوجياما لخوارزمية إقليدس الموسعة . ^{[ 10 ]} ويمكن دمج تصحيح الأحرف غير المقروءة في الخوارزمية بسهولة أيضًا.

يترك $k_{1},...,k_{k}$ تكون هذه مواقع لأحرف غير قابلة للقراءة. يتم إنشاء متعدد الحدود لتحديد هذه المواقع $\Gamma (x)=\prod _{i=1}^{k}\left(x\alpha ^{k_{i}}-1\right).$ قم بتعيين القيم في المواضع غير القابلة للقراءة إلى 0 واحسب المتلازمات.

كما سبق أن حددنا صيغة فورني، فلنفترض $S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.$

لنقم بتشغيل خوارزمية إقليدية موسعة لتحديد القاسم المشترك الأصغر لكثيرات الحدود $S(x)\Gamma (x)$ و $x^{d-1}.$ الهدف ليس إيجاد القاسم المشترك الأصغر، بل إيجاد متعدد الحدود $r(x)$ درجة علمية على الأكثر $\lfloor (d+k-3)/2\rfloor$ وكثيرات الحدود $a(x),b(x)$ بحيث $r(x)=a(x)S(x)\Gamma (x)+b(x)x^{d-1}.$ درجة منخفضة من $r(x)$ ضمانات، أن $a(x)$ سيلبي متطلبات التمديد (بواسطة $\Gamma$ ) تحديد الشروط لـ $\Lambda .$

تعريف $\Xi (x)=a(x)\Gamma (x)$ وباستخدام $\Xi$ في مكان $\Lambda (x)$ ستعطينا صيغة فورني قيم الخطأ.

تتمثل الميزة الرئيسية للخوارزمية في أنها تقوم في الوقت نفسه بالحساب $\Omega (x)=S(x)\Xi (x){\bmod {x}}^{d-1}=r(x)$ مطلوب في صيغة فورني.

شرح عملية فك التشفير

الهدف هو إيجاد كلمة رمزية تختلف عن الكلمة المستلمة بأقل قدر ممكن في المواضع المقروءة. عند التعبير عن الكلمة المستلمة كمجموع أقرب كلمة رمزية وكلمة خطأ، فإننا نحاول إيجاد كلمة خطأ بأقل عدد من القيم غير الصفرية في المواضع المقروءة. متلازمة $s_{i}$ يقيد الشرط كلمة الخطأ

s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.

يمكننا كتابة هذه الشروط بشكل منفصل أو يمكننا إنشاء متعددة الحدود

S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}

وقارن المعاملات القريبة من القوى $0$ ل $d-2.$

S(x){\stackrel {\{0,\cdots ,\,d-2\}}{=}}E(x)=\sum _{i=0}^{d-2}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}\alpha ^{cj}x^{i}.

لنفترض وجود حرف غير قابل للقراءة في الموضع $k_{1},$ يمكننا استبدال مجموعة من المتلازمات $\{s_{c},\cdots ,s_{c+d-2}\}$ حسب مجموعة المتلازمات $\{t_{c},\cdots ,t_{c+d-3}\}$ مُعرَّف بالمعادلة $t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}.$ لنفترض أن كلمة خاطئة تخضع لجميع القيود التي تفرضها المجموعة الأصلية $\{s_{c},\cdots ,s_{c+d-2}\}$ من المتلازمات التي تنطبق، أكثر

t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}=\alpha ^{k_{1}}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}-\sum _{j=0}^{n-1}e_{j}\alpha ^{j}\alpha ^{ij}=\sum _{j=0}^{n-1}e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)\alpha ^{ij}.

مجموعة جديدة من المتلازمات تحد من متجه الخطأ

f_{j}=e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)

بنفس الطريقة التي قيدت بها المجموعة الأصلية من المتلازمات متجه الخطأ $e_{j}.$ باستثناء الإحداثيات $k_{1},$ حيث لدينا $f_{k_{1}}=0,$ أن $f_{j}$ يساوي صفرًا، إذا $e_{j}=0.$ بهدف تحديد مواضع الأخطاء، يمكننا تغيير مجموعة المتلازمات بطريقة مماثلة لتشمل جميع الأحرف غير المقروءة. هذا يُقصر مجموعة المتلازمات بمقدار $k.$

في الصياغة متعددة الحدود، استبدال مجموعة المتلازمات $\{s_{c},\cdots ,s_{c+d-2}\}$ مجموعة المتلازمات $\{t_{c},\cdots ,t_{c+d-3}\}$ يؤدي إلى

T(x)=\sum _{i=0}^{d-3}t_{c+i}x^{i}=\alpha ^{k_{1}}\sum _{i=0}^{d-3}s_{c+i}x^{i}-\sum _{i=1}^{d-2}s_{c+i}x^{i-1}.

لذلك،

xT(x){\stackrel {\{1,\cdots ,\,d-2\}}{=}}\left(x\alpha ^{k_{1}}-1\right)S(x).

بعد استبدال $S(x)$ بواسطة $S(x)\Gamma (x)$ ، سيحتاج المرء إلى معادلة للمعاملات القريبة من القوى $k,\cdots ,d-2.$

يمكن للمرء أن ينظر في البحث عن مواضع الخطأ من منظور إزالة تأثير المواضع المحددة، على غرار البحث عن الأحرف غير المقروءة. إذا وجدنا $v$ إذا كانت المواضع التي يؤدي استبعاد تأثيرها إلى الحصول على مجموعة من المتلازمات تتكون من جميع الأصفار، فإنه يوجد متجه خطأ يحتوي على أخطاء فقط في هذه الإحداثيات. $\Lambda (x)$ إذا رمزنا إلى متعددة الحدود التي تزيل تأثير هذه الإحداثيات، فسنحصل على

S(x)\Gamma (x)\Lambda (x){\stackrel {\{k+v,\cdots ,d-2\}}{=}}0.

في خوارزمية إقليدس، نحاول تصحيح ما لا يزيد عن ${\tfrac {1}{2}}(d-1-k)$ الأخطاء (في المواضع القابلة للقراءة)، لأنه مع زيادة عدد الأخطاء، قد يكون هناك المزيد من الكلمات المشفرة على نفس المسافة من الكلمة المستلمة. لذلك، بالنسبة لـ $\Lambda (x)$ إذا كنا نبحث عن ذلك، فيجب أن تكون المعادلة صحيحة للمعاملات القريبة من القوى التي تبدأ من

k+\left\lfloor {\frac {1}{2}}(d-1-k)\right\rfloor .

في صيغة فورني، $\Lambda (x)$ يمكن ضربها في عدد قياسي يعطي نفس النتيجة.

قد يحدث أن تجد خوارزمية إقليدس $\Lambda (x)$ من درجة أعلى من ${\tfrac {1}{2}}(d-1-k)$ بوجود عدد من الجذور المختلفة يساوي درجتها، حيث تستطيع صيغة فورني تصحيح الأخطاء في جميع جذورها، على أي حال، قد يكون تصحيح هذا العدد الكبير من الأخطاء محفوفًا بالمخاطر (خاصةً مع عدم وجود قيود أخرى على الكلمة المستلمة). عادةً بعد الحصول على $\Lambda (x)$ في حالة وجود درجة أعلى، نقرر عدم تصحيح الأخطاء. قد يفشل التصحيح في هذه الحالة. $\Lambda (x)$ يحتوي على جذور ذات تعددية أعلى أو أن عدد الجذور أقل من درجته. يمكن أيضًا اكتشاف الفشل باستخدام صيغة فورني التي تُرجع خطأً خارج نطاق الأبجدية المُرسلة.

صحح الأخطاء

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

أمثلة على فك التشفير

فك تشفير الشفرة الثنائية بدون أحرف غير قابلة للقراءة

لنفترض وجود رمز BCH في GF(2 ⁴ ) مع $d=7$ و $g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1$ (يُستخدم هذا في رموز الاستجابة السريعة ). لنفترض أن الرسالة المراد إرسالها هي [1 1 0 1 1] ، أو في تدوين متعدد الحدود، $M(x)=x^{4}+x^{3}+x+1.$ يتم حساب رموز "مجموع التحقق" عن طريق القسمة $x^{10}M(x)$ بواسطة $g(x)$ وأخذ الباقي، مما ينتج عنه $x^{9}+x^{4}+x^{2}$ أو [ 1 0 0 0 0 1 0 1 0 0 ] . تُضاف هذه إلى الرسالة، لذا فإن كلمة المرور المرسلة هي [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ] .

الآن، تخيل وجود خطأين في البتات أثناء الإرسال، وبالتالي فإن الكلمة المشفرة المستلمة هي [1 0 0 1 1 1 0 0 0 1 1 0 1 0 0]. بالصيغة متعددة الحدود:

R(x)=C(x)+x^{13}+x^{5}=x^{14}+x^{11}+x^{10}+x^{9}+x^{5}+x^{4}+x^{2}

لتصحيح الأخطاء، احسب المتلازمات أولاً. مع الأخذ في الاعتبار $\alpha =0010,$ لدينا $s_{1}=R(\alpha ^{1})=1011,$ $s_{2}=1001,$ $s_{3}=1011,$ $s_{4}=1101,$ $s_{5}=0001,$ و $s_{6}=1001.$ بعد ذلك، قم بتطبيق إجراء بيترسون عن طريق تقليل عدد الصفوف في المصفوفة الموسعة التالية .

\left[S_{3\times 3}|C_{3\times 1}\right]={\begin{bmatrix}s_{1}&s_{2}&s_{3}&s_{4}\\s_{2}&s_{3}&s_{4}&s_{5}\\s_{3}&s_{4}&s_{5}&s_{6}\end{bmatrix}}={\begin{bmatrix}1011&1001&1011&1101\\1001&1011&1101&0001\\1011&1101&0001&1001\end{bmatrix}}\Rightarrow {\begin{bmatrix}0001&0000&1000&0111\\0000&0001&1011&0001\\0000&0000&0000&0000\end{bmatrix}}

بسبب وجود الصف الصفري، فإن المصفوفة $S 3\times3$ منفردة، وهذا ليس مفاجئًا نظرًا لوجود خطأين فقط في كلمة الترميز. مع ذلك، فإن الزاوية العلوية اليسرى للمصفوفة مطابقة للمصفوفة $[S 2\times2 | C 2\times1]$ ، مما يؤدي إلى الحل. $\lambda _{2}=1000,$ $\lambda _{1}=1011.$ متعدد الحدود الناتج لتحديد موقع الخطأ هو $\Lambda (x)=1000x^{2}+1011x+0001,$ والتي تحتوي على أصفار عند $0100=\alpha ^{-13}$ و $0111=\alpha ^{-5}.$ أسس $\alpha$ تتوافق هذه القيم مع مواقع الخطأ. لا حاجة لحساب قيم الخطأ في هذا المثال، لأن القيمة الوحيدة الممكنة هي 1.

فك التشفير باستخدام أحرف غير قابلة للقراءة

لنفترض السيناريو نفسه، ولكن الكلمة المستلمة تحتوي على حرفين غير مقروءين [1 0 0 ؟ 1 1 ؟ 0 0 1 1 0 1 0 0]. نستبدل هذين الحرفين غير المقروءين بأصفار، مع إنشاء متعددة الحدود التي تعكس موقعهما. $\Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).$ نقوم بحساب المتلازمات $s_{1}=\alpha ^{-7},s_{2}=\alpha ^{1},s_{3}=\alpha ^{4},s_{4}=\alpha ^{2},s_{5}=\alpha ^{5},$ و $s_{6}=\alpha ^{-7}.$ (باستخدام الترميز اللوغاريتمي المستقل عن التشاكلات في حقل غالوا GF(2 ⁴ ). للتحقق من صحة الحساب، يمكننا استخدام نفس تمثيل الجمع المستخدم في المثال السابق. وصف سداسي عشري لقوى $\alpha$ (الأرقام المتتالية هي 1، 2، 4، 8، 3، 6، C، B، 5، A، 7، E، F، D، 9 مع الجمع القائم على عملية XOR الثنائية.)

لنجعل المتلازمة متعددة الحدود

S(x)=\alpha ^{-7}+\alpha ^{1}x+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{5}x^{4}+\alpha ^{-7}x^{5},

حساب

S(x)\Gamma (x)=\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}.

قم بتشغيل خوارزمية إقليدس الموسعة:

{\begin{aligned}&{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+2\alpha ^{7}x^{6}+2\alpha ^{-3}x^{7}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{-5}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\left(\alpha ^{-7}+\alpha ^{3}\right)x+\left(\alpha ^{3}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-5}+\alpha ^{-6}\right)x^{3}+\left(\alpha ^{3}+\alpha ^{1}\right)x^{4}+2\alpha ^{-6}x^{5}+2x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\left(1+\alpha ^{-4}\right)+\left(\alpha ^{1}+\alpha ^{2}\right)x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-5}+\alpha ^{-4}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\left(\alpha ^{7}+\alpha ^{-7}\right)+\left(2\alpha ^{-7}+\alpha ^{4}\right)x+\left(\alpha ^{-5}+\alpha ^{-6}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-7}+\alpha ^{-4}+\alpha ^{6}\right)x^{3}+\left(\alpha ^{4}+\alpha ^{-6}+\alpha ^{-1}\right)x^{4}+2\alpha ^{5}x^{5}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}{\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.\end{aligned}}

لقد وصلنا إلى متعددة حدود من الدرجة الثالثة على الأكثر، و

{\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},

نحصل

{\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.

لذلك،

S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}\right)-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)x^{6}=\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}.

يترك $\Lambda (x)=\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}.$ لا تقلق من ذلك $\lambda _{0}\neq 1.$ أوجد جذرًا للمعادلة التالية باستخدام طريقة البحث الشامل: $\Lambda .$ الجذور هي $\alpha ^{2},$ و $\alpha ^{10}$ (بعد العثور على سبيل المثال) $\alpha ^{2}$ يمكننا أن نقسم $\Lambda$ بواسطة المونوم المقابل $\left(x-\alpha ^{2}\right)$ ويمكن إيجاد جذر المونوم الناتج بسهولة).

يترك

{\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{-5}x^{4}\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}{\bmod {x^{6}}}\end{aligned}}

لنبحث عن قيم الخطأ باستخدام الصيغة

e_{j}=-{\frac {\Omega \left(\alpha ^{-i_{j}}\right)}{\Xi '\left(\alpha ^{-i_{j}}\right)}},

أين $\alpha ^{-i_{j}}$ هي جذور $\Xi (x).$ $\Xi '(x)=\alpha ^{2}x^{2}.$ نحصل

{\begin{aligned}e_{1}&=-{\frac {\Omega (\alpha ^{4})}{\Xi '(\alpha ^{4})}}={\frac {\alpha ^{-4}+\alpha ^{-7}+\alpha ^{-5}+\alpha ^{7}}{\alpha ^{-5}}}={\frac {\alpha ^{-5}}{\alpha ^{-5}}}=1\\e_{2}&=-{\frac {\Omega (\alpha ^{7})}{\Xi '(\alpha ^{7})}}={\frac {\alpha ^{-4}+\alpha ^{-4}+\alpha ^{1}+\alpha ^{1}}{\alpha ^{1}}}=0\\e_{3}&=-{\frac {\Omega (\alpha ^{10})}{\Xi '(\alpha ^{10})}}={\frac {\alpha ^{-4}+\alpha ^{-1}+\alpha ^{7}+\alpha ^{-5}}{\alpha ^{7}}}={\frac {\alpha ^{7}}{\alpha ^{7}}}=1\\e_{4}&=-{\frac {\Omega (\alpha ^{2})}{\Xi '(\alpha ^{2})}}={\frac {\alpha ^{-4}+\alpha ^{6}+\alpha ^{6}+\alpha ^{1}}{\alpha ^{6}}}={\frac {\alpha ^{6}}{\alpha ^{6}}}=1\end{aligned}}

حقيقة أن $e_{3}=e_{4}=1,$ لا ينبغي أن يكون ذلك مفاجئاً.

وبالتالي فإن الكود المصحح هو [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

فك التشفير باستخدام أحرف غير قابلة للقراءة مع عدد قليل من الأخطاء

لنُظهر سلوك الخوارزمية في حالة وجود عدد قليل من الأخطاء. لنفترض أن الكلمة المستلمة هي [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].

مرة أخرى، استبدل الأحرف غير المقروءة بأصفار أثناء إنشاء متعددة الحدود التي تعكس مواقعها $\Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).$ احسب المتلازمات $s_{1}=\alpha ^{4},s_{2}=\alpha ^{-7},s_{3}=\alpha ^{1},s_{4}=\alpha ^{1},s_{5}=\alpha ^{0},$ و $s_{6}=\alpha ^{2}.$ إنشاء متعدد الحدود للمتلازمة

{\begin{aligned}S(x)&=\alpha ^{4}+\alpha ^{-7}x+\alpha ^{1}x^{2}+\alpha ^{1}x^{3}+\alpha ^{0}x^{4}+\alpha ^{2}x^{5},\\S(x)\Gamma (x)&=\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}.\end{aligned}}

لنقم بتشغيل خوارزمية إقليدس الموسعة:

{\begin{aligned}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}&={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}\\x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+2\alpha ^{-1}x^{6}+2\alpha ^{6}x^{7}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{3}+\alpha ^{1}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\left(\alpha ^{-5}+\alpha ^{5}\right)x+2\alpha ^{-7}x^{2}+2\alpha ^{6}x^{3}+2\alpha ^{4}x^{4}+2\alpha ^{2}x^{5}+2x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\left(1+\alpha ^{2}\right)+\left(\alpha ^{0}+\alpha ^{-6}\right)x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}\end{aligned}}

لقد وصلنا إلى متعددة حدود من الدرجة الثالثة على الأكثر، و

{\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},

نحصل

{\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}.

لذلك،

S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{1}x\right)-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)x^{6}=\alpha ^{7}+\alpha ^{0}x.

يترك $\Lambda (x)=\alpha ^{3}+\alpha ^{1}x.$ لا تقلق من ذلك $\lambda _{0}\neq 1.$ أصل $\Lambda (x)$ يكون $\alpha ^{3-1}.$

يترك

{\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{-7}x+\alpha ^{-4}x^{2}+\alpha ^{5}x^{3},\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{7}+\alpha ^{0}x{\bmod {x^{6}}}\end{aligned}}

لنبحث عن قيم الخطأ باستخدام الصيغة $e_{j}=-\Omega \left(\alpha ^{-i_{j}}\right)/\Xi '\left(\alpha ^{-i_{j}}\right),$ أين $\alpha ^{-i_{j}}$ هي جذور متعددة الحدود $\Xi (x).$

\Xi '(x)=\alpha ^{-7}+\alpha ^{5}x^{2}.

نحصل

{\begin{aligned}e_{1}&=-{\frac {\Omega \left(\alpha ^{4}\right)}{\Xi '\left(\alpha ^{4}\right)}}={\frac {\alpha ^{7}+\alpha ^{4}}{\alpha ^{-7}+\alpha ^{-2}}}={\frac {\alpha ^{3}}{\alpha ^{3}}}=1\\e_{2}&=-{\frac {\Omega \left(\alpha ^{7}\right)}{\Xi '\left(\alpha ^{7}\right)}}={\frac {\alpha ^{7}+\alpha ^{7}}{\alpha ^{-7}+\alpha ^{4}}}=0\\e_{3}&=-{\frac {\Omega \left(\alpha ^{2}\right)}{\Xi '\left(\alpha ^{2}\right)}}={\frac {\alpha ^{7}+\alpha ^{2}}{\alpha ^{-7}+\alpha ^{-6}}}={\frac {\alpha ^{-3}}{\alpha ^{-3}}}=1\end{aligned}}

حقيقة أن $e_{3}=1$ لا ينبغي أن يكون ذلك مفاجئاً.

وبالتالي فإن الكود المصحح هو [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

الاقتباسات

↑ ريد وتشين 1999 ، ص 189
↑ هوكينغهيم 1959
↑ بوز وراي تشودري 1960
↑ "نظام ترميز مركبة الهبوط فوبوس: البرمجيات والتحليل" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 9 أكتوبر 2022. تم الاطلاع عليه بتاريخ 25 فبراير 2012 .
↑ ماريلي، أليسيا؛ ميشيلوني، رينو (2018). "رموز BCH لمحركات الحالة الصلبة" . داخل محركات الحالة الصلبة (SSDS) . سلسلة سبرينغر في الإلكترونيات الدقيقة المتقدمة. المجلد 37. الصفحات 369-406 . doi : 10.1007/978-981-13-0599-3_11 . ISBN 978-981-13-0598-6تم الاطلاع عليه بتاريخ 23 سبتمبر 2023 .
↑ جيل، بدون تاريخ ، ص. 3
↑ ليدل وبيلز 1999 ، ص 229
^ جورنشتاين وبيترسون وزيرلر 1960
↑ جيل، بدون تاريخ ، ص 47
^ ياسو سوجياما، ماساو كاساهارا، شيغيتشي هيراساوا، وتوشيهيكو ناميكاوا. طريقة لحل المعادلات الرئيسية لفك رموز Goppa. المعلومات والتحكم، 27: 87-99، 1975.

مراجع

المصادر الأولية

Hocquenghem، A. (سبتمبر 1959)، “Codes Correcteurs d’erreurs”، شيفر (بالفرنسية)، 2 ، باريس: 147-156
بوز، آر سي ؛ راي-تشودري، دي كيه (مارس 1960)، "حول فئة من رموز المجموعة الثنائية المصححة للأخطاء" (ملف PDF) ، المعلومات والتحكم ، 3 (1): 68-79 ، رمز Bibcode : 1960InfCo...3...68B ، doi : 10.1016/s0019-9958(60)90287-4 ، ISSN 0890-5401 ، مؤرشف (ملف PDF) من الأصل بتاريخ 2022-10-09

مصادر ثانوية

جيل، جون (بدون تاريخ)، ملاحظات EE387 رقم 7، النشرة رقم 28 (ملف PDF) ، جامعة ستانفورد، الصفحات 42-45 ، مؤرشفة (ملف PDF) من الأصل بتاريخ 2022-10-09 ، تم استرجاعها في 21 أبريل 2010 يبدو أن ملاحظات المقرر الدراسي تُعاد صياغتها لعام ٢٠١٢: http://www.stanford.edu/class/ee387/ مؤرشفة بتاريخ ٥ يونيو ٢٠١٣ على موقع Wayback Machine
غورنشتاين، دانيال ؛ بيترسون، دبليو. ويسلي ؛ زيرلر، نيل (1960)، "رموز بوز-تشودري المصححة لخطأين شبه مثالية"، المعلومات والتحكم ، 3 (3): 291-294 ، doi : 10.1016/s0019-9958(60)90877-9
ليدل، رودولف؛ بيلز، غونتر (1999)، الجبر المجرد التطبيقي ( الطبعة الثانية)، جون وايلي
ريد، إيرفينغ إس .؛ تشين، شومين (1999)، ترميز التحكم في الأخطاء لشبكات البيانات ، بوسطن، ماساتشوستس: دار نشر كلوير الأكاديمية ، رقم ISBN 0-7923-8528-4

للمزيد من القراءة

بلاهوت، ريتشارد إي. (2003)، الرموز الجبرية لنقل البيانات ( الطبعة الثانية)، مطبعة جامعة كامبريدج ، رقم ISBN 0-521-55374-1
جيلبرت، دبليو جيه؛ نيكلسون، دبليو كيه (2004)، الجبر الحديث مع التطبيقات (الطبعة الثانية )، جون وايلي
لين، س.؛ كوستيلو، د. (2004)، ترميز التحكم في الأخطاء: الأساسيات والتطبيقات ، إنجلوود كليفس، نيوجيرسي: برنتيس هول
ماكويليامز، إف جيه؛ سلون، إن جيه إيه (1977)، نظرية رموز تصحيح الأخطاء ، نيويورك، نيويورك: شركة نورث هولاند للنشر
رودرا، أتري، CSE 545، رموز تصحيح الأخطاء: التوافقية والخوارزميات والتطبيقات ، جامعة بافالو، مؤرشف من الأصل في 18 ديسمبر 2012 ، تم استرجاعه في 11 مايو 2009

[1] ريد وتشين 1999 ، ص 189

[2] هوكينغهيم 1959

[3] بوز وراي تشودري 1960

[4] "نظام ترميز مركبة الهبوط فوبوس: البرمجيات والتحليل" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 9 أكتوبر 2022. تم الاطلاع عليه بتاريخ 25 فبراير 2012 .

[5] ماريلي، أليسيا؛ ميشيلوني، رينو (2018). "رموز BCH لمحركات الحالة الصلبة" . داخل محركات الحالة الصلبة (SSDS) . سلسلة سبرينغر في الإلكترونيات الدقيقة المتقدمة. المجلد 37. الصفحات 369-406 . doi : 10.1007/978-981-13-0599-3_11 . ISBN 978-981-13-0598-6تم الاطلاع عليه بتاريخ 23 سبتمبر 2023 .

[6] جيل، بدون تاريخ ، ص. 3

[7] ليدل وبيلز 1999 ، ص 229

[8] جورنشتاين وبيترسون وزيرلر 1960

[Gill-Forney-9] جيل، بدون تاريخ ، ص 47

[10] ياسو سوجياما، ماساو كاساهارا، شيغيتشي هيراساوا، وتوشيهيكو ناميكاوا. طريقة لحل المعادلات الرئيسية لفك رموز Goppa. المعلومات والتحكم، 27: 87-99، 1975.

[

[

[

[ 4 ]

[ 5 ]

6

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗