Information Theorymessage1message2message3…ORsymbol1symbol2symbol3…Informationsourcetransmitter (encode)receiver(decode)destinationmessage signal messagenoisesourceInformation source selects a desired message from a set of possible messages OR selects a sequence of symbols from a set of symbolsto represent a message. communication channelANDmessage1=symbol1, symbol2message2=symbol3, symbol5Destination decides which messageamong set of (agreed) possible messages,the information source sent.Transition MatrixToFrom1122330.2 0.8 00.4 0 0.60.5 0.5 0Starting from 1, the next number will be 1 (20%), 2(80%), 3 (0%)Starting from 2, the next number will be 1 (40%), 2( 0%), 3 (60%)Starting from 3, the next number will be 1 (50%), 2(50%), 3 (0%)The first number has a 20% chance of being 1, 40% of being 2, and 40% of being 3 ! v = 0.2 0.4 0.4[ ]! P =0.2 0.8 00.4 0 0.60.5 0.5 0" # $ $ $ % & ' ' ' Discrete Markov ChainToFromArrows originating in State 1Arrows originating in State 2Arrows originating in State 3120.50.60.40.80.20.531122330.2 0.8 00.4 0 0.60.5 0.5 0ip(i)1! 0.22! 0.43! 0.4j1231! 0.2! 0.8! 02! 0.4! 0! 0.6i3! 0.5! 0.5! 0pi(j)j1231! 0.04! 0.16! 02! 0.16! 0! 0.24i3! 0.2! 0.2! 0p(i,j)Digram probabilitiesp(i,j)=p(i)pi(j)What are the relative frequencies of the combination of symbolsij=11,12,13… (digram) after one time step?After one step11 4%12 16%13 0%21 16%22 0%23 24%31 20%32 20%33 0%What about in steady state?mymarkovonestep.mvx + vy + vz + . . .=1What is the probability distribution in the steady state?VssP= Vssvss=[vx vy vz …]n+1 equationsn unknownsVssP= Vss! vxvyvz[ ]0.2 0.8 00.4 0 0.60.5 0.5 0" # $ $ $ % & ' ' ' = vxvyvz[ ]! 0.2vx+ 0.4vy+ 0.5vz= vx0.8vx+ 0vy+ 0.5vz= vy0vx+ 0.6vy+ 0vz= vzvx+ vy+ vz= 1! vxvyvz[ ]= 0.354 0.404 0.242[ ]1 35.4% 2 40.4%3 24.2% In the homework, the initial and steady state probability distributions are the same.mymarkovss.mip(i)10.3542! 0.4043! 0.242j1231! 0.2! 0.8! 02! 0.4! 0! 0.6i3! 0.5! 0.5! 0pi(j)j1231! 0.0708! 0.2832! 02! 0.1616! 0! 0.2424i3! 0.121! 0.121! 0p(i,j)Steady State Digram probabilitiesp(i,j)=p(i)pi(j)What are the steady state relative frequencies of the combinationof symbols ij=11,12,13,… (digram)?Step in steady state11 7%12 28%13 0%21 16%22 0%23 24%31 12%32 12%33 0%1 35.4% 2 40.4%3 24.2% H=-(0.708)log2(0.708)-(0.2832)*log2(0.2832)-0-(0.1616)log2(0.1616)- (0.2424)log2(0.2424)- (0.121)log2(0.121) = 2.526 bits/(symbol combo) mymarkov.m, mymarkovss2.mEntropyH(X,Y)=H(X)+H(Y)The average information per symbol is greatest when the symbols equiprobable.Average information/symbol called Entropy H! H = " pilog pi( )i#H also obeys additive propertyif events are independent.For unfair coin, pH=p, pT=(1-p) Information TheoryInformationsourcetransmitter (encode)receiver(decode)destinationsymbolssymbolscommunication channelHsource(p)0/1’sH is the average number of bits/symbol to represent the information. If you encode using morebits/symbol, then the extra bits are redundant. Compression removes the redundancy. Youcan't compress more after the redundancy is gone; all you are left with is information.The entropy gives us a lower limit on the number of bits per symbol we can achieve.“Quinn’s interpretation”When sending straight binary code, if some letters are more common than others, 0's and1's won't be equally probable in the (0/1) stream. Using encoding, we can try to makethe (0/1) stream have equiprobable 0's and 1's. Shannon-Fano coding splits the symbol frequency chart 50/50, then repeats for each branch. Each (0/1) stream will be answering "is the symbol you want to send in the upper branchor lower branch?" and there's a (close to) equiprobable chance it will be either.So, the amount of information in the (0/1) stream is increased using the compression codingover the simple binary coding. Using more complicated compression coding, you can come closer to the (0/1) stream having equiprobable 0's and 1's.CompressionShannon Fano Split symbols so probabilities halvedEx. “How much wood would a woodchuck chuck” 31 charactersASCII 7bits/character, so 217 bitsFrequency charto 0.194c 0.161h 0.129w 0.129u 0.129d 0.097k 0.065m 0.032a 0.032l 0.032! H = " pilog pi( )i#H=-(0.194 log20.194 + 0.161 log20.161 +…)H=2.706 bits/symbol, so 83.7 bits for sentenceo has -log20.194=2.37 bits of informationl has -log20.032= 4.97 bits of informationThe rare letters carry more informationZIP implosion algorithm uses thisCompressionShannon Fano Split symbols so probabilities halved(or as close as possible)Ex. “How much wood would a woodchuck chuck” 31 charactersFrequency charto 0.194c 0.161h 0.129w 0.129u 0.129d 0.097k 0.065m 0.032a 0.032l 0.0320.4840.5160.1940.290.2580.2580.1610.1610.1290.1290.1290.0970.0650.096 0.0320.064 0.0320.032CompressionShannon Fano Split symbols so probabilities halvedEx. “How much wood would a woodchuck chuck” 31 charactersFrequency charto 0.194c 0.161h 0.129w 0.129u 0.129d 0.097k 0.065m 0.032a 0.032l 0.0321011101011000100011010001000 000100000000100000000001000000CompressionShannon Fano Split symbols so probabilities halvedEx. “How much wood would a woodchuck chuck” 31 charactersFrequency charto 0.194c 0.161h 0.129w 0.129u 0.129d 0.097k 0.065m 0.032a 0.032l 0.0321011101011000100011010001000 00010000000010000000000100000011101100011010001000100001000001000000“Prefix free - one code is never the start of another code”CompressionShannon Fano Split symbols so probabilities halvedEx. “How much wood would a woodchuck chuck” 31 charactersEncoding charto 0.194 6c 0.161 5h 0.129 4w 0.129 4u 0.129 4d 0.097 3k 0.065 2m 0.032 1a 0.032 1l 0.032 1p #6(2)+5(3)+4(3)+4(3)+4(3)+3(3)+2(4)+1(5)+1(6)+1(6)=97 bits97bits/31 characters=3.129 bits/characterH=2.706 bits/symbol11101100011010001000100001000001000000Huffman CodingEx. “How much wood would a woodchuck chuck” Frequency charto 0.149c 0.161h 0.129w 0.129u 0.129d 0.097k 0.065m 0.032a 0.032l 0.032o 0.149c 0.161h 0.129w 0.129u 0.129d 0.097k 0.065al 0.064m 0.032Add two lowest probabilitiesgroup symbolsResortRepeato 0.149c 0.161h 0.129w 0.129u 0.129d 0.097alm 0.096k 0.065o 0.149c 0.161almk 0.161h 0.129w 0.129u 0.129d 0.097Huffman CodingEx. “How much wood would a woodchuck chuck” o 0.194c 0.161h 0.129w 0.129u 0.129d 0.097k 0.065m 0.032a 0.032l 0.032o 0.194c 0.161h 0.129w 0.129u