Introduction to Information Theory

Shannon Theory Overview

• Established in 1948, foundational framework for Information Theory.
• Consists of three main components: measurement of information, source coding theory, and channel coding theory.

Measurement of Information

• Key inquiry: determining how to measure information in bits.
• Events are inherently probabilistic, leading to the conclusion that the entropy function serves as the definitive measure of information.

Entropy Function Example

• Case study: Tossing a die yields 6 outcomes (1, 2, 3, 4, 5, 6).
• Each outcome has an equal probability (1/6).
• The resulting information quantity (2.585 bits) is not an integer, highlighting the abstract nature of information measurement.

Source Coding Theorem

• Shannon's assertion: to reliably store information from a random source X, an average of H(X) bits are needed for each outcome.
• Example: After 1,000,000 dice tosses, storing outcomes with a minimum of 3 bits each totals 3,000,000 bits.
• ASCII requires 8 bits (1 byte) for each outcome, leading to a total of 8,000,000 bits for data storage.

Compression Insights

• Shannon's contribution suggests only 2.585 bits are necessary for data storage per outcome, allowing for significant compression to 2,585,000 bits for 1,000,000 outcomes.
• Comparison of compression ratios reveals the efficiency of Shannon's optimal approach.

Compression Ratio Statistics

• Original file size: 8,000,000 bits (100%).
• Shannon's compressed file size: 2,585,000 bits (32.31% compression).
• Winzip compression: 2,930,736 bits (36.63% compression).
• WinRAR compression: 2,859,336 bits (35.74% compression).

Conclusion

• Shannon's theoretical framework demonstrated substantial potential for data compression, validated mathematically over half a century ago.