📡 Shannon's First Theorem

Noiseless Coding Theorem — Fundamental Limit of Lossless Source Coding

1️⃣ What is Shannon's First Theorem?

Shannon's First Theorem is also known as the Noiseless Coding Theorem or Shannon's Source Coding Theorem.

It describes the theoretical limit for lossless compression of data generated by an information source.

The average number of bits required to represent a source symbol cannot be smaller than the entropy of the source.

H(X) ≤ L

where:

• H(X) = entropy of the source
• L = average codeword length

2️⃣ Statement of Shannon's First Theorem

H(X) ≤ L < H(X) + 1

For a discrete memoryless source and a suitable binary prefix code, there exists a code whose average codeword length satisfies:

H(X) ≤ L < H(X)+1

Meaning: Entropy represents the theoretical minimum average number of bits required per source symbol for lossless coding.

3️⃣ Entropy of a Source

Suppose a source produces symbols:

X = {x₁,x₂,...,xₙ}

with probabilities:

P(X) = {p₁,p₂,...,pₙ}

The entropy is:

H(X) = −Σ pᵢ log₂(pᵢ)

where:

• pᵢ is the probability of symbol xᵢ
• logarithm is base 2
• entropy is measured in bits/symbol

4️⃣ Average Codeword Length

Suppose each symbol xᵢ is represented by a codeword of length lᵢ.

L = Σ pᵢlᵢ

Thus the average number of bits per source symbol is the probability weighted average of codeword lengths.

Symbol	Probability	Code	Length	pᵢlᵢ
A	0.50	0	1	0.50
B	0.25	10	2	0.50
C	0.125	110	3	0.375
D	0.125	111	3	0.375

L = 0.50 + 0.50 + 0.375 + 0.375

L = 1.75 bits/symbol

5️⃣ Complete Mathematical Example

Example: Four-Symbol Source

Symbol	Probability	Code	Length
A	0.50	0	1
B	0.25	10	2
C	0.125	110	3
D	0.125	111	3

Step 1 — Calculate Entropy

H = −[0.5log₂0.5 +0.25log₂0.25 +0.125log₂0.125 +0.125log₂0.125]

H = 0.5 + 0.5 + 0.375 + 0.375

H = 1.75 bits/symbol

Step 2 — Calculate Average Code Length

L = Σpᵢlᵢ

L = (0.5)(1)+(0.25)(2)+(0.125)(3)+(0.125)(3)

L = 1.75 bits/symbol

Step 3 — Verify Shannon's Theorem

H ≤ L

1.75 ≤ 1.75

Therefore, the code reaches the entropy bound exactly.

6️⃣ Why Can't We Go Below Entropy?

📊 Information Limit

Entropy represents the average information generated by the source. Lossless coding cannot represent that information using fewer average bits than its information content.

🗜️ Compression Limit

A compression algorithm may reduce the average code length, but it cannot continuously beat the entropy limit for a source without losing information.

💾 Data Storage

Entropy helps estimate how efficiently source data can theoretically be stored.

📡 Communication

It provides a fundamental limit for lossless transmission of source information.

7️⃣ Shannon-Fano Coding Connection

Shannon-Fano coding assigns shorter codes to more probable symbols and longer codes to less probable symbols.

Example

Symbol	Probability	Possible Code
A	0.40	0
B	0.30	10
C	0.20	110
D	0.10	111

Key idea: The more probable a symbol is, the shorter its code should generally be.

8️⃣ Huffman Coding and Shannon's Theorem

Huffman coding is another important lossless source coding technique. It constructs a prefix code with minimum average codeword length among binary prefix codes for a given symbol distribution.

H(X) ≤ L_Huffman < H(X)+1

For some probability distributions, Huffman coding can achieve entropy exactly. For others, it produces an average length slightly above entropy.

9️⃣ Ten Quick Numerical Examples

No.	Source Probabilities	Entropy	Observation
1	0.5, 0.5	1.000	Maximum for 2 symbols
2	0.8, 0.2	0.722	Biased source
3	0.9, 0.1	0.469	Highly biased
4	0.25,0.25,0.25,0.25	2.000	Uniform 4-symbol source
5	0.5,0.25,0.125,0.125	1.750	Non-uniform source
6	0.4,0.3,0.2,0.1	1.846	Four-symbol source
7	0.7,0.1,0.1,0.1	1.357	One dominant symbol
8	0.6,0.2,0.1,0.1	1.571	Moderate uncertainty
9	0.5,0.3,0.2	1.485	Three-symbol source
10	0.25,0.5,0.125,0.125	1.750	Reordered probabilities

🔟 Interactive Shannon Theorem Calculator

Enter four probabilities and four codeword lengths. The probabilities should add up to approximately 1.

P₁

P₂

P₃

P₄

Codeword Lengths

L₁

L₂

L₃

L₄

Click Calculate.

1️⃣1️⃣ Verify the Shannon Bound

H(X) ≤ L

Suppose:

H(X)=1.75

and

L=1.75

Then:

1.75 ≤ 1.75

The code is optimal with respect to the entropy bound.

For a general code, if:

H(X) ≤ L < H(X)+1

the average code length is within one bit per symbol of the theoretical entropy limit.

1️⃣2️⃣ Animated Concept

📡 Source
Symbols

➜

📊 Probability
pᵢ

➜

🧮 Entropy
H(X)

➜

🔤 Codewords
lᵢ

➜

📏 Average
L

➜

✅ H ≤ L

Click Start Animation

1️⃣3️⃣ Applications

🗜️ Data Compression

Used to understand the fundamental limit of lossless compression.

📁 File Compression

The principle is relevant to compression techniques such as Huffman coding and related statistical coding methods.

📡 Communication

Provides the source-coding limit before considering transmission noise.

💾 Storage

Helps determine how efficiently information can theoretically be represented.

1️⃣4️⃣ Formula Summary

Entropy: H(X) = −Σpᵢlog₂(pᵢ)

Average Code Length: L = Σpᵢlᵢ

Shannon's Bound: H(X) ≤ L

Practical Single-Symbol Bound: H(X) ≤ L < H(X)+1

📌 Remember:

Entropy is the fundamental lower bound on the average number of bits per source symbol required by lossless source coding.

Created by Bijan Krishna Paul
B.K.PAUL Bhairab Ganguly College