Monday, June 15, 2009

C code for Confidence level computation for BER testing

Article is "statistical confidence levels for estimating error probability".

The first function calculates the confidence level (CL) given the number bit errors measured (n), the total number of bits tested (N), and the expected BER (ph).


// CL = 1 - (\Sigma^{0}_{N}(n * ph)^k/(k!)) * e^{-n * ph}
double solve_CL_from_N_n_ph(unsigned N, double n, double ph)
{
double emnp = exp(-n * ph);
double sum = 1;
double product = 1;
for(unsigned k = 1; k <= N; k++)
{
product *= (n * ph / k);
sum += product;
}
sum *= emnp;
return(1 - sum);
}


The second function computes the minimum number of bits that need to be tested to confirm a certain confidence level (CL) of an expected BER (ph). If the number of bit errors measured upon receiving of such number of bits is less than N, the hypothesis is confirmed positively. The formula to compute n given N greater than 0 is mathematically hard to solve. This function solves by trying out different values of n in a binary search manner using the first function (which is reverse of the function in question) until n is converged to a certain extent.

double solve_n_from_ph_CL_N(double ph, double CL, unsigned N)
{
if(N==0)
return(-log(1-CL)/ph);
else
{
// solve n using binary search, based on "solve_CL_from_N_n_ph"
double upper_n = N/ph * max(100, N), // enlarge at least 100 times
lower_n = 100000, // at least 100000 data
cur_n = upper_n, next_n;
double min_interval = 100; // minimum internal to break the search
while(1)
{
double cur_CL = solve_CL_from_N_n_ph(N, cur_n, ph);
if(cur_CL >= CL) // if calculated value is more confident, try to reduce n
{
upper_n = cur_n;
next_n = lower_n + (upper_n - lower_n)/2;
} else
{
lower_n = cur_n;
next_n = upper_n - (upper_n - lower_n)/2;
}
if(fabs(next_n - cur_n) < min_interval)
break;
cur_n = next_n;
}
return(cur_n);
}
}