Hamming code

The $𝑞$ -ary $[𝑛, 𝑛 - 𝑘]$ Hamming code $C \leq 𝕂 𝑛 𝑞$ is the (unique up to linear equivalence) whose $[𝑛, 𝑘]$ Orthogonal code has a maximal projective system.¹ #m/def/code It follows that

𝑛 = (𝑘 1) 𝑞 = 𝑞 𝑘 - 1 𝑞 - 1

the number of points in $P G (𝑘 - 1, 𝑞)$ . Hamming codes are perfect 3-error correcting codes.

Proof of uniqueness and perfection

Uniqueness follows from uniquenes of the dual code $C ⟂$ : Since this is a maximal projective code, any column of the same size will be linearly dependent with one of the columns of its generator matrix, and therefore there exists a monomial transformation relating any two such matrices.

Clearly the minimum distance is three. Now let $⃗ 𝐱 \in C$ be a codeword. Then

| C | ∣ ―― B 1 (⃗ 𝐱) ∣ = 𝑞 𝑛 - 𝑘 (1 + 𝑛 (𝑞 - 1)) = 𝑞 𝑛 = ∣ 𝕂 𝑛 𝑞 ∣

hence these spheres partition $𝕂 𝑛 𝑞$ .

Sometimes, the extended code of a Hamming code is also referred to as a Hamming code.

Construction

From the characterization above, it follows that a parity check matrix of the $𝑞$ -ary $[𝑛, 𝑛 - 𝑘]$ Hamming code may be constructed by enumerating homogenous coördinates for all $𝑛$ points in $P G (𝑘 - 1, 𝑞)$ , and collecting these as columns for the check matrix.

Special cases

$[8, 4, 4] 2$ extended Hamming code

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

1999. Introduction to coding theory, §3.3, p. 38 ↩

Hamming code

Construction

Special cases

Footnotes