ℹ️Information Theory Unit 1 – Introduction to Information Theory

What's Information Theory?

• Field of study that quantifies, stores, and communicates information
• Developed by Claude Shannon in the 1940s at Bell Labs
• Provides mathematical framework for analyzing information transmission, storage, and processing
• Applies to diverse areas including telecommunications, data compression, cryptography, and machine learning
• Fundamental concepts include entropy, mutual information, channel capacity, and coding theory
• Enables efficient and reliable communication systems (internet, smartphones, satellite communications)
• Plays crucial role in modern digital technologies and infrastructure

Key Concepts and Definitions

• Information defined as reduction in uncertainty after receiving a message
• Bit basic unit of information, represents binary choice between two equally likely alternatives
• Source generates messages or sequences of symbols drawn from an alphabet
• Encoder converts source messages into codewords for transmission over a channel
• Channel medium over which encoded information is transmitted (wired, wireless, optical fiber)
• Decoder reconstructs original message from received codewords
• Noise any factor that corrupts or interferes with the transmitted signal
• Distortion measure of dissimilarity between the original and reconstructed messages

Measuring Information

• Amount of information in a message depends on its probability
• Less likely messages convey more information than more predictable ones
• Self-information $I(x) = -\log_2 P(x)$, where $P(x)$ is the probability of event $x$
  • Measured in bits if logarithm base 2 is used
• Joint entropy $H(X,Y)$ measures uncertainty in a pair of random variables $X$ and $Y$
  • $H(X,Y) = -\sum_{x,y} P(x,y) \log_2 P(x,y)$
• Conditional entropy $H(Y|X)$ uncertainty in $Y$ given knowledge of $X$
  • $H(Y|X) = -\sum_{x,y} P(x,y) \log_2 P(y|x)$
• Mutual information $I(X;Y)$ reduction in uncertainty of $Y$ due to knowledge of $X$
  • $I(X;Y) = H(Y) - H(Y|X)$

Entropy: The Heart of Information Theory

• Entropy $H(X)$ measures average amount of information or uncertainty in a random variable $X$
  • $H(X) = -\sum_{x} P(x) \log_2 P(x)$
• Quantifies the minimum number of bits needed to encode a message without loss
• Maximum entropy achieved when all outcomes are equally likely
• Joint entropy, conditional entropy, and mutual information are derived from basic entropy concept
• Entropy used to characterize information sources, channels, and communication limits
• Plays central role in data compression, coding theory, and cryptography
• Understanding entropy is key to designing efficient information processing systems

Data Compression Basics

• Data compression reduces size of data by removing redundancy
• Lossless compression allows perfect reconstruction of original data (text, executable files)
  • Examples: Huffman coding, arithmetic coding, Lempel-Ziv algorithms
• Lossy compression achieves higher compression ratios but with some information loss (images, audio, video)
  • Examples: JPEG, MP3, MPEG
• Compression ratio measures reduction in data size, $CR = \frac{\text{uncompressed size}}{\text{compressed size}}$
• Theoretical limit for lossless compression is the entropy of the data source
• Practical compression algorithms balance compression ratio, computational complexity, and data type

Channel Capacity and Noise

• Channel capacity $C$ maximum rate at which information can be reliably transmitted over a noisy channel
  • $C = \max_{P(X)} I(X;Y)$, maximized over input distribution $P(X)$
• Shannon's noisy channel coding theorem establishes fundamental limits of communication
• Noise reduces channel capacity and introduces errors in transmitted messages
• Signal-to-noise ratio (SNR) measures relative strength of signal compared to noise
  • Higher SNR enables higher channel capacities
• Channel coding introduces redundancy to combat noise and ensure reliable communication
• Examples of noisy channels: wireless links, telephone lines, storage media
• Capacity-achieving codes (Turbo codes, LDPC codes) approach theoretical limits

Coding Theory Fundamentals

• Coding theory studies design of error-correcting codes for reliable data transmission and storage
• Error-correcting codes add redundancy to messages to detect and correct errors introduced by noise
• Linear block codes encode $k$ information bits into $n$-bit codewords, $n > k$
  • Generator matrix $G$ used for encoding, parity-check matrix $H$ for decoding
• Hamming distance measures number of positions in which two codewords differ
• Minimum distance $d_{min}$ of a code determines its error-correcting capability
  • Code can correct up to $\lfloor \frac{d_{min}-1}{2} \rfloor$ errors
• Convolutional codes generate parity bits based on sliding window of input bits
  • Decoded using Viterbi algorithm or MAP (maximum a posteriori) decoding
• Codes designed to approach channel capacity while minimizing complexity and delay

Real-World Applications

• Data compression: ZIP files, PNG images, MP3 audio, MPEG video
• Error correction: CDs, DVDs, QR codes, satellite communications
• Cryptography: random number generation, key distribution, secure communication protocols
• Machine learning: feature selection, dimensionality reduction, clustering
• Genetics: DNA sequence analysis, genome compression, mutation modeling
• Neuroscience: neural coding, information processing in the brain
• Financial markets: portfolio optimization, risk assessment, high-frequency trading
• Physics: entropy in thermodynamics, quantum information theory