An RS code \(C_{\text{RS}}(n, k)\) over \(\text{GF}(q)\) that can correct \(t\) element errors has the following parameters:
For \(C_{\text{RS}}(7, 5)\) over \(\text{GF}(2^3)\), we have code vectors with 7 3-bit elements, two of which are parity elements, and we can correct up to 1 element error.
Build \(\text{GF}(2^3)\) using \(f(x) = 1 + x^2 + x^3\). We can enumerate the elements using
\[f(z) = 1 + z^2 + z^3 = 0 \implies z^3 = 1 + z^2\]
So that, for instance
\[z^4 = zz^3 = z(1 + z^2) = z + z^3 = z + 1 + z^2\]
| Element | Polynomial | Binary |
|---|---|---|
| 0 | 0 | 000 |
| 1 | 1 | 100 |
| \(z\) | \(z\) | 010 |
| \(z^2\) | \(z^2\) | 001 |
| \(z^3\) | \(z^2 + 1\) | 101 |
| \(z^4\) | \(z^2 + z + 1\) | 111 |
| \(z^5\) | \(z + 1\) | 110 |
| \(z^6\) | \(z^2 + z\) | 011 |
F2 = GF(2)
R.<x> = PolynomialRing(F2)
f = 1 + x^2 + x^3
assert(f.is_irreducible())
F8.<z> = F2.extension(f)The generator polynomial is formed by taking the product
\[g(x) = \prod_{i = 1}^{n - k} \Phi_i(x) = (x - z) (x - z^2) \cdots (x - z^{n - k})\]
The corresponding generator for \(C_{\text{RS}}(7, 5)\):
\[g(x) = (x + z)(x + z^2) = x^2 + (z + z^2)x + z^3 = x^2 + z^6x + z^3\]
g = (x + z) * (x+z^2)
assert(g == x^2 + z^6*x + z^3)Messages are converted into polynomials with coefficients from \(\text{GF}(q)\) using the table above:
\(m=\) (001 101 111 010 011) \(\implies m(x) = z^2 + z^3x + z^4x^2 + zx^3 + z^6x^4\)
msg = [0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1]
coefs = [F8(msg[i:i+3]) for i in range(0, len(msg), 3)]
m = sum(c*x^i for (i, c) in enumerate(coefs))
assert(m == z^2 + z^3*x + z^4*x^2 + z*x^3 + z^6*x^4)The systematic form is obtained by taking the remainder \(p(x)\) of the division of \(x^{n - k}m(x)\) by \(g(x)\) so that \(x^{n - k}m(x) = q(x)g(x) + p(x)\).
Here we have \(x^2 m(x) = z^2x^2 + z^3x^3 + z^4x^4 + zx^5 + z^6x^6\) which leaves \(p(x) = z^5x\).
v = m*x^2
q = v // g
p = v % g
assert(p == z^5*x)The resulting code polynomial is our original message prefixed by two parity check elements.
\[ \begin{align} c(x) &= p(x) + x^2m(x)\\ &= z^2x^2 + z^3x^3 + z^4x^4 + zx^5 + z^6x^6\\ &= \text{(000 110 001 101 111 010 011)} \end{align} \]
Assume we received a polynomial \(r(x)\) which is related to a code polynomial \(c(x)\) along with some noise \(e(x)\).
\[r(x) = c(x) + e(x)\]
Evaluating \(r(x)\) at the roots \(z^i\) gives us \(2t\) equations of the form
\[r(z^i) = e(z^i), i \in \{1, 2, \dots, 2t\}\]
From which we can solve for \(t\) error locations and \(t\) error values.
If we receive r = (000 110 001 101 111 111 011), then
\[r(x) = z^5x + z^2x^2 + z^3x^3 + z^4x^4 + z^4x^5 + z^6x^6\]
And since \(t = 1\), we have two equations in two unknowns:
So that \(e(x) = z^3x^5\) and the corrected code vector is
\[ \begin{align} c(x) &= e(x) + r(x)\\ &= z^5x + z^2x^2 + z^3x^3 + z^4x^4 + zx^5 + z^6x^6\\ &= \text{(000 110 001 101 111 010 011)} \end{align} \]
r_msg = [0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
coefs = [F8(r_msg[i:i+3]) for i in range(0, len(r_msg), 3)]
r = sum(c*x^i for (i, c) in enumerate(coefs))
e_loc = r(z^2) / r(z)
e_val = r(z)^2 / r(z^2)
e = e_val * x^log(e_loc, z)
assert(e == z^3 * x^5)
c = e + r
d = [j for i in c.coefficients()[-5:] for j in i]
assert(msg == d)