Galois Campo De La Transformada De Fourier De

Question

hay dos definiciones de Reed-Solomon códigos, como la transmisión de puntos y como código BCH ( http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction ). En la Wikipedia no está escrito que podemos transformar a partir de una definición a la segunda mediante el uso de la transformada de Fourier.

Así, por ejemplo no es RS(7, 3) (longitud de palabra es de 7, por lo que la palabra es máximo 7 - 1 = 6 grado del polinomio y el grado de mensaje polinomio es máximamente 3 - 1 = 2) código con polinomio generador $g(x)=x^4 + \alpha^3 x^3 + x^2 + \alpha x + \alpha^3 = (x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)$.

Dejar mensaje polinomio ser, por ejemplo,$m(x) = \alpha x^2 + \alpha x + 1$.

Así pues, siguiendo la definición que se ha creado BCH-estilo de la palabra (a partir de la definición):

Sistemática de la palabra es $c_{sys}(x)=x^4m(x) + (x^4m(x)) \bmod g(x)=\alpha x^6 + \alpha x^5 + x^4 + \alpha^5 x^3 + x^2 + \alpha^2 x + \alpha^5$.

No sistemático de la palabra es $c_{nonsys}(x)=m(x)g(x)= \alpha x^6 + \alpha^2 x^5 + \alpha^6 x^4 + \alpha^6 x^3 + \alpha^3 x^2 + \alpha^2 x + \alpha^3$.

Y la palabra creada con la segunda definición (transmisión de puntos):

$c_{tp}(x) = m(\alpha^5)x^6 + m(\alpha^4)x^5 + m(\alpha^3)x^4 + m(\alpha^2)x^3 + m(\alpha)x^2 + m(1)x + m(0) $ $= \alpha x^6 + \alpha x^5 + \alpha^4 x^4 + \alpha^6 x^3 + \alpha^4 x^2 + x + 1$.

Así que ahora he intentado comprobar la equivalencia de estas dos palabra métodos de creación. Como está escrito en la Wikipedia: $c_{tp_i} = c_{nonsys}(\alpha^i)$ y Galois Campo de la transformada de Fourier debe ser utilizado.

Traté de cómputo para $0...\alpha^5$, $1...\alpha^6$, $\alpha^5...0$, $\alpha^6...0$ y el resultado siempre es incorrecto.

Así que la pregunta es: cuando se da la palabra creada con BCH-esquema de codificación, a continuación, cómo transformarla en equivalente de la palabra creada con la transmisión sistema de puntos y viceversa?

Answer 1

Presumiblemente su $\alpha$ es un primitivo elemento que satisface la ecuación de $\alpha^3=\alpha+1$ (frente a un primitivo elemento que satisface la ecuación de $\alpha^3=\alpha^2+1$, que es la otra alternativa) - al menos esa opción me permitió reproducir sus resultados tanto para el polinomio generador $g(x)$ así como el polinomio $c_{nonsys}(x)=m(x)g(x)$.

Sin embargo, no parece ser un error en la fórmula para la segunda definición. Con este tipo de RS-códigos, no evaluar el mensaje polinomio cero, sólo en los elementos del grupo multiplicativo. El artículo de la Wikipedia está de acuerdo, así que usted debe calcular $$ c_{tp}(x)=m(\alpha^6)x^6+m(\alpha^5)x^5+m(\alpha^4)x^4+m(\alpha^3)x^3+m(\alpha^2)x^2+m(\alpha)x+m(1), $$ que es igual a (a menos que cometí un error) $$ c_{tp}(x)=\alpha^6x^6+\alpha x^5+\alpha x^4+\alpha^4 x^3+\alpha^6 x^2+\alpha^4x+1. $$

Pero yo no podía encontrar la relación entre las dos codificaciones de un artículo de Wikipedia. ¿Estás seguro de que iba a ir así? Lo que dice (y tiene) es que la secuencia de coeficientes del polinomio $c_{tp}(x)$ es la DFT de la secuencia de los coeficientes del mensaje polinomio $m(x)$. Por lo tanto debemos ser capaces de recuperar el mensaje como la DFT inversa de los coeficientes de $c_{tp}(x)$. Vamos a probar!

$$ c_{tp}(\alpha^{7-0})=c_{tp}(1)=\alpha^6+\alpha+\alpha+\alpha^4+\alpha^6+\alpha^4+1=1, $$ $$ c_{tp}(\alpha^{7-1})=c_{tp}(\alpha^6)=1+\alpha^3+\alpha^4+\alpha+\alpha^4+\alpha^3+1=\alpha, $$ $$ c_{tp}(\alpha^{7-2})=c_{tp}(\alpha^5)=\alpha+\alpha^5+1+\alpha^5+\alpha^2+\alpha^2+1=\alpha. $$ No parece que, en efecto, se recuperaron los coeficientes de $m(x)$. El coeficiente de grado $i$ plazo es recibido como $c_{tp}(\alpha^{7-i})$. Debido a $c_{tp}(x)$ es válida la palabra, sabemos de antemano que $c_{tp}(\alpha^j)=0$ $j=1,2,3,4$ que es tal como bueno, debido a que los valores de los coeficientes de $x^6, x^5, x^4, x^3$ respectivamente, y el mensaje polinómicas es de segundo grado.

La equivalencia de la prueba en el artículo de la Wikipedia se trata de mostrar que el conjunto resultante de los vectores (= RS-código) es el mismo para ambos métodos de codificación de mensajes. No es tratando de decir algo acerca de la transformación de la palabra conseguido mediante la codificación de un mensaje de $m(x)$ codificados en el espíritu de la primera definición a otra palabra que se corresponden con el mismo mensaje de $m(x)$, cuando se codifica con el segundo método. Estoy bastante seguro de que es todo lo que el argumento en Wikipedia está tratando de decir.

Eso sí, no debe ser una manera de lograr la transformación que usted estaba buscando. Por desgracia no recuerdo ahora mismo, cómo va. Se basaría en el hecho de que la multiplicación de polinomio que nos dio el polinomio $c_{nonsys}(x)$ es más o menos como una convolución. Así que cuando tomamos la DFT en cuenta que corresponde a pointwise la multiplicación. Convertir esta idea en una fórmula útil que podríamos prueba dura más tiempo y espacio que puedo invertir en este momento, así que me detengo en este punto por ahora.

Answer 2

Con $m(x)$ el mensaje y $g(x) = (x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)$ el polinomio generador. Entonces $$ c_{\text{sys}}(x) = x^4 m(x) + (x^4 m(x) \bmod g(x)) = d(x)g(x) $$ es un múltiplo de a $g(x)$. Por otro lado, $c_{\text{nonsys}}(x) = m(x)g(x)$ es otra codificación de $m(x)$.

Para cualquier polinomio $f(x)$ grado $6$ o menos, definir $F_i = f(\alpha^{-i})$, $0 \leq i \leq 6,$ y $F(z) = \sum_{i=0}^6 F_i z^i$ como la transformada de Fourier de $f(x)$. A continuación, $f_j = F(\alpha^j) = \sum_{j=0}^6 F_j\alpha^j$ $f(x)$ se llama el inversa de la transformada de Fourier de $F(z)$. (El factor de $(1/N)$ que se muestra en Las transformadas de Fourier pasa a tener un valor de $1$ aquí). Entonces, ¿cuál es la transformada de Fourier la transformación de $c_{\text{nonsys}}(x)$? Tenemos $$C_{\text{nonsys}, i} = c_{\text{nonsys}}(\alpha^{-i}) = \begin{cases}0, & i = 3, 4, 5, 6,\\ m(\alpha^{-i})g(\alpha^{-i}), & i = 0, 1, 2\end{casos}$$ desde $(\alpha^{-3}, \alpha^{-4},\alpha^{-5},\alpha^{-6}) = (\alpha^{4},\alpha^{3},\alpha^{3},\alpha^{1})$$c_{\text{nonsys}}(x)$, siendo un múltiplo de $g(x)$ $\alpha, \alpha^2, \alpha^3, \alpha^4$ como raíces. Por lo tanto, hemos $$\begin{align*} C_{\text{nonsys}}(z) &= \sum_{i=0}^6 C_{\text{nonsys}, i}z^i\\ &= C_{\text{nonsys}, 0} + C_{\text{nonsys}, i}z + C_{\text{nonsys}, i}z^2\\ &= [m(1)g(1)] + [m(\alpha^{-1})g(\alpha^{-1})]z + [m(\alpha^{-2})g(\alpha^{-2})]z^2 \end{align*} $$ como el mensaje de "polinomio" de grado $2$ (o menos) que obtiene codificado en $c_{\text{nonsys}}(x)$ como la transmisión "puntos" de la palabra.