6.441-7 Shannon-Fano-Elias codes, Slepian-Wolf

LECTURE 7Last time:Huffman codes • Lecture outlineElias codes • Slepian-Wolf • Compression: pulling it together • Reading: Scts. 5.8-5.9, 14.4 through the end of 14.4.4.1. Huffman codesHuffman codes are optimal The algorithm we have builds from the least likely elements onwards Do we need to view the whole codeword to decode? Would such a code be more or less robust to slight errors in distribution? In general, how important is it to know the actual distribution? Still want to make frequent elements short and infrequent one longer. Elias codesEncoder has a sliding structure The length of the codeword is variable Take a binary string 011010111010 we can consider it as a real 0.011010111010 Suppose the probability assignment is 0.7 for 0 and 0.3 for 1 We can create a description of the source-word as follows:divide the interval [0,1)as new bits are read, subdivide the the speciffie interval further in proportion to the probabilities Mapping the sourceword to thecodewordFor the sourceword, after n − 1 source bits, an interval [an−1, bn−1) has been specified Bit n specifies a new interval [an, bn) such that If bit n is 0, then an = an−1 and bn = an−1+ p(bn−1 − an−1) If bit n is 1, then an = an−1+p(bn−1 −an−1) and bn = bn−1 The codeword divides interval in halves We do not necessarily need to receive the whole codeword to start decoding Length of the codewordWe make the codeword long enough to deterrmin in which part of the sourceword interval we are That is to say that the codeword interval must be inside the sourceword interval 2−n ≤ PXn (xn) −n ≤ log �PXn (xn)� � 1 � n ≥ log PXn (xn) which is satisfied by taking � 1 � n = �log � +1 PXn(xn) Length of the codewordThe average length is then: �xn∈X n PXn (xn) � �log � 1 � � +1� PXn(xn) ≤ H(Xn)+2 This is very close to the limit given by the AEP Hoewever, for short sequences, this may not be particularly good MIT OpenCourseWarehttp://ocw.mit.edu 6.441 Information Theory Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.