Procedimento de Chien

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na álgebra abstrata, o procedimento de Chien, cujo o 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 raizes de polinómios error-locator encontrados na descodificação do código de Reed-Solomon e código de BCH.


Algoritmo[editar | editar código-fonte]

Denotando o polinómio (sobre o corpo finito GF(q)) cujas raizes 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 raizes 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[editar | editar código-fonte]