3
$\begingroup$

Why is the threshold for detecting errors $2d+1$? I am aware that the question has been asked before, for example here, but the answers provided didn't really justify why the formula contains $+1$.

So why is there $+1$ in the equation?

$\endgroup$
  • $\begingroup$ What is your question? What former question are you referring to? $\endgroup$ – Yuval Filmus Oct 27 '19 at 16:52
  • $\begingroup$ cs.stackexchange.com/questions/32592/… was referring to this one, but i didn't understand the +1 $\endgroup$ – Ryan gomez Oct 27 '19 at 17:10
  • $\begingroup$ Think of a collection of disjoint spheres of radius $d$ (d-error correcting code); then codewords are $2d+1$ distance from eachother, because the distance between spheres must be at least $1$ (since it's a discrete space). However, only up to $2d$ errors can be always detected, not $2d+1$ $\endgroup$ – Real Nov 27 '19 at 13:31
1
$\begingroup$

Let's look at a simple, concrete example where $d=4$. Suppose the codebook is $C = \{0000,1111\}$. This means the sender transmits either the codeword $0000$ or the codeword $1111$ during each block of communication, and no other binary strings are transmitted. For example, to transmit a $0$ bit, the string $0000$ is transmitted, and to transmit the $1$ bit, the string $1111$ is transmitted. The hamming distance of this code is $4$.

Suppose the sender transmits one of the above two codewords, and suppose the receiver gets $0010$. Then the receiver knows that the transmitted codeword has been corrupted by the noisy channel because the received vector is not either of the two transmitted codewords (only $0000$ or $1111$ could have been transmitted). Thus, the receiver is able to "detect" that an error has occurred (i.e. that the transmitted codeword has been corrupted by the noisy channel). If the noisy channel flips up to any $3$ bits, the receiver will detect an error, but if the channel flips all $4$ bits - say $0000$ was transmitted and $1111$ was received - then the receiver will wrongly conclude that the received codeword $1111$ was the transmitted codeword. Thus, we say this code can detect up to $3$ bit errors because the minimum distance between any two codewords in this codebook is at least $4$. If only up to $3$ bits are flipped, then such an error can't convert one codeword into another because any two codewords differ in at least $4$ positions. More generally, if the hamming distance is $d$, then up to $d-1$ errors can be detected.

Suppose again that the received vector is $0010$. Then, the receiver will detect that an error has occurred. But can it correct the error and figure out which codeword was transmitted? The receiver can use the nearest-neighbor decoding rule, which says if the received vector is not one of the codewords (in the codebook), then make the decision that the transmitted codeword is the one closest (in hamming distance) to the received vector. This is a good rule when the probability of a bit getting flipped is small. Because $0000$ is closer to $0010$, the receiver concludes that $0000$ was transmitted. But what if the received vector is $0011$? Then, both $0000$ and $1111$ are equally distant from the received vector. The receiver will not be able to correct $2$ errors (it can only detect that an error has occurred, but not correct it).

Ideally, we would like any two codewords to differ in a large number of positions. Define the sphere of radius $d$ centered around a codeword $x$ to be the set of all codewords which differ from $x$ in at most $d$ positions. For example, the sphere of radius $1$ centered at $0000$ is the subset of vectors $\{0000,1000, 0100, 0010, 0001\}$. Because the sphere of radius $1$ centered at $0000$ and the sphere of radius $1$ centered at $1111$ are disjoint, the nearest-neighbor decoding rule will decode correctly if the number of bit flips is at most $1$. The above code of hamming distance $4$ can correct up to $\lfloor (4-1)/2 \rfloor = 1$ error. Because of the possibility that the received vector can be $0011$ or $0101$, etc, the code can't correct $2$ errors.

More generally, if the spheres of radius $d$ centered at any two codewords in the codebook are disjoint, then the nearest-neighbor decoding rule will correct up to $d$ errors. For any two such spheres to be disjoint, any two codewords must differ in at least $2d+1$ positions. If there exist some two codewords in $2d$ or fewer positions, then these two codewords could both be the nearest-neighbors of some received vector. Visualize in your mind the picture in $3$ dimensions of two spheres of radius $d$, which end up being disjoint because the distance between their centers is $2d+1$.

Thus, if the hamming distance is $2d+1$, the code can correct up to $d$ errors. Or, if the hamming distance is $d$, the code can correct up to $\lfloor (d-1)/2 \rfloor$ errors.

$\endgroup$
0
$\begingroup$

A code $C$ can detect up to $d$ errors if the minimal distance between two codewords of $C$ is at least $d+1$. Suppose that the sent codeword was $x$, and the received one was $x'$, which differs from $x$ by at least 1 and at most $d$ symbols. Since the minimal distance is at least $d+1$, $x'$ is not a codeword, and so the error is detected.

A code $C$ can correct up to $d$ errors if the minimal distance between two codewords of $C$ is at least $2d+1$. Suppose that the sent codeword was $x$, and the received one was $x'$, which differs from $x$ by at most $d$ symbols. I claim that $x$ is the only codeword which differs from $x'$ by at most $d$ symbols, and so $x'$ can be corrected to $x$. Otherwise, there would be another codeword $y$ which differs from $x'$ by at most $d$ symbols, but then $x,y$ would differ by at most $2d$ symbols.

$\endgroup$
  • $\begingroup$ so basically the +1 is because of the initial d+1? $\endgroup$ – Ryan gomez Oct 27 '19 at 17:15
  • $\begingroup$ how does the error detection code knows which is the correct codeword if the error is equidistant from x and y since from what i understood based on what u wrote, the 2d is essentially extending the detection range from x to y $\endgroup$ – Ryan gomez Oct 27 '19 at 17:22
  • $\begingroup$ The correct codeword is not equidistant from $x$ and $y$. There is only one codeword at distance at most $d$ from $x'$, namely $x$. $\endgroup$ – Yuval Filmus Oct 27 '19 at 18:25
  • $\begingroup$ can it happen that x' is the same number of d steps from x and y and if yes what will the error correction code do? $\endgroup$ – Ryan gomez Oct 28 '19 at 0:06
  • $\begingroup$ I already answered this. $\endgroup$ – Yuval Filmus Oct 28 '19 at 5:31

Your Answer

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

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