SME
Communication Systems · Problem type
Binary symmetric channel capacity
Use this for “A binary symmetric channel flips each bit with probability 0.1. Find its capacity.”
This is an example. Type your own values to start a new problem.
H(p)
=
−
p
log₂
p
−
(1
−
p
)
log₂(1
−
p
)
C
=
1
−
H(p)
Formulas
H(
p
)
=
−
p
log₂
p
−
(1
−
p
)
log₂(1
−
p
)
0.469 = −0.1 log₂ 0.1 − (1 − 0.1) log₂(1 − 0.1)
C
=
1
−
H(
p
)
0.531 = 1 − 0.469
Assumptions
•
Each bit sent is flipped with probability p, independently, a 0 as likely as a 1.
•
H(p) is the binary entropy: the uncertainty, in bits, that the channel adds to each bit.
•
C is in bits per channel use; p and 1 − p give the same capacity.
Step-by-step
WE KNOW
p = 0.1
FIND
binary entropy (H(p)), capacity per use (C)
Step 1 · Find binary entropy (H(p))
Use H(p) = −p log₂ p − (1 − p) log₂(1 − p)
A
flip
with
probability
p
carries
log₂(
1
p
)
bits
of
surprise,
no
flip
log₂(
1
1 −
p
);
weight
each
by
how
often
it
happens.
H(
p
)
=
p
×
log₂(
1
p
)
+
(1
−
p
)
×
log₂(
1
1 −
p
)
H(
p
)
=
0.1
×
log₂(
1
0.1
)
+
(1
−
0.1)
×
log₂(
1
1 − 0.1
)
0.1 × 3.3219 + 0.9 × 0.152
0.3322 + 0.1368
H(
p
)
=
0.469
bit
Step 2 · Find capacity per use (C)
Use C = 1 − H(p)
Each
use
sends
1
bit,
but
H(
p
)
of
it
is
lost
to
the
flips.
C
=
1
−
0.469
C
=
0.531
bit
Check
Put the numbers back in. Both sides should match.
0.469 = −0.1 log₂ 0.1 − (1 − 0.1) log₂(1 − 0.1) ✓
0.531 = 1 − 0.469 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Information theory basics
Main lesson
Shannon capacity
Use this for “A 3 kHz phone line has a 30 dB signal-to-noise ratio. Find its Shannon capacity.”
Average code length
Use this for “Codewords of 1, 2, 3 and 3 bits are sent with probabilities 1/2, 1/4, 1/8, 1/8. Find the average length.”
Block code rate and correction
Use this for “The (7, 4) Hamming code has minimum distance 3. Find its rate and the errors it corrects and detects.”