# How can I correct this Hamming code?

I'm trying to decode the following Hamming sequence (using EVEN parity and knowing there is a 1-bit error), which contains an ASCII value: 01100110101

I've tried to check for the correctness of each parity bit:

    p1 p2 d3 p4 d5 d6 d7 p8 d9 d10 d11
0  1  1  0  0  1  1  0  1   0   1
p1 - 0     1     0     1     1       1
p2 -    1  1        1  1         0   1
p4 -          0  0  1  1
p8 -                      0  1   0   1


p1, p4 and p8 checks are all even and correct.

p2 check is odd, hence the parity bit is incorrect and needs to be flipped. The actual message then becomes 00100110101 and the ASCII value can be read as 1011101.

Supposedly this value is incorrect - can anyone point out the mistake I made?

• Wouldn't Hamming Code be more appropriate in the Signal Processing StackExchange? – KingDuken Aug 9 '18 at 21:53
• @KingDuken It is perfectly appropriate in either. – koverman47 Aug 9 '18 at 22:25
• @polyethene Why do you think that this is wrong? It looks correct. Since p2 has the only odd sum, the bit p2 itself has to be wrong (all the other bits are used by at least 2 controll sums, which would mean that at least two bits are wrong). – Jakube Aug 10 '18 at 13:57
• I suggest you edit the question to describe where you got the idea that this is incorrect. If someone told you that, maybe they are wrong. If you read it somewhere, maybe whatever you read was in error. – D.W. Aug 10 '18 at 16:11
• Someone (this OP?) will pay 10 dollars if you answer the question here at reddit.com – Apass.Jack Aug 12 '18 at 22:24

The original problem is, I believe, the following.

When using Hamming code with EVEN parity for 7-bit ASCII characters, the following symbol is retrieved: 01100110101.

Assuming a 1-bit error, what was the original stored symbol? Write down your answer as a 7-bit binary, with no spaces.

OP's statement, "..., which contains an ASCII value: 01100110101", rephrases the original problem statement in a slightly confusing way, as pointed out by Yuval Filmus.

OP's procedure and result is correct, as said in Jakube's comment and indicated in D.W.'s comment. I have verified it as well according to Hamming code at wikipedia.

OP's procedure and result will not be repeated here.

Someone mentioned that "The usual Hamming code has length of the form $2^\ell−1$". For $\ell=4$, the usual Hamming code of length 15 is defined by the following table from wikipedia. If we truncate the last 4 columns, we will get the truncated Hamming code of length 11, which should be, presumably, the Hamming code used in OP's question.

"Supposedly this value is incorrect - can anyone point out the mistake I made?"

This is the turning point to the climax (or anti-climax). There are four possibilities.

1. A different kind of (truncated) Hamming code is used.
For example, all four parity bits could have been specified to be put together in the first four bits. That is, the first four bits, 0110 are the usual p1, p2, p4 and p8 parity bits while the remaining 0110101 are the data bits. In that case, we rearrange the bits to form the usual Hamming code as (p1)(p2)0(p4)110(p8)101, which is 01011100101. Then p1, p2, p4 check are odd while p8 is OK. So we flip the $1+2+4 =7$-th bit to obtain 01011110101. So the corrected data bit will be 0111101. Well, OP can check if this or something similar is the case.

2. "This is from a quiz on my university's LMS, the site is saying my answer is incorrect."
As D.W. suggested, maybe they are wrong. Maybe whatever you read was in error. There might be a typo in the statement of the quiz. There might be an error in the original answer by the quiz owner. There might be an error in the answer-checking process by the site. There might be a critical typo in OP's post. And so on.

3. Jakube, D.W., I, and, apparently, many others have not been able to find the mistake. That is very unlikely, though.

4. The last possibility stands for, as always, all other probably even lesser possibilities.