Source CodingOutlineCompressionHuffman EncodingHuffman Encoding(continued)Slide 6Lempel-ZivLempel-Ziv(continued)AudioAudio (c’d)Slide 11Slide 12Slide 13Slide 14VideoVideo (cd)UCBSource CodingJean WalrandEECSUCBOutlineCompressionLosless:HuffmanLempel-ZivAudio:ExamplesDifferentialADPCMSUBBANDCELPVideo:Discrete Cosine TransformMotion CompensationUCBCompressionGoal:Reduce the number of bits to encode sourceLossless: For dataLossy: For voice, videoApproaches:UCBHuffman EncodingLosslessKey Idea: Use shorter code words for more frequent symbolsEX1:UCBHuffman Encoding(continued)EX2:UCBHuffman Encoding(continued)If the symbols are independent and identically distributed, the Huffman encoding is the prefix-free code with the minimum average number of bits.Note: The Shannon encoding requires fewer bits, but requires encoding large blocks of symbols.Both codes assume that the distribution is known.UCBLempel-ZivLosslessSymbols are not independentDistribution is not knownWant to minimize the average number of bitsTypical application: any fileApproach: Build dictionary and replace string with location of prefix in the dictionaryUCBLempel-Ziv(continued)Example:UCBAudioExamples:Speech:PCM 64kbpsADPCM 32-64kbpsSBC 16-32kbpsVSELP-CELP 2.4-8kbpsAudio:PCM 1400kbpsMPEG 48-384kbpsUCBAudio (c’d)Differential Encoding (also used for Video): Key Idea is that differences between successive samples may be smallDifficulty: Error PropagationUCBAudio (c’d)Differential Encoding (c’d)UCBAudio (c’d)ADPCM: Adaptive Differential PCMPredict next value, encode errorUCBAudio (c’d)Sub-Band Coding: Improves performanceUCBAudio (c’d)CELP (Code Excited Linear Predictor)UCBVideoDiscrete Cosine TransformObjective: Extract “Visible Information”f(x, y) = m,n F(m, n) cos(mx) cos(ny)UCBVideo (cd)Motion CompensationIdea: Track motion of pictureEncode (motion vector,
View Full Document