Coding theory MOC

Hamming code

The 𝑞-ary [𝑛,𝑛 −𝑘] Hamming code C ≤𝕂𝑛𝑞 is the (unique up to linear equivalence) whose [𝑛,𝑘] Orthogonal code has a maximal projective system.¹ code It follows that

𝑛=(𝑘1)𝑞=𝑞𝑘−1𝑞−1

the [[Number of subspaces of a Galois geometry|number of points in PG⁡(𝑘 −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, and therefore there exists a monomial transformation relating any two such matrices.

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

|C|∣――B1⁡(⃗𝐱)∣=𝑞𝑛−𝑘(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 ^check of the 𝑞-ary [𝑛,𝑛 −𝑘] Hamming code may be constructed by enumerating homogenous coördinates for all 𝑛 points in [[Galois geometry|PG⁡(𝑘 −1,𝑞)]], and collecting these as columns for the check matrix.

Special cases

• Binary 8,4,4 extended Hamming code

---

tidy | en | SemBr

Footnotes

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