1
$\begingroup$

What types of basic variations of the Hamming code are there and what are their objectives? I was taught the following version:

$ L = n + k $ $ n \geq \log_2M $ $ k \ge \log_2(n+k+1) $

where $M$ - number of alphabet symbols, $L$ - length of a codeword, $n$ - number of information bits, $k$ - number of parity bits. How does such a variation change the analysis and the algorithms involved as compared to the canonical way of coding?

Edit summary:

  • I switched the notation to the one I was provided with originally.
  • I switched the logarithm base from implicit $a$ to explicit 2.
  • 0
    @DilipSarwate That's why I initially provided the alternative notation - the original one seems like nothing I have seen in the textbooks. Please edit my question if you think switching the notation might help improve its readability. Do you have any idea what sort of Hamming code variation is it? The notation alteration might be due to the fact that my lecturer comes from Russia.2012-08-31

1 Answers 1

3

A canonical binary Hamming code consists of $2^{2^m - 1 - m}$ binary vectors of length $2^m - 1$. These vectors form a $(2^m - 1 - m)$-dimensional vector subspace of the $(2^m-1)$-dimensional vector space $\mathbb F_2^{2^m-1}$. The code is sometimes referred to as a perfect code. Each of the $2^{2^m-1}$ possible received vectors is either a codeword of the Hamming code or is at Hamming distance at most $1$ from exactly one codeword. Thus, every possible received vector is decodable using a nearest-neighbor strategy: map received vector $y$ into the nearest codeword $z$. If there were no transmission errors or there was one transmission error (that is, at most one of the $2^m-1$ transmitted bits got flipped from a $0$ to a $1$ or from a $1$ to a $0$, the $z$ that the decoder finds is the same as the $x$ that was transmitted. On the other hand, if more than one transmission error occurred, the $z$ that the decoder finds is not the same as the $x$ that was transmitted, and a decoder error occurs. It is important to understand that the decoder is quite unaware that it has found the wrong codeword.

For future reference, I note that the decoder obtains $z$ by changing (complementing) at most one bit in $y$.

Decoders for canonical Hamming codes are always able to determine a valid codeword as the nearest neighbor (in the Hamming metric) to the received word $y$. In contrast, many decoding algorithms (for other codes) fail to decode some possible received words $y$ because the algorithm is unable to determine the nearest codeword. In such cases, an undecodable error pattern is said to have been detected. The decoder usually passes on the received word $y$ to the end user together with an indication that $y$ is not a valid codeword. In many practical systems, a re-transmission is requested whenever such a decoding failure occurs.


A shortened Hamming code of length $2^m-1-s$ is a $(2^m-1-m-s)$-dimensional subspace of the $(2^m-1-m)$-dimensional space constituting the canonical Hamming code. This subspace is usually obtained by setting a fixed number $s$ of data bit positions to $0$. Commonly, for ease of implementation, the first $s$ data bit positions are set to $0$. The transmitted codeword is also shorter by $s$ positions because the first $s$ bits of each (canonical Hamming) codeword are not transmitted. Since the encoder and decoder are designed by a common intelligence, there is no need to transmit the $s$ leading zeroes in each codeword; the decoder can always insert them at the beginning of each received word if it needs them in order to carry out the decoding algorithm. In fact, let us assume for convenience that the decoder inserts the missing zeroes at the beginning of each codeword and then executes the canonical Hamming code decoding algorithm.

If zero or one of the transmitted bits in a codeword from a shortened Hamming code is received in error, the decoder will decode correctly, complementing the bit, if any, that is in error.

If more than one transmission error has occurred, then there are two possibilities to be considered.

  • changing one bit in the received $2^m-1-s$ bits maps $y$ into a codeword $z$ in the shortened code. This is a decoding error, just as with the canonical Hamming code.

  • Changing one bit in the prepended $s$ zero bits would change $000\cdots 0z$ into a codeword $00\cdots 010\cdots 0y$ in the canonical Hamming code. Since these $s$ bits must be $0$, the decoder concludes that an undecodable error pattern occurred in the $2^m-1-s$ bits that were actually transmitted, and this information can be passed on to the end user..

In summary, a decoder for a canonical Hamming code never fails to decode. It always produces a valid codeword as its output. On the other hand, the decoder for a shortened Hamming code can sometimes fail to decode and can signal the end user that the $y$ that it is sending on is not a valid codeword in the shortened code, and that there are at least two bit errors in $y$.

  • 0
    I think it's worth mentioning/emphasizing that simply cutting off the first $s$ bits of the codeword only works for canonical Hamming codes (i.e., where the generator matrix begins with the identity matrix). In that case, any data word beginning with $s$ zeroes is guaranteed to produce a codeword which also begins with $s$ zeroes. But for non-canonical Hamming codes, this is not necessarily the case. Non-canonical codes can still be shortened, but it is somewhat more complicated.2013-07-31