بحث عن الكلاب

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

تكمن المشكلة في إيجاد جذور متعددة الحدود Λ ( x ) (على الحقل المنتهي GF( q ) ): $${\displaystyle \Lambda (x)=\lambda _{0}+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{t}x^{t}}$$

يمكن إيجاد الجذور باستخدام طريقة البحث الشامل: يوجد عدد محدود من قيم x ، لذا يمكن حساب قيمة متعددة الحدود لكل عنصر xᵢ _. إذا كانت قيمة متعددة الحدود تساوي صفرًا، فإن هذا العنصر هو جذر.

في الحالة البسيطة x  =  0 ، يكفي اختبار المعامل λ₀ للتأكد من أنه يساوي صفرًا. فيما يلي، سينصبّ الاهتمام فقط على قيم _xᵢ غير الصفرية _.

يتضمن التقييم المباشر لكثير الحدود O ( t² ⁾ من عمليات الضرب العامة و O ( t ) من عمليات الجمع. أما الطريقة الأكثر كفاءة فتستخدم طريقة هورنر التي تتطلب O ( t ) من عمليات الضرب العامة و O ( t ) من عمليات الجمع. ويمكن لكلتا الطريقتين تقييم عناصر الحقل المنتهي بأي ترتيب.

يُحسّن بحث تشين ما سبق باختيار ترتيب مُحدد للعناصر غير الصفرية. على وجه الخصوص، يحتوي الحقل المنتهي على عنصر مولد (ثابت) α . يختبر تشين العناصر بترتيب المولد α₁ ^، α₂ ^، α₃ ^، ... . بالتالي، لا يحتاج بحث تشين إلا إلى O ( t ) من عمليات الضرب بالثوابت و O ( t ) من عمليات الجمع . عمليات الضرب بالثوابت أقل تعقيدًا من عمليات الضرب العامة.

يعتمد بحث تشين على ملاحظتين:

• كل قيمة غير صفرية${\displaystyle \beta }$يمكن التعبير عنها على النحو التالي${\displaystyle \alpha ^{i_{\beta }}}$بالنسبة للبعض${\displaystyle i_{\beta }}$، أين${\displaystyle \alpha }$هو عنصر بدائي من${\displaystyle \mathrm {GF} (ف)}$،${\displaystyle i_{\beta }}$هو عدد القوة للعنصر الأولي${\displaystyle \alpha }$وهكذا أصبحت السلطات${\displaystyle \alpha ^{i}}$ل${\displaystyle 0\leq i<(q-1)}$تغطية الحقل بأكمله (باستثناء العنصر الصفري).
• توجد العلاقة التالية:$${\displaystyle {\begin{array}{lllllllllll}\Lambda (\alpha ^{i})&=&\lambda _{0}&+&\lambda _{1}(\alpha ^{i})&+&\lambda _{2}(\alpha ^{i})^{2}&+&\cdots &+&\lambda _{t}(\alpha ^{i})^{t}\\&\triangleq &\gamma _{0,i}&+&\gamma _{1,i}&+&\gamma _{2,i}&+&\cdots &+&\gamma _{t,i}\\\Lambda (\alpha ^{i+1})&=&\lambda _{0}&+&\lambda _{1}(\alpha ^{i+1})&+&\lambda _{2}(\alpha ^{i+1})^{2}&+&\cdots &+&\lambda _{t}(\alpha ^{i+1})^{t}\\&=&\lambda _{0}&+&\lambda _{1}(\alpha ^{i})\,\alpha &+&\lambda _{2}(\alpha ^{i})^{2}\,\alpha ^{2}&+&\cdots &+&\lambda _{t}(\alpha ^{i})^{t}\,\alpha ^{t}\\&=&\gamma _{0,i}&+&\gamma _{1,i}\,\alpha &+&\gamma _{2,i}\,\alpha ^{2}&+&\cdots &+&\gamma _{t,i}\,\alpha ^{t}\\&\triangleq &\gamma _{0,i+1}&+&\gamma _{1,i+1}&+&\gamma _{2,i+1}&+&\cdots &+&\gamma _{t,i+1}\end{array}}}$$

بمعنى آخر، يمكننا تعريف كل${\displaystyle \Lambda (\alpha ^{i})}$كمجموع مجموعة من الحدود${\displaystyle \{\gamma _{j,i}\mid 0\leq j\leq t\}}$ومنها يمكن اشتقاق المجموعة التالية من المعاملات على النحو التالي: $${\displaystyle \gamma _{j,i+1}=\gamma _{j,i}\,\alpha ^{j}}$$

وبهذه الطريقة، يمكننا أن نبدأ من${\displaystyle i=0}$مع${\displaystyle \gamma _{j,0}=\lambda _{j}}$، ثم تكرار العملية على كل قيمة من قيم${\displaystyle i}$حتى${\displaystyle (q-1)}$إذا كانت النتيجة الإجمالية في أي مرحلة تساوي صفرًا، أي $${\displaystyle \sum _{j=0}^{t}\gamma _{j,i}=0,}$$ ثم${\displaystyle \Lambda (\alpha ^{i})=0}$كذلك${\displaystyle \alpha ^{i}}$هو جذر. وبهذه الطريقة، نتحقق من كل عنصر في الحقل.

عند تطبيق هذا النهج في الأجهزة، فإنه يقلل بشكل كبير من التعقيد، حيث تتكون جميع عمليات الضرب من متغير واحد وثابت واحد، بدلاً من متغيرين كما هو الحال في نهج القوة الغاشمة.

• Chien، RT (أكتوبر 1964)، “إجراءات فك التشفير الدورية لرموز Bose-Chaudhuri-Hocquenghem”، معاملات IEEE حول نظرية المعلومات ، IT-10 (4): 357–363 ، doi : 10.1109/TIT.1964.1053699 ، ISSN 0018-9448 
• لين، شو؛ كوستيلو، دانيال ج. (2004)، ترميز التحكم في الأخطاء: الأساسيات والتطبيقات (الطبعة الثانية  )، إنجلوود كليفس، نيوجيرسي: برنتيس هول، ISBN 978-0130426727
• جيل، جون (بدون تاريخ)، ملاحظات EE387 رقم 7، النشرة رقم 28 (ملف PDF) ، جامعة ستانفورد، الصفحات 42-45 ، مؤرشفة من الأصل (ملف PDF) بتاريخ 30-06-2014 ، تم استرجاعها في 21 أبريل 2010