Búsqueda de perros

En álgebra abstracta , la búsqueda de Chien , llamada así por Robert Tienwen Chien , es un algoritmo rápido para determinar raíces de polinomios definidos sobre un cuerpo finito . La búsqueda de Chien se utiliza comúnmente para encontrar las raíces de polinomios localizadores de errores que se encuentran al decodificar códigos Reed-Solomon y códigos BCH .

Algoritmo

El problema es encontrar las raíces del polinomio Λ( x ) (sobre el cuerpo finito GF( q ) ): $${\displaystyle \Lambda (x)=\lambda _{0}+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{t}x^{t}}$$

Las raíces se pueden encontrar mediante la fuerza bruta: hay un número finito de x , por lo que el polinomio se puede evaluar para cada elemento x _i . Si el polinomio se evalúa como cero, entonces ese elemento es una raíz.

Para el caso trivial x  = 0 , solo es necesario probar el coeficiente λ ₀ para determinar si es cero. A continuación, la única preocupación será si x _i es distinto de cero .

Una evaluación sencilla del polinomio implica multiplicaciones generales O ( t ² ) y sumas O ( t ) . Un esquema más eficiente utilizaría el método de Horner para multiplicaciones generales O ( t ) y sumas O ( t ) . Ambos enfoques pueden evaluar los elementos del cuerpo finito en cualquier orden.

La búsqueda de Chien mejora lo anterior al seleccionar un orden específico para los elementos distintos de cero. En particular, el campo finito tiene un elemento generador (constante) α . Chien prueba los elementos en el orden del generador α ¹ , α ² , α ³ , .... . En consecuencia, la búsqueda de Chien solo necesita O ( t ) multiplicaciones por constantes y O ( t ) adiciones. Las multiplicaciones por constantes son menos complejas que las multiplicaciones generales.

La búsqueda de Chien se basa en dos observaciones:

• Cada valor distinto de cero puede expresarse como para algún , donde es un elemento primitivo de , es el número de potencia del elemento primitivo . Por lo tanto, las potencias para cubren todo el campo (excluyendo el elemento cero). ${\displaystyle \beta }$ ${\displaystyle \alpha ^{i_{\beta }}}$ ${\displaystyle i_{\beta }}$ ${\displaystyle \alpha }$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle i_{\beta }}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{i}}$ ${\displaystyle 0\leq i<(q-1)}$
• Existe la siguiente relación: $${\displaystyle {\begin{array}{lllllllllll}\Lambda (\alpha ^{i})&=&\lambda _{0}&+&\lambda _{1}(\alpha ^{i})&+&\lambda _{2}(\alpha ^{i})^{2}&+&\cdots &+&\lambda _{t}(\alpha ^{i})^{t}\\&\triangleq &\gamma _{0,i}&+&\gamma _{1,i}&+&\gamma _{2,i}&+&\cdots &+&\gamma _{t,i}\\\Lambda (\alpha ^{i+1})&=&\lambda _{0}&+&\lambda _{1}(\alpha ^{i+1})&+&\lambda _{2}(\alpha ^{i+1})^{2}&+&\cdots &+&\lambda _{t}(\alpha ^{i+1})^{t}\\&=&\lambda _{0}&+&\lambda _{1}(\alpha ^{i})\,\alpha &+&\lambda _{2}(\alpha ^{i})^{2}\,\alpha ^{2}&+&\cdots &+&\lambda _{t}(\alpha ^{i})^{t}\,\alpha ^{t}\\&=&\gamma _{0,i}&+&\gamma _{1,i}\,\alpha &+&\gamma _{2,i}\,\alpha ^{2}&+&\cdots &+&\gamma _{t,i}\,\alpha ^{t}\\&\triangleq &\gamma _{0,i+1}&+&\gamma _{1,i+1}&+&\gamma _{2,i+1}&+&\cdots &+&\gamma _{t,i+1}\end{array}}}$$

En otras palabras, podemos definir cada uno como la suma de un conjunto de términos , de los cuales se puede derivar el siguiente conjunto de coeficientes de la siguiente manera: ${\displaystyle \Lambda (\alpha ^{i})}$ ${\displaystyle \{\gamma _{j,i}\mid 0\leq j\leq t\}}$ $${\displaystyle \gamma _{j,i+1}=\gamma _{j,i}\,\alpha ^{j}}$$

De esta manera, podemos empezar con , e iterar a través de cada valor de hasta . Si en cualquier etapa la suma resultante es cero, es decir , entonces también lo es una raíz. De esta manera, verificamos cada elemento en el campo. ${\displaystyle i=0}$ ${\displaystyle \gamma _{j,0}=\lambda _{j}}$ ${\displaystyle i}$ ${\displaystyle (q-1)}$ $${\displaystyle \sum _{j=0}^{t}\gamma _{j,i}=0,}$$ ${\displaystyle \Lambda (\alpha ^{i})=0}$ ${\displaystyle \alpha ^{i}}$

Cuando se implementa en hardware, este enfoque reduce significativamente la complejidad, ya que todas las multiplicaciones constan de una variable y una constante, en lugar de dos variables como en el enfoque de fuerza bruta.

Referencias

• Chien, RT (octubre de 1964), "Procedimientos de decodificación cíclica para los códigos de Bose-Chaudhuri-Hocquenghem", IEEE Transactions on Information Theory , IT-10 (4): 357–363, doi :10.1109/TIT.1964.1053699, ISSN  0018-9448
• Lin, Shu; Costello, Daniel J. (2004), Codificación de control de errores: fundamentos y aplicaciones (segunda edición), Englewood Cliffs, NJ: Prentice-Hall, ISBN 978-0130426727
• Gill, John (nd), EE387 Notes #7, Handout #28 (PDF) , Stanford University, pp. 42–45, archivado desde el original (PDF) el 2014-06-30 , consultado el 21 de abril de 2010