Information Theory: Source Coding

Questions and Answers

What qualifies a code as a prefix code?

No codeword can be a prefix of any other codeword. (correct)

No codeword can be a suffix of another codeword.

Codewords must all have the same length.

Each codeword must be unique.

What does the Kraft inequality help determine for a code?

The optimal length of each codeword.

The maximum number of codewords possible.

The total probability of all codewords combined.

Whether the code satisfies the necessary conditions for prefix coding. (correct)

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

The length of the longest codeword.

The total number of symbols in the code.

The entropy of the source. (correct)

The average probability of all codewords.

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

Its codeword length should not exceed H(X) + 1. Signup and view all the answers

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

H(X) ≤ L ≤ H(X) + 1. Signup and view all the answers

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

1.815 Signup and view all the answers

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

A mapping from x to a finite length string of symbols from a D-ary alphabet. Signup and view all the answers

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

By multiplying the probability of each random variable by its corresponding codeword length. Signup and view all the answers

Which condition is NOT part of defining an efficient code?

The code must have a minimum length. Signup and view all the answers

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

A mapping from finite length strings of X to finite length strings of D. Signup and view all the answers

Which characteristic defines a uniquely decodable code?

No output string can represent more than one input string. Signup and view all the answers

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

1.75 bits Signup and view all the answers

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

Different inputs must map to different codewords. Signup and view all the answers

What is represented by the variable l(x) in the context of source coding?

The length of the source code C associated with x. Signup and view all the answers

Study Notes

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.

Description

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.