extended Hamming code

Question

Hello I am trying to do an exercise, but I got stuck on it since till now I was using Hamming $\require{cancel}\cancel{(7, 4)}$ $[8,4]$? and everything was going fine and I understand it. So I have the word $1??10010$, which was received over a binary erasure channel, which garbled the second and third bit, I have to find the second and the third bit, could you please help me thanks in advance.

Answer 1

If an errors-only decoding algorithm is available for a binary code, then there is an easy way to decode erasures. For this specific code, there is a decoding algorithm that can correct single errors and detect two errors. So, the erasures-only decoding algorithm works as follows.

• Step I: Replace all the erasures by $0$ to create a purely binary "received" word $\mathbf r_0$ and apply the errors-only decoding algorithm to find the most likely transmitted codeword $\mathbf c_0$. Note that it is possible that the decoding algorithm will fail to decode and report that there are two errors in $\mathbf r_0$ and it has no idea what the most likely transmitted codeword is.

• Step II: Replace all the erasures by $1$ to create a purely binary "received" word $\mathbf r_1$ and apply the errors-only decoding algorithm to find the most likely transmitted codeword $\mathbf c_1$. Note that it is possible that the decoding algorithm will fail to decode and report that there are two errors in $\mathbf r_1$ and it has no idea what the most likely transmitted codeword is.

Now the replacements of the erasures are guaranteed to produce one of two possible results:

(i) exactly one of $\mathbf r_0$ and $\mathbf r_1$ is indeed a valid codeword, and so that particular decoding will produce a most likely transmitted codeword while the other decoding will result in a decoding failure,

and

(ii) both $\mathbf r_0$ and $\mathbf r_1$ are at distance $1$ from a codeword $\mathbf c$ and so both decodings will result in $\mathbf c$ being returned as the most likely transmitted codeword.

Consequently, Step III of the erasures-only decoding algorithm is

• Step III: If exactly one Step I or Step II results in a valid codeword, return that codeword as the most likely transmitted codeword. If both Steps I and II return the same valid codeword, return that codeword as the most likely transmitted codeword.

---

Note added in response to Jyrki Lahtonen's comments:
The answer above was written in response to the specific question about the binary $[8,4]$ extended Hamming code, but, as noted in Jyrki's comments, with just a minor modification, the algorithm also works for arbitrary binary codes on an errors-and-erasures channel instead of the erasures only channel.

A binary code with minimum distance $d$ can correct up to $t = \left\lfloor\frac{d-1}{2}\right\rfloor$ errors. Now suppose that the received word $\mathbf r$ has $e$ errors and $\varepsilon$ erasures in it. Note that the receiver knows the locations of $\varepsilon$ erasures but it does not know the location of the errors; indeed, the receiver does not even know the value of $e$ ! Thus, Steps I and II create purported received words $\mathbf r_0$ and $\mathbf r_1$ at distances $e+\varepsilon_0$ and $e+\varepsilon_1$ from the transmitted codeword where $\varepsilon_0 + \varepsilon_1 = \varepsilon$. Now, if $2e+\varepsilon < d$, then at least one (possibly both) of $\mathbf r_0$ and $\mathbf r_1$ is at distance at most $t$ from the transmitted codeword. Consequently, at least one (and possibly both) of $\mathbf c_0$ and $\mathbf c_1$ is the transmitted codeword. While we are guaranteed that at least one of Steps I and II returns the transmitted codeword, the other Step might result in a decoder failure (and we know already how to handle that case in Step III), but, in general, it is possible for the other Step to return a different codeword.

Example: Suppose that a codeword of weight $4$ in the binary $[8,4]$ extended Hamming code is transmitted and that three of the four $1$'s get erased. Then, $\mathbf r_0$ has weight $1$ and gets decoded into the all-$0$ codeword with one error being corrected in the decoding process, while $\mathbf r_1$ is the transmitted codeword itself and so gets decoded into the transmitted codeword with no errors being corrected in the decoding process.

So, what should be done when Steps I and II return different codewords $\mathbf c_0$ and $\mathbf c_1$? The answer is that Step III should return the result of whichever Step corrected fewer errors. Is it possible for Steps I and II to correct the same number of errors? Yes, but in this case, they are guaranteed to return the same codeword, not different codewords as long as the constraint $2e+\varepsilon < d$ is satisfied. Of course, the decoder does not know whether the constraint is satisfied or not, and, as Jyrki's example in the comments shows, it is possible for Steps I and II to return different codewords with the same number of errors being corrected in each case.

In the absence of the side information referred to in Jyrki's comment, we modify Step III slightly to

• Step III: If exactly one Step I or Step II results in a valid codeword, return that codeword as the most likely transmitted codeword. If both Steps I and II return the same valid codeword, return that codeword as the most likely transmitted codeword. If Steps I and II result in different codewords, then return the result of whichever Step corrected fewer errors, but if both Steps corrected the same number of errors, then declare a decoding failure.