Error correcting codes

Noisy communication channels

Is this working?

Am I muted?

Can you hear me through space?

Can you hear me through the atmosphere?

Errors are inevitable

Errors are inevitable

Errors are inevitable

Correcting errors

Can we do better?

Yes, we can.

Using number theory!

The strategy

We have a set \(M\) of messages (strings of length \(n\)).

We encode each \(m \in M\) to a longer string \(f(m)\).

So that \(f(m_1)\) and \(f(m_2)\) are not too close if \(m_1 \neq m_2\).

What is "too close"?

Given two strings \(n_1\) and \(n_2\), define the Hamming distance \(d(n_1,n_2)\)between them to be the number of places in which \(n_1\) and \(n_2\) differ.

Not too close = Hamming distance at least \(k\).

Using the strategy

Allows \(\lfloor k/2 \rfloor \) errors to be corrected!

Using the strategy

Allows \(\lfloor k/2 \rfloor \) errors to be corrected!

How we execute the strategy?

How do we find an \(f\)?

Using finite fields!

What is a field?

A field \(F\) is a set together with operations \(+\) (addition) and \(\times\) (multiplication) satisfying the familiar rules.

1. Addition is associative, commutative, has an identity element (\(0\)).
2. Multiplication is associative, commutative, has an identity element (\(1\)).
3. Distributive law holds: \(a \times (b+c) = a \times b + a \times c\).
4. Every non-zero element has a multiplicative inverse.

Examples

1. \(\mathbb Q\) is a field (with the usual \(+, \times\)).
2. \(\mathbb R\) is a field (with the usual \(+, \times\)).

Finite fields

Take \(\mathbb F_p = \{0,1,\dots, p-1\}\)
with \(+\) and \(\times\) done modulo \(p\).

Theorem: \(\mathbb F_p\) is a field.

Multiplicative inverses in \(\mathbb F_5\).

Polynomials

For any field \(F\), let \(F[x]\) denote the set of polynomials with variable \(x\) and coefficients in \(F\).

Example: In \(\mathbb F_5[x]\), we have elements like

Polynomials

We add and multiply polynomials as usual, but remembering to always use the given operations for \(F\).

For example, in \(\mathbb F_5[x]\), we have \[ (\overline 2 x+ \overline 1) \cdot (\overline 1 x+ \overline 3) = \overline 2 x^2 + \overline 2 x + \overline 3. \]

Zeros of polynomials

Most of the usual properties of polynomials continue to hold.

1. If \(p(a) = 0\) then \((x-a)\) divides \(p(x)\); that is, \(p(x) = (x-a) q(x)\) for some \(q(x)\).
2. As a result, if \(p(x)\) has degree \(n\), then it has at most \(n\) zeros.
3. As a result, if \(p_1(x)\) and \(p_2(x)\) are distinct and have degree at most \(n\), then \(p_1(a) = p_2(a)\) for at most \(n\) values of \(a\).

Reed-Solomon codes

Message space: length-3 strings of \(\{0,1,2,3,4\}\).

Encoding \((p_1, p_2, p_3)\)

1. Think of \((p_1,p_2,p_3)\) as the polynomial \(p(x) = p_1 x^2 + p_2 x + p_3\) in \(\mathbb F_5[x]\).
2. Encode this polynomial into a length-5 string \((p(0),p(1),p(2),p(3),p(4))\).

Reed-Solomon codes

1. Think of \((p_1,p_2,p_3)\) as the polynomial \(p(x) = p_1 x^2 + p_2 x + p_3\) in \(\mathbb F_5[x]\).
2. Encode this polynomial into a length-5 string \((p(0),p(1),p(2),p(3),p(4))\).

Example:

What is the hamming distance?

What is the Hamming distance of the encodings of \(p\) and \(q\)?

At least 3!

Two distinct polynomials of degree at most 2 must differ in at least 3 out of the 5 values of \(x\) in \(\mathbb F_5\).

Recap

Encode: Length-3 string to length-5 string

Gain: Ability to correct any 1-bit errors.

Better than tripling!

Applications

Reed-Solomon codes (and their more sophisticated analogues) are used in many places!

Applications

Applications

Applications

Applications

More questions

1. Are there other finite fields, besides \(\mathbb F_p\)?
2. Can we do better than Reed-Solomon?

Thank you!