Typical Sequences 2.10 2001/07/11 2005/10/26 21:02:21.823 GMT-5 Behnaam Aazhang aaz@ece.rice.edu Roy Ha rha@rice.edu Dinesh Rajan dinesh@ece.rice.edu Mohammad Jaber Borran mohammad@ece.rice.edu Behnaam Aazhang aaz@ece.rice.edu entropy information theory typical sequence A description of typical sequences. If the binary symmetric channel has crossover probability ε then if x is transmitted then by the Law of Large Numbers the output y is different from x in n ε places if n is very large. d H x y n ε The number of sequences of length n that are different from x of length n at n ε is n n ε n n ε n n ε x 0 0 0 and ε 1 3 and n ε 3 1 3 . The number of output sequences different from x by one element: 3 1 2 3 2 1 1 2 3 given by 1 0 1 , 0 1 1 , and 0 0 0 . Using Stirling's approximation n n n n 2 n we can approximate n n ε 2 n ε 2 ε 1 ε 2 1 ε 2 n H b ε where H b ε ε 2 ε 1 ε 2 1 ε is the entropy of a binary memoryless source. For any x there are 2 n H b ε highly probable outputs that correspond to this input. Consider the output vector Y as a very long random vector with entropy n H Y . As discussed earlier, the number of typical sequences (or highly probably) is roughly 2 n H Y . Therefore, 2 n is the total number of binary sequences, 2 n H Y is the number of typical sequences, and 2 n H b ε is the number of elements in a group of possible outputs for one input vector. The maximum number of input sequences that produce nonoverlapping output sequences M 2 n H Y 2 n H b ε 2 n H Y H b ε

The number of distinguishable input sequences of length n is 2 n H Y H b ε The number of information bits that can be sent across the channel reliably per n channel uses n H Y H b ε The maximum reliable transmission rate per channel use R 2 M n n H Y H b ε n H Y H b ε The maximum rate can be increased by increasing H Y . Note that H b ε is only a function of the crossover probability and can not be minimized any further. The entropy of the channel output is the entropy of a binary random variable. If the input is chosen to be uniformly distributed with p X 0 p X 1 1 2 . Then p Y 0 1 ε p X 0 ε p X 1 1 2 and p Y 1 1 ε p X 1 ε p X 0 1 2 Then, H Y takes its maximum value of 1. Resulting in a maximum rate R 1 H b ε when p X 0 p X 1 1 2 . This result says that ordinarily one bit is transmitted across a BSC with reliability 1 ε . If one needs to have probability of error to reach zero then one should reduce transmission of information to 1 H b ε and add redundancy. Recall that for Binary Symmetric Channels (BSC) H Y | X p x 0 H Y | X = 0 p x 1 H Y | X = 1 p x 0 1 ε 2 1 ε ε 2 ε p x 1 1 ε 2 1 ε ε 2 ε 1 ε 2 1 ε ε 2 ε H b ε Therefore, the maximum rate indeed was R H Y H Y | X X Y The maximum reliable rate for a BSC is 1 H b ε . The rate is 1 when ε 0 or ε 1 . The rate is 0 when ε 1 2

This module provides background information necessary for an understanding of Shannon's Noisy Channel Coding Theorem. It is also closely related to material presented in Mutual Information.