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()) 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
- 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