Don't know if I made this assignment correct, so I'd be very thankful for checking and maybe giving some hints if anything is wrong:
Let $F = GF(26
)$ be K[x] modulo the primitive polynomial $h(x) = 1 +x
^2 +x
^3 +x
^5 +x
^6$
, and let $\alpha$ be the
class of x. The table below gives the binary representation of the elements of $GF(2^6
)$
Let $\beta =
\alpha^9$
so that $1;\beta ; … ; \beta^6$ are all distinct and
$\beta^7 = 1$. Let $g(x) = (1 + x)(\beta + x)(
\beta^2 + x)(
\beta^3 + x)$.
Then g(x) generates a Reed-Solomon code RS(7;5) over F of length n = 7 and design distance $\delta= 5$. Note
that this is the general case of Reed-Solomon codes where $\beta$ is not necessarily a primitive element of $GF(2^6
)$.
Compute the error locating polynomial $A(z)$ using the first method as in Section 6.3 (method with forming the extended matrix) if the syndromes
of a received word $w1$ are $s_0 =
\alpha^{20}; s_1 = \alpha; s2 =
\alpha^{15}; s_3 =
\alpha^{58}$. Check that $A(\alpha^
3
) = 0$ and factorize A.
Can this happen if an error of weight at most 2 occurred during transmission?
So after calculations I've found that ther error locating polynomial $A(z) = \alpha^{18} + \alpha^{26}x+x^2 = (x+\alpha^3)(x+\alpha^{15})$
I don't understand the question if it can happen when an error of weight at most 2 occured during transmission? It can because the error locating polynomial has 2 roots, therefore it can find locations of at most 2 errors? (+ while calculating the rank of extenden matrix was 2, so there were 2 errors) ?
Also how to interprete "Let $\beta =
\alpha^9$"? obviously like here the error can't be on place 15 because th code length is only 7? how to transform it to $\beta$?
Best Answer
The point that you are being asked to comprehend here is that just because you find an error-locator polynomial (by solving what is sometimes called the key equation for Reed-Solomon and more generally of BCH) decoding that factors into linear factors over the field, it is not necessarily the error-locator polynomial of the error pattern that actually occurred.
With a cyclic RS code of length $7$ over GF$(2^6)$, the syndrome values can be any arbitrarily chosen $4$ elements of GF$(2^6)$, but only a few of the $(2^6)^4$ possible syndromes correspond to correctable error patterns of weight $2$ or less. In most of the cases, the error-locator polynomial found by solving the key equation does not factor into linear factors over the field, and so we can detect that more than $2$ errors have occurred even though we cannot correct them. In some cases including the one that you are looking at, the error-locator polynomial does factor into linear factors, but the inverses of the roots cannot possibly be the error locations. Valid error locations are all the $7$-th roots of unity (that is, powers of $\beta$), and the error locations that you found are not $7$-th roots. Thus, no error pattern of weight $2$ or less could have caused this syndrome.
As a practical matter, the roots of the error-locator polynomial are found by a process called the Chien search which consists of simply evaluating the error-locator polynomial at the powers of $\beta$. (The reason that such an unsophisticated method is used is that it simplifies the implementation of a BCH decoder in hardware, and to some extent in software too). The results of the Chien search will be that the error-locator polynomial does not have as many roots as its degree among the $7$-th roots of unity, and so an uncorrectable error pattern has occurred.