SME
Communication Systems
Information theory basics
Use this for “A source sends four symbols with probabilities 1/2, 1/4, 1/8, 1/8. Find its entropy.”
Chart
0.5 + 0.25 + 0.125 + 0.125 = 1.
H = Σ p × (−log₂ p) = 0.5 × 1 + 0.25 × 2 + 0.125 × 3 + 0.125 × 3 = 1.75 bits.
This is an example. Type your own values to start a new problem.
p₁
Probability of symbol 1
example
p₂
Probability of symbol 2
example
p₃
Probability of symbol 3
example
p₄
Probability of symbol 4
example
Σp
Sum of probabilities
worked out (not typed)
H
Entropy
calculated · bit
Hₘₐₓ
Largest entropy
worked out (not typed) · bit
η
Efficiency
calculated · %
Formulas
Σp
=
p₁
+
p₂
+
p₃
+
p₄
1 = 0.5 + 0.25 + 0.125 + 0.125
H
=
−(
p₁
log₂
p₁
+
p₂
log₂
p₂
+
p₃
log₂
p₃
+
p₄
log₂
p₄
)
1.75 = −(0.5 log₂ 0.5 + 0.25 log₂ 0.25 + 0.125 log₂ 0.125 + 0.125 log₂ 0.125)
Hₘₐₓ = log₂ 4
2 = log₂ 4
η
=
100
×
H
Hₘₐₓ
87.5
=
100
×
1.75
2
Assumptions
•
The source sends one of four symbols at a time, each independently of the ones before.
•
Entropy H is in bits per symbol (logs base 2); a symbol never sent adds 0.
•
Four equally likely symbols give the largest entropy, Hₘₐₓ = log₂ 4 = 2 bits.
Step-by-step
WE KNOW
p₁ = 0.5, p₂ = 0.25, p₃ = 0.125, p₄ = 0.125
FIND
sum of probabilities (Σp), entropy (H), largest entropy (Hₘₐₓ), efficiency (η)
Step 1 · Find sum of probabilities (Σp)
Use Σp = p₁ + p₂ + p₃ + p₄
One of the four symbols is always sent, so the probabilities must add to 1.
Σp = 0.5 + 0.25 + 0.125 + 0.125
Σp = 1
Step 2 · Find entropy (H)
Use H = −(p₁ log₂ p₁ + p₂ log₂ p₂ + p₃ log₂ p₃ + p₄ log₂ p₄)
A
symbol
sent
with
probability
p
carries
log₂(
1
p
)
bits;
weight
each
by
how
often
it
is
sent.
H
=
p₁
×
log₂(
1
p₁
)
+
p₂
×
log₂(
1
p₂
)
+
p₃
×
log₂(
1
p₃
)
+
p₄
×
log₂(
1
p₄
)
H
=
0.5
×
log₂(
1
0.5
)
+
0.25
×
log₂(
1
0.25
)
+
0.125
×
log₂(
1
0.125
)
+
0.125
×
log₂(
1
0.125
)
0.5 × 1 + 0.25 × 2 + 0.125 × 3 + 0.125 × 3
0.5 + 0.5 + 0.375 + 0.375
H
=
1.75
bit
Step 3 · Find largest entropy (Hₘₐₓ)
Use Hₘₐₓ = log₂ 4
Four
equally
likely
symbols
carry
the
most:
2
bits
each,
as
2
2
=
4.
Hₘₐₓ = log₂(4)
Hₘₐₓ = 2 bit
Step 4 · Find efficiency (η)
Use η = 100 × H ÷ Hₘₐₓ
How much of the most it could carry the source does carry, as a percent.
η
=
100
×
1.75
2
η
=
175
2
η
=
87.5%
Check
Put the numbers back in. Both sides should match.
1 = 0.5 + 0.25 + 0.125 + 0.125 ✓
1.75 = −(0.5 log₂ 0.5 + 0.25 log₂ 0.25 + 0.125 log₂ 0.125 + 0.125 log₂ 0.125) ✓
2 = log₂ 4 ✓
87.5
=
100
×
1.75
2
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
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.”
Binary symmetric channel capacity
Use this for “A binary symmetric channel flips each bit with probability 0.1. Find its capacity.”
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.”