Source Coding

List a table that compare different source coding schemes.

1) What's the limitation of Shannon code? How to improve it?
The design of Shannon codes takes a probability-matching approach: the code length of a symbol matches the probability of the symbol. L_i=ceiling(-log p_i).

2) What's the limitation of Fano code? How to improve it?
Fano code uses equal partitioning based on probability: minimize the difference of the probabilities of the two partitioned sets.

3) What's the limitation of Huffman code? How to improve it?
Huffman code uses sorting and merging of symbol sets based on probability: merge the two sets with the least probabilities.

4) Arithmetic code

5) Universal code: Lempel-Ziv code

Source coding reduces redundancy while channel coding increases redundancy.   Since redundancy can increase robustness against error (as in channel coding), why do we use source coding (reducing redundancy) and channel coding (increasing redundancy) at the same time for multimedia transmission over networks?   The reason is that the source coding reduces redundancy, the pattern of which cannot be effectively used by the receiver to recover errors; on the other hand, the pattern of redundancy in channel codes is carefully designed (using the finite field theory) and can be effectively utilized by the receiver in error correction (assuming the receiver knows the pattern of redundancy in the channel code).  

General coding techniques

• Lossless coding
  • Key idea: Probability matching (match the codeword length with the probability of the message/codeword) so that the average codeword length is minimized
  • Coding schemes:
    • Huffman coding (block-based coding)
      • Counterpart in forward error correction: block coding
      • The average bit rate of the code is lower bounded by the joint entropy of the symbols coded together
    • Arithmetic coding (sequence-based coding)
      • Counterpart in forward error correction: convolutional coding
      • The average bit rate of the code is lower bounded by the entropy rate of the sequence
• Lossy coding (=quantization)
  • Scalar quantization
    • Uniform quantizer (simplest but typically not optimal except for a uniformly-distributed random variable)
    • MMSE quantizer
      • Given the number of quantization levels (or the number of bits to represent a value), minimize the mean squared error (MSE) between the original value and the reconstruction value.
  • Vector quantization
  • Use the distortion-rate function to characterize the performance bound while Use entropy or entropy rate to characterize the performance bound
  • Typically, the pdf is unknown in practice; hence, for pdf-optimized quantizers, training is required to obtain the codebook.  Such a training algorithm is called Lloyd-max algorithm, or LBG algorithm, or k-means algorithm.

Video coding techniques

• Transform coding
  • Karhunen Loeve transform (KLT)
    • Optimal unitary transform
    • KLT + optimal bit allocation + MMSE scalar quantization for each transform coefficient achieves similar rate-distortion performance as vector quantization, but at a reduced complexity
  • Discrete cosine transform (DCT)
    • Suboptimal unitary transform
    • Transform coding + optimal bit allocation + MMSE scalar quantization + fixed-length coding for the quantization indices; in practice, use transform coding + uniform scalar quantization (different coefficient requires different quantization step-size, which is similar to optimal bit allocation) + variable-length coding since the latter achieves similar rate-distortion performance as the former, but at a reduced complexity
  • Block-based coding
• Predictive coding
  • Use closed loop prediction.
  • Linear prediction, AR(N) model
    • Sequence-based coding, as compared to transform coding, which is block-based.   Hence, order-N predictive coding can achieve higher compression efficiency than length-N transform coding, for any finite N.
    • Useful in audio, but not useful in video.   For video, motion-compensated prediction is used, instead of AR(N) model.
  • Motion-compensated prediction
    • Used in MPEG-1/2/4 and H.261/263/264

• Embedded coding
  • successively refine the description of the signal
  • Similar to turbo decoding, successively refine processing of the signal

• Vector quantization
  • Lloyd’s algorithm
    • The following algorithms based on the same principle of Lloyd’s algorithm:
      Generalized Lloyd’s algorithm
      Linde-Buzzo-Gray (LBG) algorithm
      K-means
      ISODATA
  • K-means vs. ISODATA