Information Theory: Source Coding

Study Notes

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.

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.

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.

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.