Procedimento de Chien

Predefinição:Sem notas 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:

$\mathrm{\Lambda }(x)={\lambda }_0+{\lambda }_{1}x+{\lambda }_2{x}^2+\cdots +{\lambda }_t{x}^t$

Conceptualmente, podemos avaliar $\mathrm{\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{G}\mathrm{F}(q)$, $i_{\beta }$ é a potência do elemento primitivo $\alpha$. Assim as potências ${\alpha }^i$ por cada $0\le i<(q-1)$ cobrem o espectro inteiro (excluindo o elemento zero).
• A seguinte relação existe:

$\begin{array}{ccccccccccc}\mathrm{\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}{ccccccccccc}\mathrm{\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 $\mathrm{\Lambda }({\alpha }^i)$ como a soma de um conjunto de termos $\{{\gamma }_{j,i}|0\le j\le 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 $\mathrm{\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

• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation