Notes on Error-Correcting Codes
Last Modified 2022-03-17
Definition: Alphabet, Letter, Symbol
An alphabet is a finite set. We call the elements of an alphabet letters or symbols.
Definition: Word, Length, Kleene Star, Kleene Closure,
A word over an alphabet
In other words,
Definition: Code, Block Length, Codeword
A code over an alphabet
Definition: Systematic Encoding Map
Let
Definition: Indicator Function,
The indicator function of a logical proposition
Definition: Hamming Distance,
Let
Similarly, the relative Hamming distance between
The Hamming distance
Definition: Message Length, Dimension, Rate, Minimum Distance, Distance,
Let
- The message length or dimension of a code
is the quantity . - The rate of a code
is the quantity . - The minimum distance (or simply distance) of a code
is the minimum Hamming distance between its distinct codewords, i.e., .
A code
Definition: Hamming Ball,
Let
The volume of a Hamming ball is simply its cardinality, and is denoted by
Note that this quantity is independent of the choice of word
Definition: Erasure, Error
TODO
Minimum Distance is a Proxy for Robustness
Theorem: Let
can correct erasures. can detect errors. can correct errors.
Proof: TODO
Hamming Bound
Theorem: Let
Proof: Let
contradicting the hypothesis that
Taking the base-
Dividing both sides by
Definition: Perfect Code
Let
In other words, a code is perfect if it saturates the Hamming bound.
Definition: Linear Code
Let
Note that the linear-algebraic notion of dimension coincides with our previous definition of the dimension of a code. If
Definition: Generator Matrix, Parity-Check Matrix, Dual,
Let
- A generator matrix for
is a matrix whose column space is . - A parity-check matrix for
is a matrix whose kernel is . - The dual of
is the linear code .
Here,
Because every vector space has a basis, every linear code
Gilbert–Varshamov Bound
Theorem: Let
Proof: Let
Let
TODO
Remark: The Gilbert-Varshamov bound actually holds for any