5.5 Reed-Solomon Codes

Reed-Solomon Codes

Reed–Solomon codes encode a message $m$ as a polynomial $P(x)$ over a finite field $\mathrm{GF}(q)$, adding redundancy so the message can be recovered even if some symbols are lost or corrupted. The polynomial has degree at most $n-1$ for a message of length $n$, and is evaluated at $n+k$ distinct indices/positions, where $k$ is the number of redundancy symbols. Any $n$ correct points are enough to fully reconstruct $P(x)$ using polynomial interpolation.

The error tolerance depends on how much redundancy is added:

• A message with erasures (i.e., only values of errors unknown) with at most $k$ symbols missing can be recovered using the transmission of $n+k$ symbols.
  • Messages with erasures are decoded using polynomial interpolation
• A message with general errors (i.e., values and indices of errors unknown) with at most $k$ symbols corrupted can be recovered using the transmission of $n+2k$ symbols. Such messages are recovered using the Berlekamp-Welch algorithm:
  1. Construct the error-locator polynomial $E(x)={\prod }_{i=1}^k(x-e_i)$ with degree $k$, which has roots exactly at the indices of the errors.
  2. Construct $Q(x)=P(x)E(x)$ with degree $n+k-1$, such that for every received symbol $r_i$, $Q(i)=r_{i}E(i)$ is nonzero if no error occurred at point $i$.
  3. Solve $Q(i)=r_{i}E(i)$ for each $i=1,\dots ,n+2k$ over the finite field ${\mathbb{F}}_q$.
  4. Obtain the encoding by computing $P(x)=Q(x)/E(x)$.
  5. Obtain the message by evaluating $P(i)$ for each $i=1,\dots ,n$.

Correctness

Examples

Berlekamp-Welch Algorithm with Fewer Errors

Suppose Alice wants to send 1 message to Bob and wants to guard against 1 general error. She decides to encode the message with $P(x)=4$ (on $\mathrm{GF}(7)$) such that $P(0)=4$ is the message she wants to send. She then sends $P(0),P(1),P(2)=(4,4,4)$ to Bob.

Suppose Bob receives the message $(4,5,4)$. Without performing Gaussian elimination explicitly, find $E(x)$ and $Q(x)$. Since we see that the error is in $i=1$, we have that $E(x)=x-1$, and therefore $Q(x)=4x-4$.

Now, suppose there were no general errors and Bob receives the original message $(4,4,4)$. Show that the $Q(x),E(x)$ that you found in the last part still satisfies $Q(i)=r_{i}E(i)$ for all $i=0,1,2$. Since there are no errors, $4x-4=r_i(x-1)$ for all $i$.

Verify that $E(x)=x$, $Q(x)=4x$ is another possible set of polynomials that satisfies $Q(i)=r_{i}E(i)$ for all $i=0,1,2$. Since $Q(i)=r_{i}x=4x$ for all $i=0,1,2$, this tuple is a valid solution.

Suppose you’re actually trying to decode the received message $(4,4,4)$. Based on what you showed in the previous two parts, what will happen during row reduction when you try to solve for the unknowns? There will be a free variable, since there are multiple solutions to this system (i.e., it is underdetermined).

Prove that in general, no matter what the solution of $Q(x)$ and $E(x)$ are though, the recovered $P(x)$ will always be the same. Proof by contradiction. Let $Q(x)$ and $Q^{\prime }(x)$ be two distinct polynomials, such that $Q(x)=P(x)E(x)$ and $Q^{\prime }(x)=P(x)E^{\prime }(x)$. Then, $\frac{Q(x)}{E(x)}=\frac{Q^{\prime }(x)}{E^{\prime }(x)}.$ However, since the polynomials are distinct,

Error-Correcting Codes (ECC)

An error-correcting code is a mathematical scheme for encoding a message into a longer sequence (called a codeword) in such a way that the original message can still be recovered even if parts of the codeword are lost or corrupted during transmission. This is done by introducing structured redundancy into the message using algebraic techniques.

In the case of algebraic error-correcting codes, such as Reed-Solomon codes, the message is treated as a list of values over a finite field \mathbb{F}_q, and encoded using a polynomial P(x) of bounded degree. The codeword is constructed by evaluating P(x) at several points. This ensures that the original polynomial—and hence the message—can be reconstructed even if some of the evaluations are missing or incorrect.

The distinction between a message and a codeword is central: the message contains only the original data, while the codeword includes redundant values designed specifically for robustness against transmission errors.

---

Reed-Solomon Encoding

Given a message of n symbols (m_1, \dots, m_n) over a finite field \mathbb{F}_q, where q is a prime or prime power larger than n, one constructs a unique polynomial P(x) \in \mathbb{F}_q[x] of degree at most n - 1 such that P(i) = m_i for i = 1, \dots, n.

To form the codeword, the sender evaluates this polynomial at n + r distinct points (typically 1, 2, \dots, n + r) and transmits the values (P(1), P(2), \dots, P(n + r)). The integer r represents the number of redundant symbols added for robustness.

---

Erasure Correction Capability

If up to k of the n + k transmitted values are erased (i.e., lost, but their positions are known), then the original polynomial P(x) can still be uniquely reconstructed using the remaining n known evaluations. This is guaranteed because a polynomial of degree n - 1 is uniquely determined by n distinct points.

Outcome: Reed-Solomon codes can recover from up to k known erasures by transmitting n + k total symbols.

---

General Error Correction (Berlekamp-Welch Algorithm)

If up to k symbols in the received codeword are corrupted (and their locations are unknown), the original message can still be recovered, provided that 2k redundant symbols were added. That is, the total number of transmitted symbols must be n + 2k.

The recovery algorithm constructs a system of equations based on the identity Q(i) = r_i \cdot E(i), where:

• Q(x) = P(x) \cdot E(x) is a polynomial of degree n + k - 1,

• E(x) is the error-locator polynomial of degree k, whose roots correspond to error positions,

• r_i are the received values.

By solving this system, one can recover both E(x) and Q(x), and then compute the original message polynomial as P(x) = Q(x)/E(x).

Outcome: Reed-Solomon codes can correct up to k general (unknown) errors if n + 2k symbols are transmitted.

---