Error correcting codes

#matematik-discmath

Definition: Binary code

A binary code of length is a subset , and an element of is called a code word.

Definition: Distance between words

The distance between two code words is

The distance is thus the number of differing bits.

Theorem

The distances between code words define a metric on .

Proof:
It is clear that and . Furthermore, we have

Definition: Smallest distance

Given a binary code the smallest distance is

Definition: Nearest neighbour decryption

Nearest neighbour decryption means interpreting a potentially erroneous received word as the closest word in , in terms of distance .

Theorem

A code can correct errors with nearest neighbour decryption if Proof:
Begin with any word and apply errors to get , meaning . Now, let where . Then, by the triangle inequality we have meaning is the nearest neighbour of .

Linear code

A binary code is linear if it is a linear subspace of , i.e. for every .

Here, is thus treated as a vector space over the field . The dimension of is the dimension of when treated as such a vector space.

Weight of a word

For any , the weight of is the number of 's in , i.e.

Theorem

Let be linear, and . Then Proof:
For any we have , and since is linear, we have , so we must have .

Definition: Parity-check matrix

A parity check matrix is a matrix . It gives rise to a linear code

Theorem

Let and . If all columns of are nonzero and distinct from each other, then can correct error.

Proof:
All columns of being nonzero and distinct from each other means that they are pairwise linearly independent. Hence any has at least 's. By Theorem, this means , which by Theorem means can correct error.

Definition: Hamming code

Given an , a Hamming code is the kernel of a parity-check matrix containing all nonzero column vectors exactly once.

Importantly, by our previous theorem Hamming codes can thus correct error.

Theorem

A Hamming code generated by has dimension .

Proof:
It is clear that the image of is of dimension , and that the preimage is of dimension , meaning .

Theorem

Among all binary codes with words of length that can correct error, the Hamming code with words of length is the largest, i.e. has the greatest number of words. Because of this, we call the Hamming code perfect.

Proof:
Let be a code that can correct error. We must clearly have . For any we can define and thus get that all are disjoint since . We also know meaning We already know the dimension of the hamming code is , so its size is (we have -coefficients to choose) meaning it's at least as large as .