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.

Algoritmo

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

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

Conceptualmente, podemos avaliar $\Lambda (\beta )$ por cada não-zero $\beta$ em GF($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 $\beta$ pode ser expresso como $\alpha ^{i_{\beta }}$ para alguns $i_{\beta }$, onde $\alpha$ é um elemento primitivo (sugerido do inglês, primitive element) de $\mathrm {GF} (q)$, $i_{\beta }$ é a potência do elemento primitivo $\alpha$. Assim as potências $\alpha ^{i}$ por cada $0\leq i<(q-1)$ cobrem o espectro inteiro (excluindo o elemento zero).

• A seguinte relação existe:

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

${\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 $\Lambda (\alpha ^{i})$ como a soma de um conjunto de termos $\{\gamma _{j,i}|0\leq j\leq t\}$, dos quais o próximo conjunto de coeficiente pode ser derivado, e assim:

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

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

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

assim $\Lambda (\alpha ^{i})=0$ também, logo $\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.

Referências

• Chien, R. T. (October 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 (unknown), EE387 Notes #7, Handout #28 (PDF), Stanford University, pp. 42–45, consultado em April 21, 2010