Arithmetic CodingAdditional Material Spring 2015.ppt

1、Arithmetic Coding Additional Material Spring 2015,CMPT 365 Multimedia Systems,Outline Part I,Introduction Basic Encoding and Decoding Scaling and Incremental Coding Integer Implementation Adaptive Arithmetic Coding Binary Arithmetic Coding Applications JBIG, H.264, JPEG 2000,Limitations of Huffman C

2、ode,Need a probability distribution,Hard to adapt to changing statistics,Minimum codeword length is 1 bit Serious penalty for high-probability symbols,Example: Binary source, P(0)=0.9 Entropy: -0.9*log2(0.9)-0.1*log2(0.1) = 0.469 bit Huffman code: 0, 1 Avg. code length: 1 bit Joint coding is not pra

3、ctical for large alphabet.,Arithmetic coding: Can resolve all of these problems. Code a sequence of symbols without having to generate codes for all sequences of that length.,Introduction,1,00,010 011,Recall table look-up decoding of Huffman code N: alphabet size L: Max codeword length Divide 0, 2L

4、into N intervals One interval for one symbol Interval size is roughly proportional to symbol prob.,dcba,Arithmetic Coding,Disjoint and complete partition of the range 0, 1) 0, 0.8), 0.8, 0.82), 0.82, 1) Each interval corresponds to one symbol Interval size is proportional to symbol probability,Obser

5、vation: once the tag falls into an interval, it never gets out of it,0,1,a b c,Some Questions to think about:,Why compression is achieved this way? How to implement it efficiently? How to decode the sequence? Why is it better than Huffman code?,Example:,Map to real line range 0, 1) Order does not ma

6、tter Decoder need to use the same order,Disjoint but complete partition: 1: 0, 0.8): 0, 0.7999999 2: 0.8, 0.82): 0.8, 0.8199999 3: 0.82, 1): 0.82, 0.9999999 (Think about the impact to integer implementation),Encoding,Input sequence: “1321”,Range 1,Final range: 0.7712, 0.773504): Encode 0.7712,Diffic

7、ulties: 1. Shrinking of interval requires high precision for long sequence.2. No output is generated until the entire sequence has been processed.,Cumulative Density Function (CDF),For continuous distribution:,For discrete distribution:,Properties: Non-decreasing Piece-wise constant Each segment is

8、closed at the lower end.,Encoder Pseudo Code,low=0.0, high=1.0; while (not EOF) n = ReadSymbol(); RANGE = HIGH - LOW; HIGH = LOW + RANGE * CDF(n); LOW = LOW + RANGE * CDF(n-1); output LOW;,Keep track of LOW, HIGH, RANGE Any two are sufficient, e.g., LOW and RANGE.,Decoding,Decode 1,Drawback: need to

9、 recalculate all thresholds each time.,Simplified Decoding,Normalize RANGE to 0, 1) each time No need to recalculate the thresholds.,Decoder Pseudo Code,Low = 0; high = 1; x = Encoded_number While (x low) n = DecodeOneSymbol(x); output symbol n; x = (x - CDF(n-1) / (CDF(n) - CDF(n-1); ;,Outline,Intr

10、oduction Basic Encoding and Decoding Scaling and Incremental Coding Integer Implementation Adaptive Arithmetic Coding Binary Arithmetic Coding Applications JBIG, H.264, JPEG 2000,Scaling and Incremental Coding,Problems of Previous examples: Need high precision No output is generated until the entire

11、 sequence is encoded,Key Observation: As the RANGE reduces, many MSBs of LOW and HIGH become identical: Example: Binary form of 0.7712 and 0.773504:0.1100010, 0.1100011, We can output identical MSBs and re-scale the rest: Incremental encoding This also allows us to achieve infinite precision with fi

12、nite-precision integers.,E1 and E2 Scaling,E1: LOW HIGH) in 0, 0.5) LOW: 0.0xxxxxxx (binary), HIGH: 0.0xxxxxxx.,0 0.5 1.0,Encoding with E1 and E2,0 0.8 1.0,Input 1,Encode any value in the tag, e.g., 0.5Output 1 All outputs: 1100011,To verify,LOW = 0.5424 (0.10001010. in binary), HIGH = 0.54816 (0.10

13、001100. in binary). So we can send out 10001 (0.53125) Equivalent to E2E1E1E1E2 After left shift by 5 bits: LOW = (0.5424 0.53125) x 32 = 0.3568 HIGH = (0.54816 0.53125) x 32 = 0.54112 Same as the result in the last page.,Comparison with Huffman,Input Symbol 1 does not cause any output Input Symbol

14、3 generates 1 bit Input Symbol 2 generates 5 bits,Symbols with larger probabilities generates less number of bits. Sometimes no bit is generated at all Advantage over Huffman coding Large probabilities are desired in arithmetic coding Can use context-adaptive method to create larger probabilityand t

15、o improve compression ratio.,Note: Complete all possible scaling beforeencoding the next symbol,Incremental Decoding,0 0.8 1.0,Decode 1: Need 5 bits (verify) Read 6 bits: Tag: 110001, 0.765625,Input 1100011,Summary: Complete all possible scaling before further decodingAdjust LOW, HIGH and Tag togeth

16、er.,Summary Part I,Introduction Encoding and Decoding Scaling and Incremental Coding E1, E2 Next: Integer Implementation E3 scaling Adaptive Arithmetic Coding Binary Arithmetic Coding Applications JBIG, H.264, JPEG 2000,Outline Part II,Review Integer Implementation Integer representation E3 Scaling

17、Minimum word length Binary Arithmetic Coding Adaptive Arithmetic Coding,Encoding Without Scaling,Input sequence: “1321”,Range 1,Final range: 0.7712, 0.773504): Encode 0.7712,E1 and E2 Scaling,E1: LOW HIGH) in 0, 0.5) LOW: 0.0xxxxxxx (binary), HIGH: 0.0xxxxxxx.,0 0.5 1.0,Encoding with E1 and E2,0 0.8

18、 1.0,Input 1,Encode any value in the tag, e.g., 0.5Output 1 All outputs: 1100011,To verify,LOW = 0.5424 (0.10001010. in binary), HIGH = 0.54816 (0.10001100. in binary). So we can send out 10001 (0.53125) Equivalent to E2E1E1E1E2 After left shift by 5 bits: LOW = (0.5424 0.53125) x 32 = 0.3568 HIGH =

19、 (0.54816 0.53125) x 32 = 0.54112 Same as the result in the last page.,Encoding Pseudo Code with E1, E2,EncodeSymbol(n) /Update variablesRANGE = HIGH - LOW;HIGH = LOW + RANGE * CDF(n);LOW = LOW + RANGE * CDF(n-1);/keep scaling before encoding next symbolwhile LOW, HIGH in 0, 0.5) or 0.5, 1) send 0 f

20、or E1 and 1 for E2scale LOW, HIGH ,(For floating-point implementation),Incremental Decoding,0 0.8 1.0,Decode 1: Need 5 bits (verify) Read 6 bits: Tag: 110001, 0.765625,Input 1100011,Summary: Complete all possible scaling before further decodingAdjust LOW, HIGH and Tag together.,Decoding Pseudo Code

21、with E1, E2,DecodeSymbol(Tag) RANGE = HIGH - LOW; n = 1; While ( (tag - LOW) / RANGE = CDF(n) ) n+; HIGH = LOW + RANGE * CDF(n);LOW = LOW + RANGE * CDF(n-1);/keep scaling before decoding next symbolwhile LOW, HIGH in 0, 0.5) or 0.5, 1) scale LOW, HIGH by E1 or E2 ruleLeft shift Tag and read one more

22、 bit to LSBreturn n; ,(For floating-point implementation),Outline,Review Integer Implementation Integer representation E3 Scaling Complete Algorithm Minimum word length Binary Arithmetic Coding Adaptive Arithmetic Coding Applications JBIG, H.264, JPEG 2000,Integer Implementation,Old formulas:,HIGH L

23、OW + RANGE * CDF(n); LOW LOW + RANGE * CDF(n-1);,Integer approximation of CDF ( ): The number of occurrence of each symbol is usually collected by a counter. Allow adaptive arithmetic coding,Integer Implementation,HIGH LOW + RANGE * CDF(n); LOW LOW + RANGE * CDF(n-1);,Why + 1 in RANGE and 1 in HIGH?

24、 HIGH should be less than the LOW of the next interval The best integer value is HIGH = (next LOW) 1 HIGH, HIGH + 1) still belongs to the current interval,although we could not represent it explicitly.,Example,For 8-bit integers, initial LOW = 0, HIGH = 255 RANGE=256,If n = 1:,If n = 2:,If n = 3:,E1

25、 Scaling for Integer,E1 Scaling: 0, 0.5) 0, 1), E1(x) = 2 x. LOW = 0xxxxxxx, HIGH =0xxxxxxx Output the MSB value 0, then shift left by 1 bit,Important trick: Shift in 1 to HIGH and 0 to LOW HIGH: 0xxxxxxx xxxxxxx1 HIGH = (HIGH 1) + 1; LOW: 0xxxxxxx xxxxxxx0 LOW = LOW 1;,Always assume HIGH ends with

26、infinite number of 1s: So that it approximates the LOW of the next interval.,This also ensures the RANGE is doubled after scaling: HIGH LOW + 1 (2 x HIGH + 1 2 x LOW + 1) = 2(HIGH LOW + 1),E2 Scaling for Integer,E2 Scaling: 0.5, 1) 0, 1), E2(x) = 2 (x - 0.5) LOW = 1xxxxxxx, HIGH =1xxxxxxx Output the

27、 MSB, then shift left by 1 bit (mul by 2),Same trick: Shift in 1 to HIGH and 0 to LOW HIGH: 1xxxxxxx xxxxxxx1 HIGH = (HIGH 1) + 1; LOW: 1xxxxxxx xxxxxxx0 LOW = LOW 1;,0 203 255,Input 1,Integer Encoding,LOW: 167 (10100111) HIGH: 203 (11001011)After E2: (shift in an 1 to HIGH and 0 to LOW) LOW: 1(0100

28、1110) 78 (8-bit) HIGH: 1(10010111) 151 (8-bit)In 8.1 format (8 bits for integer, 1 bit for fractional): LOW: (10100111.0) 167 HIGH: (11001011.1) 203.5By shifting in an 1 to HIGH, we can cover the range 203, 203.5. The entire range 203, 204) can be covered by always shifting in 1 to HIGH.,0, 0.8) LOW

29、 = 0, HIGH = 203. 0.8, 0.82) LOW = 204, HIGH = 208. Can we represent an interval in 203, 204) ? (Sequence 1333333),Outline,Review Integer Implementation Integer representation E3 Scaling Complete Algorithm Minimum word length Binary Arithmetic Coding Adaptive Arithmetic Coding,E3 Scaling: 0.25, 0.75

30、)0, 1),If RANGE straddles 1/2, E1 and E2 cannot be applied, but the range can be quite small Example: LOW=0.4999, HIGH=0.5001Binary: LOW=0.01111., HIGH=0.1000 We may not have enough bits to represent the interval.,Integer Implementation of E3,Another way to implement E3 (Sayood book pp. 99): Left sh

31、ift old LOW and HIGH, complement new MSB.,Same trick: Shift in 1 to HIGH and 0 to LOWHIGH = (HIGH QUARTER) 1) + 1;LOW = (LOW - QUARTER) 1;QUARTER = 2(M - 2) for m-bit integer. (64 for m = 8 bits),LOW 01xxxxxx 0xxxxxx0 HIGH 10xxxxxx 1xxxxxx1,Signaling of E3,What should we send when E3 is used? Recall

32、: we send 1 if E2 is used, send 0 if E1 is used,What do they mean? A series of E3 followed by an E1 is equivalent to an E1 followed by a series of E2. A series of E3 followed by an E2 is equivalent to an E2 followed by a series of E1.,Example,0 0.8 1.0,Input 1,0 0.656 0.8,Input 3,Previous example wi

33、thout E3:,With E3:,The range after E2E3 is the same as that after E1E2,Another View of the Equivalence,Scaling of a range in 0.5, 0.75) with E1E2,Equivalent scaling of the range in 0.5, 0.75) with E2E3,E2,E1,E3,E2,A Simple Proof of E2E3 = E1E2,Given the same range r: After applying E3: 0.25, 0.75) 0

34、, 1), the range becomes r3 = (r 0.25) x 2 After applying E2, the range becomes r4 = (r3 0.5) x 2 = (r 0.25) x 2 0.5) x 2 = (r 0.5) x 2 x 2= r2,Given an original range r: After applying E2: 0.5, 1) 0, 1), the range becomes r1 = (r 0.5) x 2 After applying E1: 0, 0.5) 0, 1), the range becomes r2 = r1 x

35、 2 = (r 0.5) x 2) x 2,For formal proof: www.copro.org/download/ac_en.pdf,Encoding Operation with E3,0.312 0.5424 0.54816 0.6,Input 2,With E3:,Without E3:,Dont send anything when E3 is used, but send a 0 after E2: The bit stream is identical to that of the old method Subsequent encoding is also same

36、because of the same final interval,Output 0 here!,Decoding for E3,0 0.8 1.0,Input 1100011 Read 6 bits: Tag: 110001 (0.765625) Decode 1,Same status as the old method: low, high, range, tag.,Summary of Different Scalings,Need E1 scaling,Need E2 scaling,Need E3 scaling,No scaling is required. Ready to

37、encode/decode the next symbol.,0 0.25 0.5 0.75 1.0,Outline,Review Integer Implementation Integer representation E3 Scaling Complete Algorithm Minimum word length Binary Arithmetic Coding Adaptive Arithmetic Coding,Encoding Pseudo Code with E1, E2, E3,EncodeSymbol(n) /Update variablesRANGE = HIGH - L

38、OW + 1;HIGH = HIGH + RANGE * Cum( n ) / N - 1; LOW = LOW + RANGE * Cum(n-1) / N;/Scaling before encoding next symbol EncoderScaling(); /see next slide ,(For integer implementation),Encoding Pseudo Code with E1, E2, E3,EncoderScaling( ) while (E1, E2 or E3 is possible) if (E3 is possible) HIGH = (HIG

39、H - QUARTER) 0) /send info about E3 nowsend complement of b /E2 (E3)n = (E1)n E2Scale3 -; /Send one bit for each E3 ,DecodeSymbol(Tag) RANGE = HIGH - LOW + 1; n = 1; While (Tag LOW + RANGE * Cum(n) / N - 1) n+; HIGH = LOW + RANGE * Cum(n) / N - 1;LOW = LOW + RANGE * Cum(n-1) / N;/keep scaling before

40、 decoding next symbolDecoderScaling(Tag); /next slidereturn n; ,Decoding Pseudo Code with E1, E2, E3,(For integer implementation),Intervals: 0, 203, 204, 208, 209, 255,Decoding Pseudo Code with E1, E2, E3,DecoderScaling(Tag) while (E1, E2 or E3 is possible) if (E1 or E2 is possible) LOW = LOW 1;HIGH

41、 = (HIGH 1) + 1;Tag = Tag 1;Tag = Tag | ReadBits(1);if (E3 is possible) LOW = (LOW - QUARTER) 1;HIGH = (HIGH - QUARTER) 1) + 1;Tag = (Tag - QUARTER) 1;Tag = Tag | ReadBits(1); ,0 203 255,Input 1,Integer Encoding with E1, E2, E3,Final output: 11000100 10000000,0 203 255,Integer Decoding with E1, E2,

42、E3,Read 8 bits: 11000100 (196) Decode 1,Input: 11000100 10000000,Outline,Review Integer Implementation Integer representation E3 Scaling Complete Algorithm Minimum word length Binary Arithmetic Coding Adaptive Arithmetic Coding,How to decide the word length m?,Need to guarantee non-zero interval for

43、 all symbolsin the worst case:, RANGE cannot be too small at any time. Intuitive!,How to decide the word length m?,Condition: 1/4 (2m) N Example: N = 50, min m = 8 (1/4M=64),When do we have the smallest RANGE without triggering a scaling?,Outline,Review Integer Implementation Binary Arithmetic Codin

44、g Adaptive Arithmetic Coding,Binary Arithmetic Coding,Arithmetic coding is slow in general:To decode a symbol, we need a seris of decisions and multiplications: While (Tag LOW + RANGE * Cum(n) / N - 1) n+; ,The complexity is greatly reduced if we have only two symbols: 0 and 1.,symbol 0 symbol 1,Onl

45、y two intervals in 0, 1): 0, x), x, 1),0 x 1,Encoding of Binary Arithmetic Coding,Only need to update LOW or HIGH for each symbol.,Decoding of Binary Arithmetic Coding,0 0.6 1,Tag,While (Tag LOW + RANGE * Cum(n) / N - 1) n+; ,Only one decision to make:,if (Tag LOW + RANGE * Cum(Symbol 0) / N - 1) n

46、= 1; else n = 0; ,Applications of Binary Arithmetic Coding,Increasingly popular: JBIG, JBIG2, JPEG2000, H.264 Covert non-binary signals into binary first H.264: Golomb-Rice Code Bit-plane coding Various simplifications to avoid multiplication: H.264: Table look-up for RANGE * Cum(n) / N JBIG: Elimin

47、ate multiplication by assuming the RANGE is close to 1. Scale if RANGE too small.,Outline,Review Integer Implementation Binary Arithmetic Coding Adaptive Arithmetic Coding,Adaptive Arithmetic Coding,Observation: The partition of 0, 1) can be different from symbol to symbol The bit stream can be decoded perfectly as long as both encoder and decoder are synchronized (use the same partition). General approach: Starting from a pre-defined probability distribution Update probability after each symbol,