チエン検索

抽象代数学において、ロバート・ティエンウェン・チェンにちなんで名付けられたチェン探索は、有限体上で定義された多項式の根を決定するための高速アルゴリズムです。チェン探索は、リード・ソロモン符号やBCH 符号の復号化で発生するエラー位置多項式の根を見つけるためによく使用されます。

問題は、多項式Λ( x )の根を（有限体GF( q )上で）求めることです。 $${\displaystyle \Lambda (x)=\lambda _{0}+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{t}x^{t}}$$

根は力ずくで見つけられるかもしれません。xの数は有限なので、多項式は各要素x _iに対して評価できます。多項式がゼロに評価された場合、その要素は根です。

x  = 0 という単純なケースでは、係数λ _{0 がゼロかどうかのみをテストする必要があります。以下では、} x _{i が}ゼロでないかどうかのみを考慮に入れます。

多項式を直接評価するには、 O ( t ² ) 回の一般的な乗算とO ( t )回の加算が必要です。より効率的な方式としては、 O ( t ) 回の一般的な乗算とO ( t )回の加算にホーナー法を使用します。どちらのアプローチでも、有限体の要素を任意の順序で評価できます。

Chien 探索は、非ゼロ要素の特定の順序を選択することで、上記を改良します。特に、有限体には (定数) 生成元αがあります。Chien は、生成元の順序α ¹、 α ²、 α ³、 ....で要素をテストします。その結果、Chien 探索では、定数によるO ( t )回の乗算とO ( t )回の加算のみが必要になります。定数による乗算は、一般的な乗算よりも複雑ではありません。

Chien の検索は、次の 2 つの観察に基づいています。

• ゼロでない各 は、ある についてと表現できます。ここで、は の原始元、は原始元 のべき乗です。したがって、 のべき乗は、体全体 (ゼロ元を除く) をカバーします。${\displaystyle \beta}$${\displaystyle \alpha ^{i_{\beta }}}$${\displaystyle i_{\beta}}$${\displaystyle \alpha}$${\displaystyle \mathrm {GF} (q)}$${\displaystyle i_{\beta}}$${\displaystyle \alpha}$${\displaystyle \alpha^{i}}$${\displaystyle 0\leq i<(q-1)}$
• 次の関係が存在します。$${\displaystyle {\begin{array}{llllllllllll}\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{配列}}}$$

言い換えれば、それぞれを一連の項の合計として定義することができ、そこから次の係数のセットを次のように導くことができます。 ${\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}}$

このアプローチはハードウェアに実装すると、すべての乗算が、総当たりアプローチの場合の 2 つの変数ではなく、1 つの変数と 1 つの定数で構成されるため、複雑さが大幅に軽減されます。

• Chien、RT (1964 年 10 月)、「Bose-Chaudhuri-Hocquenghem コードの巡回復号化手順」、IEEE 情報理論トランザクション、IT-10 (4): 357–363、doi :10.1109/TIT.1964.1053699、ISSN  0018- 9448
• リン・シュウ、コステロ、ダニエル・J（2004）、エラー制御コーディング：基礎と応用（第2版）、エングルウッドクリフス、ニュージャージー：プレンティスホール、ISBN 978-0130426727
• Gill, John (nd)、EE387 ノート #7、配布資料 #28 (PDF) 、スタンフォード大学、pp. 42–45、2014-06-30のオリジナル(PDF)からアーカイブ、 2010 年4 月 21 日取得