Error-Correcting Codes

(Copied/paraphrased/annotated from the script on Discrete Mathematics HS21 by Prof. Ueli Maurer)

Motivation and Introduction

Error-correcting codes are used in many communication protocols and other applications. For example, the digital information on a CD is stored in such a manner that even if some of the information is lost (e.g. because of a scratch or dirt on the disc), the entire information can still be reconstructed without quality degradation, as long as sufficiently much of the data is still available.

There are two types of problems that can occur in data transmission or when reading data from a storage medium. First, data can be erased, meaning that when reading (or receiving) it one realizes that it is missing. Second, data can contain errors, The second type of problem is more severe because it is not even known where in a data stream the errors occurred. A good error-correcting scheme can handle both problems.

Encoding

💡 A $(n, k)$ -encoding function $E$ for some alphabet $A$ is an injective function that maps a list $(a_{0}, \dots, a_{k - 1}) \in A^{k}$ of $k$ (information) symbols to a list $(c_{0}, \dots, c_{n - 1}) \in A^{n}$ of $n > k$ (encoded) symbols in $A$ , called codeword:

$E : A^{k} ⟶ A^{n} : (a_{0}, \dots, a_{k - 1}) ⟼ E ((a_{0}, \dots, a_{k - 1})) = (c_{0}, \dots, c_{n - 1}) .$

For an encoding function $E$ one often consider the set

$C = Im (E) = {E ((a_{0}, \dots, a_{k - 1})) ∣ a_{0}, \dots a_{k - 1} \in A}$

of codewords, which is called an error-correcting code.

💡 An $(n, k)$ -error-correcting code over the alphabet $A$ with $∣ A ∣ = q$ is a subset of $A^{n}$ of cardinality $q^{k}$ .

It is natural to use as the alphabet $A = {0, 1}$ , i.e., to take bits as the basic unit of information. However, for several reasons (one being the efficiency of encoding and in particular decoding), one often considers larger units of information, for example bytes (i.e., $A = {0, 1}^{8}$ ).

💡 The Hamming distance between two strings of equal length over a finite alphabet $A$ is the number of positions at which the two strings differ.

💡 The minimum distance of an error-correcting code $C$ , denoted $d_{min} (C)$ , is the minimum of the Hamming distance between two codewords.

Example

The following code is a $(5, 2)$ -code over the alphabet ${0, 1}$ :

${(0, 0, 0, 0, 0), (1, 1, 1, 0, 0), (0, 0, 1, 1, 1), (1, 1, 0, 1, 1)} .$

The minimum distance is 3.

Decoding

💡 A decoding function $D$ for an $(n, k)$ -encoding function is a function $D : A^{n} ⟶ A^{k}$ .

The idea is that a good decoding function takes an arbitrary list $(r_{0}, \dots, r_{n - 1}) \in A^{n}$ of symbols and decodes it to the most plausible (in some sense) information vector $(a_{0}, \dots, a_{k - 1})$ . Moreover, a good decoding function should be efficiently computable.

The error-correcting capability of a code $C$ can be characterized in terms of the number $t$ of errors that can be corrected. More precisely:

💡 A decoding function $D$ is $t$ -error correcting for encoding function $E$ if for any $(a_{0}, \dots, a_{k - 1})$

$D ((r_{0}, \dots r_{n - 1})) = (a_{0}, \dots, a_{k - 1})$

for any $(r_{0}, \dots, r_{n - 1})$ with Hamming distance at most $t$ from $E ((a_{0}, \dots, a_{k - 1}))$ .

A code $C$ is $t$ -error correcting if there exists $E$ and $D$ with $C = Im (E)$ where $D$ is $t$ -error correcting.

📖 A code $C$ with minimum distance $d$ is $t$ -error correcting if and only if $d \geq 2 t + 1$ .

Proof: ( $⟸$ ) If any two codewords have Hamming distance at least $2 t + 1$ (i.e., differ in at least $2 t + 1$ positions), then it is impossible that a word $(r_{0}, \dots, r_{n - 1}) \in A^{n}$ could result from two different codewords by changing $t$ positions. Thus if $(r_{0}, \dots, r_{n - 1})$ has a distance at most $t$ from a codeword $(c_{0}, \dots, c_{n - 1})$ , then this codeword is uniquely determined. The decoding function $D$ can be defined to decode to (one of) the nearest codeword(s) (more precisely, to the information resulting (by $E$ ) in that codeword).

( $⟹$ ) If there are two codewords that differ in at most $2 t$ positions, then there exists a word $(r_{0}, \dots, r_{n - 1})$ which differs from both codewords in at most $t$ positions; hence it is possible that $t$ errors can not be corrected. This proves the theorem.

Example

A code with minimum distance $d = 5$ can correct $t = 2$ errors. The code in the other example above can correct a single error ( $t = 1$ ).

Codes based on Polynomial Evaluation

A very powerful class of codes is obtained by polynomial interpolation if $A$ has a field structure, i.e., $A = GF (q)$ for some $q$ :

📖 Let $A = GF (q)$ and let $α_{0}, \dots α_{n - 1}$ be arbitrary distinct elements of $GF (q)$ . Consider the encoding function

$E ((a_{0}, \dots, a_{k - 1})) = (a (α_{0}), \dots, a (α_{n - 1})),$

where $a (x)$ is the polynomial

$a (x) = a_{k - 1} x^{k - 1} + \dots + a_{1} x + a_{0} .$

This code has minimum distance $n - k + 1$ .

Proof: The polynomial $a (x)$ of degree $k - 1$ can be interpolated from any $k$ values, i.e., from any $k$ codeword symbols. If two polynomials agree for $k$ arguments (or, equivalently, if two codewords agree at $k$ positions), then they are equal. This means that two different codewords cannot agree at $k$ positions. Hence any two codewords disagree in at least $n - k + 1$ positions. This proves the theorem.

An ( $n, k$ )-code over the field $GF (2^{d})$ can be interpreted as a binary ( $d n, d k$ )-code (over $GF (2)$ ). The minimum distance of this binary code is at least that of the original code because two different $GF (2^{d})$ -symbols must differ in at least one bit (but can of course differ in more than one bit).

Example

Polynomial codes as described are used for storing information on Compact Discs. In fact, the coding scheme of CD’s makes use of two different such codes. The field is $GF (2^{8})$ defined by an irreducible polynomial of degree 8 over $GF (2)$ and the two codes are a (32, 28)-code over $GF (2^{8})$ and a (28, 24)-code over $GF (2^{8})$ , both with minimum distance 5.