Suppose we have a communication channel that has a bit-error rate of 50% and the bits are flipped at random such that the receiver has no efficient way to tell which bits have been flipped and there are no error correction bits transmitted with the signal. How do you calculate the information loss (in bits) imposed by the channel? I know there a Shannon formula for doing this but I don't know what it is! Could someone solve this for me with a specific example? Thank you.

  • 2
    $\begingroup$ I don't have the formula at hand, but I can tell you that the information rate is 0. This is easy to see once you realize that all output bit streams are equally likely regardless of the input bit stream. $\endgroup$ – Jim Clay Mar 1 '14 at 2:43
  • $\begingroup$ And is this homework? $\endgroup$ – Jim Clay Mar 1 '14 at 2:43
  • 2
    $\begingroup$ Whether or not any "error correction bits" are transmitted with the signal, the channel capacity is $0$ as Jim Clay has already pointed out. If you want a specific formula that evaluates to $0$, then calculate the capacity from $$C = 1 - H(p) = 1 + p\log_2 p + (1-p)\log_2(1-p)$$ where $p$ is the crossover probability, $\frac{1}{2}$ in this case. $\endgroup$ – Dilip Sarwate Mar 1 '14 at 3:32
  • $\begingroup$ @JimClay Hi Jim and thank you and Dilip for the insightful comments, and no this is not homework, I am just a beginner in information theory. $\endgroup$ – William Hird Mar 1 '14 at 4:28

A binary input - binary output channel which flips bits with equal probabilities is known as a Binary Symmetric Channel. bsc

(Image Credit: Wikipedia - Binary Symmetric Channel)

The channel capacity $C$ is the maximum (actually, a supremum) mutual information between the channel inputs and the channel outputs over input distributions. You can't get information through a channel more than its capacity. Intuitively, this says that by designing the way you put inputs into the channel well, you can maximize the amount of stuff coming out of the channel that you can recover (and this limit is the capacity).

Mathematically, this is $$C = \sup_{p(x)} I(X;Y)$$ where $p(x)$ is probability distributions on the input $X$ and $Y$ is the output of the channel.

In this case, you can write the input of the channel as $P(X=0) = q$ and $P(X=1) = 1-q$. With this distribution, you can see that $P(Y=0) = P(X=0 \text{ and no crossover}) + P(X = 1 \text { and crossover}) = q(1-p) + (1-q)p$ and $P(Y=1) = 1-P(Y=0)$. The mutual information between $X$ and $Y$ is given by $I(X;Y)=\sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}$ where $p(x,y)$ is the joint distribution of $x$ and $y$, and $p(x)$, $p(y)$ are the distributions of $x$ and $y$ respectively. By writing down $I(X;Y)$ and then maximizing over $q$, you will see $C = 1 - H(p)$ where $H(p)$ is the binary entropy function $-p \log_2 p - (1-p) \log_2 (1-p)$. Then, in your case, $p = \frac{1}{2}$ where $H(p) = 1$, so the capacity is $0$.

If you're interested in learning more about this, a few good books to look (at very different levels of difficulty):

  • Elements of Information Theory (Second Edition), by Tom Cover and Joy Thomas (Easy, Probably Best Starting Point)
  • Information Theory and Reliable Communication, by Robert Gallegar (A bit harder)
  • Information Theory: Coding Theorems for Discrete Memoryless Channels by Czisar and Korner (Pretty hard)
  • Information Theory by Robert B. Ash (Dover book, Easy)

And an unrelated book which I love, but couldn't keep myself from mentioning, is David Mackay's Information Theory, Inference and Learning Algorithms (free on his website), even though it doesn't go over channel capacity.

  • $\begingroup$ Nice answer :-) $\endgroup$ – William Hird Mar 1 '14 at 14:31

the information capacity through a channel is, from Shannon,

$$ I = \int_0^B \log_2 \left( 1 + \frac{S(f)}{N(f)} \right) df $$

where $I$ is the rate of information passed through the channel in bits per unit time, $B$ is the one-sided bandwidth, $S(f)$ is the power spectrum of the signal and $N(f)$ is the power spectrum of the noise.

  • $\begingroup$ -1 This answer is not useful. $\endgroup$ – Dilip Sarwate Mar 1 '14 at 3:33
  • $\begingroup$ The channel considered in this problem is a binary symmetric channel, for which this does not apply. $\endgroup$ – Batman Mar 1 '14 at 5:52
  • $\begingroup$ both of you guys are mistaken, technically. if you make some assumptions (like $S(f)/N(f)$ is constant with $f$, at least for $0<f<B$), you can derive $S/N$ from the problem statement. that equation is the sole governing relationship. you down-arrows speak more about your useful answers than about mine. $\endgroup$ – robert bristow-johnson Mar 1 '14 at 16:58
  • 2
    $\begingroup$ Unfortunately, comments cannot be downvoted, but the answerer's response above is even more nonsensical and useless (and deserving of a downvote) than the original answer. $\endgroup$ – Dilip Sarwate Mar 1 '14 at 22:47

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.