For an integer , the binary Hamming code has a parity-check matrix containing each nonzero vector of exactly once as a column. Its parameters are
The columns contain a basis, so the matrix has rank . A weight-one codeword would require a zero column, and a weight-two codeword would require repeated columns, both impossible. Two distinct nonzero columns sum to a third distinct nonzero column, giving a weight-three codeword. These facts prove the stated dimension and minimum Hamming distance.
A single error in coordinate has syndrome equal to column , so the syndrome directly identifies the corrupted bit. For this is the Hamming code of length seven. The excluded case gives the length-one zero code, not a code of minimum Hamming distance three.
For , use one nonzero representative from each one-dimensional subspace of as a parity-check matrix column. The rank is ; no zero or proportional columns imply minimum Hamming distance at least three. Two independent columns and the representative of their sum give a weight-three relation, proving equality. Every nonzero syndrome uniquely identifies one column and one nonzero error value.
For odd , put and choose of order in . Because is odd, the powers , , represent every projective point once. The cyclic code defined by is therefore monomially equivalent to a ternary Hamming code, with the displayed generator polynomial of a cyclic code. This statement requires a qualification: at , every ternary cyclic length-four, dimension-two code has a weight-two generator, so none has Hamming distance three.
Set and let be a primitive element of a finite field . The powers represent every projective point once. Their kernel code is a ternary Hamming code. Since , its polynomial description is a negacyclic code, generated by the minimal polynomial of an algebraic element over .
Let generate , , and set . The binary cyclic code defined by has a parity-check matrix consisting of every nonzero vector of once, after choosing a basis and ordering its columns. It is therefore a Hamming code. Its generator polynomial is the minimal polynomial of an algebraic element , of degree .
Here , and the weight enumerator convention is . The dual code is the binary simplex code, with enumerator . The MacWilliams identity gives the formula. For , the ordinary enumerator is ; for , the degenerate one-word code has enumerator .
For , a codeword in a Hamming code is a subset of the nonzero vectors of whose sum is zero. Ordered weight-three supports of a vector are determined by two distinct nonzero vectors, giving choices. For weight four, the third vector must avoid the three nonzero vectors in the linear span of the first two, giving choices. For weight five, the first three must be linearly independent, and the fourth must avoid all seven nonzero vectors in their linear span, giving choices. The final vector is their sum. Dividing by , , and counts unordered supports of a vector and proves the displayed weight enumerator coefficients.
Appending an overall parity bit to a binary Hamming code of redundancy gives the extended Hamming code with parameters
The extension preserves dimension. Every resulting codeword has even Hamming weight, while every original nonzero codeword has weight at least three. A weight-three codeword extends to weight four, proving that the minimum Hamming distance is exactly four.
For , extending the Hamming code of length seven gives the familiar linear code. A membership test detects every error of weight at most three, and nearest-word decoding corrects one error. Joint single-error correction and double-error detection uses the overall parity together with the original syndrome: a nonzero original syndrome with odd overall parity indicates a single error in an original coordinate, whereas a nonzero original syndrome with even overall parity detects a double error, under the assumption that at most two bits changed.
The binary linear code known as the Hamming code of length seven is the kernel of a parity-check matrix whose columns are all the nonzero vectors of . Its dimension is four. No one-column or two-column sum vanishes, but some three-column sum does, so its minimum Hamming distance is three. The syndrome of a one-bit error is its column, uniquely identifying the erroneous position.
The binary simplex code is the dual of the binary Hamming code. For redundancy it has parameters .
Its relation to the Hamming code is duality, not equality of the code families.
When the columns of are every nonzero vector in , a nonzero row vector defines a nonzero linear functional . Exactly half the input vectors take value : translation by any vector on which the functional is pairs its zero and one fibres. Removing the zero input removes only a zero value. Thus every nonzero word in the binary simplex code has Hamming weight .
A Hamming code has words, and each radius-one Hamming ball contains vectors. Its minimum distance is three, so these balls are disjoint, and their total size is . They therefore partition the ambient space, making the code perfect.

Ancestors (6)

  1. Linear code
  2. Coding theory
  3. Algebra
  4. Area of mathematics
  5. Mathematics
  6. Home

Synonyms (1)

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)

Hamming code is an error-detecting and error-correcting code used in digital communications and data storage. It was developed by Richard W. Hamming in the 1950s. Hamming codes can detect and correct single-bit errors and can detect two-bit errors in the transmitted data. ### Key Features of Hamming Code: 1. **Redundancy Bits**: Hamming codes add redundant bits (also called parity bits) to the data being transmitted.