# Galois Field Fourier Transform

there are 2 interpretations for Reed - Solomon codes, as sending factors and also as BCH code (http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction ). On Wikipedia there is created that we can change from one definition to 2nd by utilizing Fourier change.

So as an example there is RS (7, 3) (size of codeword is 7, so codeword is maximally 7 - 1 = 6 level polynomial and also level 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)$.

Allow message polynomial be as an example $m(x) = \alpha x^2 + \alpha x + 1$.

So adhering to the definition that there is developed BCH - design 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 - organized 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 also the codeword developed with 2nd definition (sending factors):

$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 currently I attempted to examine equivalence of these 2 codeword production approaches. As it is created on Wikipedia: $c_{tp_i} = c_{nonsys}(\alpha^i)$ and also Galois Field Fourier Transform need to be made use of.

I attempted to calculate it for $0...\alpha^5$, $1...\alpha^6$, $\alpha^5...0$, $\alpha^6...0$ and also the outcome is constantly wrong.

So the inquiry is: when it is offered codeword developed with BCH - inscribing system after that just how to change it to equal codeword developed with sending factor system and also the other way around?

11
2022-06-07 14:31:57
Source Share
Answers: 2

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.

4
2022-06-25 09:08:21
Source

Presumably your $\alpha$ is a primitive component pleasing the formula $\alpha^3=\alpha+1$ (in contrast to a primitive component pleasing the formula $\alpha^3=\alpha^2+1$, which is the various other choice) - at the very least that selection permitted me to duplicate your outcomes for both the generator polynomial $g(x)$ along with the polynomial $c_{nonsys}(x)=m(x)g(x)$.

Nonetheless, there appears to be a blunder in your formula for the 2nd definition. With this sort of RS - codes, you do not review the message polynomial at absolutely no, just at the components of the multiplicative team. The Wikipedia write-up consents, so you need to compute $$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 amounts to (unless I slipped up) $$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 could not locate the relationship in between both encodings from the Wikipedia write-up in all. Are you certain that it was intended to go like that? What it claims (as well as additionally holds) is that the series of coefficients of the polynomial $c_{tp}(x)$ is the DFT of the series of the coefficients of the message polynomial $m(x)$. Consequently we need to have the ability to recoup the message as the inverted DFT of the coefficients of $c_{tp}(x)$. Allow is attempt!

$$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 resemble we, without a doubt, recouped the coefficients of $m(x)$. The coefficient of level $i$ term is obtained as $c_{tp}(\alpha^{7-i})$. Due to the fact that $c_{tp}(x)$ is a legitimate codeword, we understand beforehand that $c_{tp}(\alpha^j)=0$, for $j=1,2,3,4$ which is such as well, due to the fact that those values are the coefficients of $x^6, x^5, x^4, x^3$ specifically, and also the message polynomial is square.

The equivalence evidence in the Wikipedia write-up has to do with revealing that the resulting set of vectors (= the RS - code) coincides for both approaches of inscribing messages. It is not trying to claim anything concerning changing the codeword managed inscribing a message $m(x)$ inscribed in the spirit of the first definition to an additional codeword that would certainly represent the very same message $m(x)$, when inscribed with the 2nd method. I'm rather certain that is all that the argument in Wikipedia is trying to claim.

Mind you, there need to be a means of attaining the makeover that you were seeking. However I do not bear in mind now, just how it goes. It would certainly be based upon the reality that the polynomial reproduction that offered us the polynomial $c_{nonsys}(x)$ is essentially like a convolution. So when we take the DFT right into account that represents pointwise reproduction. Transforming this suggestion right into a valuable formula that we can examine takes even more time and also room than I can buy this presently, so I stop now in the meantime.

7
2022-06-08 01:44:49
Source