Probability of correcting errors
Error correcting codes are most simply described in terms of the errors they can certainly correct. For example, the Hadamard code used for the Mariner 9 probe to Mars encoded each 6-bit pixel to a 32-bit codeword in such a way that the original pixel could be recovered if no more than 7 bits were corrupted in transit.
What is theprobabilitythat a pixel could be repaired if corrupted? That depends on your probability model. We will assume that the probability of each bit being flipped isp and that errors are independent.
(Are errors independent, i.e. if a bit flips, is the next bit more or less likely to flip? That would depend on context.)
It's straight-forward to calculate the probability that 7 or fewer or fewer bits out of 32 flip; this is the cumulative distribution of a binomial random variable. The following Python code will return the probability ofk or fewer successes out ofn trials, each with probability of successp:
from scipy.stats import binom print(binom.cdf(k, n, p))
For example, if there is a 10% chance that each bit will flip, there's a 98.8% chance that 7 or fewer bits out of 32 will flip.
However this only gives alower bound on the probability of correcting an error. If eight bits flip in transit, we cannot tell with certainty which codeword was sent, but there will be a couple possibilities that stand out. We'll have to guess, but we've narrowed down the possibilities. With even more flipped bits, there's always a chance of recovering the original data. Still, the lower bound captures most of the probability of recovery.
Now suppose you're given a desired error recovery rate and have to determine what value ofp it can sustain. For example, someone might say they want a 98.8% chance of recovering a pixel correctly, and you could come back and sayp must be less than or equal to 0.1. This would be a conservative answer because as discussed above,p = 0.1 gives a pixel recovery probability of something more than 98.8, though it's messy to calculate how much more.
You could solve forp by trial and error, or you could use some more sophisticated math to computep directly. Given a probabilityF, you can solve forp such that the probability of up tok successes out ofn trials using the inverse of the regularized incomplete beta function.
from scipy.special import betaincinvp = 1 - betaincinv(n - k, k + 1, F)
Calculating F given n, k, and p could be a homework exercise in an introductory probability course. Solving for p given F, n, and k either requires some numerical programming or special functions and so would be a more challenging problem.
Related postsThe post Probability of correcting errors first appeared on John D. Cook.