Claude Shannon – In MemoriamOutlineClaude ShannonEntropySource CodingSource Coding (c’d)Slide 7Channel CapacityChannel Capacity (c’d)Slide 10Separation TheoremUCBClaude Shannon – In MemoriamJean WalrandU.C. Berkeleywww.eecs.berkeley.edu/~wlrUCBOutlineClaude ShannonEntropySource CodingChannel CodingSeparation TheoremUCBClaude Shannon4/30/1916 – 2/24/200137: Boolean Algebra Logical Circuits48: Mathematical Theory of CommunicationsUCBEntropyHow much information is required to convey the value of a random variable?Key insight: The quantity of information is related to the uncertainty of that value.Example 1: Coin Flip = One bit of informationExample 2: Two coin flips = 2 bitsExample 3: N equally likely values = log2(N) bitsUCBSource CodingHow do we encode the values to be able to convey them with the minimum number of bits?Key idea: Look at sequence of outcomesX(1), X(2), …, X(n) where X(m) is in {1, 2, …, K}For n large, there are only 2nH equally likely sequences where H is smaller than log2KIn fact, H = - pi log2(pi)UCBSource Coding (c’d)Example:P(1) = p = 1 – P(0)H = - p log2p – (1 – p)log2 (1 – p)Hp100.5 10UCBSource Coding (c’d)Thus, for large n:2n n-bit words2nH equallylikely n-bit words.UCBChannel CapacityQuestion: How fast can one transmit bits reliably through a noisy channel?Naïve answer: No reliable transmission is possible.Shannon’s formulation: What is the possible rate, in the long term, if one wants the bit error rate to be arbitrarily small?Shannon’ s answer: Channel CapacityUCBChannel Capacity (c’d)Example:0101Sent Receivedpp1 - p1 - pCp100.5 10UCBChannel Capacity (c’d)Justification: Choose 2nK n-bit words (fair coin flips)2n equally likelyn-bit words2nH equallylikely n-bit words forone wordsent.=> 2n/2nH = 2n(1 – H) = 2nC distinguishable codewordsUCBSeparation TheoremSource with Entropy H bits per symbolChannel with Capacity C bpsCan send C/H symbols per secondsFirst code symbols (n symbols => nH bits)Then code channel(send bits with suitable codewords)Hence: Separate source and channel
View Full Document
Unlocking...