Lecture notes on Data Compression Arithmetic Coding Contents z Huffman coding revisited z History of arithmetic coding z Ideal arithmetic coding z Properties of arithmetic coding 2 Huffman Coding Revisited How to Create Huffman Code z Construct a Binary Tree of Sets of Source Symbols z Sort the set of symbols with non decreasing probabilities z Form a set including two symbols of smallest probabilities z Replace these by a single set containing both the symbols whose probability is the sum of the two component sets z Repeat the above steps until the set contains all the symbols z Construct a binary tree whose nodes represent the sets The leaf nodes representing the source symbols z Traverse each path of the tree from root to a symbol assigning a code 0 to a left branch and 1 to a right branch The sequence of 0 s and 1 s thus generated is the code for the symbol 3 Properties of Huffman Coding z z Huffman codes are minimum redundancy codes for a given probability distribution of the message Huffman coding guarantees a coding rate lH within one bit of the entropy H z z Average code length lH of the Huffman coder on the source S is bounded by H S lH H S 1 Studies showed that a tighter bound on the Huffman coding exists z z Average code length lH H S pmax 0 086 where pmax is the probability of the most frequently occurring symbol So if the pmax is quite big in case that the alphabet is small and the probability of occurrence of the different symbols is skewed Huffman coding will be quite inefficient 4 Properties of Huffman Coding continued z Huffman code does not achieve minimum redundancy because it does not allow fractional bits z Huffman needs at least one bit per symbol z z z z For example given alphabet containing two symbols with probability p1 0 99 p2 0 01 The optimal length for the first symbol is log 0 99 0 0145 The Huffman coding however will assign 1 bit to this symbol If the alphabet is large and probabilities are not skewed Huffman rate is pretty close to entropy 5 Properties of Huffman Coding continued z If we block m symbols together the average code length lH of the Huffman coder on the source S is bounded by H S lH H S 1 m z However the problem here is that we need a big codebook If the size of the original alphabet is K then the size of the new code book is Km z Thus Huffman s performance becomes better at the expense of exponential codebook size 6 Another View of Huffman Coding z Huffman code re interpreted here by mapping the symbols to subintervals of 0 1 at the base value of the subintervals z The code words if regarded as binary fractions are pointers to the particular interval in the binary code z An extension to this idea is to encode the symbol sequence as a subinterval leads to arithmetic coding binary fraction symbol probability code W 0 5 1 0 1 X 0 25 01 0 01 Y 0 125 001 0 001 Z 0 125 000 0 000 7 Arithmetic Coding z The idea is to code string as a binary fraction pointing to the subinterval for a particular symbol sequence z Arithmetic coding is especially suitable for small alphabet binary sources with highly skewed probabilities z Arithmetic coding is very popular in the image and video compression applications 8 A Bit of History z The idea that code string can be a binary fraction pointing to the subinterval for a particular symbol sequence is due to Shannon 1948 and was used by Elias 1963 to successive subdivision of the intervals z Shannon observed that if the probabilities were treated as high precision binary numbers then it may be possible to decode messages unambiguously z David Huffman invented his code around the same time and the observation was left unexplored until it re surfaced in 1975 9 A Bit of History continued z The idea of arithmetic coding was suggested by Rissanen 1975 from the theory of enumerative coding by Pasco 1976 z The material of this notes is based on the most popular implementation of arithmetic coding by Witten etc published in Communications of the Association for Computing Machinery 1987 z Moffat etc 1998 also proposed some improvements upon the 1987 paper however the basic idea remains same 10 Static Arithmetic Coding Consider an half open interval low high Initially interval is set as 0 1 and range high low 1 0 1 Interval is divided into cumulative probabilities of n symbols For this example n 3 p a 1 2 p b 1 4 and p c 1 4 3 4 3 4 1 c c c c 3 4 11 16 47 64 b b b b 1 2 23 32 5 8 a a 0 1 2 96 128 a 11 16 a 47 64 Any value in the range 47 64 96 128 encodes bcca 11 Adaptive Arithmetic Coding Consider an half open interval low high Initially interval is set as 0 1 and range high low 1 0 1 Interval is divided into cumulative probabilities of n symbols each having the same probability 1 n at the beginning 6667 6667 6667 1 c 1 3 c 1 4 c 5834 c 3 6 2 5 2 3 6334 b 1 3 6501 b 2 4 b b 2 6 1 3 2 5 4167 6001 a 1 3 6390 a a 1 6 a 1 4 6334 3333 1 5 5834 0 Any value in the range 6334 6390 encodes bcca 12 Update Frequency in Arithmetic Encoding z A static zero order model is used in the first example z Dynamic second example update is more accurate Initially we have a frequency distribution z Every time we process a new symbol update the frequency distribution z 13 Properties of Arithmetic Coding The dynamic version is not more complex than the static version The algorithm allocates logpi number of bits to a symbol of probability pi whether or not this value is low or high Unlike Huffman codes which is a fixed to variable coding scheme arithmetic coding is variable to fixed coding scheme and is capable of allocating non integral number of bits to symbols producing a near optimal coding It is not absolutely optimal due to limited precision of arithmetic operations Incremental transmission of bits are possible avoiding working with higher and higher precision numbers 14 Update Interval in Arithmetic Encoding z Two main parts in the arithmetic coding z z z z Update frequency distribution Update subinterval Initially we have the interval L Low L R Range as 0 1 Symbols of the alphabet are mapped to the integers 1 2 s n For each incoming symbol s the interval is updated as z z Low L L R sj 11 P j Range R R P s This summation can be precalculated When s 1 the second term is set to 0 15 Ideal …
View Full Document
Unlocking...