1948, Shanon's fundamental problem: Reliable communication over an unreliable channel

 

eg:

 

 

 

 

 

 

 

 

 

change the physics: replace equipment with a better one. 

system solution: add encoding and decoding 

 

 

 

 hat means a guess

 

s -> \hat{s}

 

toy example: binary symmetric channel

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

partity coding: even->0 for p; odd->1 for p

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

\hat{s} = 0 1 1 1 1

 

 

 

 

why the majority vote decoder is the best?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  

 

 

 

 

 

 

 

 answer: 61

 

 

 

 

74 hamming code

 

 

 

 

 

 

encoder: even for 0 and odd for 1

 

 

decoder:

 

the second one got flipped but we dont know yet.

 

 

 

 

t = 1000101

 

any single flip can be detected and corrected, but if >1, then in trouble

 

 

 

 

 

 

 

 

 Shanon proved that you can  get the error probability arbitrarily small , without the rate having to go to zero

and the boundary between achievable and unachievable is the green line

 

 C is the capacity

 

 

 

 

 binary symmetric channel : bsc

 

binary entropy function

 

eg, f=0.1 => H2f = 0.53 => only two disk in the box and there exists an encoding system and a decoding system that can correct as many errors as you want (< all errors).

=> shanon's noisy channel coding theorem