Procedimento de Chien: diferenças entre revisões
← nova página: Na álgebra abstrata, o '''procedimento de Chien''', cujo o nome advém de R. T. Chien, é um algoritmo rápido para determinar a Raiz (mat... |
|||
Linha 80: | Linha 80: | ||
|doi=}} |
|doi=}} |
||
[[Categoria:Detecção e correção de erros]] |
|||
[[Category:Error detection and correction]] |
|||
[[Category:Finite fields]] |
Revisão das 18h40min de 16 de novembro de 2012
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
Denotando o polinómio (sobre o corpo finito GF()) cujas raizes queremos determinar como:
Conceptualmente, podemos avaliar por cada não-zero em GF(). Aqueles que resultarem em 0 são raizes 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. (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)