Information Theory and Coding

Why it matters

Information Theory and Coding is crucial for efficient data transmission and storage, enabling the reduction of data size without losing essential information and ensuring accurate data recovery despite errors during transmission. This is vital in telecommunications, data storage, and digital communication systems.

Key ideas

• Information Theory: Studies the quantification of information, primarily through concepts like entropy, which measures the uncertainty or randomness of a source.
• Entropy (H): Represents the average amount of information produced by a stochastic source of data. Higher entropy indicates more unpredictability.
• Shannon's Theorem: Establishes the maximum rate at which information can be transmitted over a communication channel with arbitrarily small error probability below capacity using sufficiently long suitable codes; it does not promise zero error for every finite transmission.
• Source Coding: Involves compressing data to reduce redundancy, using techniques like Huffman coding and Lempel-Ziv-Welch (LZW) coding.
• Channel Coding: Focuses on error detection and correction to ensure data integrity, employing methods such as Hamming codes, Reed-Solomon codes, and convolutional codes.
• Error Detection and Correction: Techniques like parity checks and cyclic redundancy checks (CRC) are used to detect errors, while forward error correction (FEC) methods correct them.

Formulas

The capacity formula shown is specifically the band-limited AWGN Shannon–Hartley model; discrete-channel capacity is generally maximized mutual information.

• H(X) = -Σ p(x) log₂ p(x)
  • H(X): Entropy of the source (bits)
  • p(x): Probability of occurrence of symbol x
• C = B log₂(1 + S/N)
  • C: Channel capacity (bits per second)
  • B: Bandwidth of the channel (Hz)
  • S/N: Signal-to-noise ratio (dimensionless)

Worked example

Given: A source emits symbols A, B, and C with probabilities 0.5, 0.3, and 0.2 respectively. Calculate the entropy of the source.

1. Identify probabilities: p(A) = 0.5, p(B) = 0.3, p(C) = 0.2
2. Apply entropy formula: H(X) = -Σ p(x) log₂ p(x)
3. Calculate each term:
   • -p(A) log₂ p(A) = -0.5 log₂ 0.5 = 0.5
   • -p(B) log₂ p(B) = -0.3 log₂ 0.3 ≈ 0.521
   • -p(C) log₂ p(C) = -0.2 log₂ 0.2 ≈ 0.464
4. Sum the terms: H(X) = 0.5 + 0.521 + 0.464 = 1.485

Final Answer: approximately 1.485 bits per source symbol. A binary Huffman code A=0, B=10, C=11 has average length 1.5 bits/symbol, above the entropy bound.

Common mistakes

• Confusing entropy with data rate or bandwidth.
• Misapplying logarithm bases in entropy calculations (ensure base 2 is used).
• Ignoring the impact of noise on channel capacity calculations.

For GATE EC

Questions often involve calculating entropy, channel capacity, or applying coding techniques like Huffman coding. Practice problems on error detection and correction, and understand the application of Shannon's Theorem in determining channel capacity.

Quick check

1. What is the primary goal of source coding?
2. Define entropy in the context of information theory.
3. How does channel coding improve data transmission?

Answers: 1. To reduce data redundancy. 2. A measure of uncertainty or randomness in a data source. 3. By detecting and correcting errors in transmitted data.