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

في نظرية الترميز ، تحسب خوارزمية فورني (أو خوارزمية فورني ) قيم الخطأ في مواقع الخطأ المعروفة. وتُستخدم كإحدى خطوات فك تشفير رموز BCH ورموز ريد - سولومون (وهي فئة فرعية من رموز BCH). وقد طوّر جورج ديفيد فورني الابن هذه الخوارزمية عام 1965. ^{[ 1 ]}

يلزم تقديم المصطلحات والإعداد...

تبدو الكلمات المشفرة مثل كثيرات الحدود. وبحسب التصميم، فإن لكثيرة الحدود المولدة جذورًا متتالية α ^c ، α ^{c +1} ، ..., α ^{c + d − 2} .

المتلازمات

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

${\displaystyle \Lambda (x)=\prod _{i=1}^{\nu }(1-x\,X_{i})=1+\sum _{i=1}^{\nu }\lambda _{i}\,x^{i}}$

أصفار الدالة Λ ( x ⁾ هي X₁₋₁ ^, _... , Xₙ₋₁ ^. هذه الأصفار هي مقلوب مواقع ^الخطأ _.${\displaystyle X_{j}=\alpha ^{i_{j}}}$.

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

في الحالة الأكثر عمومية، يمكن تحديد أوزان الخطأ e _j عن طريق حل النظام الخطي

${\displaystyle s_{0}=e_{1}\alpha ^{(c+0)\,i_{1}}+e_{2}\alpha ^{(c+0)\,i_{2}}+\cdots \,}$

${\displaystyle s_{1}=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \,}$

${\displaystyle \cdots \,}$

مع ذلك، توجد طريقة أكثر كفاءة تُعرف بخوارزمية فورني، وهي تعتمد على استيفاء لاغرانج . أولًا، احسب متعدد الحدود لتقييم الخطأ ^{[ 3 ].}

${\displaystyle \Omega (x)=S(x)\,\Lambda (x){\pmod {x^{2t}}}\,}$

حيث S ( x ) هي متعددة الحدود للمتلازمة الجزئية: ^{[ 4 ]}

${\displaystyle S(x)=s_{0}x^{0}+s_{1}x^{1}+s_{2}x^{2}+\cdots +s_{2t-1}x^{2t-1}.}$

ثم قم بتقييم قيم الخطأ: ^{[ 3 ]}

${\displaystyle e_{j}=-{\frac {X_{j}^{1-c}\,\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}\,}$

تُسمى القيمة c غالبًا "الجذر المتتالي الأول" أو "fcr". في بعض البرامج، يتم اختيار c = 1 ، وبالتالي يتبسط التعبير إلى:

${\displaystyle e_{j}=-{\frac {\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}}$

Λ '( x ) هو المشتق الرسمي لكثير الحدود لتحديد الخطأ Λ ( x ): ^{[ 3 ]}

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

في التعبير أعلاه، لاحظ أن i عدد صحيح ، وأن λ _i سيكون عنصرًا من الحقل المنتهي . يمثل المؤثر ⋅ الضرب العادي (الجمع المتكرر في الحقل المنتهي) وهو نفسه مؤثر الضرب في الحقل المنتهي ، أي

${\displaystyle i\lambda =(1+\ldots +1)\lambda =\lambda +\ldots +\lambda .}$

على سبيل المثال، في الخاصية الثانية،${\displaystyle i\lambda =0,\lambda }$بحسب ما إذا كان i زوجيًا أم فرديًا.

استيفاء لاغرانج

يقدم جيل (بدون تاريخ ، الصفحات 52-54) اشتقاقًا لخوارزمية فورني. 

عرّف متعدد الحدود لتحديد موقع المحو

${\displaystyle \Gamma (x)=\prod (1-x\,\alpha ^{j_{i}})}$

حيث يتم تحديد مواقع المسح بواسطة j _i . قم بتطبيق الإجراء الموضح أعلاه، مع استبدال Γ بـ Λ .

في حالة وجود أخطاء ومسح، استخدم متعدد الحدود لتحديد موقع الأخطاء والمسح

${\displaystyle \Psi (x)=\Lambda (x)\,\Gamma (x)}$

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

• فورني، ج. (أكتوبر 1965)، "حول فك تشفير رموز BCH"، معاملات IEEE في نظرية المعلومات ، 11 (4): 549-557 ، doi : 10.1109/TIT.1965.1053825 ، ISSN 0018-9448 
• جيل، جون (بدون تاريخ)، ملاحظات EE387 رقم 7، النشرة رقم 28 (ملف PDF) ، جامعة ستانفورد، الصفحات 42-45 ، مؤرشفة من الأصل (ملف PDF) في 30 يونيو 2014 ، تم استرجاعها في 21 أبريل 2010 
• كتاب دبليو ويسلي بيترسون