Hamming Codes

The Hamming distance is a special measure of distance between two code words. It counts the number of positions where two symbols are different. For binary codes it corresponds to the number of bits that are different in two code words.

The Hamming distance has uses in coding theory for error detection and correction.

A binary code that uses every possible codeword for a given number of bits has Hamming distance 1. This is the minimum; Hamming distance 0 makes no sense. A code with Hamming distance 2 can detect 1-bit errors. A code with Hamming distance 3 can detect 2-bit errors and correct 1-bit errors, and so on.

Here is a little code snipped that calculates the Hamming distance between two code words:

template<
  /// Integer type of the code word, i.e. int, or unsigned long long, etc.
  typename T>
/// Calculate the Hamming distance for two code words.
//!
//! The algorithm works for different types of code words and calculates the
//! Hamming distance between them.
//!
//! /return The Hamming distance between the two code words.
unsigned char hamming_distance(T x, T y)
{
  unsigned char hamming_distance = 0;

  T d = x ^ y;
  for (int i=0; i<sizeof(T)*8; ++i)
    hamming_distance += (d & (1 << i)) ? 1 : 0;
  return hamming_distance;
}

Here is some code that can generate a Hamming code with a given number of bits and a given distance.

template< /// Integer type of the code word, i.e. int, or unsigned long long, etc. 
  typename T>
/// Make a Hamming code.
//!
//! The algorithm starts with a code of zero and finds the first code word with
//! the desired distance. It continues and finds the next code word with the
//! desired distance to both zero and the code word found in the previous step.
//! It continues further and finds the next code word with the desired distance
//! to all previously found code words, until all the candidates are exhausted.
//!
//! /return The code words of the Hamming code arranged in a vector.
std::vector make_hamming_code(
  /// The number of bits used in the Hamming code.
  unsigned char bits,
  /// The desired Hamming distance used in the Hamming code.
  unsigned char distance)
{
  std::vector hamming_code;
  hamming_code.push_back(0);
  for (T i=0; i<(1<<bits); ++i)
  {
    unsigned char found_distance=0;
    for (std::vector::const_iterator j=hamming_code.begin();
      j!=hamming_code.end(); ++j)
    {
      found_distance = hamming_distance(*j, i);
      if (found_distance < distance)
        break;
    }

    if (found_distance < distance)
      continue;

    hamming_code.push_back(i);
  }

  return hamming_code;
}

The code returned is not the only possible Hamming code with the given characteristics (number of bits and distance). In particular, the bits of any two bit-positions in all code words can be swapped, and the bits of any bit-position in all code words can be inverted. These operations do not affect the calculation of the Hamming distance, and thus transform one Hamming code into another Hamming code with the same characteristics.