3
$\begingroup$

I've been struggling with several Hamming code/error detection questions because the logic behind it doesn't seem to make sense.

eg.1

enter image description here

eg.2

enter image description here

I don't really understand the above two examples and the calculations taking place.

How were the conclusions reached concerning the categories of bin position (dec/bin), parity/data bit and value in e.g 1?

Secondly I don't understand the process taking place in e.g. 2 at all. Does it follow that:

General rule: For any code C,

  • errors of less than $d(C)$ bits can be detected,
  • errors of less than $d(C)/2$ bits can be corrected.

Definition: A code C with $d(C) \geq 3$ is called error-correcting.

If this is correct then how would I put it into practice. Would really appreciate some assistance!

Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome! Please add proper references for your images. $\endgroup$
    – Raphael ♦
    Apr 23, 2012 at 17:13

1 Answer 1

Reset to default
5
$\begingroup$

Well, these examples are not easy to read, by they are indeed correct.

e.g.1:

The word to code has 4 bits, and lets call them $b_1 b_2 b_3 b_4$. To this "data" word add 3 parity bits (adding is over $GF(2)$):

  • $p_1 = b_1 \oplus b_2 \oplus b_3$,
  • $p_2 = b_1 \oplus b_2 \oplus b_4$, and
  • $p_3 = b_1 \oplus b_3 \oplus b_4$.

[remark: for odd parity, add "1" to each equation, e.g., $p_1 = b_1 \oplus b_2 \oplus b_3 \oplus 1$]

Then we transmit the code word

$$C= b_1 b_2 b_3 p_1 b_4 p_2 p_3$$

Why this particular order? They want the "position" of the parity bits to be "1" "2" and "4" (starting to count from the right side) which corresponds to bit positions "001" "010" and "100". This is meaningful in order for the decoding to work as they demonstrate.

You can see by the colors which parity bit belongs to which data-bits.

(Awful explanation in my eye, but, oh well.)

as for the decoding: e.g. 2

the procedure to decode is the following:

  1. recompute $p_1, p_2, p_3$ from the received $b_1b_2b_3b_4$
  2. if you got the same values as the received codeword (the $p_1,..$ you received) - then everything is fine
  3. Otherwise - the error is located in position $x$ where $x$ is the sum of locations of the parity bits $\{1,2,4\}$. For instance, if only $p_3$ is incorrect, than the error is in bit no "1" - $p_1$ itself is the only one got flipped. If $p_3$ and $p_1$ mismatch, than you need to flip the bit in location $1+4=5$, that is, $b_3$.

Note that this code fixes only a single error.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Eg1) Why do we add 3 parity bits to 0110? $\endgroup$
    – methuselah
    Apr 23, 2012 at 11:41
  • $\begingroup$ Eg1) How do you compute p1, p2 and p3? $\endgroup$
    – methuselah
    Apr 23, 2012 at 11:53
  • $\begingroup$ @methusaleh why 3 bits? That's the code.. (this will make the code distance 3, which will allow correcting $\lfloor 3/2\rfloor=1$ errors. $\endgroup$
    – Ran G.
    Apr 23, 2012 at 17:08
  • $\begingroup$ @methusaleh to compute $p_1$ you add the bits written in the answer $\mod 2$. in other words take the XOR of them: $p_1 = b_1 \text{ XOR } b_2 \text{ XOR } b_3$. $\endgroup$
    – Ran G.
    Apr 23, 2012 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.