0
$\begingroup$

This is about error control coding formula

$$ d \ge c+u+1$$

of a block code, with

  • $c$ being the number of correctable errors,
  • $u$ being the number of uncorrectable errors, and
  • $d$ being the distance of the code.

Per my understanding, this is applicable for all the block codes - linear or not. Now let us dissect the repeat code with respect to this formula.

Repeat code with $k=1$, $n=7$: Let us say we repeat each bit 7 times. $\mathrm 0$ is sent as $\mathrm 0000000$ and $\mathrm 1$ is sent $\mathrm 1111111$. $d = 7$ in this case. We conclude that all these combinations below are possible:

$$\begin{array}{|c|c|}\hline c & u \\ \hline 6& 0\\ 5& 1\\ 4& 2\\ 3& 3\\ 2& 4\\ 1& 5\\ 0& 6\\\hline \end{array}$$

  • Now let us consider $c=3$ and $u =3$. With respect to the repeat code we are discussing above, what does it really mean?
  • Can someone kindly explain with examples ?
  • How does the explanation change with one or two more of the above combinations?
$\endgroup$
  • $\begingroup$ I realise after posting the question that c<=d so the last 3 combinations are not possible. $\endgroup$ – Seetha Rama Raju Sanapala Feb 7 '16 at 6:07
  • $\begingroup$ the first three combinations aren't possible; the last three are merely unnecessarily bad decoding. $\endgroup$ – Marcus Müller Feb 7 '16 at 10:25
  • $\begingroup$ Because I could not understand it well, I went through several videos and the books but the concept is simple enough I think now. You have the minimum distance d between any pair of codes. So you can have upto d-1 errors and still be able to detect you are in error where as d errors might convert one codeword into another. If we require that a max of t errors be corrected we require that d>= 2t+1 so that the errors of one codeword do not overlap with another codeword that has suffered t errors. $\endgroup$ – Seetha Rama Raju Sanapala Feb 7 '16 at 13:45
  • $\begingroup$ How do I put this... why didn't you do that research before asking here? Considerable time went into answering your question. $\endgroup$ – Marcus Müller Feb 7 '16 at 14:15
  • $\begingroup$ @Marcus Muller: First of all, sorry. But like I said before, I went through several videos and texts of videos etc before posting the question. Some one was talking about ball, someone else was talking about sphere and detectable errors etc. I have worked out several problems but it was all confusing, I could not even frame the question properly. Now it is clear. $\endgroup$ – Seetha Rama Raju Sanapala Feb 10 '16 at 9:34
1
$\begingroup$

You have to realize that $d$ is specifically the minimum distance in your code, i.e. the distance between the to code words that are closest together.

And $u$ is not exactly the number of "uncorrectable errors", but the maximum number of errors that can definitely be detected, but not corrected correctly.

Note that "distance" here is the hamming distance, i.e. the number of bits you'd have to flip until you end up with another codeword.

We conclude that all these combinations below are possible: ...

False. The first three lines ($c\in\{6,5,4\}$) are impossible.

Also, your table doesn't make much sense. Given a code, you'd always correct as many errors as possible¹, so for a given code, $c$ is given, and $u$ is given. The fact that

$$\begin{align*} c &=& \#(\text{detectable bit flips, which ARE correctable})\\ &=& \#(\text{total detectable bit flips}) &- \#(\text{detectable bit flips, which AREN'T correctable})\\ &=& (d-1) &- u\tag{*} \end{align*}$$

is just your definition of $c$.

A $k=7$ repetition code can never correct 6, 5 or even 4 bit errors; I find "you can't flip more than $\left\lfloor \frac d2 \right\rfloor$ bits until it looks more like another codeword than like the original" highly intuitive, so the only way I can explain this is by example:

take your 0 code word, and flip 4 bits:

0 0 0 0 0 0 0 
0 1 1 1 0 1 0

Now, that looks much more like the 1 keyword, doesn't it? In fact, 0 1 1 1 0 1 0 has a hamming distance of 4 to the 0 code word, and a hamming distance of 3 to the 1 code word, so it's closer to 1, and will correctly be identified as error, but falsely get corrected to 1.

Looking at this, any error is detectable, as long less than the minimum distance bits are flipped (for any code, pretty logical, isn't it?). So,

$$c_\text{max} = d -1 \text.$$

Now, your formula simply "happens" when you put in your definition of $c$ and $u$, see $(*)$ above.

There's not much to explain here: for repitition codes $d=k$, and you can always correct $\left\lfloor \frac d2 \right\rfloor=\left\lfloor \frac k2 \right\rfloor$ bit errors and detect $d-1=k-1$ errors.

One can't explain your other combinations, as they are basically wrong for any maximum likelihood decoder. You can of course work "worse" than possible, but especially for the repitition codes, summing up the received bits and deciding whether the result is larger than $\frac k2$ gives you $c=\left\lfloor \frac k2 \right\rfloor$ and thus, $u=(d-1)-c=(k-1)-\left\lfloor \frac k2 \right\rfloor =\left\lceil \frac{k-1}{2}\right\rceil $, and, in your $k=7$ case, $c=u=3$.


¹: point is that there's many codes where you can't, with reasonable effort, correct as much correctable errors as the code would allow you too, that means that $c \le \left\lfloor \frac d2 \right\rfloor$ in general, and that's why $d\ge c+u +1$ and not $d = c+u +1$. However, repetition codes are so trivial, we can truly Maximum-Likelihood-decode them and correct $\left\lfloor \frac d2 \right\rfloor$ errors.

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