Accuracy of error correcting codes:

An excursion in probability

Mike May, S.J., Saint Louis University

We have been looking at error correcting codes. The justification for using error correcting codes is that we want to improve the accuracy of transmission over a noisy communications channel. The question to be addressed in this worksheet is how much these codes improve the reliability of the channel.question arises. The broader background question is to determine the cheapest (most efficient) code that will provide the level of reliability we need.

To make the issue concrete, we will suppose that we want to transmit a message of 1000 bits over a channel where the reliability of any bit sent being correctly received is p=.99. What is the probaility that the entire message gets through?

Straight transmission

The easiest case to compute the probabilities for is plain transmission with no error correction. We are trying to send n = 1000 words of data, with each word containing a single bit of information. Each word is transmitted accurately with a probability p, so the entire message is sent accurately with a probability of p^n.

> p:= .99; mlength := 1000:
prob0101word := p:
Prob0101mess := prob0101word^mlength;

We see that there is essentially no chance that the entire message will get transmitted accurately.

Single error correction

With single error correcting codes we need to work a bit harder. Then a word is received correctly if there are zero or one errors in transmition. The probability that an m bit prod is transmitted without errors is . The probability that the word is transmitted with a single error is . To convince yourself of the last statement note that there are n choices for the wrong bit, that the n-1 correct bits each occur with a probabilty of p, and that the erroneous bit occurs with probobility (1-p). Once we compute the probability pword, that a word is transmitted correctly, we note that there are words needed to transmit 1000 bits of information with an (m,n) code.

> p0errword := (p,m) -> p^m:
p1errword := (p,m) -> m*p^(m-1)*(1-p):
pcorword1 := (p,m) -> p0errword(p,m) + p1errword(p,m):
pcormess := (p,m,n,mlength) -> pcorword1(p,m)^ceil(mlength/n):

Consider the majority vote, (3,1) code and compute the probability of correctly transmitting a single word, and of tranmitting an entire message correctly.

> pword0301 := pcorword1(p,3);
pmess0301 := pcormess(p,3,1,mlength);

Thus a simple majority vote code the chances that a single bit of information is transmitted incorrectly decreases from 1 in 100 to 3 in 10000. The chances that the entire message is received correctly increases to almost 3 out of 4.

It is worthwhile to consider the probabilities with (7,4), (15,11), (31,26) codes. With each code it is instructive to compare the probability of correctly transmitting a single word with the code with the probability of correctly transmitting the same ammount of data without error correction.

> p := .99:
pword0704 := pcorword1(p,7);
noerr4bit:= p^4;
pmess0704 := pcormess(p,7,4,mlength);
pword1511 := pcorword1(p,15);
noerr11bit:= p^11;
pmess1511 := pcormess(p,15,11,mlength);
pword3126 := pcorword1(p,26);
noerr26bit:= p^26;
pmess3126 := pcormess(p,31,26,mlength);

Notice the expected pattern, the longer the coding scheme, the less tolerant it is of errors

Exercises:

1) For the 5 codes we have considered so far, what are the chances of correctly transmitting a 1000 bit message the the chances of correctly transmitting a single bit is .999

>

2) Find the probabilitly p at which point the probability of correctly transmitting a single bit is the same as the probability of correctly sending a 1000 bit message with a (7,4) code.

>

Multiple error correction

To evaluate codes that can correct more than one error we need a formula for the probability that a word will have exactly k errors. We note that there are m choose k ways to select the i locations for the errors This lets us produce a function for the possibility of exactly k errors in a code of length m where each bit has a probability of p of being transmitted correctly.

> pexactierr := (p,m,k) -> combinat[numbcomb](m,k)*p^(m-k)*(1-p)^k:

The numbcomb(m,k) command from the combinat package computes the number of ways to choose i elements from a set of s elements if we do not distinguish the order in which things are choose. The formula for this is that m choose k is .

Now we can turn our attention to a (15, m) code and ask the probability of tranmitting a word with exactly k errors.

> p :=.99:
`prob of 0 errors ` = pexactierr(p,15,0);
`prob of 1 errors ` = pexactierr(p,15,1);
`prob of 2 errors ` = pexactierr(p,15,2);
`prob of 3 errors ` = pexactierr(p,15,3);

What we are interested in is the probability that a word sent with a t-error correcting code will be received with no more than t-errors. Thus we want a procedure to sum the probabilities of 0 to k errors.

> ponlyierr := proc(p,m,i)
local temp,k:
temp := 0:
for k from 0 to i do temp := temp + pexactierr(p,m,k) od;
end:

Consider now with the (15, 7) code which is double error correcting and with the (15,5) code which is tripple error correcting. We want to know the probability that a single word is received with few enough errors to be correctly understood. Since a word in the (15, 5) code carries 5 bits of information, we compare with the probability of sending 5 single bits correctly using either straight transmission, or the majority vote (3, 1) code.

> pword1507 := ponlyierr(p,15,2);
pword1505 := ponlyierr(p,15,3);
noerr5bit := p^5;
major5bit := ponlyierr(p,3,1)^5;

The increase in efficiency is worth noting. We are using a channel that makes a mistake in 1 bit out of 100. On a 5 bit string, plain transmission makes an error in almost 1 word in 20, majority vote raises accuracy so there is an error in 1 word in 700, but with a (15,5) code we send 5 bits of information and be misunderstood in about 1 word in 125,000.

Consider now the probability of sending the entire 1000 bits correctly.

> pcormessmult := (p,m,n,i,mlength) -> ponlyierr(p,m,i)^ceil(mlength/n):

> p := .99:mlength := 10^3:Digits := 20:
pcormessmult(p,15,7,2,mlength);
pcormessmult(p,15,5,3,mlength);

Thus on a channel with .99 efficiency, we can use a (15,5) triple error correcting code to send 1000 bit messages with .9975 efficiency.

Exercises:

3) Suppose the channel sends a single bit with accuracy of .999. What is the probability of accurately sending a 10^6 bit message using either a (15, 7) double error correcting code or a (15, 5) triple error correcting code.

>

4) To work with higher accuracies we need to change the accuracy of Maple. We do this by changing the value of the Digits variable which is normally set to 10. Change Digits to 30. If we assume that the Bible is a 10^9 bit message, what is the probaability that it will be sent accurately over a channel that sends each bit with an accuracy of .99 if we are using a (15, 5) triple error correcting code?

>

5) We can construct a (31,11) 5-error correcting code and a (31,6) 6-error correcting code. Find the probability od correctly tranmitting a 10^6 bit message with each of these codes when p is .99 and .999

>

6) The (3,1) single error code, the (31,11) 5 error code, and the (63,24) 10-error code, each have a sending efficency of about 1/3. How do they compare on accuracy for sending a 10^6 bit message on a channel that has an accuracy of .99 for each bit?

>