# Syndrome decoding and error correction

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?

• $e_1$ and $e_4$ are leaders of the same coset so $e_1+e_4$ is a codeword. Therefore this code has $d\le2$. Dec 11, 2017 at 20:52
• Also, $e_1+e_5$ and $e_4+e_5$ also seem to be leaders of the coset corresponding to syndrome $110$. Dec 11, 2017 at 20:56
• @JyrkiLahtonen I gave this example to simplify my question. My question is about when can't I correct the errors? In this case you say $d \leqslant 2$, so does that mean that I can't correct any code? So the syndromes here are useless? Dec 11, 2017 at 21:03
• With that code you can correct a single error, if that error occurs in positions $2,3$ or $5$, when you have a unique coset leader. In other cases you can flip a coin between the coset leaders (still better than giving up!), or you can use soft information. If your receiver can tell that e.g. bit #1 was more reliable than bit #4, you can take advantage in some cases. Dec 11, 2017 at 21:25
• With soft information available you can successfully correct some errors even with a $d=2$ code. But that may be going too far for now? Dec 11, 2017 at 21:26

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.