WUSTL ESE 523 - ESE523Lec102013 (30 pages)

Previewing pages 1, 2, 14, 15, 29, 30 of 30 page document View the full content.
View Full Document

ESE523Lec102013



Previewing pages 1, 2, 14, 15, 29, 30 of actual document.

View the full content.
View Full Document
View Full Document

ESE523Lec102013

87 views


Pages:
30
School:
Washington University in St. Louis
Course:
Ese 523 - Information Theory
Unformatted text preview:

ESE 523 Information Theory Lecture 12 Joseph A O Sullivan Samuel C Sachs Professor Electrical and Systems Engineering Washington University 2120E Green Hall 211 Urbauer Hall 314 935 4173 jao wustl edu 10 08 13 J A O Sullivan ESE 523 Lecture 12 1 Information Theory and the News http www insidescience org blog 2013 09 13 information theorycounts size animal languages Information Theory Counts Size Of Animal Languages The frequency and repetition of symbols yield a measure of the information content in human languages The symbols in English are the 26 letters of the alphabet plus a space character For animal modes of communication however figuring out the symbols can be a bit trickier and researchers don t have the benefit of huge animal language libraries that they can mine he uses the term N gram As an independent investigator affiliated with the Citizen Scientists League Smith has previously used statistical methods to probe complex linguistic systems like Meroitic an extinct and undeciphered East African language The dolphin s vocabulary has approximately 36 words while the figure for whales is about 23 the starling song repertoire is estimated at 119 to 202 songs 2 10 08 13 J A O Sullivan ESE 523 Lecture 12 Outline Channel Coding Theorem Concept of perfect communication Information capacity Examples properties Definition of achievability Jointly typical pairs of sequences Set up channel coding theorem Channel coding theorem Proof of converse Fano s Inequality 3 10 08 13 J A O Sullivan ESE 523 Lecture 12 Concept of Perfect Communication Perfect communication is possible achievable over any channel input X output Y I X Y 0 W Encoder Xn information transfer Channel p y x Yn 0 code C of length n such that max Pr error c 10 08 13 c C J A O Sullivan ESE 523 Lecture 12 Decoder W 4 Channels A discrete memoryless channel DMC is a triple X p y x Y The nth extension of a discrete memoryless channel is the channel Xn p yn xn Y n where p yk x k y k 1 p yk xk k 1 2 n n n n Without feedback p y x p yk xk k 1 W 10 08 13 Encoder Xn Channel p y x Yn J A O Sullivan ESE 523 Lecture 12 Decoder W 5 Information Capacity Definition The information capacity of a DMC is C max I X Y p x Remark Later we will show that all rates R less than C are achievable where 1 R log Codebook Cardinality n 6 10 08 13 J A O Sullivan ESE 523 Lecture 12 Binary Symmetric Channel Crossover probability q X 0 1 1 q 0 q Y q 1 1 q I X Y H Y H Y X H Y p x H Y X x x H Y h q Achieved when P X 0 0 5 1 h q 7 10 08 13 J A O Sullivan ESE 523 Lecture 12 Z Channel X 1 0 1 I X Y H Y H Y X H Y p 0 0 p 1 1 0 Y 1 2 1 2 1 1 q 2 log 1 q 2 q 2 log q 2 q I X Y max 1 q 2 log 1 q 2 q 2 log q 2 q q 2 5 C log 5 2 q H Y X 0 0 H Y X 1 1 P X 1 q 10 08 13 J A O Sullivan ESE 523 Lecture 12 8 Properties of C C max I X Y p x C is nonnegative I X Y is nonnegative C log X C log Y I X Y is a continuous function of p x I X Y is a concave function of p x Important for optimization strategies such as Blahut Arimoto Proved in an earlier lecture 9 10 08 13 J A O Sullivan ESE 523 Lecture 12 A Channel Code An M n code for X p y x Y consists of An index set 1 2 M An encoding function Xn 1 2 M Xn A decoding function g Y n 1 2 M W Encoder Xn Xn Channel p y x Yn W Decoder g w P g Y n w X n X n w The probability of error is n max w Maximal probability of error w 1 2 M Average probability of error P n 1 e Equally likely codewords 10 08 13 M M w 1 w P g Y n W J A O Sullivan ESE 523 Lecture 12 10 Achievability and Theorem The rate R of an M n code is R logM n bits per transmission The rate R is achievable if there exists a sequence of 2nR n codes such that n 0 as n The capacity of a discrete memoryless channel is the supremum of achievable rates C max I X Y p x p x 0 p x 1 x X Theorem All rates below capacity C are achievable Conversely any sequence of 2nR n codes with n 0 as n must have R C 11 10 08 13 J A O Sullivan ESE 523 Lecture 12 Achievability Proof Outline Use a random code i i d elements of codewords Find the average probability of error averaged over all codewords and over all codes If the average probability of error is low at least one code has low average probability of error averaged over all codewords Throwing away the half of the codewords with the highest probability of error gives a code with maximum probability of error low and the same asymptotic rate 12 10 08 13 J A O Sullivan ESE 523 Lecture 12 Proof forward part Based on random coding Fix p x Generate a random 2nR n code with i i d entries drawn from p x x2 1 x1 1 x 2 x2 2 1 C nR nR x 2 x 2 2 1 2nR xn 1 xn 2 xn 2nR n P C p xi w w 1 i 1 Reveal codebook to encoder and decoder P W w 2 nR Generate a random message Transmit Xn w n n n P y X w p yi xi w The decoder receives Yn i 1 13 Use typical set decoding 10 08 13 J A O Sullivan ESE 523 Lecture 12 Proof of Forward Part Typical Set Decoding and Probability of Error Typical set decoding select Xn w if it is jointly typical with yn and no other codeword is jointly typical with yn Compute the probability of error averaged over all codes Later a particular code is selected Symmetry w r t code index Define error events W W P P C Pe n C C 1 P C nR 2 C 1 nR 2 2nR C P C C w w 1 2nR w 1 C w P C 1 C P W 1 C 14 10 08 13 J A O Sullivan ESE 523 Lecture 12 Jointly Typical Sequences Asymptotic Equipartition Property Definition The set A n of jointly typical sequences with respect …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view ESE523Lec102013 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ESE523Lec102013 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?