### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Intro to Algebraic Coding MTH 416

MSU

GPA 3.57

### View Full Document

## 86

## 0

## Popular in Course

## Popular in Mathematics (M)

This 42 page Class Notes was uploaded by Donny Graham on Saturday September 19, 2015. The Class Notes belongs to MTH 416 at Michigan State University taught by U. Meierfrankenfeld in Fall. Since its upload, it has received 86 views. For similar materials see /class/207302/mth-416-michigan-state-university in Mathematics (M) at Michigan State University.

## Reviews for Intro to Algebraic Coding

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/19/15

1 MTH 416 Introduction to Algebraic Coding Homework 4Solutions Let 5 be an alphabet For m E 5 let qm be a probability distribution on 5 For m E 5 de ne Pm inductively as follows 130 1 and if Pm already has been de ned then de ne P008 Pqz8 for all s E 5 Show that 513 is a source We will rst show by induction on the length of m that Pm E 0 1 for all z E 5 If x has length 0 then x 0 and so Pm 1 by de nition ofp Now suppose x has length larger than 0 Then z gs for some y E 5 and s E 5 By de nition of P Pm Pyqys By induction Py E 0 1 Since qy is a probabilty distribution on 5 qys E 0 1 Hence also Pm Pyqys E 0 1 and so P is a function from 5 to 0 1 P 1 by de nition of P Let x E 5 Since qm is a probabilty distribution on 5 2565 qms 1 Hence ZIP9 ZPzqm8 Pqu8 PW 391 1 565 565 565 and so all requirements of a source have been veri ed LetFIXJgt 01 andFKXLgt 01 be channels PutPFXP Letp be a probability distribution on I X K let p the marginal distribution ofp on I and let p the marginal distribution ofp on K Lett be the joint distribution ofp and P on I X K X I X L let t the joint distribution ofp and 1 on I X I and let t the joint distribution ofp and F on K X L Show that a t is the marginal distribution oft on I X I and t is the marginal distribution oft on K X L b pr and p are independent with respect to p then t and t are independent with respect to t a Since P 1quot X P we have Dawn 1ij Since t is the joint distribution of p and P ti kjl Pi kFi kjl Hilarile 1 Since 19 is marginal distribution ofp on I 3 Pi 2 PM keK Since 25 is the joint distribution of p and 1quot on I x I7 4 752739 Ptrtj Z pikPj keK Since P is a channel 5 21 1 leL Let 75 be the marginal distribution oft on I x I Then 6 7 Z tltakgtltazzgt Z PWFWQ ka j lt2 F341 ZPltLkgtP j klerL klerL keK leL keK By 3 and 57 25 t and so 25 is the marginal distribution oft on I x J Since p is marginal distribution ofp on K 7 Pi prs ieI Since 25 is the joint distribution of p and P on K gtlt L7 8 75 Pgrgl ZPikPkl ieI Since 1quot is a channel 9 2 Pg 1 jeJ Let t be the marginal distribution oft on K x L Then 10 til 2 75931001 Z Emmiti 219010ng 21 ZpikPkl ijeIxJ ijeIxJ 13961 jeJ ieI By 8 and 10 t t and so t is the marginal distribution of t on K X L b If p and p are independent with respect to p then paw pgpg Thus 750310031 PltugtPltikgtltugt P ptP gP k z p F gMp P z 7527759 Thus t and t are idependent With respect to t 3 Let n be the largest positiue integer such that there exists a Z error correcting code C with C 136 and 0 n a Find an upper bound k for n b Find a lower bound in for n by constructing a Z error correcting code C with C Q EEG and 0 m c Determine n a By the packing bound 1 6 6 lt r 2 i0 So n1 6 g 64 and n g Since n is an integer this gives n S 9 So k 9 is an upper bound for n b Let H be the matrix 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 Since the last three columns span 162 ColH IF and so dim ColH 3 Put C NulH Then dim C 6 7 dim NulH 6 7 3 3 and 0 8 Since the columns vectors of H are nonzero and pairweise distinct C is a 1 error correcting code Thus m 8 is lower bound for n c Suppose there exists a 1 error correcting code C Q B6 With 0 9 Put K 1 23 456 For a E 18 and 0 g i g 6 put Nia b E B6 l dab If b E Nia then b is uniquely determine by the set k E K 1 ak y 1 of size i So lNial Fix a E C and de ne Di C Nia So Di consists of the codewords of distancei from a Put di Since D0 a do 1 Since C is 1 error correcting C has minimum distance at least 2 1 1 3 Thus D1 D2 0 and so d1 d2 0 Since C has minimum distance at least three 6 N1c N1E 0 for all 0 3A 6 E C By the packing bound lemma 1 lZN1cl 0 Z 91 6 63 060 i0 Since llBEGl 26 647 there exists a unique element x E B6 with z 2060 N1c Thus for all 2 E B6 with 2 7E z there exists 2 E C with d22 g 1 Let 2 E N2a with 2 y m Since da72 2 and da7 2 g 1 we have 1 S da7 2 g 3 Hence 2 6 D1 U D2 U D3 Since D1 D2 0 we conclude that 2 6 D3 It follows that 2 E UceDa N1c Since the holds for all 2 E N2a with 2 7E z and since 1N2al 15 conclude that e 14 g l U N2a m N1cl 15 c D3 Let c 6 D3 Note that of the six elements in B6 of distance 1 from 37 three are in D2a and the other three are in D4a Indeed if 11 0 1 and k E K with bk 7 ck then dab 2 if ak ck and dab 4 if ak 7E ck Thus lN2a N1cl 3 Together with we conclude that lU N2a N1Cl Z lN2a N1Cl Z 33d3 06 D3 06 D3 06 D3 So implies that 13 5 Hence 1 U NrltagtmNiltcgti Z iNrltagtmNiltcgti Z 33da15 WM cEDa 06 D3 ceD3 and U N4a N1C N4a c D3 So each element of N4a is of distance 1 from a codeword in D3 Since 0 has minimum distance three7 no element of N4a is a code word Thus D4 0 and d4 O LetcE D5UD6andputIi 6K l ci a andf 2 6K 1 ai7 6i Then m dea 2 5 and f d5a 2 5 Since lIUfl 6 this gives l1 m fl 2 4 For i e I m f we have oi 7 ai 7 6i and so oi 61 Thus dcE 67 lI fl 674 2 Since C has minimum distance at most three we conclude c E This shows that lD5 U D6l S 1 and so d5 d6 S 1 Since 0 Ugo Di we conclude 6 9101Zdi10050d5d67 i0 a contradiction 4 Let C be 2 error correcting code with C Q B8 and 0 5 Put F z 6138 l 1072 231 allce 0 Determine Consider E lBE8 F z E B8 l dcz 2 for some c E C Note that E U N2c Since 0 is a 2 error correcting the N2cc E C are pairwise distjoint and so t cEC Z ceC 2 El l U N203 lN2cl 2 l0l1828 537 185 ceC ceC i0 lBSl lEl 28 7185 256 7185 71 Thus lllgs Let n and r be a non negatiue integers with 2r n Show that there exists an r error correcting code C such that C Q l3 and Zr n lClZ 2 2 i0 Let C Q B be an r error correcting code with 0 maximal Let 2 E B We claim that z E N27c for some c E C lf 2 E C we can choose c 2 So suppose z C By maximality of 0 CU is nor an r error correcting code Hence there exists de E C with dd e g 2r Since C is an r error correcting code7 ole Q C and so we may assume 1 z and e E C Then at E NZT e and we can choose c e So the claim is proved and thus B U060 N27c By the packing bound lemma 2r lN2rCl and SO 2 mm U N242 ceC lN2rcl lCl 6 Letn 2l1 be ositiue odd inte er De nea b EB b a 000000 andb 111111 p g 7 3 Put Rn a7b Suppose an extended BSC with bit error probability e lt and an MD decision rule are used a Compute lFal and b Forl E N let pl be a probability distribution on RZHL Show that lim MR2117pl 0 lgtoo 7 a Let 2 E 18 and put w wt2 Then da2 w and db2 n 7 w So if O w lthena2 aandifl1 w nthena2b Thus Fa 2 E 18 lwt2 21 1 and Fb 2 E 18 lwt2 1 Observe thar Fa U Fb 18 and Fa U Fb 0 Thus lFal HEW 2 221471 We claim that lFal For 2 212n de ne 2 2 where 172139 Note that 2 1 if and only if 0 Thus wt2 n 7 wt2 Hence 2 E Fa if and only if 2 E Also 2 2 and so the map Fa 7 Fb 2 e 2 is a bijecttion Thus lFal and so 2 Fal lFal 2211 Hence 2211 1 W01 7 WW 7 T 7 22 b Since dab 21 1 the minimin distance of C is 21 1 Thus C is an l error correcting code Hence by a lemma in class for any c E C Mc S lFclel1 2215511 Allele e4el and so 2 e4el e4el 2pc e4el 060 060 Since 5 lt i 45 lt 1 and so limHoo e4el 0 As 0 g MR2H1pl easy the Sandwich theorem implies limHoo MR211pl O MR2117 pl EMA10 S 060 Let kn be positive integers and C Q l3 be a Z error correcting code with 0 2k and information rate p 2 06 Find lower bounds for k and n Since 3 p 2 06 k 2 0671 By the packing bound 2k1nlCl1n 2 and so 1 n g 27 Put m n 7 k then m is a postive integer and since k 2 06n m 04n and so 1n31gm Thusg2m and Hence 5m 2 2m1 For m 1 2 3 we have 5m 2 71217 While 2 quot1 4 8 16 respectively Hence m 2 4 n2 m10andk06n6 8 LetF be the BSC with bit error probability e 003 and C Q 1310000 be code with information rate p 083 If 19 is the equal probability distribution on C nd a lower bound for H WW Put n 10000 By Lemma 7 HF p Z npi 39y there 39y is the capacity of the BSC By Lemma 7 1 1 7 V 7 7 lt 39y He 1 5 HO 030970 0 0310g2 003 0 97log2 03997 7 0 20 Thus HP p 2 10000083 7 020 10000 063 6300 9 a Does there exist a 1 error correcting linear code C Q 310 with 0 12852 b Let C Q lilng be a 1 error correcting linear code Find an upper bound for the informa tion rate of C a 1281 110 gt 27 23 2107 so by the packing bound7 no such code exist b Let k dim C Then 0 2k and by the packing bound7 2W1 12 g 212 Thus 2 1 g 21 Since 23 lt 13 g 24 28 2124 g lt 21H 29 Thus k g 8 and 0 g 28 10 Let k be a positiue integer and put n 2k 2 Let C consists of all m 12n 6 IV such that 16 Zn mk1 and for all 1 S l g k 17 M xlk1 0 i1 a Find an n gtlt k matrix E such that CEyly lF b Determine the information rate and minimum distance of C Note that z zlkl if and only if zlk1 ml for all 1 g l g k 1 Hence we can choose m1 zk freely and then n1 901 2 k7k2 9017mm 9027 72k1 9 2k2 n1 901 2 9mg Sowithyizifor1 i kweget 1 3 MTH 416 Introduction to Algebraic Coding Homework 2Solutions Consider a memoryless source with alphabetS a7 b7 c If one such source has probability distribution 06703701 and another probability distribution 05703702 which one has larger entropy What probability distribution on S produces the largest entropy The equal probability distribution has the largest entropy Let p 06703701 and q 05703702 Since q is closer to the equalprobability distributions7 q should have larger entropy To con rm l l l H2p 06log2 0310g2 01log2 m 130 1 1 1 Hm 05 log2 g 0310g2 a 02 log2 a m 149 Use the Shannon Fano rule to construct a pre x free binary code for a source with probability distribution 057 03702 Is this code optimal 05 03 02 39BlH quot6 1 2 3g 5 og2 1 1 2 3 So we need one codeword of length 17 one of length 2 and one of length three We can choose 07 107 110 The code is not optimal since 010711 is pre x three code with smaller average length Find a Hu man code for a source with probability distribution 040370170170067004 04 03 01 01 006 004 0 10 110 1110 11110 11111 04 03 01 01 01 0 10 110 1110 1111 04 03 01 02 0 10 110 111 04 03 03 0 10 11 04 06 0 1 1 0 So the Hufmann code is 01011011101111011111 4 While computing a Hu man code in each application of the Hu man rule H1 a new symbol 5 with probability is introduced Show that the average length L of the Hu man code is the sum of these Let h S 7 13 be a Huffman code Let 51 be the new symbol and 131 the new probability distribution introduced during the i th application of Huffman rule H1 Put m Then m 7 1 application of H1 are necessary to construct h Put a with a 0 if m 1 We need to show that Lh a If m Lh 0 0 Thus 4 holds in this case Suppose m gt 1 and suppose inductively that 4 holds for Huffman codes on alphabets of size m 7 1 By construction of h7 there exists a Huffman code h on an alphabet g of size m 7 1 such that h is obtained from h Via an application of Huffman rule H2 Set 6 232113450 Then 17 then 0 is the only code word and so 1 063951 1 By the induction assumption 2 Lh 6 and by Theorem 317 3 L01 L03 25151 Combining the last three equation we get Llthgt L03 1316 6 H3161 0 5 For a code c let TLc be the sum of the lengths of the codewords and Mc the maximal length of a codeword a Let h and h be codes as in Hu man rule H2 Show that Mh g Mh 1 and TLh g TLh MOB 2 b Ifc is a Hu man code on an alphabet of size N show that 2 7 Mc N71 and TLc a Let a E S such that lha is maximal Then Mh lha If s 31 a 31 s 7 then ha h a and so Mh 101a mm 3 Ma 3 M03 1 If a s or a s 7 then a 0 or 17where z Hence lhalx1lh 1 Mh 1 We have TLlthgt 21013 seS 1h8lh8 2 1018 seS S lm0lz1 2 1038 seS S lm1l1 2 1038 seS S 1h 2 1h Z 1036 seS S lt Mh2TLh 3 b If N 17 then 0 is the only codeword So Mh 0 17 1 and TLh 0 1212172 Hence b holds in this case Suppose now that N gt 1 and b holds for Huffman codes on alphabets of size N 7 1 By construction7 there exists a Huffman code h on an alphabet of size N 7 1 such that h is obtained from h Via an application of Huffman rule H2 By the induction assumption Ml1 N11N72andTLh N712N 1 2N275V72 Using a we get MhltMh1N721N71 72 N2 7 N N2 N 7 2 TLh g TLh Mh 2 g f N 7 2 2 So b also holds for Huffman codes on alphabets of size N Complete the proof of Theorem 318 for the case that t 3 and t 3 Suppose that t 3 and t 3 De ne a code 6 for S as follows 55 m and 53 Cs for all 3 e S m 3 Observe that c isthe code constructed from 6 according to Hu man rule H2 So applying Lemma 317 to h7 h and c7 6 we get Mb 7 L03 256 and Lltcgt 7 Me 256 Since h is optimal we have LE and since 0 is optimal7 Lc Lh Thus Lh Lh 253 LE15 La Lh Thus equality must hold everywhere and so Lc Lh Since 0 is an optimal code7 also h is an optimal code Letp be a probability distribution on a set S and let 0 S 7 3 be a PF binary code For 3 E S de ne 53 E 18 and d3 E 13 by CS e3d3 So if CS 12n with m E lBE then e3 m1 and d3 mgzg Let b 618 De ne Sb3ESle3b and let Cb be the function from S5 7 3 de ned by 3178 d3 for all 3 6 Sb Prove that a Cb is a PF binary code on Sb b De ne qb 2965b ps and for s 6 55 de ne pbs Then pb is a probability distribution on 55 c Let L7L0 and L1 be the auerage codeword lengths of the codes C CO and c1 with respect to the probability distributions p p0 and p1 respectiuely Then Lq0L0q1L1 1 d Ifc is an optimal code for the source 57p then cb is an optimal code for the source 51271912 a By de nition7 05 is a function from Sb to l8 We need to show that 05 is 1 1 and pre x free Let st 6 55 Then es b et and so cs bds bcbs and ct bcbt lf cbs cbt we get cs bcbs bcbt ct Since c is 1 17 this means 8 t and so 05 is 1 1 If cbs is a pre x of cbt7 then cbt cbsw for some w 6 ll With w 7 0 Hence ct bcbt bcbsw csw and so cs is a pre x of ct7 a contradiction So cbs is not a pre x of cbt and so 05 is pre x free b Note that both ps and qb are positive and so pbs is positive for all s 6 55 We compute Ems 2 7198 Zsesb 198 1 sesb sesb qb qb qb ln particular7 pbs 1 for all s 6 Sb and so 195 is a probability distribution on 55 c L Zses P8l08 Zses P8l68d8 ZSESPS1 1018 2963148 Zsesp8ld8 1 Zses s wsh 1 Zseso P8ld8 29651 P8ld8 1 Zseso Z p8l008 29651 PSl018 1 qo 29650 P08l008 11 25651p18l618 1 qoLo qiLi d For b 01 let 65 be an optimal code for 5 De ne E S a ll by 6s 060s if s 6 SO and s 1018 ifs E 51 So 63 bcbs7 Where b es We claim that E is a pre x free code Let 37 t E S such that 6s is equal to 6t or 6s is a pre x of 6t Then 6t Esw for some w 6 EV Let b es Then 6t 6sw bcbsw 8 Thus the rst digit of 6t I So b et and bEbt 6t bEbsw Hence Ebt Ebsw Since 65 is a pre x free code we conclude that w D and t 3 Thus 6 is 1 1 and pre x free Let i he and I4 be the average length of E 60 61 with respect to p p0 and p1 respec tively From c applied to 6 we have i qofO qlfl 1 Since 0 60 and 61 are optimal we conclude that L qoioq1 11 q0L0q1L11L Thus equality must hold everywhere So IO L0 and I4 L1 Since 60 and 61 are optimal also co and cl are optimal Let m be a positive integer and let pm be the probability distribution on an alphabet Sm with m symbols in which each symbol is equally probable a Determine the Hu man code cm for Smpm and the average codeword length Lm of cm b Ifm 2k show that Lm H m c Show that LZkJrl HP2k1 1 Remark If you cannot solve a in general at least do the cases m 1 2 3 4 5 6 78 2k and 2k1 a Put k llogz ml and i 2k 7 m So k is the smallest integer with 2k 2 m Hence 21H ltm 2k and 2amp21H gt 2k7m2 2k72k Thus0 ilt 2 Let I be any subset of 18 1 with lIl i Since llBEk ll 2114 gt i such a subset exists and I 7 lBEZk l Put J lBEk 1I Then J is non empty subset of IBEX 1 and lJl 2k 1 7 i De ne 01u110v1lu E IU E I Then CI has i codewords of length k 7 1 and QlJl codewords of lenth k Note that QlJl 22 1 7i 2k7 2i 2k 7i 7i m7i Thus lCIl i m7i m and CI has average length 7ik71m7ik iik7imk7ikimk7ii 7 L k m m m m We claim that C is pre x free So suppose that zy 6 CI such that z is a pre x of y Then x has smaller length than y and so lx k 71 and ly k Hence z E I and y 20 or y 21 for some 2 E I Since z is a pre x of y of length k 7 1 it follows that z 2 a contradiction since I and J are disjoint We will now show that any optimal code on Sm with respect to pm is equal to CI for some subset I of EB 1 with I 2 Since each of the 01 s has the same average word length7 this shows that all the 01 s all optimal codes with respect to pm Let C be a set of codewords of an optimal code on Sm with respect to pm Let r be the maximal length a codeword We will prove next that 1 IwaCthenr71 lw Let w E C Since r is the maximal length of a code word7 lw r By 3157 there exists two codewords of length r of the form 0 and 1 Since w is not a pre x of any element if C7 neither w0 nor w1 is the pre x of any element of C If w 0 or 17 then lw r and 1 holds So suppose w 7 0 and w y 1 Since neither 0 nor 1 are the pre x of any element of C7 0 and 1 are the only elements of C with pre x It follows that D C U 7w07w1 0 17 w is pre x free code with m elements We have TLD 7 TLC 1 lw0 lw1 7 l0 l1 lw r71lw71lw717rrlw Ti 1 400 Since C is an optimal code with respect to the equal probability distribution7 TLC S TLD Thus r717lw2 0 and lw r71 Hence 1 holds Let I be the set of codewords of length k 7 1 Let J be the set of words of length k 7 1 which are pre xes of a codeword of length k 2 I J0 Let w E J Then w is a pre x of a codeword of length k and since C is pre x free7 w is not a codeword Thus w I and so I J 3 IUJlBT 1 Let w 6 EB 1 and suppose that w I and w I So w is neither a codeword nor the pre x of a code word Any pre x of w has length at most r 7 2 and so by 1 is not a codeword Let y be a codeword of length r and de ne E C U w Since y is not a codeword7 w C and since w is not a pre x of a code words7 E is pre x free Thus E is a pre x free code of size m But the total length of C minus the total length of E is ly7lwr7711 Thus C has total length larger than E7 a contradiction since C is optimal This contradiction proves 3 4 Let w E I then both w0 and w1 are in C By de nition of J7 w is a pre x of a codeword of length r Thus at least one of wO and w1 is a code word Suppose now that wO is a codeword7 but w1 is not Put F CU ww0 We claim that F is pre x free lndeed7 by 1 any element of C has length at least r 7 1 and so cannot be a pre x of w Also the only words of length less or equal to r with pre x w are wO and 1017 neither of which is in F Thus F is pre x free Also m7 but as in 3 F has total length one less than C7 a contradiction 5 CCjkrandllli If x 6 CI then either z E I or z wO or z w1 for some w E J By de nition7 I Q C and by 3 both wO and w1 are in 0 So CI Q C Let y E C Then by 1 7 ly r 7 1 or r In the rst case7 y E I Q CI In the second case y wO or w1 for some w E lBV l Then w E J and so again y 6 CI Thus C CI Put 8 It follows that m lCl 101 2T 7 s with 0 g s lt 27 1 Hencer llogzml and sm72T m72k 7i This completes part a of Exercise 8 b If m 2k for some k E N then i 0 and so by Lm k logzm c This is false Indeed we will prove that L241 P109241 0 Form211wehavekl1andi2171andsoby 2l 17 l 21 2 21 2l1 the Sandwich Theorem implies l71 Wl1 Since 1 iog22l 1 HWH Lm z Lml172 2 21139 L241 HP211 0 Let R P be a source and suppose that 3 17 if 1 2 m3 is euen 19 901902963 1 E ifm1m2x3 is odd So for example 193001 1716 and 193101 1376 a Compute pa for 1 g l g 3 7 Compute pub for 1 l1 lt l2 3 3 c Show that pal and 1902 are independent with respect to pal for 1 l1 lt l2 3 d Show that 191 and pail are not independent with respect to p3 e Show that S P is not memoryless Compute HQ for1 T g 3 T g Verify that asp 32 S a S f ll and HP3 g HP1 HP239 a and b Let k l with 1 gl 3 3 or k 1112 with 1 3 ll lt12 3 By Lemma 13c in the Lecture Notes7 191 Z 293y 2653 yFw Let y ylygygyg 6 3 Recall here from the lecture notes that yk y ifkl and yk yliylz Of k 11712 Let 2 6 123 with 2 7t 1 if k z and 11 7g 2 g 12 if k 1112 Let y y1y2y3 e 53 With 24139 0 De ne 297 E 53 by 297739 yj ifj 75 i and 197139 1 Then 2971y2373 yiy2ys1 and so 331 332 333 is odd if and only if yl yg yg is even Thus one of p3y and 19337 is while the other is Hence p3y p3g T16 1473 Also observe that for each 2 E 53 with 21 17 there exists a unique y E 53 with yi 0 and z 37 Moreover7 2k yk It follows that 29 Z 19324 Z My Z My Z My 1429 i EU yes3 2653 2653 3653 3653 yk w yk w yk w yk w yk w 2120 2121 2120 2120 where u is the number of y in 3 with yk z and yi 0 If k l7 the l coordinate of y is z the i coordinate is 0 and the one remaining coordinate is 0 or 1 So u 2 and 1 1 pl 12 E for all m E S If k 11127 then the ll coordinate of y is 1 the lg coordinate of y is 1 and the i coordinate is 0 So there is a unique such y and u 1 Hence 1 1 1112 7 7 2 p 41 4 for alleS c We have 1 1 1 pll 12m Z PltlllP122 and so pal and 1902 are independent with respect to pltllgtl2 d 193000 7367 1910 and 192 3 00 Since 7 T36 we conclude that 191 and 192 3 are not independent with respect to 193 e We have P000 p3000 1376 and 190 plt1gt0 5 Since 1 7g g S P is not memoryless f Since p1 and p2 are equal probability distribution on S and 2 respectively7 we have from Homework 1 that Hp1 logz lSl log2 2 1 and Hp2 logz 152 log24 2 For x mlzgzg 6 53 let 1 2 m3 We compute Hung ZEQSaPBWNng Z mesa PSWNng tZ mfgiaddPSWHng lml is even 3 16 1 2 653 E 10g2 7 t 2 653 10g2 16 lml is even is odd 44710g234 4 3710g231 iglogz m 28 Thus 1 1 1 1 4 log 3 H 1 17 2 721 diH 3 7772 no9 129 7209 2 7an3p 3 4 gBYf7 1 1 1 2 1 3 1Hp2Hpgt3Hp Also Hp3 m 28 and Hp1Hp212 3 So Hp3 Hp1hp2 and g is veri ed 10 Given a stationary source S P with entropy H Let n7q7r7 s be integers with n qr s 0 sltrn21 undq21 Showthut a Hue S Hoar lt1 3 i Hltpsgt b n 2320 H3 H Hint Given 6 gt 07 choose r such that f Q lt H Let K be the maximum value of Hp9 for 0 S s lt r and choose a positive integer no such that g lt By Theorem 17b in the Lecture notes7 HQ HOW S HUD Hps and so a 109 gmw 11029 By Theorem 17c7 1 HWT S qr H p E H and so M imam El 1 7 1 How 3110 Be 71 qT 71 T 71 T T 71 ltgt and ltgt imply a b Let e be a given positive real number Since H infT Z Hp7 there exists r 6 2 with 1 e 7H T lt H 7 e T p gt 2 Let K maiXoSKT Hp5 and choose a positive integer no with no 2 r and K e i lt 7 no 2 Now let n any integer with n 2 no Then n qr s for some q7 s with 0 g s lt n Since no 2 r q 2 1 By de nition of K7 Hp5 S K and so by w Lgkgggg By a 110971 S H99717 EFF HES S 1333 HES and so by and MTH 416 Introduction to Algebraic Coding Fall 2010 Review for the Final Solutions 1 Construct a Hu man code for a source with alphabet S 12345 and probability distribution p 01030150 20 25 For easier computation we list the elements in order of their probablity l 3 4 5 2 000 001 01 10 11 01 015 02 025 03 00 01 10 11 025 02 025 03 0 10 11 045 025 03 0 l 045 055 2 l 2 Use the LZW decoding rules to decode 352 with respect to the initial dictionary D0 AB7 CD X c i Dic 1A 2B 3C 4D SCSCC 5006CCB 2B7 The decoded message is CCCB 75 3 Given a channel l with input alphabet abc and output alphabet de Suppose that the joint distributiont ofl is given by a Compute the input distribution p the output distribution 4 and the channel F b Are p and 4 independent with respect to t a To compute p and q we sum up the entries in each row and colum of ti t d e p a 0 1 0 1 02 b 02 0 2 04 c 03 0 1 04 q 06 0 4 Recall that tij pinj and so Fij I i Thus we obtain F by dividing row i oft by pi b We have paqd 02 06 0 12 a 0 1 tad and so p and q are not independent with respect to t Given a memoryless source with alphabet S Green White and probability distribution 0406 a Compute the entropy H of the source b Based on the proof of Theorem 411 nd a positive integer n such that there exists a pre xfree binary code on S with average wordlength Ln such that is within 20 of H a By Theorem 49 for a memoryless source the entropy of the source is equal to the entropy of the probablity distributioni So H 704 log2 04 06 log2 0 6 m 0971 We want 7quot lt 02H So we need to apply theorem 411 with e 0 2Hi According to the proof of Theorem 411 it suf ces to choose lt 5 and so 2 2 710 10 ngtm 710i30i E N 0971 Thus we can choose n 11 5 Let C Q 111100 be linear code of dimension 60 T C X 111100 gt 01 a channel with capacity 55 and p the equalprobability distribution on C Does there exist a decision rule a z 111100 gt C such that MCp F a S 5 By Theorem X3 in the supplemental lecture notes quot 1 M gt 1 7 1 7 i P on Where M MCp Ra 5y is the capacity per symbol of the channel and p is the information rate and n the length of code In our case 3 055 p 0 6 and n 100 Hence 0 55 1 55 1 56 4 1 1 M 1777717717 75 gt 016 016 100 60 60 60 60 15 gt 20 So there does not exist a decision rate With M g 570 6 Let C Q 1F be a cyclic code and suppose that 0110 E C and that C Determine C Solutions 1 Since 0110 6 C and C is cyclic 1100 6 C The polynomial corresponding to 1100 is 1x and so by Lemma XVl5a the canonical generator 9 of C must divide 1 x Thus 9 1 or g 1 x If g 1 C ng contrary to the asumptionsl Hence 9 1 x We have h I 4 1 1 x x2 x3 11 and so H 1111 is a check matrix for C Thus C consists of all binary strings of length 4 and even weightl Solution 2 75 7 Let C be binary linear code with check matrix 1 1 1 0 0 0 1 0 1 0 H 1 1 0 0 1 0 1 1 1 1 a What is the dimension of C 7 Determine a check matrix I for C which is in standard form c Determine a generating matrix for C b Let H be the matrix consisting of the rst three rows of H 11100 H01010 11001 Observe that the last row of H is the sum of the rst three rows Thus for any 2 6 E3 the last coordinate of H2 is the sum of the rst three It follows that H2 0 if and only if H2 0 So C NulH NulH and H is a check matrix for G Since H A713 Where 11 1401 11 and 13 is 3 X 3identity matrix H is in standard form a Observe that the last three columns of H span ngi Hence ColH F3 and dim ColH 3 Hence dimC57dimColH5732l I c Since H is a check matrix in standard form A713 E lt 2 is a generating matrix A Concretly t5 H HOHOH HHHHO 8 Does there exist a linear 2error correct code of length 12 and information rate 05 Let C be linear 2error correcting code of length 12 and dimension hi By the packing bound r n n 0 g2 10 We have lCl 2k r 2 and n12i So 2k112 66 g 212 and 212 212 2k lt 7 7 25 7 79 lt 26 Hence h lt 6 and C has information rate i lt 05 Thus there does not exist a linear 2error correcting code of length 12 and information rate 05 9 Let E be a nite eld containing R with 64 Let f 1z15 and h lzz2z4 15 Suppose that a is a primitive element oflE and that a is a root of Let C be the BCH code with designated distance 5 with respect to a a Show that f is irreducible in F2 b For 0 g 239 g 6 nd bj 6 1150 gj g 5 with a3i Elobjaj c Show that a3 is a root of h d Compute the canonical generator 9 6 F2 for C e Compute the dimension h of C Find upper and lower bounds for the minimal distance 6 of C 9 Let c7 2 be a 1bit errorfor C Letz 2021111253 with 2139 6 F2 Suppose that 20 ziai 1a In which hit did the error occur that is determined i E N with 0 g i g 63 and ci a We will show that f and h are irreducible So let s 6 g Let t an irreducible polynomial t 6 Fix of degree at most 3 and B a root oft is some eld containing ngl We will show that B is not a root of s It will follow that t does divide si Since every reducible polynomial of degree six is divisible by an irreducible polynomial of degree at most 3 3 we will conclude that s is irreduciblei From previous homework problems we know that the irreducible polynomials in R of degree less than three are z1z1z12 1zz3 and 1z2zgl 1ft I then B 0 Since s has constant term 1 s0 1 f 01 Ht 1 I then B 1 Since s has an odd numbers of terms s1 1 f 0 1n the following observe that t is the minimal polynomial of and so f 0 for all 0 y r 6 F2 with degr lt deg ti Suppose t 1 1 12 Then t l 13 71 and so BS 11 Hence B4 and B5 11 We compute M 151 Bamandh 1 2 1 5BQa O Suppose thatt 1zzgl Then 3 1BB4 BB2 and B5 B32 1 2 1 2i hus fw1B1f32 520andh 15B2 521f32BQa O Suppose thatt112zgi Then g152 45531552 and 56 53V 1 221 4f352v Thus fw15552132y oandh515 21 525f32 w o So is not a root of s and it follows as already mentioned that s is irreducible for s f and 85 Sinceaisaroot off a51ai Hence a 1 a a 151oz7 a9a3a5a3a4 a12a521a21a2 115a3a12a31a2a3a5 ama5a121a1a21aa2agi cha31a3a5a12a131a31a1a21aa2a301 d g is the least common multiple of mmma2mazma4i Since a is a root of f also a2 and a4 a22 are roots of f Since f is a monic irreducible polynomial Lemma XVH3f implies ma maz 771044 By c a3 is a root of h and since h is a monic irreducible polynomial mag hi Thus gfh 1z151z12z415 1I12I4I6II2I3z5z715z718110112 113I41518I10112 e C is a cyclic code of length HEN 63 with canonical generator 9 of degree 12 So C has dimension 63 7 12 l f C is a BCH code of designated distance d 5 and so C has minimal distance 6 Z 5 We have 63 7636261 7 7 12 lt3 7Wgt20gt3060736000gt404872 and so 63 0 lt 3gt gt 251212 263 Thus the packing bound shows that C is not 3errorcorrectingl So 6 lt 2 3 1 7 Hence 5lt6 6 Remark 6 is actually equal to 5 We compute t I 1 13 14 15 15g xi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 g 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 139 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 I49 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 I59 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 159 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 t 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 Thus t 11g zlozl7zml The binary string of length 63 corresponding to t is a codeword of weight 5 Thus 6 g 5 Since 6 2 d 5 6 5 g Let i 6 N with 0 g i lt 63 and cl zit Then Cz 1111 By assumption 2a 1 1 By Lemma XV1116 5a 0 and so a5 1a 2a caai 0ai ail Since a is a primitive element aj0 j lt 63 are pairwise distinctl Hence 239 6i 10 Consider the Feistel system with M C F X 1F 7 3 K F3 and 11 2111 12 21 F 7 I2 22 13 A 13 11 1021011 E 73 Compute c Ek and verify that Dkc m 1 0 Let m X07X1 and so X0 0 and X1 1 1 Also 0 0 Hence 1 1 0 1 101 1 1 0 X2XoFk1X1 0 F lt0 1 0 00 0 0 0 1 0 0 0 00 0 0 0 0 0 0 000 0 0 X3X1Fk2X2 1 F 0 1 10 1 1 0 0 0 0 00 0 0 0 1 0 0 100 0 0 X4X2FksXs 0 F 0 0 10 0 1 1 0 0 0 00 0 0 0 Hence 0 0 CEkm X47X3 1 7 0 1 0 0 7 10 kg kg 101 and so We compute 0 1 0 100 0 0 Y2Y07FkiY1 1 F 0 1 10 1 1 X2 0 0 00 0 0 0 0 0 0 0 000 0 0 0 Y3Y1FkY2 0 F 0 0 10 0 1 1 XL 0 0 0 00 0 0 0 0 1 0 0 1 01 0 1 1 Y4Y2Fl 7Y3 0 F lt0 1 0 00 0 0 X01 0 0 0 00 0 0 0 Hence 1 0 Dk6Y47Y3 0 1 m 0 0 75 11 Consider the RSA cryptosystem with M green white blue maize 115 Z M a ZR green a 1 white a 2 blue a 4 maize a 8 green if r 0 white if r 1 blue if r 2 maize if r 3 15ZZ4gtMTL4gt where r is computed as follow Let n 2km with 10721 E N and m odd Put r k4 a Compute 4515 7 Compute B15820 a Compute 2 E153white a Compute D1557 e Find e 6 Z4505 with 3e E 1 mod VeTify that D15ez white a 1535and soq 153715E1248i b 320 64 5 26 5 Thus T 64 2 and B15820 bluei c a15White 2i 23 8 and so E 153 i d72 49E4mod1574E72E42E16E1mod15andso75 774E71E mod 15 Thus 7515 7i 7 20 7 So T 0 and 157 green Thus D1557 green e We use the Euclidean algorithm to nd the gcd of 3 and 4515 8 8 03 3 08 12 412 2 18 23 421 1 718 33 431 0 Hence1E1833andso33E1mod8iThuse3i f 2 8 by c and e 3 by e We compute 82 E 64 E 4 mod 15 and 83 E 882 E 84 E 32 E 2 mod 15 So 28 15 2i 2 21 1 T 1 and so B15 2 Whitei So indeed D138 White 75 12 Given a oTyptosystem with C and a pTobability distTibutioTL T on K a Let h 6 7C and c 6 C Show that theTe exists a unique m E M with Ek c 7 Let I be the enoTyptioTL channel of the CTyptosystem with Tespect to T Show that Erma mEM foT all c 6 C a Let h 6 79 Since Ek is 17 1 and so Since C is nite this means Ek Ci Hence for each c 6 C there exists a least one m in M With Ek m 0 Since Ek is 11 this m is unique b Fix 5 6 Mi We compute 2 2 W Z Z We meM keIC keIC meM Ek mc Ek mc MTH 416 Introduction to Algebraic Coding F10 Homework 5Solutions 1 Let C be the binary linear code with check matrix OOOOHHHH OOHHHHOO HHHHOOOO HHHHHHHH OOOOOOOH OOOOOOHO OOOOOHOO OOOOHOOO OOOHOOOO OOHOOOOO OHOOOOOO HOOOOOOO a Compute the dimension k of C 17 Find a generating matrix E of C c Compute the minimum distance 6 of C d Determine the largest positiue integer r such that C is r error correcting e Let 039 be any MD decision rule for C Compute a110100001000 0110000111111 and 0101111101111 h Is C cyclicf2 i Is C perfectf2 a The last 8 columns of H clearly span F3 and so ColH F3 and so dim ColH8 Hence dim C dim Nu1H 12 7 dim ColH 12 7 8 4 I b Since H is in standard form 14187 lt 4 is a generaing matrix for C So we can A choose OHHHHOOOOHO HHHHOOOOOHOO 0 0 0 1 1 1 1 1 1 1 1 1 OOOOl l HHOOOH O c The minimum distance 6 of C is the smallest number of columns whose sum is zero Since none of the columns are zero 6 gt 1 Since no two distinct columns of H are equal7 6 gt 2 The sum of columns 13 and 4 is zero7 so 6 g 3 Thus 6 3 d By de nition7 C is r error correcting if and only if 2r1 6 Since 6 3 the largest such r is r 1 e No nice solutions for part e Sorry7 I picked the wrong words h The cyclic shift of the rst column of E is d 0100011110000 If at is in C it would be a linear combination of the columns of E Looking at the rst fours bits7 1 would have to the second column of E But at is not equal to second columns of E and so 1 C Thus C is not cyclic i A 1 error correct code is perfect if and only if the packing bound is sharp We compute T 71 C 241 12 l lt gt This is not a power of 2 and so is not equal to 212 So C is not a perfect code Let H be the check matrix for the Humming code of length n 2m 7 1 using the numerical order on the columns Put C NulH and suppose that m 2 3 a Letaa1an 618 withai 1for1gig3undai0for4 i n so a11100001sa60 b Letbb1bn EB withbl 1for1 i 6 undai0for7 i n so b1111110000 Ist C CO Show that the ideal lt1zgt in V5 Put t n 7 6 and denote by as an arbitrary row vector of length t Then 000000t 000000 H 000000 000111 011001 101010 Note that Ha is the sum of the rst three columns of H Since the numbers of 1 s in the rst three entries of any row of H is even Ha 0 and so a E C Note that H1 is the sum of the rst six columns of H Since the number of 1 s in the rst six entries in the last row of H is odd Hb 7E 0 Which of the following codes are cyclic a 01 0000 1100 0110 0011 1001 b 02 0000 1100 0110 0011 1001 1010 0101 1111 a 1100 6 C1 0011 6 C1 but 1100 0011 1111 C1 S0 C1 is not linear and hence also not cyclic b Observe that Cg consist of the eight words of even weight A word has even weight if and only if the sum of the coordinates is 0 So Cg NulH where H is the 1 x 4 matrix 1 1 1 1 Hence Cg is a linear code Cyclic shifts do not change the weight so any cyclic shift of a word of even weight still has even weight Hence Cg is a cyclic code corresponds to the code in F3 consisting of all the words of even weight Put h 1zz2m3m4 Then 1mh 571 and so 9 is the canonical generator for 1 Moreover the code C corresponding to 1 x has check matrix H 1 11 11 and so consists of all words of length ve such that the sum of the coordinates is 0 Thus C consist of exactly all words of length 5 and even weight a Determine all factors of m5 7 1 in 7 Determine a generating matrix for each cyclic code of length 5 Put h 1 z 2 3 m4 Then 5 7 1 1 zh We claim that h is irreducible in ng Otherwise h is divisible by an irreducible polynomial f of degree 1 or 2 If degf 1 then 0 or 1 is a root of f and so also h But 710 1 h1 a contradiction The polynomials of degree 2 are 2 z z7z2 1 m 1z 1z2 z zz 1 and 2 z 1 So 1 2 z 1 is the only irreducible polynomial of degree 2 Since 1 h 3 4 z31 z and f neither divides z nor 1 m7 1 does not diVide f h and also not h This contradiction shows that h is irreducible It follows that the factors of 5 71 are 1 261 1 z 2 3 462 with e 6 01 So the factors are 171x71zm2m3x47m571 b Each cyclic code is determined by its canonical generator 9 g is a factor of 5 7 1 and so by a we obtain the following four generating matrix 1 0 01 91 E 0 0 Cr 0 0 0 0 OOHOO 0 0 0 1 0 H0000 1 O 0 0 1 1 O O g1z7 E 0 1 1 0 7C words ofevenlength5and even weight 0 O 1 1 O O O 1 1 1 g1zz2z3z4 E 1 C0000011111 1 1 O O 9355717 E 0 C00000 O O 6 Determine a check matrix for the cyclic code corresponding to the ideal lt1x2x3x4x6gt in V15 We compute m9 m7 m6 m3m2 1 x6m4m3x21 15 1 m15ltF13lt gt12gt11 9 13lt gt12 gt11 9 z13 mll109 7 z12 10 7 z12 1098 6 x9m8m7 m6 1 m9 x7 x6m5 m3 m8 m5 m3 1 m8 z6m5m4 m2 m6 x4m3m21 m6 x4m3m21 0 Thus h MW x9 7 6 3 2 1 Hence the coef cients of h starting at the leading coef cient and ending at the constant term are 1011001101 So the check matrix for C is 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 H 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 7 Let E Show that a 1 9002 f962 900239 b We 11952 a We have fg2 fffggfggf2fgfg92 f22f9f2v Since 2 1 1 0 in MM we conclude that f g2 f2 92 b Observe rst that 02 0 and 12 1 Thus as a2 a for all a 6 F2 We will prove b by induction on deg f If degf S 07 then x a for some a 6 F2 and so by quot7 f2z a2 a mz Suppose now that degf gt 0 and that b holds for polynomials of degree less that deg f Note that x z gz for some n 6 2 and gz 6 mm with degg lt deg 1 So 92z 9amp2 by the induction assumptions Then using a we compute f290 90 9002 90 2 9290 902 9902 902 So b is proved Let C be the binary linear code with check matrix 1 0 0 1 1 1 0 1 H 0 1 1 1 0 0 1 1 a Find a syndrome look up table for C with respect to H b Let a be the decision rule corresponding to the syndrome look up table in a Compute 01100 and 01110 a Oberve that ColH consist of the eight codewords of length 4 and even weight So there are eight syndrome We compute the syndrome of each word of length 4 in order of their weight7 disrecarding any words whose syndrome already appeared earlier7 until we found all eight syndromes 2 0000 1000 0100 0010 0001 1100 0110 0011 1010 0101 s 0000 1100 0110 0011 1111 1010 0101 0011 1111 1001 x x x x x x X X x MTH 416 Introduction to Algebraic Coding F10 Homework 3Solutions 1 Consider a memoryless source with alphabet S a7b7c7d and probability distribution p 05703701701 Let c be the arithmetic code on ST a Calculate the auerage word length of 62 per symbol and compare it with the entropy of p b Compute c2bd and C3acd a m P n n Pn La 025 4 2 3 075 ab 015 6 3 4 060 at 005 20 5 6 030 ad 005 20 5 6 030 ha 015 6 3 4 060 bb 009 11 4 5 045 be 003 33 6 7 021 bd 003 33 6 7 021 ea 005 20 5 6 030 CI 003 33 6 7 021 CC 001 100 7 8 008 Cd 001 100 7 8 008 ea 005 20 5 6 030 CI 003 33 6 7 021 CC 001 100 7 8 008 Cd 001 100 7 8 008 2135 476 So the average word length is 476 and the average word length per symbol is 476 238 1 1 1 1 Hp 0510g2 03log2 01log2 01log2 m 169 b To simplify the computation of 07 we rst prove 1 If S P is a ordered memoryless source and m m1xn E S Then 71 07x ZPz1xl1ozzi 71 For n 17 this clearly holds So suppose its true for 71 Let 72 6 S 1 and write zys7 zutwithyuES and 82565 Thenzltzifandonlyifultyoruyand t lt 8 Thus altzgt 263me zuegnztestwmggstt zltm u z s 2753 Pltugt P0 23130 altzgt Pltygtaltsgt 21 Px1 xi71ami Px1znamn1 Pm1mi1axi We have and so abc ab Pbac 05 03 08 05 024 074 and aacd aa Paac Pacad 0 05 08 05 01 09 04 0045 0445 Also Pbc 03 3901 003 and Pacd 05 01 3901 0005 We compute m P 04 n n 27 c c be 003 074 33 6 7 9472 95 1011111 acd 0005 0445 200 8 9 22784 228 011100100 SO 02bc 1011111 and 03acd 011100100 2 Use the LZW decoding rules to decode 13785487314568911131243122021351122 if D0 B DE N 0 R T u wxloougtwooxlwgtdu H 91 EHEZOEHPJUU39 0 00x1 01ggtwwgtd Hwozmowg HOOUwEszOHwEUOzmHEZOEHmw gogg ngggwEwEZMHEzOEHm 3 Compute the LZW codeword for MISSISSIPPI if D0 M7I7S7 P quotUUJHK MISSISSIPPI HH HO WN UHgtOJNH FUHHMMHZ mm m UmmHm H H m m wggtugtoo www H D quotU 1 So the codeword is 123368442 4 Consider a channel I with input and output alphabet I J 1 b7 07d Suppose that PM 015 for all ij E I with i 7 j Write down the matrix for this channel Since P is a channel7 1Zr rii 2 Pi P3015 P045 7396 79 for all i E I Thus PM 055 and 5 Let I be a channel with input I and output I Let F be a channel with input I and output K PutF PT so PM ZjEJFQjPjk a Show that P is a channel with input I and output K b If 1w is a BSC with bit error probability e and P is a BSC with bit error probability e show that P is a BSC and compute the bit error probability of P a Let i E I Then 2106K PM 2106K ZjEJ PijFjk Eaart mar2 1 1 1 Since 1 27 and ng are non negative real numbers7 also PM 276 ngF Jlk is a non negative realy numbers Hence implies that PM g 1 for all i 6 I7 k E K So P is a function from I x K to 01 and together with we conclude that F is a channel with input I and output K b We have 1quot 1111 e 17 e equot 17 e 17 5 7 5H 7 255 5 7 5H 7 255 5 7 5H 7 255 17 5 7 5H 7 255 Hence P is a BSC with bit error probability e e e 7 2e e Consider the BSC P with bit error probability e 001 and input probability distribution p 0604 a Compute the probability distribution q of the output b Compare the entropies ofp and q 0 Compute the joint distribution t d Compute Ht7 HPp7 Hqlp7 HMO and Hqll39 6 Verify that 1370 12 190137010 191111011 where p 129072911 31 099 001 001 099 q pr 06 04 0598 0402 HQ 706log206 04log204 m 0971 and Hq 7059810g2 0598 040210g2 0402 m 0972 So the entropy of q is slightly larger than the entropy of p 06 099 001 0594 0006 t 04 001 099 0004 0396 d Ht 70594log2 0594 000610g2 0006 000410g2 0004 039610g2 0396 m 1052 H1 p Ht 7 Hq1052 7 0972 0080 Hq p Ht 7 Hp 1052 7 0971 0081 Hq 0 H099001 709910g2099 00110g2001 0081 Hq 1 H001099 0081 e p0Hq 0 p1Hq 1 m 006 0081 04 0081 0081 s Hq p 7 Let P be a channel with input I and output J Letp and q be probability distribution on I and J respectively linked uia P so q pr Lett be the joint distribution on I X J with respect to p and P so tij pinj De ne Aji for allj E J andi E I De ne A J X I7 gt Aji Show that a A is a channel with input J and output I b p 614 e Let t be the joint distribution on J X I with respect to q and A so tji quji Then tji tij for alli E I andj E J and Ht Ht d Forj E J put Aj A g So Aj is the j th row of A and Aj is a probability distribution on I Put Hp HAj Then Hltp q 20111020 jeJ a LetjEJ We have to ZieItiJ39 qa39 A 77i1 ltgt 71ij i39eI i39eI Since tij is a non negative real number and qj is a postive real number7 A is a non negative real number Thus implies that tij 1 and so A is a function from J x I to 07 1 Together with we conclude that A is a channel with input J and output I b We compute the i coordinate of qA t CIAL39 quAji quil Z7517 jeJ jeJ q jeJ So qA is the marginal distribution of t on I and thus by a lemma in class is equal to tir C 7591 quJ39i qa39qj to Thus 1 1 HW Z tji39 10g2 f Z tijlogzi HOE ji39eJxI W i jeIxJ H d Hplq Ht 7 Hq Ht 7 So d follows from Theorem 513 applied to the Channel A the input distribution q on I7 the output distribution p on I and the joint distribution t on J x I 8 LetT be a channel with input I and output I and suppose there exists a real number r such that Hq r for alli E I Putm Proue that a fr p Hq 7 r for all probability distributions p on I where q pP b The capacity 39y ofP is at most logm 7 r c 39y logm 7 r if and only if there exists a probability distribution p on I such that q is the equal probabilities distribution on I Let 77 be the set of probability distributions on I a Let p E 73 As proved on page 84 of the text book7 fr p Hq 7 Hq By Theorem 513 HMP ZPiHW l i 2W eri r1r i39eI i39eI id and so frP Hq Hqlp Hq 7 r b and Let q be the equal probability distribution on J Then by Theorem 311 frp Hq 7r Hq 7r logzmir with equality if and only if q q Thus 7 maxfrp 10g2 m i r 12673 with equality if and only if q q for some p E 77 that is pF q for some 19 E 77 09 0 01 9 Let P Compute the extended channel F2 0 2 09 0 01 09 0 01 P P x P x 0 1 0 0 1 0 09 0 01 09 0 01 09 0 01 09 0 01 0 1 0 0 1 0 0 1 0 0 09 0 01 1 09 0 01 09 0 01 0 1 0 0 1 0 0 1 0 0 81 0 0 09 0 0 0 09 0 0 01 0 09 0 0 0 0 01 0 0 0 09 0 01 0 0 0 0 0 0 1 0 0 0 0 10 LetF be a binary channel with P00 1 and F10 f where 0 lt f lt 1 Consider a code with codewords C 000111 a Compute P for a E C and z E 133 7 Determine a maximum likelihood decision rule SinceP isa channel7 F00F01 1 and F10F11 1 Hence F01 171000 171 0 and P1117P1017f Thus 1 0 1 f 17f a Let 2 212223 with 21 6 01 Then

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.