Information Theory: Source Coding

What qualifies a code as a prefix code?

What does the Kraft inequality help determine for a code?

What is the lower bound of the codeword length L of a prefix code determined by?

What characterizes an optimum code in relation to the entropy H(X)?

What does the average codeword length for an optimal prefix code satisfy?

Given the example code C, what was the calculated value of H(X)?

What is the definition of a source code C for a random variable X?

How is the expected length L(C) of a source code calculated?

Which condition is NOT part of defining an efficient code?

What is the extension C* of a code C defined as?

Which characteristic defines a uniquely decodable code?

In the given example, what is the average codeword length L(C) for the random variable X?

What does it mean for a code to be non-singular?

What is represented by the variable l(x) in the context of 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.

This quiz covers the fundamentals of source coding in information theory, including definitions and examples. Understand how source codes relate to random variables and the calculation of average codeword length. Test your knowledge on the concepts of finite length strings and encoding.