Skip to main content
added 10 characters in body
Source Link
Yuval Filmus
  • 280.8k
  • 27
  • 317
  • 515

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 differing 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$.

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$.

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 differing 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$.

Source Link

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.