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.

AlgoritmoEditar

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ênciasEditar

  • 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  Verifique data em: |data= (ajuda)
  • 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  Verifique data em: |ano=, |acessodata= (ajuda)