I have a basic question about Hamming distances, something confuse me in the book I'm reading about it.

Let's assume we have a codeword $y$ that received an error $e$. Thus we had the following event:

$$ y_0 \rightarrow y'=y_0+e $$

In Nielsen & Chuang, page 449, he says:

Provided the probability of a bit flip is less than 1/2, the most likely codeword to have been encoded is the codeword y which minimizes the number of bit flips needed to get from y to y',that is,which minimizes wt(e)= d(y, y').

Where $d(a,b)$ is the Hamming distance between $a$ and $b$, and $wt(e)$ is the Hamming weight of $e$, which is $d(e,0)$.

My question is the following:

I agree that if there is more probability of no bit flip than the probability to have one, then the most likely codeword is the closest one from $y'$, thus a codeword $y$ minimising $d(y,y')$.

However, as he writes $d(y,y')=wt(e)$, he seems to assume that the closest vector from $y'$ is necesseraly the one we encoded. Which for me is not true in general, the error could have put us closer to another encoded word than the one we encoded right ?

Where is my misunderstanding here ?

  • $\begingroup$ Maybe I didn't understand your question but I feel you have possibly answered your own question. The part that you agree with is equivalent to what you have problem with. Since you agree that y minimizes distance over all the codewords isn't that same the statement? $\endgroup$ – Root Jul 25 at 13:48
  • $\begingroup$ @Root I can reformulate my question as: why do we have $d(y,y')=wt(e)$ ? Why is it equal to the rhs. For me it is not obvious. I hope it is more clear now =) $\endgroup$ – StarBucK Jul 25 at 13:58
  • $\begingroup$ Now if I understand things right your question is why $y-y'=e$? $\endgroup$ – Root Jul 25 at 14:00
  • $\begingroup$ @Root Yes that's it. For me it is only true if $y$ was the originally encoded message $y_0$ but I could expect it as not being true in general $\endgroup$ – StarBucK Jul 25 at 14:03
  • $\begingroup$ If $y$ is different from $y_0$ and $y_0$ is closer to $y'$ than $y$ then that is contradicting with the part you agree with. $\endgroup$ – Root Jul 25 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.