2
$\begingroup$

Let us have the following definition: We have a W which is an alphabet with |W| = $2^n$ (the number of elements), and a codebook C which maps uniquely each element of the alphabet to the binary sequence of length n. The code is sent over the n-th extension of the binary symmetric channel with crossover probability of p , that is, P[X=1, Y=0] = P[X=0, Y=1] = p. When received, it is decoded with $C^{-1}$.

My question is, how can we find and show conditions on p so that the average probability of error of the channel goes to zero, as $n \rightarrow \infty $ ?

$\endgroup$
2
$\begingroup$

The capacity of the binary symmetric channel is $1-H(p)$ where $H(p)$ is the Shannon entropy of a Bernoulli(p) distribution (see, for example, Cover and Thomas, Elements of Information Theory 2e, Chapter 7).

The rate of a (M,n) code (which maps M input values to a binary vector of length $n$) is $\frac{\log M }{n}$.

The channel coding theorem says that you can achieve any rate below the capacity (i.e. the average/maximum probability of error goes to zero).

In your case, it looks like you want a $(2^n,n)$ code, which has rate $1$, so you can only communicate with vanishing probability of error if $p=0,1$.

$\endgroup$
4
  • $\begingroup$ How do you actually get $p = 0,1$? $\endgroup$ Jun 11 '17 at 17:13
  • $\begingroup$ Entropy is 0 for those two values. If p=0, you get the input at the output. If p=1, you get the inverted input at the output. In either case, you can perfectly map the output to the input. $\endgroup$
    – Batman
    Jun 11 '17 at 19:40
  • $\begingroup$ Okay, so for p=0 or p=1 $H(p) = 0$. Then the capacity will be exactly 1...how does that relate to the rate of the code? Any why do we want a rate of 1? However, can you show that the average error probability goes to 0 when $n$ goes to infinity? $\endgroup$ Jun 11 '17 at 20:08
  • $\begingroup$ You should read my answer (or chapter 7 of Cover & Thomas, Elements of Information Theory 2e). The channel coding theorem tells you rates which are achievable (and otherwise, average/maximal probability of error goes to 1). $\endgroup$
    – Batman
    Jun 11 '17 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.