How to decode encoded, and corrupted in transmission message in Galois Field $2^5$ with one error?

149 Views Asked by At

We are given $GF(2^5, x^5+x^2+1 )$. We had some $ X_1, ..., X_5 $ message items from our $ GF(32) $ which we do not know and need to find. Thay were encoded via service blocks $ Y_1...Y_7 $ with next rule:

$$\large(\mathfrak{x}+\mathfrak{e})(\mathfrak{x}+\mathfrak{a})\sum_{i=1}^5X_i\;\mathfrak{x}^{i-1}\equiv\sum_{\ell=1}^7Y_\ell\;\mathfrak{x}^{\ell-1}$$

and we got next information out of some chain of encoder + transmition:

$$\begin{align*}\tilde{Y}_1&=(0,0,1,1,0) & \tilde{Y}_5&=(1,0,1,0,0)\\ \tilde{Y}_2&=(1,0,1,0,0)& \tilde{Y}_6&=(1,0,1,0,0)\\ \tilde{Y}_3&=(1,1,0,0,0)& \tilde{Y}_7&=(0,0,1,1,0)\\ \tilde{Y}_4&=(1,1,0,1,1)\\ \end{align*}$$

We are given that no more than 1 blocks we are given are incorrect.

How to get $ X_1 ... X_5 $?

reading wiki example on BCH codes I do not quite get steps I shall perform in my case... and even after getting $ Y_1...Y_7 $ how to get original $ X_1...X_5 $ ?

1

There are 1 best solutions below

3
On BEST ANSWER

For any valid sequence $Y_1,\ldots,Y_7$ the two equations $$ \sum_{i=1}^7Y_i=0 $$ and $$ \sum_{i=1}^7a^{i-1}Y_i=0 $$ should hold. This is seen as follows. These sums compute the values of the encoded polynomial $$Y(x)=Y_1+Y_2x+\cdots+Y_7x^6$$ at the points $x=1$ and $x=a$ respectively. They are both zeros of $Y(x)$, because the factors $x-1=x+1$ and $x-a=x+a$ appear in the defining equation $$ Y(x)=(x+1)(x+a)M(x). $$ Here $M(x)=\sum_{i=1}^5X_ix^{i-1}$ is the message polynomial. We see that these equations do not hold for the received sequence $\tilde{Y}_i, i=1,\ldots,7$, because $S(1)=\sum_{i=1}^7\tilde{Y}_i=(1,0,1,1,1)$ is not zero. Therefore at least one of the symbols $\tilde{Y}_i,i=1,\ldots,7$ is in error. Assume that only a single error happened, so there exists an index $i_0$ such that $\tilde{Y}_{i_0}=Y_{i_0}+E$, where $E\neq0$, and $\tilde{Y}_i=Y_i$ for all $i\neq i_0$. Compute also $$ S(a)=\sum_{i=1}^7a^{i-1}\tilde{Y}_i. $$ I cannot do this for you, because you didn't tell me whether you use little-endian or big-endian notation. IOW I don't know, whether for example your $\tilde{Y}_2=(1,0,1,0,0)$ is equal to $a^0+a^2$ or $a^4+a^2$.

Once you have $S(1)$ and $S(a)$, then the rest is straightforward. Because these checksums are linear combinations of the $Y$s, and they vanish whenever we have a valid codeword, we have that $$ S(1)=\sum_{i=1}^7\tilde{Y}_i=E+\sum_{i=1}^7Y_i=E+0=E, $$ and $$ S(a)=\sum_{i=1}^7a^{i-1}\tilde{Y}_i=a^{i_0-1}E+\sum_{i=1}^7a^{i-1}Y_i=a^{i_0-1}E. $$ We want determine $i_0$, because that tells us which symbol $\tilde{Y}_i$ is corrupt. And we want to solve $E$, because that is the 'error amount'. From the preceding equations you can compute $$ a^{i_0-1}=\frac{a^{i_0-1}E}{E}=\frac{S(a)}{S(1)}. $$ Because you know both $S(1)$ and $S(a)$, this is easy to calculate. The answer should be one of the elements $1,a,a^2,\ldots,a^6$. Just compute these elements of $GF(32)$ and look for match. If you find one, then you know $i_0-1$, and hence the location of the errorneous coefficient. If there is no match, then more than one error has occured.

Of course, the error value $E$ is then equal to $S(1)$. So you simply add $E=S(1)$ to the coefficient $\tilde{Y}_{i_0}$, because $Y_{i_0}=\tilde{Y}_{i_0}+E$.

At the end you extract the polynomial $M(x)$ e.g. by long division as Dilip pointed out.