Procedimento de Chien: diferenças entre revisões

45 bytes removidos ,  02h00min de 30 de janeiro de 2016
m
ajuste(s), typos fixed: cujo o → cujo, raizes → raízes (3) utilizando AWB
m (Bot: A migrar 1 interwikis, agora providenciados por Wikidata em d:Q5097155)
m (ajuste(s), typos fixed: cujo o → cujo, raizes → raízes (3) utilizando AWB)
Na [[Álgebra abstrata|álgebra abstrata]], o '''procedimento de Chien''', cujo o nome advém de R. T. Chien, é um algoritmo rápido para determinar a [[Raiz (matemática)|raiz]] de um [[Polinómio|polinómio]] definido sobre um [[Corpo finito|corpo finito]]. O caso mais típico para a utilização do procedimento de Chien é no cálculo das raizesraí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(<math>q</math>)) cujas raizesraízes queremos determinar como:
 
:<math>\ \Lambda(x) = \lambda_0 + \lambda_1 x + \lambda_2 x^2 + \cdots + \lambda_t x^t </math>
 
Conceptualmente, podemos avaliar <math>\Lambda(\beta)</math> por cada não-zero <math>\beta</math> em GF(<math>q</math>). Aqueles que resultarem em 0 são raizesraízes do polinómio.
 
O procedimento de Chien é baseado em duas observações:
&\triangleq& \gamma_{0,i} &+& \gamma_{1,i} &+& \gamma_{2,i} &+& \cdots &+& \gamma_{t,i}
\end{array}
</math>
 
:<math>
 
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==