03.1 Error Detection and Correction

Why would we want to detect/correct errors?

• The internet drops data packets (due to congestion)
• Not all bits on a storage device can be retrieved
• Wireless signals are noisy

We have 2 “channel models”:

• The erasure channel → data is lost
• The error channel → data is changed

Definition

We have the erasure weight (or error weight) $p$ the total number of erasures (or errors)

Introduction to Channel Coding

Example

Let’s suppose we want to transport the message $01$ across the erasure channel

If we transport it as is, we have no way of knowing the original message

Now let’s do some channel coding (by adding redundancy) → every bit is expanded to cover three bits ⇒ $00$ becomes $000000$, $01$ becomes $000111$, etc…

Now if we have an error, we can easily reconstruct our original message

We can of course do the same for the error channel

The example we showed is a block code $(n,k)$, with $n=6$, and $k=2$ ⇒ each $k$ source symbol is substituted by $n$ channel symbols over the same alphabet.

With the alphabet $\{0,1\}$ ⇒ binary $(n,k)$ block code

Definitions

• We have $\mathcal{C}$ the set of codewords
• We have a codeword $c$ an element of ${\mathcal{A}}^n$
• The block length is $n$
• Each codeword carries $k={\log }_{|\mathcal{A}|}|\mathcal{C}|$ information bits
• We have the rate $\frac{k}{n}$ bits per symbol

Hamming distance

Definition

We have the Hamming distance $d(x,y)$ between two $n$-tuples $x,y$ ⇒ the number of positions they differ

$x=10$, $y=00$, $d(x,y)=1$

⇒ The hamming distance is a mathematical distance (comparable to the distance between two points in 2 dimensions) ⇐> it satisfies

• Non negativity: $d(x,y)\ge 0,\forall x,y$
• Symmetry: $d(x,y)=d(y,x)$
• Triangle inequality: $d(x,z)\le d(x,y)+d(y,z)$

Decoders

We can therefore minimize errors by correcting for errors with the minimum distance from known codewords

Definition

For a code $\mathcal{C}$, we have its minimum distance $$ d_{\min} (\mathcal C) = \min_{x, y \in \mathcal C; x \neq y}d(x, y)

We can expect 3 results from a decoder:

• For an error channel:
  1. Error correction ⇒ we get the original signal back
  2. Error detection ⇒ we detect that an error has occurred (but cannot recover the message)
  3. Decoding error ⇒ the decoder makes the wrong decision while correcting
• For an erasure channel:
  1. Erasure correction ⇒ we get the original signal back
  2. Erasure detection ⇒ (erasures are always found out)
  3. Decoding error ⇒ the decoder fills the missing symbols wrongfully

Theorem

Channel errors of weight $p<d_{\min }(\mathcal{C})$ do not lead to a codeword, and are detected

Channel errors of weight $p\ge d_{\min }(\mathcal{C})$ lead to another codeword ⇒ cannot be detected by a minimum-distance decoder

Theorem

A minimum distance decoder for a code $\mathcal{C}$ corrects all erasures of weight $p$ ⇐> $p<d_{\min }(\mathcal{C})$

Theorem

A minimum distance decoder for a code $\mathcal{C}$ corrects all channel errors of weight $p$ ⇐> $p<\frac{d_{\min }(\mathcal{C})}{2}$

To find the minimum distance of $\mathcal{C}$, where $|\mathcal{C}|=M$, we need $\left(\begin{array}{c}M\\ 2\end{array}\right)$ comparisons ⇒ This is not always very applicable ⇐> large amount of codewords

Singleton’s Bound

Theorem

Regardless of the size of $\mathcal{A}$, the minimum distance satisfies

$$d_{\min }-1\le n-k$$

We call the block codes that satisfy this bound with equality Maximum Distance Separable code — or simply MDS

03.2 Finite Fields and Vector Spaces