Reed-Solomon Error Correction – Decoding#
Reed-Solomon codes are an especially powerful tool for efficient multi-bit error detection and correction. In my last post, I discussed how to encode messages. In this post, I will discuss how to correct errors and decode the message.
Syndromes#
Now that we have protected our message with redundant symbols, let us assume that the message we actually received is \(U(x)\) such that
\(E(x)\) is called the error polynomial, since it is the difference between the received and the transmitted message.
The \(i\)-th syndrome \(S_i(x)\) is defined by
Important
Note that \(S_i\) is actually a constant since we are taking the remainder when dividing by \((x + \alpha^i)\), and the order of the remainder must be less than that of the divisor.
Alternatively, we can rewrite the equation as
where \(V_i(x)\) are the quotients.
If we rearrange and plug in \(\alpha_i\), we will get
As \(S_i(x)\) is a constant function, \(S_i(x) = S_i(\alpha^i)\). Thus
Note
We have dropped the \((x)\) of \(S_i(x)\), since \(S_i\) is a constant.
Example:
This is our transmitted message in my last blog post:
Let us assume that during transmission, the second symbol (the first check symbol) got entirely flipped: \((01)_2 \to (10)_2\).
Then
Alternatively,
The Fundamental Equation#
You may have wondered why we would like to calculate the syndromes in the first place. Syndromes are the stepping stones to locating and correcting errors.
Note
The last equality is true because \(x + \alpha^i\) is a factor of \(g(x)\). Thus \(g(\alpha^i) = 0\).
With the equation above in hand, the next step is to determine \(E(x)\) from the syndromes.
Warning
The following sections contain complex mathematical manipulation.
As at most \(t\) errors can be corrected, let
Therefore
where \(X_j = \alpha^{e_j}\).
Note
We have omitted proving the fact that properties of exponents apply to \(\alpha\).
Caution
\(j \in [1, t]\cap\mathbb{Z}\), but \(e_j \in [0, n-1]\cap\mathbb{Z}\).
Consider the geometric series
After a series of manipulations:
We can define the locator polynomial \(\Delta(x)\) as
and the evaluator polynomial \(\Omega(x)\) as
Then
As \(S_k\) doesn’t reallly exist when \(k\to\infty\), we can rewrite it in modulo form:
This is the Fundamental Equation.
Locating and Detecting Errors#
Up to this point, we still have little clue why we need the Fundamental Equation or the nasty-looking locator and evaluator polynomials.
However, this is just about to change.
The following is the derivative of the locator polynomial \(\Delta(x)\):
Warning
When using the power rule
where \(c\) is a constant, we cannot directly multiple \(c\) and \(n\) as they are from different fields. Instead we add \(c\) to itself \(n\) times.
This is surprisingly similar to \(\Omega(x)\). In fact, we have the following equation:
And here we go. If we can find \(\Omega(x)\) and \(\Delta(x)\), then all we have to do is:
For every \(i \in [0, n-1]\cap\mathbb{Z}\), find \(\alpha^i\) and its multiplicative inverse \(\alpha^{-i}\) (with the multiplication table)
Plug \(\alpha^{-i}\) into the locator polynomial \(\Delta(x)\). If \(i\) is indeed one of \(e_j\), call it \(e_l\), then \(\Delta(\alpha^{-i}) = \Delta(X_l^{-1}) = 0\). (since \((1 - X_lx)\) is one of the factors of \(\Delta(x)\))
For every \(i\) that passed step 2, evaluate \(X_l\frac{\Omega(X_l^{-1})}{\Delta'(X_l^{-1})}\) to get the error at that position
Extend Euclidean Algorithm#
The (other) hard part is finding the two polynomials, \(\Delta(x)\) and \(\Omega(x)\). To do this, first we need to take a look at the Extended Euclidean Algorithm.
The Bézout identity states that there exists integers \(u\) and \(v\) such that
With the EEA, we can solve for both the greatest common divisor and the Bézout coefficients with the following Python code:
def extended_gcd(a: int, b: int) -> dict[str, int]:
old_d, d = a, b
old_u, u = 1, 0
old_v, v = 0, 1
while d != 0:
q, r = divmod(old_d, d)
old_d, d = d, r
old_u, u = u, old_u - q * u
old_v, v = v, old_v - q * v
return {
"gcd": old_d,
"u": old_u,
"v": old_v,
}
I won’t go into the details here. Here’s a link to the Wikipedia article on this algorithm if you want to dive deeper.
The most important fact about this algorithm is that it also works for polynomials and \(GF[2^m]\) fields, or specifically the Fundamental Equation:
Peeking at our Bézout identity above, we discover that this equation is in the exact same format. If we apply the EEA for \(\sum_{k=0}^{2t-1} S_kx^k\) and \(x^{2t}\), we will be able to find both \(\Omega(x)\) (the gcd) and \(\Delta(x)\) (one of the Bézout coefficients).
Example:
As r is already a constant (equivalent to r == 0 in the algorithm), we iterate one last time,
jump out of the while loop and return.
Finishing the Example#
Once we get \(\Omega(x)\) and \(\Delta(x)\), we follow the procedure described earlier.
- \[\begin{split} \begin{align*} \alpha^0 &= 1 \\ \alpha^1 &= 2 \\ \alpha^2 &= 3 \\ \alpha^{-1} &= 2^{-1} = 3 \\ \alpha^{-2} &= 3^{-1} = 2 \\ \end{align*} \end{split}\]
- \[\begin{split} \begin{align*} \Delta(\alpha^0) &= 1 + 3 = 2 \\ \Delta(\alpha^{-1}) &= 3 + 3 = 0\;\mathcal{(ERROR!)} \\ \Delta(\alpha^{-2}) &= 2 + 3 = 1 \\ \end{align*} \end{split}\]
- \[ Y_l = \alpha^1\frac{\Omega(\alpha^{-1})}{\Delta'(\alpha^{-1})} = 2\cdot\frac{2}{1} = 3 \]
This is the correct answer as the double bit error is represented by \(3 = (11)_2\) at the second position.
Citations and Credits#
Clarke, C. K. P. “R&d white paper.” Reed-Solomon error correction,” WHP 31 (2002).
Shankar, Priti. “Decoding Reed-Solomon Codes Using Euclid’s Algorithm.” Resonance, vol. 12, no. 4, Apr. 2007, pp. 37–51. DOI.org (Crossref), https://doi.org/10.1007/s12045-007-0037-y.
Huge thanks to my professor Mr. Thomas Riordan for making the best out of both papers.