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]

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