Crossover probability
p = 0.1: each bit flips independently
Symmetric.
A binary symmetric channel flips each transmitted bit with probability . Its capacity is , where is the binary entropy function.
This page is easier if you are comfortable with:
The uniform input is optimal, and then bit while , so (mutual information). If the channel is perfect and ; if the output is pure noise and . For , and : about half a bit per use. For , and . The logs are explained in the definition of a logarithm.
The capacity is symmetric about : a channel that flips 90% of bits is as good as one that flips 10%, because we can invert the output. The shape of (a smooth hump with maximum 1 at ) comes from the entropy concept of Shannon entropy; near it rises steeply because of the term (logarithm limits).
The capacity in the channel capacity theorem sets the best rate of a code over this channel, and finite codes are limited by the Hamming bound. Redundancy is a way to buy reliability, in the spirit of code length limits.
A channel that flips bits at random has capacity given by one minus the binary entropy of the flip probability.
Capacity falls to zero at p = 0.5 and is symmetric about it.
These examples are worked by hand, step by step, so you can compare your own working.
Find the capacity for ().
Find the capacity for .
Find the capacity for .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
p = 0.1: each bit flips independently
Symmetric.
0.9³ = 0.729
All survive.
P(error) = 3p²(1 − p) + p³ = 0.028
Two or more flips.
3 × 0.1 × 0.9² = 0.243
Binomial.
A binary symmetric channel flips each transmitted bit independently with probability p. Block error probabilities are binomial: a 3-fold repetition code decoded by majority vote fails when 2 or 3 bits flip, with probability 3p²(1 − p) + p³.
Probability that 3 bits all arrive correctly (p = 0.1).
Probability exactly one of 3 bits flips.
Probability the repetition code decodes wrongly.
By what factor does coding reduce the error rate from p = 0.1?
p²(1 − p) ✗
3p²(1 − p) ✓
Three positions for the correct bit.
only two flips ✗
add p³ ✓
Three flips also fails.
useless ✗
flip the output ✓
Equivalent to 1 − p.
burst errors ✗
BSC flips independently ✓
Model assumption.
Try each one on paper, then open the answer. Use the solver above to see the full working.
0.729
0.243
0.104
0.0073
0.6561
0.0486
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
A channel flipping each bit with probability p.
1 − H(p).
3p²(1 − p) + p³.
Yes, by assumption.
channel capacity.
Singleton and Hamming bounds.
More in Advanced statistics and stochastic processes and the formula sheets.