Sphere packing condition for a perfect code

$C \subseteq 𝑆 𝑛 𝑞$ is a perfect $𝑒$ -error correcting code, iff the Hamming balls $B 𝑒 (𝐶) \cap B 𝑟 (𝐷) = \emptyset$ for any two codewords $𝐶 \neq 𝐷$ and #m/thm/code

| C | 𝑒 \sum 𝑖 = 0 (𝑛 𝑖) (𝑞 - 1) 𝑖 = 𝑞 𝑛

Proof

Given a codeword $𝑐 \in C$ , the number of strings with Hamming distance $𝑖$ is given by

∣ {𝑥 \in 𝑆 𝑛 𝑞 : 𝑑 (𝑥, 𝑐) = 𝑖} ∣ = (𝑛 𝑖) (𝑞 - 1) 𝑖

since there are $(𝑛 𝑖)$ combinations of positions different from $𝑐$ , and each differing position may be one of $𝑞 - 1$ letters. Hence, for a code to be perfect, the closed balls of radius $𝑒$ must partition $𝑆 𝑛 𝑞$ , giving the expression above.

The latter part can be interpreted as

The first $𝑒 + 1$ terms of a row in Pascal's triangle sum to a power of $𝑞$ .

#state/tidy | #lang/en | #SemBr