6
$\begingroup$

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=(

  • 0
    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.2012-01-16

1 Answers 1

6

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

  • 0
    @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$.2011-12-29