Source Coding

1. Source symbols must be encoded in
   binary
   .
2. Average code length should be minimized.
3. Remove redundancy $\rightarrow$ reduce the bit rate.

• Consider a discrete memoryless source over the alphabet $S = \{s_0, s_1, \ldots, s_k\}$.
• The probability of $s_i$: $p_{i}$.
• The code length for $s_i$: $l_i$.
• Average code length, or average bits per symbol: $L = \sum_{k=0}^{K-1} p_k \cdot l_k$.

• The minimum possible value of $L$: $L_{min}$.
• Coding efficiency of the source: $\eta=\frac{L_{min}}{L}$.

• Data compression:
  1. Remove redundant information before transmission.
  2. Use lossless data compression.
  3. A source code representing the output of a discrete memoryless source must be uniquely decodable.

A variable-length source code in which

no codeword is a prefix of another

.

• Properties of prefix codes:
  1. Every prefix code is uniquely decodable.
  2. The converse is not always true: Not every uniquely decodable code is a prefix code.

• Sum of probabilities: $1 = \sum_{k=0}^{K-1} p_k = \sum_{k=0}^{K-1} 2^{-l_k}$.
• Average code length: $L = \sum_{k=0}^{K-1} p_k \cdot l_k = \sum_{k=0}^{K-1} 2^{-l_k} \cdot l_k$.

1. Arrange symbols in descending probability order and treat them as leaf nodes.
2. Repeat the following until one node remains.
   • Select the two least probable nodes. Assign 0 to the less probable one and 1 to the other; the opposite assignment also works, provided it is consistent.
   • Merge the two into a node whose probability is the sum of their probabilities.
   • Return to step 1.
3. For each symbol, generate its binary code by following the path from its leaf node to the root.
   • The bit at the leaf becomes the final bit of the codeword.

• Variance measures variation in codeword length.
  $\sigma^2 = \sum_{k=0}^{K-1} p_k (l_k - \overline{L})^2$
• Choose a Huffman tree with
  higher variance
  to help avoid errors.
  → A higher-variance tree has more diverse codeword lengths and can handle errors better.

• The higher-variance tree can handle errors better.