1

I have a query on (7,4) Hamming code.

The generator polynomial for this is \$g(x) = x^3 + x + 1\$. The non-systematic code for the message signal \$m(x)\$ is \$c(x) = m(x)g(x)\$

The above procedure is giving a different answer from what is given in many of books. The (7,4) Hamming code is given as:

\$\{P_1 P_2 M_1 P_3 M_2 M_3 M_4\}\$ is the code word for \$\{M_4 M_3 M_2 M_1\}\$ message signal where

\$P_1\$ is even parity bit for \$M_1M_2M_4\$

\$P_2\$ is even parity bit for \$M_1M_3M_4\$ and

\$P_3\$ is even parity bit for \$M_2M_3M_4\$

My query is that the above mentioned is not obtained both by systematic and non-systematic coding procedures. Can you please explain me where am I going wrong. (is it the generator polynomial or coding procedure ?)

I don't know whether it is the correct stack to post this question. Couldn't find one for communication engineering hence posted here.

Thanks in advance.

KillaKem
  • 1,740
  • 2
  • 13
  • 26
METALHEAD
  • 165
  • 1
  • 3
  • 11
  • It's 40 years since I did this in my comms course, so I'm not going to answer (might get something wrong), but it's about the arrangement of the transmitted codeword. Putting the bits in that order means the syndrome has the same value as the position of the errored bit. Pull apart what g(x) (polynomial) is doing when you multiply, and you should find it doing what the 3 parity sums do. G(x) (matrix) will need to be 7x4 to make the transmistted word under matrix multiplication, just adding unit rows and re-arranging g(x). – Neil_UK Feb 25 '17 at 09:15

1 Answers1

3

(7,4)-Hamming code can be implemented with many different generator/parity-check matrix pairs, or in other words just because an implementation is said to be a (7,4)-Hamming code does not mean that the codewords used will be necessarily be of form \$\{P_1P_2M_1P_4M_2M_3M_4\}\$.

Having the codewords be in the form given above gives the advantage of the value of the syndrome equating the error location, so after we get the syndrome we can just compute the decimal value of our syndrome and just flip that bit. If the codewords are in another form then we will need to match the syndrome obtained to the appropriate column of the parity check matrix in order to evaluate the error location.

Using the classic implementation of the (7,4)-Hamming code (i.e with codewords of form \$\{P_1P_2M_1P_4M_2M_3M_4\}\$) we get a parity check matrix, \$H_1\$, where

$$H_1 = \left( \begin{array}{ccccccc} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array} \right) $$

If there is an error in bit position \$i\$, then the syndrome will be equal to \$c_i\$, where \$c_i\$ is the \$i^{th}\$ column of the parity check matrix. So looking at the parity check matrix in this case you can easily see that the value of the syndrome will equate to the error location.

If you use a non-systematic \$g(x)\$ then the parity check matrix will not have the very nice property we have above. You would need to calculate the syndrome and compare it against each column of the parity check matrix to see which one it matches with, the column number it matches with will be your error location i.e if it matches will column \$c_i\$ then the error is at location \$i\$. The columns of the parity check matrix (and hence the entire parity check matrix H) of the code can be computed directly using \$g(x)\$ and the set of error monomials \$e(x)\$ (\$e(x) = x^i\$). This is done by computing columns as

$$ c_i(x) = \text{Remainder} \left( \frac{e_i(x)}{g(x)} \right) = \text{Remainder} \left( \frac{x^i}{g(x)} \right) $$

where all computations are in GF(2).

KillaKem
  • 1,740
  • 2
  • 13
  • 26