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
Definition: Indicator Function,
The indicator function of a logical proposition
Definition: Hamming Distance,
Similarly, the relative Hamming distance between
The Hamming distance
Definition: Message Length, Dimension, Rate, Minimum Distance, Distance,
- 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., .
Definition: Hamming Ball,
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
Minimum Distance is a Proxy for Robustness
can correct erasures. can detect errors. can correct errors.
contradicting the hypothesis that
Taking the base-
Dividing both sides by
Definition: Perfect Code
In other words, a code is perfect if it saturates the Hamming bound.
Definition: Linear Code
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,
- 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 .
Because every vector space has a basis, every linear code
Remark: The Gilbert-Varshamov bound actually holds for any