7.6 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.

Using Stirling's approximation

Consider the output vector $Y$ as a very long random vector with entropy $nH(Y)$ . As discussed earlier , the number of typical sequences (or highly probably) is roughly $2^{(nH(Y))}$ . Therefore, $2^n$ is the total number of binary sequences, $2^{(nH(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 thatproduce nonoverlapping output sequences

The number of distinguishable input sequences of length $n$ is

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)=\frac{1}{2}$ .

Then

Recall that for Binary Symmetric Channels (BSC)

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 .