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.

2 consecutive messages have errors. We have 9 messages from $ GF(2^6, x^6+x+1) $. Messages were encoded with $ (x+1)(x+a)(x+a^2)\sum_{i=1}^6X_ix^{i-1}=\sum_{l=1}^9Y_lx^{l-1} $ , where $ a=(0,0,0,0,1,0) $. I have 9 messages $ \tilde{Y} $ from that $ GF(2^6 $, 2 (consecutive) of which have errors. So I wonder how to solve such problem - get all $ Y $ s corrected?

I wonder if it is possible to turn my 9 items $ \tilde{Y} $ into 3 items $ \tilde{K} $ from some $ GF( 2^{18} ) $ and solve Reed-Solomon code $ (3, 18) $ following solution described here, than turn item from that $ GF( 2^{18} ) $ into 3 items from my $ GF(2^6) $ and have all my 2 errors corrected? So how to turn from $ GF(2^6, x^6+x+1) $ into $ GF(2^{18}, something?) $ and back from that $ GF(2^{18}) $ into my "home" $ GF(2^{6}) $?

Let me introduce an image that explains what I meant by converting 9 messages from $ GF(2^6) $ by turning tham into 3 messages in $ GF(2^{18}) $. enter image description here My Idea is: if it is any how possible to to turn from $ GF(2^6, x^6+x+1) $ into $ GF(2^{18}, something?) $ and back than it is probably possible to turn from $ GF(2^6, x^6+x+1) $ into $ GF(2^{24}, something?) $ and back. If we could turn our 9 messages into 3 from $ GF(2^{24}) $ and 3 from $ GF(2^{18}) $ we would always have to fix only one message with error in that field. With simple algorithm, and with out iterations all over blocks.

If such cnversion (from one GF into another, group of messages into message) is possible, than what would be $ a $ in new field, what would be irreducible polynomial for that $ GF(2^{24}) $ or $ GF(2^{18}) $ ?

ofcourse we can not bother with $ GF(2^{24}) $ and simply use something like: enter image description here


So real problem: we have ( as Dilip Sarwate calls them) symbols $ \tilde{Y} $. (in $ GF(2^6, {\alpha}^{6}+\alpha+1) $) $$ [1, 0, 1, 1, 0, 0], $$$$[1, 1, 1, 1, 1, 1], $$$$[0, 0, 1, 1, 1, 0], $$$$[1, 0, 0, 1, 1, 1], $$$$[0, 1, 0, 0, 1, 1], $$$$[1, 1, 0, 1, 0, 1], $$$$[0, 0, 0, 1, 1, 0], $$$$[1, 0, 0, 0, 1, 0], $$$$[0, 0, 0, 0, 1, 0] $$

There are $0$ or $1$ or $2$ errors in the 9 symbols. If there are $2$ then they occur in consecutive positions.

I calculated $ S(\alpha^2) $ , $ S(\alpha) $ and $ S(1) $

$$S(\alpha^2) = \alpha^4+\alpha$$ $$S(\alpha) = \alpha^5+\alpha^4+\alpha^2 $$ $$S(1) = \alpha^4+\alpha^3+1 $$

So $$ \dfrac{S(\alpha)}{S(1)} = \alpha^5 $$ and $$ \dfrac{S(\alpha^2)}{S(\alpha)} = \alpha^5+\alpha^4+\alpha $$ and so $ \dfrac{S(\alpha)}{S(1)} $ is $ \neq $ to $ \dfrac{S(\alpha^2)}{S(\alpha)} $ and $$ \dfrac{S(\alpha)}{S(1)} - \dfrac{S(\alpha^2)}{S(\alpha)} = \alpha^4+\alpha$$

I tried to do a brute-force search for solutions to the quadratic equation $$ S(\alpha^2) + [(1+\alpha)S(\alpha)]x + [\alpha S(1)]x^2 = 0 $$ by substituting $ x = 1, \alpha, \alpha^2, \ldots, \alpha^8 $ (as Dilip Sarwate sad) and got next results: $$ {\alpha}^{4}+{\alpha}^{3}+{\alpha}^{2}+\alpha+1 $$ $$ {\alpha}^{5}+\alpha $$ $$ {\alpha}^{4}+{\alpha}^{3}+{\alpha}^{2}+\alpha+1 $$ $$ {\alpha}^{5}+{\alpha}^{4}+{\alpha}^{2}+\alpha $$ $$ {\alpha}^{5}+{\alpha}^{2} $$ $$ {\alpha}^{3}+{\alpha}^{2} $$ $$ {\alpha}^{5}+{\alpha}^{3}+{\alpha}^{2}+\alpha+1 $$ $$ {\alpha}^{5}+{\alpha}^{3}+{\alpha}^{2}+\alpha+1 $$ $$ {\alpha}^{5}+{\alpha}^{4}+{\alpha}^{3}+\alpha+1 $$ (Here is maple file I created for playing aroung GF - there is simplified API, tests for it and this task at the end of document...) The book talls me errors shall be located at $6$th and $7$th symbols but I can not find them=(

share|improve this question
    
Sounds like a burst error. Have you searched for more information using that as a keyword? I don't think that remapping this to using a Reed-Solomon code over $GF(2^{18})$ would help. After all, it is possible that the two errorneous 6-bit symbols would straddle the boundary of two 18-bit symbols. More importantly, the resulting code would be different. At least I don't see a way of re-interpreting it that way. Another thing, your terminology sounds a bit non-standard to me. Normally a single message is contained in a codeword. Here a codeword has 9 symbols, each from $GF(64)$. –  Jyrki Lahtonen Dec 22 '11 at 6:01
    
Using the notation from my answer to your previous question the system of equations $S(1)=E_1+E_2$, $S(a)=a^{i_0}(E_1+aE_2)$, $S(a^2)=a^{2i_0}(E_1+a^2E_2)$ comes out. Here the symbol $\tilde{Y}_{i_0}$ has an error of size $E_1$ and the symbol $\tilde{Y}_{i_0+1}$ is off by $E_2$. Your code is so short that it is feasible to try the different values of $i_0$, solve for $E_1$ and $E_2$ using the $S(1)$ and $S(a)$-equations, and use $S(a^2)$-equation for verifying that guess was correct/incorrect. IIRC there is a general method, but I don't remember how it goes. Dilip Sarwate may be able to help? –  Jyrki Lahtonen Dec 22 '11 at 6:44
    
Something doesn't add up. The first syndrome $S(1)$ is the sum of the received symbols, and I make that $$[1,1,1,0,1,0],$$ because the number of 1s per position is $(5,3,3,6,7,4)$ respectively, and here we are only interested in their parity. IOW the syndrome $S(1)$ is either $1+\alpha+\alpha^2+\alpha^4$ or $\alpha^5+\alpha^4+\alpha^3+\alpha$ depending on whether your notation is big-endian or little-endian. I cannot check your calculations for the other syndromes, unless you tell which notational convention your SW is following. –  Jyrki Lahtonen Jan 16 '12 at 10:14

1 Answer 1

up vote 5 down vote accepted

I think the famous review attributed to Dorothy Parker "This is not a book to be put down lightly; it should be thrown with great force." is fully applicable to whatever book myWallJSON is using to learn coding theory. In over forty years in the business, I have never encountered such dreadful nonstandard nomenclature and notation before!

Be that as it may, borrowing from @JyrkiLahtonen's comment, the issue here is that if there are $0$ or $1$ or $2$ errors in the $9$ symbols in a codeword from a $(9,6)$ Reed-Solomon code over GF$(q)$, then we can guarantee correction of one error but not two. However, if the two errors (when they occur), are guaranteed to be a burst, that is, occur in consecutive positions, then they can be corrected. With $S(1)$, $S(\alpha)$, $S(\alpha^2)$ being the syndrome (evaluations of the received polynomial at $1$, $\alpha$, $\alpha^2$), we proceed as follows.

  • If $S(1) = S(\alpha) = S(\alpha^2) = 0$, accept the received polynomial as a valid codeword

  • If $S(1), S(\alpha) \neq 0$ and $\dfrac{S(\alpha)}{S(1)} = \dfrac{S(\alpha^2)}{S(\alpha)} = \alpha^{i_0}$ where $0 \leq i_0 \leq 8$, then subtract $S(1)$ from the $i_0$-th received symbol and accept the corrected polynomial as a valid codeword. But if $i_0 > 8$, then an uncorrectable error pattern has occurred. (These assertions might be "off-by-one" because of your nonstandard notation).

  • Otherwise, do a brute-force search for solutions to the quadratic equation $$S(\alpha^2) + [(1+\alpha)S(\alpha)]x + [\alpha S(1)]x^2 = 0$$ by substituting $x = 1, \alpha, \alpha^2, \ldots, \alpha^8$.

    -- If there is a single solution, say $\alpha^4$, then the fourth and fifth symbols are in error. Solve $E_1 + E_2 = S(1), \alpha^4 E_1 + \alpha^5 E_2 = S(\alpha)$ for $E_1$ and $E_2$ to find the error values. (These might be "off-by-one" because of your nonstandard notation).

    -- If there are no solutions or there are two solutions, then an undecodable error pattern has occurred

    -- There is an elegant solution to quadratic equations over fields of characteristic $2$ that avoids brute force search (and no, it does not use the usual formula $(-b \pm \sqrt{b^2-4ac})/2a$ (can you think why?)) but describing it here will take far too long.

Edit Note added in response to a comment by Jyrki Lahtonen

A $(n,k)$ Reed-Solomon code (or more generally a maximum-distance-separable (MDS) code) over GF$(q)$ has minimum Hamming distance and minimum Hamming weight $d = n-k+1$. It also has the property that any set of $k$ symbol positions (coordinates) can be considered to be the information symbols. Alternatively, given any $d$ symbol positions, there are $(q-1)$ codewords (all scalar multiples of one another) whose $d$ nonzero symbols are in precisely these $d$ positions.

Can an MDS code of minimum distance $d$, $d$ even, correct $\frac{d}{2}$ errors? No, even though it is true that most (but not all) received words with $\frac{d}{2}$ errors in them are closer to the transmitted codeword than to any other codeword. In fact, most bounded-distance decoders declare that the error pattern is undecodable in almost all such cases though serendipitously they do manage to correct a few such error patterns. Are matters any different if we restrict attention to consecutive errors? Can the code correct $\frac{d}{2}$ consecutive errors, that is, all error bursts of length $\frac{d}{2}$? No, but a much larger fraction of the error bursts of length $\frac{d}{2}$ are correctable. Note that there exist codewords whose nonzero symbols form two bursts of length $\frac{d}{2}$, and if the error pattern is exactly one of these two bursts, the procedure described above will find both bursts as possible error patterns, and declare that the pattern is undecodable. Note that list decoding, in which the decoder produces a list of possible transmitted codewords, seems feasible (but I have not worked out the full details to my own satisfaction as yet).

share|improve this answer
1  
The opening statement alone is worth +1!! I wasn't too sure about the burst-error correcting capability of RS-codes. –  Jyrki Lahtonen Dec 22 '11 at 15:52
    
So... for me $ S(1) $ not $ = S(\alpha) $ not $ = S(\alpha^2) $ not $ =0 $ 1) are you sure that $ \dfrac{S(\alpha)}{S(1)} $ shall be $=$ to $ \dfrac{S(\alpha^2)}{S(\alpha)} $ and $=$ to $ \alpha^{i_0} $? I get $ \alpha^5 $ in $ \dfrac{S(\alpha)}{S(1)} $ and $ \alpha^5+\alpha^4+\alpha $ on $ \dfrac{S(\alpha^2)}{S(\alpha)} $... 2) I cant get anething out from BruteForce *(all combinations of $ S(\alpha^2) + [(1+\alpha)S(\alpha)]x + [\alpha S(1)]x^2 $ are not NULL =( So what shall I do? –  myWallJSON Dec 28 '11 at 22:41
    
*(book talls me that errors shall be located at $6$ and $7$th symbols (as you seem to call them) so $\alpha^5$ would seem to be somewhat the thing I shall need... but sadly I do not get $ \alpha^5 $ in $\dfrac{S(\alpha^2)}{S(\alpha)}$) –  myWallJSON Dec 28 '11 at 22:48
    
@myWallJSON Please READ the solution carefully. Receiver computes $3$ quantities $S(1),S(\alpha),S(\alpha^2)$. If all are $0$, no errors. Otherwise if $S(1),S(\alpha^2)\neq 0$, and $S(\alpha)/S(1)=S(\alpha^2)/S(\alpha)$, one error. If $S(\alpha)/S(1)\neq S(\alpha^2)/S(\alpha)$, then maybe burst of two errors; decodable if quadratic has unique root. If errors in $6$th and $7$th symbols (detected because $\alpha^5$ is root of quadratic, then solve $E_1+E_2=S(1);~E_1\alpha^5+E_2\alpha^6=S(\alpha)$ for $E_1, E_2$. It is not the case here that $S(\alpha^2)/S(\alpha)=\alpha^5$. –  Dilip Sarwate Dec 29 '11 at 3:50

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.