I'm trying to find out whether my communication protocol should have redundant information padded, in order to help the receiver correct the error (error correction code, ECC) without needing a retransmission. In other words, I'm trying to find the point at which it's more interesting to have a small overhead for each message, rather than a whole message retransmission from time to time. If needed, I assume I can ask God to tell me if the packet is altered or not.

Let's take a ECC for which, when t extra bits added, t/2 corrections are possible. Each bit has an error rate of p, so the probability P that the message gets altered (assuming independent errors) is $P=1-(1-p)^n$, where n is the message length. The probability that less than t/2 error occurs is: $$\displaystyle P(X\leq\frac t2)=\sum_{k=0}^{\lfloor\frac t2\rfloor}{n+t\choose k}p^k(1-p)^{n+t-k}$$ I think I have done most of the work but I'm not sure how to go from there to solve my initial question. I think I will need to solve the inequation $P\leq P(x\leq\frac t2)$, but I'm not sure, and in any case I don't know how to solve it. If it turns out to be infeasible to solve, I can give numerical values to help with the resolution.


You know:

a) The probability that the message has been altered,

b) The probability that the message has either not been altered ($k=0$) or that it has been altered and the ECC will be able to fix it ($P(X \leq {{t}\over{2}}$)).

From b), you can figure out the probability that the message has been altered and the ECC will not be able to fix it.

Therefore, you can figure out the fraction of the time the message would have to be resent given no ECC, let us call it $p_n$ and the fraction of the time it would have to be resent given the ECC, $p_E$.

The expected number of bits sent with no ECC = $n/(1-p_n)$ (we have to take into account that the resent message also might be altered, requiring more than one retransmission, hence the division by $1-p_n$).

The expected number of bits sent with the ECC = $(n+t)/(1-p_E)$.

From this, I think you should be able to get through the rest of the problem.

  • $\begingroup$ I have the pieces of the puzzle but I'm failing to put them together. Maybe I'm just tired. I would say $p_n=1-P(X<=t/2)$ and $p_E=P$. $\endgroup$
    – TimZEI
    Jun 13 '12 at 3:27
  • $\begingroup$ Yeah, it happens. You have $p_n$ and $p_E$ reversed in your comment. $\endgroup$
    – jbowman
    Jun 13 '12 at 13:08
  • $\begingroup$ Okay, but in any case, I don't see how to proceed. Am I to compare the two values n/(1-P) and (n+t)/P(X<=t/2) ? I wouldn't know how to do that... Is there at least a solution (which is to say, a threshold depending on n and p after which t should not be null, so in other words, there's so much noise that ECC is helpful) ? Even if I fix n, to say n=10^4, I still wouldn't know how to solve this equation, specially how to simplify the sum. Can you help please ? $\endgroup$
    – TimZEI
    Jun 13 '12 at 15:10
  • $\begingroup$ Start out with $t=2$, solve for the ECC expected value, then go to $t=4$, ... Try plotting out the resultant curve and draw a line across at the non-ECC expected value. No need to simplify the sum, many languages - R, Matlab - have the cumulative distribution of the Binomial programmed into them. $\endgroup$
    – jbowman
    Jun 13 '12 at 18:50
  • $\begingroup$ So there is no way to find out mathematically (with calculus) what is the correct value ? In other words, to solve the equation ? Even if n and p are constants ? $\endgroup$
    – TimZEI
    Jun 14 '12 at 13:34

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.