# Galois Field Fourier Transform

there are two definitions for Reed-Solomon codes, as transmitting points and as BCH code ( http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction ). On Wikipedia there is written that we can transform from one definition to second by using Fourier transform.

So for example there is RS(7, 3) (length of codeword is 7, so codeword is maximally 7 - 1 = 6 degree polynomial and degree of message polynomial is maximally 3 - 1 = 2) code with generator polynomial $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)$.

Let message polynomial be for example $m(x) = \alpha x^2 + \alpha x + 1$.

So following the definition that there is created BCH-style codeword (from definition):

Systematic codeword is $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$.

Non-systematic codeword is $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$.

And the codeword created with second definition (transmitting points):

$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$.

So now I tried to check equivalence of these two codeword creation methods. As it is written on Wikipedia: $c_{tp_i} = c_{nonsys}(\alpha^i)$ and Galois Field Fourier Transform should be used.

I tried to compute it for $0...\alpha^5$, $1...\alpha^6$, $\alpha^5...0$, $\alpha^6...0$ and the result is always incorrect.

So the question is: when it is given codeword created with BCH-encoding scheme then how to transform it to equivalent codeword created with transmitting point scheme and vice versa?

-

Presumably your $\alpha$ is a primitive element satisfying the equation $\alpha^3=\alpha+1$ (as opposed to a primitive element satisfying the equation $\alpha^3=\alpha^2+1$, which is the other alternative) - at least that choice allowed me to reproduce your results for both the generator polynomial $g(x)$ as well as the polynomial $c_{nonsys}(x)=m(x)g(x)$.

However, there seems to be a mistake in your formula for the second definition. With this type of RS-codes, you do not evaluate the message polynomial at zero, only at the elements of the multiplicative group. The Wikipedia article concurs, so you should calculate $$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),$$ which is equal to (unless I made a mistake) $$c_{tp}(x)=\alpha^6x^6+\alpha x^5+\alpha x^4+\alpha^4 x^3+\alpha^6 x^2+\alpha^4x+1.$$

But I couldn't find the relation between the two encodings from the Wikipedia article at all. Are you sure that it was supposed to go like that? What it says (and also holds) is that the sequence of coefficients of the polynomial $c_{tp}(x)$ is the DFT of the sequence of the coefficients of the message polynomial $m(x)$. Therefore we should be able to recover the message as the inverse DFT of the coefficients of $c_{tp}(x)$. Let's try!

$$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.$$ It does look like we, indeed, recovered the coefficients of $m(x)$. The coefficient of degree $i$ term is gotten as $c_{tp}(\alpha^{7-i})$. Because $c_{tp}(x)$ is a valid codeword, we know in advance that $c_{tp}(\alpha^j)=0$, for $j=1,2,3,4$ which is such as well, because those values are the coefficients of $x^6, x^5, x^4, x^3$ respectively, and the message polynomial is quadratic.

The equivalence proof in the Wikipedia article is about showing that the resulting set of vectors (= the RS-code) is the same for both methods of encoding messages. It is not attempting to say anything about transforming the codeword gotten by encoding a message $m(x)$ encoded in the spirit of the first definition to another codeword that would correspond to the same message $m(x)$, when encoded with the second method. I'm fairly sure that is all that the argument in Wikipedia is attempting to say.

Mind you, there should be a way of achieving the transformation that you were looking for. Unfortunately I don't remember right now, how it goes. It would be based on the fact that the polynomial multiplication that gave us the polynomial $c_{nonsys}(x)$ is more or less like a convolution. So when we take the DFT into account that corresponds to pointwise multiplication. Converting this idea into a useful formula that we could test takes more time and space than I can invest on this at the moment, so I stop at this point for now.

-

With $m(x)$ the message and $g(x) = (x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)$ the generator polynomial. Then $$c_{\text{sys}}(x) = x^4m(x) + (x^4 m(x) \bmod g(x)) = d(x)g(x)$$ is a multiple of $g(x)$. On the other hand, $c_{\text{nonsys}}(x) = m(x)g(x)$ is another encoding of $m(x)$.

For any polynomial $f(x)$ of degree $6$ or less, define $F_i = f(\alpha^{-i})$, $0 \leq i \leq 6,$ and $F(z) = \sum_{i=0}^6 F_i z^i$ as the Fourier transform of $f(x)$. Then, $f_j = F(\alpha^j) = \sum_{j=0}^6 F_j\alpha^j$ and $f(x)$ is called the inverse Fourier transform of $F(z)$. (The factor $(1/N)$ that shows up in Fourier transforms happens to have value $1$ here). So what is the Fourier transform of $c_{\text{nonsys}}(x)$? We have $$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{cases}$$ since $(\alpha^{-3}, \alpha^{-4},\alpha^{-5},\alpha^{-6}) = (\alpha^{4},\alpha^{3},\alpha^{3},\alpha^{1})$ and $c_{\text{nonsys}}(x)$, being a multiple of $g(x)$ has $\alpha, \alpha^2, \alpha^3, \alpha^4$ as roots. Thus, we have \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*} as the "message polynomial" of degree $2$ (or less) which gets encoded into $c_{\text{nonsys}}(x)$ as the "transmit points" codeword.

-