Coding theory MOC

Hamming code

The -ary Hamming code is the (unique up to linear equivalence) whose Orthogonal code has a maximal projective system.1 #m/def/code It follows that

the number of points in . Hamming codes are perfect 3-error correcting codes.

Proof of uniqueness and perfection

Uniqueness follows from uniquenes of the dual code : 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 be a codeword. Then

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 , and collecting these as columns for the check matrix.

Special cases

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

Footnotes

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