{ "cells": [ { "cell_type": "markdown", "id": "954baa99-8e7f-4dde-b1e6-49f29fed53cd", "metadata": {}, "source": [ "

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

\n", "\n", "

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

\n", "

1.1 Messages and codewords

\n", "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:\n", "\n", "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$.\n", "\n", "

1.2 Hamming distance between codewords

\n", "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.$$\n", "\n", "

1.3 The parameter $d$: minimum distance

\n", "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:\n", "\n", "\n", "\n", "\n", "\n", "

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

\n", "An $(n, k, d)$ code is an error-correcting code with:\n", "\n", "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.\n", "\n", "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)." ] }, { "cell_type": "markdown", "id": "8dce86fd-d1c1-4562-9c2b-61ba76159176", "metadata": {}, "source": [ "

2. Arithmetic Modulo a Prime Number

\n", "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.\n", "\n", "

2.1 Integers modulo 251

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

2.2 Operations you will implement

\n", "In your code, implement the following functions (or their equivalents):" ] }, { "cell_type": "code", "execution_count": 1, "id": "a588232c-387f-43c6-b6b9-d5aa40158ddb", "metadata": {}, "outputs": [ { "ename": "IndentationError", "evalue": "expected an indented block (553105646.py, line 6)", "output_type": "error", "traceback": [ "\u001b[0;36m Cell \u001b[0;32mIn[1], line 6\u001b[0;36m\u001b[0m\n\u001b[0;31m def f_sub(a, b):\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mIndentationError\u001b[0m\u001b[0;31m:\u001b[0m expected an indented block\n" ] } ], "source": [ "P = 251 # the prime modulus\n", "\n", "def f_add(a, b):\n", " # return (a + b) mod 251\n", "\n", "def f_sub(a, b):\n", " # return (a - b) mod 251\n", " \n", "def f_mul(a, b):\n", " # return (a * b) mod 251\n", " \n", "def f_inv(a):\n", " # return the multiplicative inverse of a (mod 251)\n", " # i.e., a number x such that (a * x) mod 251 == 1\n", " \n", "def f_div(a, b):\n", " # return a * f_inv(b) (mod 251)" ] }, { "cell_type": "markdown", "id": "5f9d939f-3796-4778-847d-05789fc0d19b", "metadata": {}, "source": [ "

3. Reed-Solomon Codes over Integers Modulo 251

\n", "We will build a simple Reed–Solomon code with parameters $$n = 15, k = 11.$$\n", "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.\n", "\n", "

3.1 Polynomials with coefficients mod 251

\n", "We will represent a polynomial by a list of its coefficients. For example,\n", "$$p(x) = 3x^2 + 5x + 7$$ can be represented as: $$[3, 5, 7].$$\n", "You will implement the following functions:" ] }, { "cell_type": "code", "execution_count": null, "id": "83cf4c81-a333-44c2-87c6-5938b76a6453", "metadata": {}, "outputs": [], "source": [ "def poly_add(p, q):\n", " \"\"\"\n", " Add two polynomials with coefficients mod 251.\n", " Return a new polynomial.\n", " \"\"\"\n", "\n", "def poly_scale(p, a):\n", " \"\"\"\n", " Multiply polynomial p by scalar a (mod 251).\n", " \"\"\"\n", "\n", "def poly_mul(p, q):\n", " \"\"\"\n", " Multiply two polynomials with coefficients mod 251.\n", " \"\"\"\n", "\n", "def poly_div(dividend, divisor):\n", " \"\"\"\n", " Polynomial long division: return (quotient, remainder)\n", " such that dividend = quotient * divisor + remainder.\n", " All arithmetic is mod 251.\n", " \"\"\"" ] }, { "cell_type": "markdown", "id": "65f270b1-aed9-4091-84e6-5eaf124e4611", "metadata": {}, "source": [ "All these functions should use `f_add`, `f_sub`, `f_mul`, `f_div` from Section 2.\n", "\n", "

3.2 Encoding messages

\n", "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\n", "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.)\n", "\n", "Given the message polynomial $P(x)$, the Reed–Solomon codeword is:\n", "$$c = (p(1), p(2), . . . , p(n)) \\textrm{ all taken mod 251}.$$\n", "This is the entire encoding process.\n", "\n", "

3.3 Why this is an error correcting code

\n", "A fundamental fact from algebra (you do not need to prove it) is:
\n", "Fact: A degree $(k−1)$ polynomial is uniquely determined by its values at any $k$ distinct points.\n", "\n", "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.\n", "\n", "

3.4 Error detection

\n", "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:\n", "
    \n", "
  1. Try to interpolate a degree-$\\leq (k−1)$ polynomial $Q(x)$ that fits all $n$ points.
    2. \n", "
  2. If interpolation succeeds (the points lie exactly on some polynomial), no errors occurred.
    3. \n", "
  3. If interpolation fails, then an error is present.
    4. \n", "
\n", "You will use a standard interpolation algorithm (e.g., Lagrange interpolation) for this. You will implement:" ] }, { "cell_type": "code", "execution_count": null, "id": "6aa20f89-9101-4c5d-b55d-1df8e30d9876", "metadata": {}, "outputs": [], "source": [ "def interpolate(points):\n", " \"\"\"\n", " Given a list of (x, y) pairs with x distinct,\n", " return the coefficients of the unique polynomial Q(x)\n", " of degree <= k-1 that fits all the points,\n", " OR return None if no such polynomial exists.\n", " \"\"\"" ] }, { "cell_type": "markdown", "id": "a8dcb739-2b14-417e-93e2-2a611e38b12a", "metadata": {}, "source": [ "

3.5 Single-error correction

\n", "To keep complexity reasonable, you are only required to correct one erroneous symbol.\n", "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:" ] }, { "cell_type": "code", "execution_count": null, "id": "2f01a1c5-c5eb-4869-9cb3-99dc3fa44c74", "metadata": {}, "outputs": [], "source": [ "def rs_correct_single_error(y, n, k):\n", " \"\"\"\n", " Attempt to correct a single corrupted value in y.\n", " Try every position i and every possible replacement value v,\n", " and check whether the modified vector fits a degree <= k-1 polynomial.\n", " Return (corrected_codeword, polynomial_coeffs) if successful.\n", " Return None if no single error can explain the received vector.\n", " \"\"\"" ] }, { "cell_type": "markdown", "id": "bc8741fb-8b01-43dd-806b-87bd18fe4dd1", "metadata": {}, "source": [ "Here is the sketch of the algorithm:\n", "
    \n", "
  1. For each position $i \\in \\{1, ..., n\\}$ and each candidate value $v$ in $\\{0, ..., 250\\}$:
    2. \n", "
      \n", "
    1. Replace $y_i$ by $v$.
      2. \n", "
    2. Try interpolating a polynomial of degree-$\\leq k−1$ that fits all $n$ points.
      3. \n", "
    3. If interpolation succeeds:
      4. \n", " \n", "
    \n", "
\n", "Since $n = 15$ and there are $251$ possible values, this search is computationally feasible.\n", "\n", "Optional task: Use the Reed-Solomon code to implement your own QR code. Depending on the amount\n", "of noise you want to tolerate, you would need to increase the length of your codeword." ] }, { "cell_type": "code", "execution_count": null, "id": "0450a8f7-14fc-4330-a6c2-84c6676c516e", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.6" } }, "nbformat": 4, "nbformat_minor": 5 }