Syndrome decoding and error correction

1k Views Asked by At

A corollary says that: A code $C$ with minimum distance $d$ detects $d−1$ errors, and only corrects $⌊\frac{d-1}{2}⌋$ errors .

So my question is:

Given a generating matrix $G$ , if some $y$ is received and I want to know what codeword was transmitted using syndrome decoding:

if $d=2$ and $t=0$ I can't find the codeword transmitted?

If $d=3,t=1$ I can only correct errors with weight $1$?

For example, If I reach this step: \begin{array}{|c|c|} \hline Syndromes & Coset\ leaders \\ \hline 000&0 \\ \hline 001&e_1=e_4 \\ \hline 100&e_2 \\ \hline 010&e_3 \\ \hline 111&e_5 \\ \hline 110&e_2+e_3 \\ \hline 011&e_1+e_3=e_4+e_3 \\ \hline 101&e_1+e_2=e_4+e_2 \\ \hline \end{array}

If $S(y)=110$, we have $e_2+e_3$ that has weight $2$. So if $d=3$ I can't correct the error?

1

There are 1 best solutions below

0
On BEST ANSWER

A commom confusion here. When the corollary says that "you can correct $⌊\frac{d-1}{2}⌋$ errors", it's actually saying that you can guarantee that you'll be able to correct all errors with at most that weight. But that doesn't mean that you won't be able to correct some other errors.

To begin with your second question:

If $d=3$, $t=1$ I can only correct errors with weight 1?

In that case you can guarantee that you'll correct all errors with weight 1. But perhaps you'll also correct succesfully some errors with weight 2 (and perhaps even more). You know that you won't be able to correct all errors with weight 2 or more.

More in detail, you'll be able to correct some errors with weight 2 if your syndrome table has some coset leader with that weight. In the classic case of the $(7,4)$ Hamming code, each coset leader covers one of the $1-$weight errors, hence here you can't correct any error with weight 2 or more.

if $d=2$ and $t=0$ I can't find the codeword transmitted?

You can't guarantee that you'll find the correct codeword, even if a single error occurs. But, again, you might correct some. If you think about it, $d=2$ corresponds to a single parity bit added. Half of the $2^n$ tuples correspond to codewords, half don't (like the white and black squares on a chessboard, if you like the anallogy - but bear in mind that the tuples actually live in the vertices of an hipercube). Then, a single error takes you to a invalid (non codeword) tuple, which has several valid codewords at distance one. It should be obvious that in this case you know there was an error (you can detect the error), but you cannot correct with certainty. If you insist on trying to correcting it, using probably syndrome decoding, you'll have to pick a coset leader among several equally probable error patterns. Sometimes you'll be lucky.