Procedimento de Chien

Na álgebra abstrata, o procedimento de Chien, cujo nome advém de R. T. Chien, é um algoritmo rápido para determinar a raiz de um polinómio definido sobre um corpo finito. O caso mais típico para a utilização do procedimento de Chien é no cálculo das raízes de polinómios error-locator encontrados na descodificação do código de Reed-Solomon e código de BCH.

Denotando o polinómio (sobre o corpo finito GF(${\displaystyle q}$)) cujas raízes queremos determinar como:

${\displaystyle \ \Lambda (x)=\lambda _{0}+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{t}x^{t}}$

Conceptualmente, podemos avaliar ${\displaystyle \Lambda (\beta )}$ por cada não-zero ${\displaystyle \beta }$ em GF(${\displaystyle q}$). Aqueles que resultarem em 0 são raízes do polinómio.

O procedimento de Chien é baseado em duas observações:

• Cada não-zero ${\displaystyle \beta }$ pode ser expresso como ${\displaystyle \alpha ^{i_{\beta }}}$ para alguns ${\displaystyle i_{\beta }}$, onde ${\displaystyle \alpha }$ é um elemento primitivo (sugerido do inglês, primitive element) de ${\displaystyle \mathrm {GF} (q)}$, ${\displaystyle i_{\beta }}$ é a potência do elemento primitivo ${\displaystyle \alpha }$. Assim as potências ${\displaystyle \alpha ^{i}}$ por cada ${\displaystyle 0\leq i<(q-1)}$ cobrem o espectro inteiro (excluindo o elemento zero).
• A seguinte relação existe:

${\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}\end{array}}}$

${\displaystyle {\begin{array}{lllllllllll}\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}}}$

Por outras palavras podemos definir cada ${\displaystyle \Lambda (\alpha ^{i})}$ como a soma de um conjunto de termos ${\displaystyle \{\gamma _{j,i}|0\leq j\leq t\}}$, dos quais o próximo conjunto de coeficiente pode ser derivado, e assim:

${\displaystyle \ \gamma _{j,i+1}=\gamma _{j,i}\,\alpha ^{j}}$

Desta maneira podemos começar em ${\displaystyle i=0}$ com ${\displaystyle \gamma _{j,0}=\lambda _{j}}$, e iterar através de cada valor de ${\displaystyle i}$ até ${\displaystyle (q-1)}$. Se em qualquer altura a soma resultante é zero, temos:

${\displaystyle \ \sum _{j=0}^{t}\gamma _{j,i}=0,}$

assim ${\displaystyle \Lambda (\alpha ^{i})=0}$ também, logo ${\displaystyle \alpha _{i}}$ é uma raiz. Desta maneira confirmamos todos os elementos no espectro.

Quando implementado em hardware esta aproximação reduz significativamente a complexidade, dado que todas as multiplicações consistem numa variável e uma constante, ao invés de duas variáveis como num aproximação bruta.

• Chien, R. T. (outubro 1964), «Cyclic Decoding Procedures for the Bose-Chaudhuri-Hocquenghem Codes», IEEE Transactions on Information Theory, ISSN 0018-9448, IT-10 (4): 357–363 
• Lin, S.; Costello, D. (2004), Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: Prentice-Hall 
• Gill, John, EE387 Notes #7, Handout #28 (PDF), Stanford University, pp. 42–45, consultado em 21 de abril de 2010