SME
Communication Systems · Problem type
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.”
Diagram
Each symbol is a leaf, its codeword the 0s and 1s on the way down; no codeword starts another.
Kraft sum: 2⁻¹ + 2⁻² + 2⁻³ + 2⁻³ = 1.
L = 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.
l₁
Length of symbol 1
example · bit
l₂
Length of symbol 2
example · bit
l₃
Length of symbol 3
example · bit
l₄
Length of symbol 4
example · bit
p₁
Probability of symbol 1
example
p₂
Probability of symbol 2
example
p₃
Probability of symbol 3
example
p₄
Probability of symbol 4
example
L
Average length
calculated · bit
K
Kraft sum
calculated
Formulas
L
=
p₁
×
l₁
+
p₂
×
l₂
+
p₃
×
l₃
+
p₄
×
l₄
1.75 = 0.5 × 1 + 0.25 × 2 + 0.125 × 3 + 0.125 × 3
K
=
2
−
l₁
+
2
−
l₂
+
2
−
l₃
+
2
−
l₄
1
=
2
-1
+
2
-2
+
2
-3
+
2
-3
Assumptions
•
A prefix code: no codeword starts another, so each symbol is a leaf of the code tree.
•
Lengths fit a prefix code exactly when the Kraft sum is at most 1.
•
No prefix code beats the entropy: L ≥ H, equal when each length is log₂(1 ÷ p).
Step-by-step
WE KNOW
l₁ = 1 bit, l₂ = 2 bit, l₃ = 3 bit, l₄ = 3 bit, p₁ = 0.5, p₂ = 0.25, p₃ = 0.125, p₄ = 0.125
FIND
average length (L), Kraft sum (K)
Step 1 · Find average length (L)
Use L = p₁ × l₁ + p₂ × l₂ + p₃ × l₃ + p₄ × l₄
Each codeword’s length, weighted by how often it is sent.
L
=
0.5
×
1
+
0.25
×
2
+
0.125
×
3
+
0.125
×
3
0.5 + 0.5 + 0.375 + 0.375
L
=
1.75
bit
Step 2 · Find Kraft sum (K)
Use K = 2−l₁ + 2−l₂ + 2−l₃ + 2−l₄
A
codeword
of
length
l
uses
up
2
−l
of
the
tree:
half
for
1
bit,
a
quarter
for
2.
K
=
2
-1
+
2
-2
+
2
-3
+
2
-3
0.5 + 0.25 + 0.125 + 0.125
K
=
1
Check
Put the numbers back in. Both sides should match.
1.75 = 0.5 × 1 + 0.25 × 2 + 0.125 × 3 + 0.125 × 3 ✓
1
=
2
-1
+
2
-2
+
2
-3
+
2
-3
✓
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.”
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.”