Shannon's Noisy Coding Theorem

The Noisy Typewriter:

The setting is:

• A typewriter with only 26 keys {A,B,..,Z} no shift key, in particular, the input and output alphabets are {A,B,..,Z}
  
  

• The typewriter is defective in that if you strike a key with a given letter, that letter or the letter following will be printed with equal probability.

  For an A you get an A or a B. To complete the cycle, for a Z you get a Z or an A. For example EEFE
  
  

• Finally, to simplify our calculations we assume a Uniform Distribution for any letter

Some Calculations:

1. BA BAABB , hence B

2. 

3. 

4. 

5. because the Channel is Symmetric (check) and

Three Fixes:

1. Halving the alphabet used, to the 13 of the 26 letters available, in particular {A,C,E,G,I,K,M,P,R,T,V,W,Y} - Given the letter that appears we could know with certainty which letter was typed. For example, If you type an E you might see an E or F but F is not a possibility and the only other way you could see an E is if a D was typed, also not a possibility.

2. Halving the effective transmission rate - We can transmit the 26 letter alphabet using the 13 letters above, however we require two transmitted letters to transmit 1 letter that can be read correctly, halving the effective transmission rate. For example:

   • if you want to type an E or F , in either case first type an E
     

   • Next, type A if you wanted an E or a C if you wanted an F.
     

   • To correctly read the letter typed:

     • Seeing an E or F, you know that a was E typed.

     • If the next letter is an A or B , then you know an A was typed. If the next letter is an C or D , then you know a C was typed
       

   • Again EA is E and EC is F.
     

   • It takes two transmissions to transmit bits. The effective transmission rate is bits per transmission.
     

     
     

3. Extend the Encode/Decode Protocol of 2. -

   Rather than 1 character + 1 check character. Send 2 characters + an error check character . For example to transmit TH, TI, UH, or UI we would type TH plus one of four check characters A,C,E, or G. The arithmetic is now, to transmit two characters without error we need to send three.
   
   

   It takes three transmissions to transmit bits. The effective transmission rate is bits per transmission.
   
   

   Going to three characters. + an error check character .
   
   We need 8 error check values, say A,C,E,G,I,K,M,P.

   What does the Math. look like?
   
   

   We cannot go any further with this specific approach because we only have 13 potential error check character values and we would need .16

   However, for the moment assume we could, what does the Math look like?
   
   

4. However we could use more than one check character. Suppose we used two check characters. Sending 6 characters + 2 error check characters gives the same transmission rate as 3 characters + 1 error check character, However, 2 error check characters allows 13 169 potential error check character values To correct 7 characters we only need 128 = 2 What would the effective transmission rate be if we could take advantage of this arithmetic?
   
   

5. Conjecture: We can get closer and closer to the Capacity but only for longer and longer messages that can take advantage of the improved rate
   
   

__________________________________________________________________________________________

Shannon's Noisy Coding Theorem for BSCs:

Given a Binary Symetric Channel,

.and Channel Matrix

We will use the fairly standard notation . Hence

and the Capacity

Theorem:

Let and , then for sufficienty large integers and we can find:

• an code with :
  
  

• 
  
  

• , where is to be read " cannot be unabiguiously decoded."
  
  

such that