82 Communication Complexity — Hamming
82.1 Overview
This module develops the combinatorics of Hamming balls and spheres over a finite alphabet \(\alpha \) of size \(q\). The main results are exact cardinality formulas: the Hamming sphere of radius \(k\) centred at any word has size \(\binom {n}{k}(q-1)^k\), and the Hamming ball of radius \(r\) has size \(\mathrm{ballVol}(n,r,q) = \sum _{i=0}^{r}\binom {n}{i}(q-1)^i\).
82.2 Declarations
A word of length \(n\) over alphabet \(\alpha \) is a function \(\mathrm{Fin}\, n \to \alpha \); it is an abbreviation for the type of length-\(n\) codewords used throughout this module.
The Hamming ball of radius \(r\) centred at \(u \in \alpha ^n\) is the finset
The Hamming sphere of radius \(r\) centred at \(u \in \alpha ^n\) is the finset
For a length-\(n\) code over an alphabet of size \(q\), the ball volume at radius \(t\) is
For any centre \(u\) and distinct radii \(r \ne t\), the Hamming spheres \(S_r(u)\) and \(S_t(u)\) are disjoint finsets.
For any centre \(u\) and bound \(r\), the family \(\{ S_t(u)\} _{t \lt r}\) is pairwise disjoint as a family of finsets indexed by \(\{ 0,\ldots ,r-1\} \).
The Hamming ball of radius \(r\) decomposes as the disjoint union
The support of \(v\) relative to \(u\) is the finset of coordinate positions where the two words differ: \(\mathrm{support}(u,v) = \{ i \in \mathrm{Fin}\, n : u_i \ne v_i\} \).
For any two words \(u,v\), the Hamming distance equals the cardinality of their support: \(\mathrm{hammingDist}(u,v) = |\mathrm{support}(u,v)|\).
For a word \(u\) and a finset \(S \subseteq \mathrm{Fin}\, n\), the support fiber is the set of words that differ from \(u\) at exactly the positions in \(S\): \(\mathrm{supportFiber}(u,S) = \{ v : \mathrm{support}(u,v) = S\} \).
If \(S \ne T\) are distinct finsets of coordinate positions, then \(\mathrm{supportFiber}(u,S)\) and \(\mathrm{supportFiber}(u,T)\) are disjoint finsets.
The Hamming sphere of radius \(r\) centred at \(u\) equals the union of support fibers over all size-\(r\) subsets of \(\mathrm{Fin}\, n\):
For a word \(u\) and position \(i\), the choices at \(i\) is the finset of symbols \(a \in \alpha \) with \(a \ne u_i\), i.e. the non-trivial alternatives for position \(i\).
For any word \(u\) and position \(i\), the number of alternative symbols at \(i\) is \(|\mathrm{choices}(u,i)| = |\alpha | - 1\).
For a word \(u\), a set \(S\) of positions, and a position \(i\), the support fiber over \(\{ i\} \cup S\) is partitioned by the value chosen at position \(i\):
For \(i \notin S\) and any alternative symbol \(a \in \mathrm{choices}(u,i)\), the slice \(\{ v \in \mathrm{supportFiber}(u,\{ i\} \cup S) : v_i = a\} \) has the same cardinality as \(\mathrm{supportFiber}(u,S)\).
For any word \(u\) and finset \(S \subseteq \mathrm{Fin}\, n\),
For any centre \(u \in \alpha ^n\) and radius \(k\),
For any centre \(u \in \alpha ^n\) and radius \(r\),
In the binary case \(q = 2\), the ball volume simplifies to