{VERSION 4 0 "IBM INTEL NT" "4.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0
0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1
257 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0
0 0 2 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 2 0 0 0 0 0
0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 1 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1
{CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }1 0 0 0 6 6 0 0
0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0
0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Headi
ng 3" 4 5 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0
0 -1 0 0 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE ""
-1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0
-1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0
0 0 0 0 0 1 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "Author" 0 19 1
{CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 8 8 0 0
0 0 0 0 -1 0 }{PSTYLE "" 4 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 35 "Accuracy of error correct
ing codes:" }}{PARA 256 "" 0 "" {TEXT -1 27 "An excursion in probabili
ty" }}{PARA 19 "" 0 "" {TEXT -1 39 " Mike May, S.J., Saint Louis Unive
rsity" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 ""
{TEXT -1 457 "We have been looking at error correcting codes. The ju
stification for using error correcting codes is that we want to improv
e the accuracy of transmission over a noisy communications channel. T
he question to be addressed in this worksheet is how much these codes \+
improve the reliability of the channel.question arises. The broader b
ackground question is to determine the cheapest (most efficient) code \+
that will provide the level of reliability we need." }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 241 "To make the issue conc
rete, 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 r
eceived is p=.99. What is the probaility that the entire message gets
through?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1
0 "" }}}{EXCHG {PARA 5 "" 0 "" {TEXT 256 21 "Straight transmission" }}
{PARA 0 "" 0 "" {TEXT -1 326 "The easiest case to compute the probabil
ities for is plain transmission with no error correction. We are tryi
ng to send n = 1000 words of data, with each word containing a single \+
bit of information. Each word is transmitted accurately with a probab
ility p, so the entire message is sent accurately with a probability o
f p^n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 83 "p:= .99; mlength := 1000:\nprob0101word := p:\nProb01
01mess := prob0101word^mlength; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
\"pG$\"#**!\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%-Prob0101messG$\"+
TZ7 " 0 "" {MPLTEXT 1 0 184 "p0
errword := (p,m) -> p^m:\np1errword := (p,m) -> m*p^(m-1)*(1-p):\npcor
word1 := (p,m) -> p0errword(p,m) + p1errword(p,m):\npcormess := (p,m,n
,mlength) -> pcorword1(p,m)^ceil(mlength/n):" }}}{EXCHG {PARA 0 "" 0
"" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 155 "Consider the majority
vote, (3,1) code and compute the probability of correctly transmittin
g a single word, and of tranmitting an entire message correctly." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1
0 66 "pword0301 := pcorword1(p,3);\npmess0301 := pcormess(p,3,1,mlengt
h);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*pword0301G$\"'-(***!\"'" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*pmess0301G$\"+VPoAu!#5" }}}{EXCHG
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 236 "Thus a s
imple majority vote code the chances that a single bit of information \+
is transmitted incorrectly decreases from 1 in 100 to 3 in 10000. Th
e chances that the entire message is received correctly increases to a
lmost 3 out of 4." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 ""
{TEXT -1 299 "It is worthwhile to consider the probabilities with (7,
4), (15,11), (31,26) codes. With each code it is instructive to com
pare the probability of correctly transmitting a single word with the \+
code with the probability of correctly transmitting the same ammount o
f data without error correction. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 272 "p := .99:\npword0704 := pco
rword1(p,7);\nnoerr4bit:= p^4;\npmess0704 := pcormess(p,7,4,mlength);
\npword1511 := pcorword1(p,15);\nnoerr11bit:= p^11;\npmess1511 := pcor
mess(p,15,11,mlength);\npword3126 := pcorword1(p,26);\nnoerr26bit:= p^
26;\npmess3126 := pcormess(p,31,26,mlength);\n" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#>%*pword0704G$\"+%e*oz**!#5" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#>%*noerr4bitG$\"),'fg*!\")" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#>%*pmess0704G$\"+2GJ:g!#5" }}{PARA 11 "" 1 "" {XPPMATH
20 "6#>%*pword1511G$\"+lAq.**!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
+noerr11bitG$\"+VDQ`*)!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*pmess1
511G$\"+]N_XT!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*pword3126G$\"+#
*pwA(*!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+noerr26bitG$\"+e9V+x!#
5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*pmess3126G$\"+*>VD<#!#5" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "Notice the expected pattern, the l
onger the coding scheme, the less tolerant it is of errors " }}{PARA
0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 5 "" 0 "" {TEXT 257 10 "Exerci
ses:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 175 "
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 correctl
y transmitting a single bit is .999" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 187 "2) Find the
probabilitly p at which point the probability of correctly transmitti
ng a single bit is the same as the probability of correctly sending a \+
1000 bit message with a (7,4) code." }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 5 "" 0 "" {TEXT -1 0 "" }}{PARA 5 "
" 0 "" {TEXT 259 25 "Multiple error correction" }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 379 "To evaluate codes that c
an correct more than one error we need a formula for the probability t
hat a word will have exactly k errors. We note that there are m choos
e k ways to select the i locations for the errors This lets us produc
e a function for the possibility of exactly k errors in a code of leng
th m where each bit has a probability of p of being transmitted correc
tly.\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "pexactierr := (p,
m,k) -> combinat[numbcomb](m,k)*p^(m-k)*(1-p)^k:\n" }}}{EXCHG {PARA 0
"" 0 "" {TEXT -1 235 "The numbcomb(m,k) command from the combinat pac
kage 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 " }{XPPEDIT 18 0 "(m!)/
(k!*(m-k)!)" "6#*&-%*factorialG6#%\"mG\"\"\"*&-F%6#%\"kGF(-F%6#,&F'F(F
,!\"\"F(F0" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0
"" 0 "" {TEXT -1 117 "Now we can turn our attention to a (15, m) code \+
and ask the probability of tranmitting a word with exactly k errors.\n
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 176 "p :=.99:\n`prob of 0 e
rrors ` = pexactierr(p,15,0);\n`prob of 1 errors ` = pexactierr(p,15,1
);\n`prob of 2 errors ` = pexactierr(p,15,2);\n`prob of 3 errors ` = p
exactierr(p,15,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%2prob~of~0~err
ors~G$\"+YNe+')!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%2prob~of~1~err
ors~G$\"+>(=JI\"!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%2prob~of~2~er
rors~G$\"+U2(R@*!#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%2prob~of~3~er
rors~G$\"+m60LS!#8" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0
"" 0 "" {TEXT -1 207 "What we are interested in is the probability tha
t 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.\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 119 "po
nlyierr := proc(p,m,i) \n local temp,k:\n temp := 0:\n for k from 0
to i do temp := temp + pexactierr(p,m,k) od;\nend:" }}}{EXCHG {PARA
0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 445 "Consider now w
ith 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 proba
bility that a single word is received with few enough errors to be cor
rectly 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.\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 115 "pword1507 \+
:= ponlyierr(p,15,2); \npword1505 := ponlyierr(p,15,3);\nnoerr5bit := \+
p^5;\nmajor5bit := ponlyierr(p,3,1)^5;" }}{PARA 11 "" 1 "" {XPPMATH
20 "6#>%*pword1507G$\"+s>%e***!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>
%*pword1505G$\"+B]()****!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*noer
r5bitG$\"+*\\+*4&*!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*major5bitG
$\"+y)3^)**!#5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 ""
0 "" {TEXT -1 358 "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, maj
ority 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." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA
0 "" 0 "" {TEXT -1 72 "Consider now the probability of sending the ent
ire 1000 bits correctly.\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
71 "pcormessmult := (p,m,n,i,mlength) -> ponlyierr(p,m,i)^ceil(mlengt
h/n):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 102 "p := .99:mlength \+
:= 10^3:Digits := 20:\npcormessmult(p,15,7,2,mlength);\npcormessmult(p
,15,5,3,mlength);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"5MoKxSPxhA%*!#
?" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"5wr#fEc)e.v**!#?" }}}{EXCHG
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 137 "Thus on \+
a channel with .99 efficiency, we can use a (15,5) triple error correc
ting code to send 1000 bit messages with .9975 efficiency.\n" }}{PARA
0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 5 "" 0 "" {TEXT 260 10 "Exerci
ses:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 226 "
3) Suppose the channel sends a single bit with accuracy of .999. Wha
t is the probability of accurately sending a 10^6 bit message using ei
ther a (15, 7) double error correcting code or a (15, 5) triple error \+
correcting code." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 406 "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 Digi
ts 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 s
ends each bit with an accuracy of .99 if we are using a (15, 5) triple
error correcting code?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 206 "5) We can construct a (31,1
1) 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" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 252 "6) The (3,1
) single error code, the (31,11) 5 error code, and the (63,24) 10-erro
r code, each have a sending efficency of about 1/3. How do they compa
re on accuracy for sending a 10^6 bit message on a channel that has an
accuracy of .99 for each bit?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT
1 0 0 "" }}}}{MARK "26 2" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }
{PAGENUMBERS 0 1 2 33 1 1 }