Sphere packing condition for a perfect code

$C \subseteq 𝑆 𝑛 𝑞$ is a [[Perfect code|perfect $𝑒$ -error correcting code]], iff the Hamming balls $B 𝑒 (𝐶) \cap B 𝑟 (𝐷) = \emptyset$ for any two codewords $𝐶 \neq 𝐷$ and 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 $𝑞$ .

tidy | en | SemBr

Sphere packing condition for a perfect code

Graph View

Backlinks