Binary Symmetric Channel Explained with Worked Examples

A binary symmetric channel flips each transmitted bit with probability . Its capacity is , where is the binary entropy function.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Binary symmetric channel means

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.

What is it used for?

A channel that flips bits at random has capacity given by one minus the binary entropy of the flip probability.

How to use binary symmetric channel

  1. Identify the flip probability .
  2. Compute .
  3. Subtract from 1.
  4. The result is the capacity in bits per use.

Graph

Capacity 1 − H₂(p) of the binary symmetric channelp = 0.11: 0.5001p = 0.5: 00.10.20.30.40.50.60.70.80.900.20.40.60.81Capacity 1 − H₂(p) of the binary symmetric channelpcapacityC = 1 − H₂(p)Graph with x from 0.001 to 0.999 and y from 0 to 1.05. Shows the curve C = 1 − H₂(p); point p = 0.11: 0.5001 at (0.11, 0.5001); point p = 0.5: 0 at (0.5, 0).

Capacity falls to zero at p = 0.5 and is symmetric about it.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: p = 0.11

Find the capacity for ().

Worked example
Answer
0.50010.5001
  1. Formula

Example 2: p = 0.5

Find the capacity for .

Worked example
Answer
00
  1. H₂(0.5)

Example 3: p = 0.01

Find the capacity for .

Worked example
Answer
0.91920.9192
  1. H₂(0.01)

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Crossover probability

p = 0.1: each bit flips independently

Symmetric.

No error in 3 bits

0.9³ = 0.729

All survive.

Repetition code (3), majority

P(error) = 3p²(1 − p) + p³ = 0.028

Two or more flips.

Exactly one flip

3 × 0.1 × 0.9² = 0.243

Binomial.

Word problems

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

All correct

Probability that 3 bits all arrive correctly (p = 0.1).

  1. 0.9³
  2. Check: ✓0.729.

One flip

Probability exactly one of 3 bits flips.

  1. 3 × 0.1 × 0.81
  2. Check: ✓0.243.

Majority fails Higher

Probability the repetition code decodes wrongly.

  1. 3 × 0.01 × 0.90.027
  2. + 0.001
  3. Check: 0.028 ✓0.028.

Improvement Higher

By what factor does coding reduce the error rate from p = 0.1?

  1. 0.1 ÷ 0.028
  2. Check: 3.57 ✓3.57.

Common mistakes

Forgetting the combinations

p²(1 − p) ✗

3p²(1 − p) ✓

Three positions for the correct bit.

Ignoring three flips

only two flips ✗

add p³ ✓

Three flips also fails.

Assuming p > 0.5 is hopeless

useless ✗

flip the output ✓

Equivalent to 1 − p.

Dependent flips

burst errors ✗

BSC flips independently ✓

Model assumption.

Exam tips

  1. Independent flips.
  2. Binomial counts.
  3. Majority: ≥ 2 flips fail.
  4. Capacity 1 − H(p).
  5. Check probabilities sum to 1.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. 0.9^3 to 3 d.p. Foundation

0.729

2. 3 × 0.1 × 0.9² to 3 d.p. Foundation

0.243

3. Majority error for p = 0.2 to 3 d.p. Foundation

0.104

4. Majority error for p = 0.05 to 4 d.p. Higher

0.0073

5. P(0 flips in 4 bits), p = 0.1, to 4 d.p. Higher

0.6561

6. P(exactly 2 flips in 4), p = 0.1, to 4 d.p. Higher

0.0486

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Binary symmetric channel (BSC)
Flips bits with probability p.
Crossover probability (p)
Chance of a flip.
Repetition code
Repeats each bit.
Majority decoding
Pick the more common bit.
Block error probability
Chance the decoded bit is wrong.
Binomial distribution
Counts independent flips.

Frequently asked questions

What is a binary symmetric channel?

A channel flipping each bit with probability p.

What is its capacity?

1 − H(p).

What is the error rate of a 3-repetition code?

3p²(1 − p) + p³.

Are flips independent?

Yes, by assumption.

Which page covers capacity?

channel capacity.

Which page covers coding bounds?

Singleton and Hamming bounds.

More in Advanced statistics and stochastic processes and the formula sheets.