Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
It looks like you have what is called a $(7,5)$ Reed-Solomon code over GF$(2^5)$. This code can correct one error, not two, and there is no way of figuring out the symbols $X_1, \ldots, X_5$ from the given $7$ symbols of which no more than $2$ are in error. If you know which of the seven $Y_i$ are in error (these are called erasures), then it is possible to find $X_1, \ldots, X_5$. Incidentally, once you have the correct $Y_i$, you can get the $X_i$ by polynomial division. –  Dilip Sarwate Dec 20 '11 at 1:53
    
yep - probably misspel on book publishers side... so no more than 1 block we are given is incorrect. –  myWallJSON Dec 21 '11 at 11:49
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
2  
+1 as usual for a thorough explanation. One minor additional point: Sometimes the occurrence of more than one error is detected because the calculations result in $S(1) = 0$ and $S(a) \neq 0$. Since $S(a) \neq 0$, we know for sure that at least one error has occurred, but we cannot divide $S(a)$ by $S(1)$ to get a possible $a^{i_0-1}$ that we can test to see if it is one of $1, a, a^2, \ldots, a^6$. So the conclusion is that more than one received symbol is in error. –  Dilip Sarwate Dec 21 '11 at 16:15
    
Could you please explain a bit more on why you take $ x=1 $ and $ x=a $ and how thay would change for cases where defining equation is something like $ Y(x)=(x+1) * (x+a) * ... * (x+a^n)M(x) $? –  myWallJSON Dec 21 '11 at 19:51
    
I looked at $x=1$ and $x=a$, because they are 'known zeros' of all polynomials corresponding to valid codewords. When you have more redundancy symbols, then the decoding becomes much more complicated. In the general case it is best to use Berlekamp-Massey algorithm. For $n=3$ (double-error-correcting code) IIRC you can still do it like in my answer, but there are more cases, and it becomes complicated –  Jyrki Lahtonen Dec 21 '11 at 21:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.