Procedimento de Chien

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

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[editar | editar código-fonte]

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

Conceptualmente, podemos avaliar por cada não-zero em GF(). 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 pode ser expresso como para alguns , onde é um elemento primitivo (sugerido do inglês, primitive element) de , é a potência do elemento primitivo . Assim as potências por cada cobrem o espectro inteiro (excluindo o elemento zero).
  • A seguinte relação existe:

Por outras palavras podemos definir cada como a soma de um conjunto de termos , dos quais o próximo conjunto de coeficiente pode ser derivado, e assim:

Desta maneira podemos começar em com , e iterar através de cada valor de até . Se em qualquer altura a soma resultante é zero, temos:

assim também, logo é 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]