Generador de polinomios Reed Solomon

Question

Estoy desarrollando un programa de ejemplo para generar un código de barras 2D. Y estoy usando el código de corrección de errores de Reed Solomon. Por ir a través de este artículo Estoy desarrollando el programa. Pero no pude entender cómo generó el polinomio generador. Alguien puede explicarme como generó el polinomio generador. Por favor, guíenme para completar este paso de corrección.

Se agradece la ayuda,

Gracias

Sunny

Answer 1

Permítanme mostrar un ejemplo de juguete de un caso, donde podemos utilizar $\alpha=2$ . En el campo finito más general no podemos pensar en $\alpha$ como si tuviera un "valor" numérico. Utilizo el campo finito $GF(11)$ que es isomorfo al anillo de clases de residuos de los enteros módulo 11. Supongo que estás al menos algo familiarizado con la aritmética modular. De esta manera podemos echar un vistazo al uso del polinomio generador en la codificación del mensaje sin tener que preocuparnos también de la construcción del campo finito. Además, la respuesta tendrá un tamaño "razonable" :-) $$ GF(11)=\{0,1,2,3,4,5,6,7,8,9,A=-1\}, $$ donde $A$ representa la clase de residuos de $10\equiv-1\pmod{11}$ . Los códigos Reed-Solomon utilizan el hecho de que el grupo multiplicativo de elementos no nulos de este (y cualquier otro) campo finito es cíclico, es decir, está formado por potencias de un elemento cuidadosamente seleccionado $\alpha$ . La prueba y el error demuestran que podemos seleccionar $\alpha=2$ porque $\alpha^0=1$ , $\alpha^1=2$ , $\alpha^2=4$ , $\alpha^3=8$ , $\alpha^4=16= 5$ , $\alpha^5=\alpha\cdot \alpha^4=2\cdot 5=10=-1$ , $\alpha^6=2\cdot A=20= 9$ , $\alpha^7=2\cdot9=18= 7$ , $\alpha^8=2\cdot7=14=3$ y $\alpha^9=2\cdot3=6$ . Nótese que i) simplemente igualo dos números cualesquiera que sean congruentes entre sí módulo 11, porque entonces los dos números representan el mismo elemento del campo, ii) no obtendré ningún elemento nuevo al continuar, porque $\alpha^{10}=2\cdot6=12=1=\alpha^0$ Así que los poderes de $\alpha$ repetir a partir de la décima potencia. Algo similar ocurre con todos los campos finitos.

En este ejemplo de juguete describo el procedimiento de codificación utilizando un código RS con alfabeto $GF(11)$ que tiene $r=4$ símbolos de control (es decir, el código tendrá una distancia mínima $r+1=5$ y poder corregir hasta $t=2$ errores, porque $2t+1=5$ . Este tipo de código RS puede transportar un mensaje compuesto por hasta seis ( $6=11-1-r$ ) símbolos $m_0,m_1,m_2,m_3,m_4,m_5$ que son todos los elementos del campo $GF(11)$ . Podríamos acordar utilizar mensajes más cortos, pero esta vez voy con el máximo. El proceso de codificación expande este mensaje en una secuencia más larga $c_0,c_1,c_2,\ldots,c_9$ de diez símbolos del campo $GF(11)$ . Para que el álgebra sea más fácil de describir, consideramos estas secuencias como polinomios. Así pues, dejemos que $x$ sea una incógnita, y escriba $$m(x)= m_0+m_1x+m_2x^2+m_3x^3+m_4x^4+m_5x^5$$ y $$c(x)= c_0+c_1x+c_2x^2+c_3x^3+\cdots+c_9x^9.$$ Para que la corrección de errores funcione como se describe, debemos asegurarnos de que el polinomio $c(x)$ representa una palabra de código válida, por lo que tiene que ser un múltiplo del polinomio generador de grado $r=4$ $$ g(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)=(x-2)(x-4)(x-8)(x-5). $$ Como ejercicio se invita a comprobar que tras expandir este producto y reducir todos los coeficientes módulo 11 se obtiene $$ g(x)=x^4+3x^3+5x^2+8x+1. $$ Hay dos formas habituales de convertir el mensaje polinómico $m(x)$ a una palabra clave $c(x)$ que siempre es divisible por $g(x)$ . La forma más sencilla (algebraicamente) es declarar $$ c(x)=g(x)m(x). $$ Esto es lo que se conoce (véase, por ejemplo, la página de Wikipedia) como codificación no sistemática, por lo que, por ejemplo, la citada página de Wikipedia y Respuesta de Dilip denota este polinomio $c_{nonsys}(x)$ . Por ejemplo, si la secuencia de mensajes que se quiere codificar es $(m_0,m_1,m_2,m_3,m_4,m_5)=(3,0,0,0,0,1)$ el polinomio del mensaje es $m(x)=3+x^5$ y $$ c_{nonsys}(x)=g(x)m(x)=g(x)(x^5+3)=3 + 2x + 4x^2 + 9x^3 + 3x^4 + x^5 + 8x^6 + 5x^7 + 3x^8 + x^9, $$ por lo que el mensaje codificado es la secuencia $(3,2,4,9,3,1,8,5,3,9)$ .

Por razones prácticas, los ingenieros suelen preferir utilizar la llamada codificación sistemática. La respuesta de Dilip (enlazada arriba) te da la siguiente receta: Calcular el polinomio $x^rm(x)=x^4(x^5+3)=x^9+3x^4$ y luego calcular el resto, al dividir este polinomio con el polinomio generador $g(x)$ . La respuesta es $r(x)=4x+4x^2+x^3$ . Así, el polinomio $$ c_{sys}(x)=x^4 m(x)-r(x)=x^9+3x^4-x^3-4x^2-4x=7x+7x^2+Ax^3+3x^4+x^9 $$ también es divisible por $g(x)$ . Esta vez la secuencia codificada es la siguiente $(0,7,7,A,3,0,0,0,0,1)$ . La razón por la que se llama sistemática es que se ve la secuencia de mensajes de carga útil $(3,0,0,0,0,1)$ al final.

\=======================

Añadido: Construcción de campos finitos de característica dos.

Aquí necesitamos más álgebra. El campo $GF(256)$ es de característica dos. En otras palabras, cada elemento $\beta \in GF(256)$ satisface la relación $\beta+\beta=0$ . Para que te hagas una idea te describo primero cómo se consigue un campo más pequeño $GF(8)$ . Esto es sólo para ahorrar espacio. La idea es que queremos listar los elementos de este campo como potencias de un elemento especial $\alpha$ de la misma manera que utilizamos las potencias de dos en el ejemplo anterior. Un campo siempre tendrá elementos especiales $0,1$ Así que para llegar a ocho elementos queremos que el campo tenga el siguiente aspecto $$ GF(8)=\{0,1,\alpha,\alpha^2,\alpha^3,\alpha^4,\alpha^5,\alpha^6\}. $$ En el ejemplo anterior de $GF(11)$ los poderes de $\alpha$ comenzó a repetirse después de la décima potencia ( $2^{10}\equiv 1\pmod{11}$ ). Aquí queremos que las potencias comiencen a repetirse a partir de la séptima ( $7=8-1$ , $10=11-1$ ), por lo que queremos $\alpha^7=1$ . Además, queremos poder sumar elementos del campo, como $\alpha^3+\alpha^5$ o $1+\alpha^4$ debe ser uno de los elementos. La forma de conseguirlo es declarar que $\alpha$ es una raíz de cierta ecuación polinómica cuidadosamente elegida. Esta vez elegimos la ecuación $$\alpha^3+\alpha+1=0.$$ O SEA, QUE.., $\alpha$ es una raíz del polinomio $p(x)=x^3+x+1$ .

¿Cómo ayuda eso? La idea es que entonces podemos calcular con potencias de $\alpha$ y utilizar siempre esa ecuación $p(\alpha)=0$ para reducir a potencias inferiores de $\alpha$ . Esto es muy parecido a lo que ocurre cuando se multiplican números complejos entre sí, se utiliza la ecuación $i^2=-1$ Por ejemplo $(2+i)(3+i)=6+2i+3i+i^2=6+5i+i^2=6+5i-1=5+5i$ . Sólo que esta vez la ecuación sólo empieza a ayudar, cuando llegamos a la tercera potencia. Aquí $$ \alpha^3=\alpha^3+0=\alpha^3+p(\alpha)=\alpha^3+\alpha^3+\alpha+1=1+\alpha, $$ porque $\alpha^3+\alpha^3=0$ . Veamos qué sucede, cuando reducimos los poderes de $\alpha$ utilizando esta relación. En la última columna de la siguiente tabla siempre la versión totalmente reducida de esa potencia de $\alpha$ . $$ \eqalign{ \alpha^0&=&&=1,\\ \alpha^1&=&&=\alpha,\\ \alpha^2&=&&=\alpha^2,\\ \alpha^3&=&&=1+\alpha,\\ \alpha^4&=&\alpha\cdot\alpha^3=\alpha(1+\alpha)&=\alpha+\alpha^2,\\ \alpha^5&=&\alpha\cdot\alpha^4=\alpha(\alpha+\alpha^2)=\alpha^2+\alpha^3=\alpha^2+(1+\alpha)&=1+\alpha+\alpha^2,\\ \alpha^6&=&\alpha\cdot\alpha^5=\alpha(1+\alpha+\alpha^2)=\alpha+\alpha^2+\alpha^3= \alpha+\alpha^2+(1+\alpha)&=1+\alpha^2,\\ \alpha^7&=&\alpha\cdot\alpha^6=\alpha(1+\alpha^2)=\alpha+\alpha^3=\alpha+(1+\alpha)&=1. }$$ Aquí la última fila era en cierto modo superflua, pero quería mostrarles que esta elección del polinomio $p(x)$ lleva a la conclusión deseada de que los poderes de $\alpha$ comienzan a repetirse después de la séptima. Obsérvese cómo una nueva línea depende siempre de la anterior, y cómo la relación $\alpha^3=\alpha+1$ se aplica tantas veces como sea necesario para eliminar todos los términos cúbicos y superiores.

Ahora deberías notar que los resultados finales en la última columna contienen todos los polinomios cuadráticos de la forma $b_0+b_1\alpha+b_2\alpha^2$ donde todos los coeficientes $b_i,i=0,1,2$ son bits, es decir, elementos del conjunto $\{0,1\}$ . Que esto haya funcionado así es una especie de milagro, pero sucedió, porque fuimos inteligentes al elegir el polinomio $p(x)$ . Observe que $p(x)$ es de grado tres, y $8=2^3$ . Obsérvese además que podemos elegir representar los elementos de $GF(8)$ de dos maneras: como un poder de $\alpha$ o como un polinomio cuadrático de $\alpha$ . ¿Qué utilizamos? Depende de lo que queramos hacer. Si queremos añadir dos elementos del campo, pasamos primero a la forma polinómica cuadrática, así por ejemplo $$ \alpha^3+\alpha^5=(1+\alpha)+(1+\alpha+\alpha^2)=(1+1)+(\alpha+\alpha)+\alpha^2=\alpha^2. $$ Por otro lado, si queremos multiplicar dos elementos del campo, simplemente utilizamos el hecho de que las potencias comienzan a repetirse después de la séptima, por lo que $\alpha^6\cdot\alpha^4=\alpha^{10}= \alpha^{7}\cdot\alpha^3=1\cdot\alpha^3=\alpha^3$ . O, si los elementos están dados en el forma polinómica cuadrática, entonces leemos la tabla de derecha a izquierda, por ejemplo $$ (1+\alpha)(1+\alpha+\alpha^2)=\alpha^3\cdot\alpha^5=\alpha^8=\alpha\cdot\alpha^7=\alpha. $$ Observa que la suma de dos polinomios cuadráticos $$ (a_0+a_1\alpha+a_2\alpha^2)+(b_0+b_1\alpha+b_2\alpha^2)=(c_0+c_1\alpha+c_2\alpha^2) $$ asciende a (debido a la $\beta+\beta=0$ regla) XOR a nivel de bits de las cadenas de bits, o $c_0c_1c_2=(a_0a_1a_2)$ ^ $(b_0b_1b_2)$ Si recuerdo la anotación C correcta.

Por estas razones tengo a mano dos tablas de consulta, cuando implemento un campo finito de característica dos en un programa. Una para convertir las potencias $\alpha^i$ a polinomios de bajo grado, y otra para ir a la inversa.

Ok, así que eso fue $GF(8)$ pero usted quiere $GF(256)$ , donde $256=2^8$ . Esta vez el campo debería tener el siguiente aspecto $$ GF(256)=\{0,1,\alpha,\alpha^2,\alpha^3,\ldots,\alpha^{254}\}. $$ Ahora los poderes de $\alpha$ empezar a repetir a partir del $255^{th}$ Así que $\alpha^{255}=1$ . En lugar de polinomios cuadráticos, ahora acabamos utilizando la representación de la forma $$ b_0+b_1\alpha+b_2\alpha^2+\cdots+b_7\alpha^7 $$ en términos de $8$ bits $b_0,b_1,\ldots,b_7$ . En otras palabras, un solo byte representará un elemento de este campo en la forma "aditiva". ¿Cómo construimos la tabla de conversión? Para ello necesitamos un polinomio adecuado $p(x)$ . Esta vez $p(x)$ debe ser de grado 8. La opción más común es $$ p(x)=x^8+x^4+x^3+x^2+1. $$ La página a la que has enlazado parece que utiliza esto. La regla de sustitución que obtenemos de esto es $\alpha^8=\alpha^4+\alpha^3+\alpha^2+1$ . Puedes utilizar esta relación para deshacerte de todas las octavas potencias (¡y superiores!) de $\alpha$ . Esta vez la tabla tendría 255 filas, así que espero que entiendas, por qué no lo voy a reproducir aquí. Tu enlace parece tener esa tabla.

Para ver una lista de otros polinomios posibles, consulte este enlace . Allí también se ofrecen otros enlaces. Los enlaces de tus otras preguntas llevan a un código C que espero sea útil.

Answer 2

Tomando un caso especial de resultados más generales, el polinomio generador de un cíclico $(n, n-2t)$ Código Reed-Solomon sobre GF $(q)$ el campo finito de $q$ elementos, es de la forma $$g(x) = g_0 + g_1x + \cdots + g_{2t}x^{2t} = (x-\alpha)(x - \alpha^2)\cdots (x-\alpha^{2t})$$ donde $n$ es el número de símbolos de una palabra de código, $t$ es el número de errores que se pueden corregir, y $\alpha$ es una primitiva $n$ -raíz de la unidad en el campo. En el caso especial de OP Sunny, $q = 2^8 = 256$ , $n = 255$ y $\alpha$ es un elemento primitivo del campo. Los elementos de GF $(256)$ puede almacenarse como $8$ -bytes de bits, y la adición en el campo es la operación OR Exclusivo bit a bit que se suele incluir como una instrucción de máquina en la mayoría de los procesadores. Además, podemos sustituir los signos menos de la expresión anterior por signos más, ya que la suma y la resta son la misma operación en cualquier GF $(2^n)$ .

La pregunta de OP Sunny parece ser: ¿cómo puedo calcular los coeficientes $g_i, 0 \leq i \leq 2t$ ? La respuesta obvia es, por supuesto, multiplicar los factores dados juntos (que es lo que el artículo al que se refiere que se refiere), pero como parece que no está seguro de cómo hacer esto, aquí hay un procedimiento iterativo para ello.

Supongamos que los coeficientes deben ser almacenados en un $(2t+1)$ -arreglo de bytes g con g[i] almacenar $g_i$ con g[0] inicializado a $1$ y todos los demás g[i] a $0$ . Los elementos $\alpha, \alpha^2,\cdots, \alpha^{2t}$ se almacenan en un $2t$ -byte matriz alpha con alpha[i] almacenar $\alpha^i$ . Supongamos que tenemos un programa mult(x,y) que toma dos bytes $x$ y $y$ representando elementos de GF $(256)$ como entrada y devuelve el byte del producto de $x$ y $y$ en GF $(256)$ . Entonces, los coeficientes $g_i$ se obtienen en g mediante el siguiente cálculo:

for i = 1 step 1 until 2t do
     begin
     for j = 2t step -1 until 1 do
           begin
           g[j] = mult(g[j], alpha[i]) XOR g[j-1]
           end
     g[0] = mult(g[0]), alpha[i])
     end

Esto parece que se está saliendo un poco del tema para math.SE pero sospecho que la gente en el StackOverflow.SE etc no están muy familiarizados con aritmética de campos finitos y similares.