Information Theory: Source Coding

Source Coding

• A source code C is a mapping from random variable X to finite-length strings from a D-ary alphabet.
• For elements x in X, codewords are denoted as C(x) and their lengths as l(x).
• Example: C(red)=00, C(blue)=11 for X={red, blue} with alphabet D={0,1}; both codewords have length 2.

Average Codeword Length

• Expected length L(C) of a source code for random variable X is calculated using the probability mass function p(x).
• Formula: L(C) = Σ p(x) l(C(x)), where l(x) is the length of the associated codeword.
• Given a random variable X with probabilities:
  • P(X=1)=1/2, C(1)=0
  • P(X=2)=1/4, C(2)=10
  • P(X=3)=1/8, C(3)=110
  • P(X=4)=1/8, C(4)=111
• Calculation yields L(C) = 1.75 bits.

Efficient Code

• A code is non-singular if different elements map to different strings: x ≠ x' implies C(x) ≠ C(x').
• A code extension C* maps sequences of symbols to strings in D, defined as C(x1 x2...xn) = C(x1) C(x2)...C(xn).
• Uniquely decodable codes have non-singular extensions; they produce only one source string from an encoded string.
• A prefix code (or instantaneous code) has no codeword that is a prefix of another codeword.
• Example of prefix code:
  • C(1)=0
  • C(2)=10
  • C(3)=110
  • C(4)=111
• Kraft inequality holds for codeword lengths l1, l2, ..., lk if Σ D^(-li) ≤ 1.

Theorem on Codeword Length

• The length L of a prefix code is bounded by the entropy H(X) of the source.
• L ≥ H(X).

Optimum Code

• An optimum code minimizes codeword length without exceeding H(X) + 1.
• Condition: L ≤ H(X) + 1.

Average Codeword Length for Optimal Prefix Code

• For a variable X, the average length L satisfies: H(X) ≤ L ≤ H(X) + 1.

Example of Optimal Prefix Code

• Given a code C with symbols {x1,x2,x3,x4}:
  • C: {00, 01, 100, 1010}
  • Probabilities: P(X) = {0.45, 0.25, 0.20, 0.10}
• Calculation shows H(X) = 1.815 and L = 2.4, with H(X) + 1 = 2.815.
• Conclusion: Code C is an optimal prefix code.