AGRL 112: Assignment 10 (Error Correcting Codes (ECC))
(IIT Delhi - Abu Dhabi)

1. An $(n, k, d)$ Error-Correcting Code

1.1 Messages and codewords

Imagine you want to send a short piece of data, for example, a list of $k$ numbers. We will call this list the message and write it as: $$m = (m_1, m_2, ..., m_k).$$ An error-correcting code takes your message $m$ and transforms it into a longer list $$c = (c_1, c_2, ..., c_n),$$ called a codeword. The error correcting code consists of all these codewords. Here:
  • $k$ = length of the original message,
  • $n$ = length of the encoded message (the codeword)
  • typically $n > k$, so we add some extra symbols (often called "parity" or "redundancy")
These extra symbols are carefully chosen so that if some of the $c_i$ are changed during transmission (because of noise or errors), we can still recover the original message $m$.

1.2 Hamming distance between codewords

To talk about error correction, we need a way to measure how "different" two codewords are. The Hamming distance between two codewords of length $n$, $$c = (c_1, ..., c_n), c' = (c_1', ..., c_n'),$$ is the number of positions where they differ: $$dist(c, c') = |\{i | c_i \neq c_i'\}|.$$ Example (with symbols being small integers): $$c = (5, 10, 3, 3, 0), c' = (5, 9, 3, 3, 2).$$ They differ in positions 1 (10 vs 9) and position 4 (0 vs 2), so $$dist(c, c') = 2.$$

1.3 The parameter $d$: minimum distance

The minimum distance $d$ of a code $\mathcal{C}$ is: $$d = \min_{c, c' \in \mathcal{C}, c\neq c'} dist(c, c'),$$ the smallest Hamming distance between any two distinct codewords of the code. Intuitively:
  • If $d$ is large, codewords are "far apart" and it is harder for errors to turn one valid codeword into another.
  • If $d$ is small, codewords are too close and even a few errors may cause confusion

1.4 What does $(n, k, d)$ mean?

An $(n, k, d)$ code is an error-correcting code with:
  • codeword length $n$,
  • message length $k$,
  • minimum distance $d$.
Why do we care about the minimum distance of a code? This is because it governs how robust our code is with respect to detecting/correcting errors.
  • Error detection: An $(n, k, d)$ code can always detect up to $d−1$ symbol errors in a codeword.
    • If at most $d−1$ symbols are changed, the received word cannot be equal to another valid codeword.
  • Error correction:An $(n, k, d)$ code can always correct up to $$t = \lfloor \frac{d-1}{2}\rfloor$$ symbol errors.
    • If at most $t$ symbols are wrong, there is a unique codeword that is closest to the received word, and we can recover it.
In this assignment, you will implement and experiment with a specific family of codes called Reed–Solomon codes, which are widely used in practice (for example, in QR codes).

2. Arithmetic Modulo a Prime Number

The Reed-Solomon codes used in QR codes use more advanced math (finite fields of size $2^8$), but this is not necessary for us. Instead, we will work with simple integers using the modulo operation.

2.1 Integers modulo 251

We will work with the numbers $$\{0, 1, 2, ..., 250\}$$ and we will always do arithmetic modulo 251.

2.2 Operations you will implement

In your code, implement the following functions (or their equivalents):
In [1]:
P = 251 # the prime modulus

def f_add(a, b):
    # return (a + b) mod 251

def f_sub(a, b):
    # return (a - b) mod 251
    
def f_mul(a, b):
    # return (a * b) mod 251
    
def f_inv(a):
    # return the multiplicative inverse of a (mod 251)
    # i.e., a number x such that (a * x) mod 251 == 1
    
def f_div(a, b):
    # return a * f_inv(b) (mod 251)

  Cell In[1], line 6
    def f_sub(a, b):
    ^
IndentationError: expected an indented block

3. Reed-Solomon Codes over Integers Modulo 251

We will build a simple Reed–Solomon code with parameters $$n = 15, k = 11.$$ So each message will have $k = 11$ symbols, and each codeword will have $n = 15$ symbols. There are $n−k = 4$ extra symbols, which will help with error detection/correction.

3.1 Polynomials with coefficients mod 251

We will represent a polynomial by a list of its coefficients. For example, $$p(x) = 3x^2 + 5x + 7$$ can be represented as: $$[3, 5, 7].$$ You will implement the following functions:
In [ ]:
def poly_add(p, q):
    """
    Add two polynomials with coefficients mod 251.
    Return a new polynomial.
    """

def poly_scale(p, a):
    """
    Multiply polynomial p by scalar a (mod 251).
    """

def poly_mul(p, q):
    """
    Multiply two polynomials with coefficients mod 251.
    """

def poly_div(dividend, divisor):
    """
    Polynomial long division: return (quotient, remainder)
    such that dividend = quotient * divisor + remainder.
    All arithmetic is mod 251.
    """

All these functions should use f_add, f_sub, f_mul, f_div from Section 2.

3.2 Encoding messages

In Reed-Solomon codes, the message is interpreted as a degree $k−1$ polynomial. For instance, if the message is $(3, 212, 43)$, then we will interpret this as the polynomial $p(x) = 3x^2 + 212x + 43$ (everything is modulo 251). To encode this message, choose $n$ distinct integers modulo 251 as evaluation points. For this assignment you must use: $$x_1 = 1, x_2 = 2, ..., x_n = n.$$ (You may assume $n < 251$, so all evaluation points are distinct.)

Given the message polynomial $P(x)$, the Reed–Solomon codeword is: $$c = (p(1), p(2), . . . , p(n)) \textrm{ all taken mod 251}.$$ This is the entire encoding process.

3.3 Why this is an error correcting code

A fundamental fact from algebra (you do not need to prove it) is:
Fact: A degree $(k−1)$ polynomial is uniquely determined by its values at any $k$ distinct points.

Therefore, even if many of the $n$ values $(P(1), ..., P(n))$ are corrupted, as long as at least $k$ of them are still correct, the original polynomial $P(x)$ can be reconstructed. This is why evaluation-based Reed–Solomon codes have minimum distance: $$d = n-k+1,$$ and can correct up to $$t = \lfloor \frac{n-k}{2} \rfloor$$ symbol errors.

3.4 Error detection

Given a received vector $$(y_1, y_2, ..., y_n),$$ we can detect errors by checking whether these values lie on some polynomial of degree $\leq k−1$. In this assignment, you will do this using a simple and direct test:
  1. Try to interpolate a degree-$\leq (k−1)$ polynomial $Q(x)$ that fits all $n$ points.
  2. If interpolation succeeds (the points lie exactly on some polynomial), no errors occurred.
  3. If interpolation fails, then an error is present.
You will use a standard interpolation algorithm (e.g., Lagrange interpolation) for this. You will implement:
In [ ]:
def interpolate(points):
    """
    Given a list of (x, y) pairs with x distinct,
    return the coefficients of the unique polynomial Q(x)
    of degree <= k-1 that fits all the points,
    OR return None if no such polynomial exists.
    """

3.5 Single-error correction

To keep complexity reasonable, you are only required to correct one erroneous symbol. Given received values $$(y_1, ..., y_n),$$ your task is to find the location and value of the single error by brute force. You will implement:
In [ ]:
def rs_correct_single_error(y, n, k):
    """
    Attempt to correct a single corrupted value in y.
    Try every position i and every possible replacement value v,
    and check whether the modified vector fits a degree <= k-1 polynomial.
    Return (corrected_codeword, polynomial_coeffs) if successful.
    Return None if no single error can explain the received vector.
    """

Here is the sketch of the algorithm:

  1. For each position $i \in \{1, ..., n\}$ and each candidate value $v$ in $\{0, ..., 250\}$:
    1. Replace $y_i$ by $v$.
    2. Try interpolating a polynomial of degree-$\leq k−1$ that fits all $n$ points.
    3. If interpolation succeeds:
      • Report success
      • return the corrected codeword and the recovered message.
Since $n = 15$ and there are $251$ possible values, this search is computationally feasible.

Optional task: Use the Reed-Solomon code to implement your own QR code. Depending on the amount of noise you want to tolerate, you would need to increase the length of your codeword.

In [ ]: