[Solved]: Encoding the sequence 0110 and determining parity, data bit and value

Problem Detail: 

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

eg.1

eg.2

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!

Asked By : methuselah

Answered By : Ran G.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1458