2
$\begingroup$

for the (7,4) Hamming code, I know how to decode a codeword using the syndrome decoding method, by just using the 3 parity bits, and it is correctable if there is just 1 error.

However, for the (8,4) extended Hamming code, I know how to decode the codewords correctly when there is no error or 1 error respectively. However, can we do that for the case of 2 errors?

$\endgroup$
1
$\begingroup$

Suppose the transmitted codeword is $\mathbf C$. If no errors occurred, or one error occurred, then $\mathbf C$ is the unique codeword that is at distance $1$ or less from the received word $\mathbf R$, and the decoding algorithm produces $\mathbf C$ as its output. When there are two errors, there is not a unique codeword that is at distance $2$ or less from the received word. One of the codewords at distance $2$ is $\mathbf C$, but there is at least one other such codeword. So, the decoding algorithm must be devised to handle this case. The possible options are

  • Declare a decoding failure, that is, tell the world that an uncorrectable error pattern has been detected. A less shameful alternative is used in ARQ (automatic-repeat-request) systems in which the receiver sends back a NACK signal to the transmitter which then retransmits $\mathbf C$. Thus, the outside world is not told that the transmission is being repeated over and over till the decoder is able to successfully decode, though the outside world may be able to infer this because it has to wait extra long for the next data bits to come out of the decoder.

  • Choose one of the codewords nearest to $\mathbf R$ and produce this as the decoder output. In this instance, the decoding might be correct because the decoder fortuitously chose $\mathbf C$, or it might be incorrect.

It is important to remember that decoding algorithms can output a wrong codeword even when they are fairly certain they got it right. If $\mathbf C$ is transmitted and the channel error pattern $\mathbf E$ is such that $\mathbf C + \mathbf E = \mathbf R$ happens to be another codeword $\hat{\mathbf C}$, then the decoder output will be $\hat{\mathbf C}$ and the decoder might even declare that it is confident that it has found the right codeword because it did not find any errors in $\mathbf R$; it matched $\hat{\mathbf C}$ in every bit! Pride, as we are told, goeth before a fall.


Finally, turning to the OP's specific question about the $(8,4)$ extended Hamming code, the decoder can tell that an even number of errors have occurred if the XOR sum of the $8$ received bits is $0$ and the rest of the syndrome (the part that is exactly the same as in the $(7,4)$ Hamming code) is nonzero. So, whenever this happens, the decoder can declare a decoding failure or send a NACK to the transmitter, or output a codeword. An easy way out in this last case is to assume that the overall parity bit is in error (and thus flip it) and then use the rest of the nonzero syndrome to correct one error in the other $7$ bits exactly as if they were from a $(7,4)$ (non-extended) Hamming code. This will give a codeword $\hat{\mathbf C}$ that is at distance $2$ from $\mathbf R$ and it will even be the transmitted codeword $\mathbf C$ if there were exactly two transmission errors, one in the $7$ bits and one in the overall parity bit.

|improve this answer|||||
$\endgroup$

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.