Hamming balls, the Hamming bound and the Gilbert–Varshamov bound #
The words ∀ i, β i at Hamming distance exactly r from a word x are obtained by choosing the
r positions where they differ and a different letter at each, so there are
∑_{|S| = r} ∏_{i ∈ S} (|β i| - 1) of them, whatever x is
(Cslib.Code.card_filter_hammingDist_eq); over an alphabet of q letters at each of n positions
this is C(n, r) (q - 1) ^ r (Cslib.Code.card_filter_hammingDist_eq_choose_mul_pow). Balls of
radius r around the words of a code of minimum distance Cslib.Code.minDist more than 2 r are
disjoint, so the code has at most q ^ n / V words, where V is the size of a ball: the
Hamming bound (Cslib.Code.card_mul_card_filter_hammingDist_le_le_prod,
Cslib.Code.card_mul_sum_choose_le_of_two_mul_lt_minDist) [Ham50],
MacWilliams and Sloane, Chapter 1, Theorem 6. Conversely, the balls of
radius d - 1 around a largest code of minimum distance at least d cover every word, so some
code of minimum distance at least d has at least q ^ n / V words, where V is the size of a
ball of radius d - 1: the Gilbert–Varshamov bound
(Cslib.Code.exists_le_minDist_and_prod_le_card_mul_card_filter_hammingDist_lt,
Cslib.Code.exists_le_minDist_and_pow_le_card_mul_sum_choose) [Gil52], by Gilbert's greedy
argument; Varshamov proved the same bound for linear codes [Var57].
Main results #
Cslib.Code.card_filter_hammingDist_eq: the size of a Hamming sphere.Cslib.Code.card_filter_hammingDist_le_eq_sum: the size of a Hamming ball, as a sum of sphere sizes.Cslib.Code.card_mul_card_filter_hammingDist_le_le_prod: the Hamming bound.Cslib.Code.card_mul_sum_choose_le_of_two_mul_lt_minDist: the Hamming bound over aq-letter alphabet.Cslib.Code.exists_le_minDist_and_prod_le_card_mul_card_filter_hammingDist_lt: the Gilbert–Varshamov bound.Cslib.Code.exists_le_minDist_and_pow_le_card_mul_sum_choose: the Gilbert–Varshamov bound over aq-letter alphabet.
References #
- R. W. Hamming, Error detecting and error correcting codes
- E. N. Gilbert, A comparison of signalling alphabets
- R. R. Varshamov, Estimate of the number of signals in error correcting codes
- [F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes] [MWS77]
The words differing from x exactly at the positions S: a different letter at each position
of S.
The size of a Hamming sphere: the words at distance r from x. It does not depend on
x.
Over an alphabet of q letters at each of n positions, a Hamming sphere of radius r has
C(n, r) (q - 1) ^ r words.
The size of a Hamming ball is the sum of the sizes of the spheres.
The Hamming bound: a code of minimum distance more than 2 r has at most ∏ i, |β i|
words in all of its balls of radius r together.
The Hamming bound [Ham50] over a q-letter alphabet at each of n positions: a code
of minimum distance more than 2 r has at most q ^ n / V words, where
V = ∑_{j ≤ r} C(n, j) (q - 1) ^ j is the size of a ball of radius r.
The Gilbert–Varshamov bound [Gil52]: for d ≥ 1 there is a code of minimum distance
at least d which has at least ∏ i, |β i| / V words, where V is the size of a ball of radius
d - 1. A largest such code works: its balls of radius d - 1 cover every word, since a word at
distance at least d from every codeword could be added to it.
The Gilbert–Varshamov bound [Gil52] over a q-letter alphabet at each of n
positions: for d ≥ 1 some code of minimum distance at least d has at least q ^ n / V words,
where V = ∑_{j < d} C(n, j) (q - 1) ^ j is the size of a ball of radius d - 1.