(12) United States Patent
`Marpe et al.
`
`USOO694371 OB2
`US 6,943,710 B2
`Sep. 13, 2005
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) METHOD AND ARRANGEMENT FOR
`ARTHMETC ENCODING AND DECODING
`BINARY STATES AND A CORRESPONDING
`COMPUTER PROGRAMANDA
`CORRESPONDING COMPUTER-READABLE
`STORAGE MEDUM
`
`(75) Inventors: Detlef Marpe, Berlin (DE); Thomas
`Wiegand, Berlin (DE)
`(73) Assignee: Faunhofer-Gesellschaft Zur
`Foerderung der Angewandten
`Forschung E.V., Munich (DE)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 10/727,801
`(22) Filed:
`Dec. 4, 2003
`(65)
`Prior Publication Data
`
`US 2004/0117714 A1 Jun. 17, 2004
`Related U.S. Application Data
`(63) Continuation of application No. PCT/EP03/04654, filed on
`May 2, 2003.
`Foreign Application Priority Data
`(30)
`May 2, 2002 (DE) ......................................... 102 20962
`
`(51) Int. Cl. ................................................. H03M 7700
`
`(52) U.S. Cl. ........................................ 341/106; 341/107
`(58) Field of Search ................................. 341/106, 107,
`341/50, 65; 382/239
`References Cited
`U.S. PATENT DOCUMENTS
`
`(56)
`
`4,891,643 A * 1/1990 Mitchell et al. ............ 341/107
`5,272.478 A 12/1993 Allen ......................... 341/107
`5,363,099 A 11/1994 Allen ......................... 341/107
`5,475,388 A * 12/1995 Gormish et al. ............ 341/107
`
`
`
`5,592,162 A 1/1997 Printz et al.
`5,973,626 A * 10/1999 Berger et al. ................. 341/65
`6,075,471. A * 6/2000 Kimura et al. ....
`... 341/107
`6,449,393 B1 * 9/2002 Peters ...........
`... 382/239
`6,757,436 B2 * 6/2004 Peters ........................ 382/239
`2005/0012648 A1 * 1/2005 Marpe et al.
`2005/0027521 A1
`2/2005 Gavrilescu et al.
`
`:
`
`OTHER PUBLICATIONS
`Dan Chevion et al.: “High Efficiency, Multiplication Free
`Approximation of Arithmetic Coding”, IEEE 1991, Order
`No. TH0373-1/91/0000/0043/801.00, pp. 43–52, Apr. 8–11,
`1991.
`David S. Taubman et al.: “JPEG2000 Image Compression
`Fundamentals, Standards and Practice”, Kluwer Academic
`Publishers, Boston, 2002, pp. 65-77, (Aug. 1, 2002).
`Ref 1.01: Title: Draft ITU-T Recommendation and Final
`Draft International Standard Joint Video Specification
`(ITU-T Rec. H.2641 ISO/IEC 14496-10 AVC). From: Joint
`Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG
`(ISO/IEC JTC1/SC29/WG 11 and ITU-T SG16 Q.6). pp.:
`1–250, Mar. 7-14, 2003.
`(Continued)
`Primary Examiner Jean Bruner Jeanglaude
`(74) Attorney, Agent, or Firm-Laurence A. Greenberg;
`Werner H. Stemer; Ralph E. Locher
`(57)
`ABSTRACT
`A method and arrangement for arithmetic encoding/
`decoding is described, wherein the probability estimation is
`performed by a finite state machine FSM, wherein the
`generation of N representative states of the FSM is per
`formed offline. Corresponding transition rules are filed in the
`form of tables. In addition, a pre-quantization of the interval
`width R to a number of K pre-defined quantization values is
`carried out. With suitable dimensioning of K and N, this
`allows the generation of a table containing all KxN combi
`nations of pre-calculated product values RXP, is for a
`multiplication-free determination of Rs. Overall, the result
`is a good compromise between high coding efficiency and
`low calculation effort.
`
`63 Claims, 4 Drawing Sheets
`
`1. Determination Of the LPS
`2. Calculation of the VariableSRPS and RMPS:
`Rites = R 2C Pres
`Rups s R - Rips
`3. Calculation of the new Oartial interval:
`if (bit = LPS) then
`L e- I + Res
`R ( - Rs
`
`else
`
`R {- Rips
`4. Updating the probability estimation PFS
`5. Outputling the bits and reno Talizing R
`
`Unified Patents, Ex. 1001
`
`000001
`
`

`

`US 6,943,710 B2
`Page 2
`
`OTHER PUBLICATIONS
`Ref 1.02: Title: Overview of the H.264/AVC Video Coding
`Standard. Author: Thomas Wiegand, Gary J. Sullivan,
`Senior Member, IEEE, Gisele Bontegaard, and Ajay Luthra,
`Senior Member, IEEE. pp. 560–576, vol. 13, No. 7, Jul.
`2003.
`Ref. 1.03: Title: Information Technology-Genetic Coding
`Moving Pictures and Associated Audio Information: Video.
`From: International Standard 13818-2 Recommendation
`ITU-T H.26. pp. 1-224, (no date).
`Ref 1.04: Title: Draft Text of Recommendation H.263 Ver
`sion 2 (“H.263+”) for Decision. From: International Tele
`communicaiton Union. pp. 1-143, 1997-2000 (no month).
`Ref 1.05: Title: Information Technology-Coding of Audio
`Visual Objects-Part 2: Visual. From: International Organi
`Zation for Standardization Organization International Nor
`malization ISO/IEC JTC1/SC29/WG 11 Coding of Moving
`Picture and Audio. pp. 1-526, Jul. 2001.
`Reg 1.06: Title: DCT Coding for Motion Video Storage
`Using Adaptive Arithmetic Coding. Author: C.A. Gonzalez,
`L. Allman, T. McCarthy, P. Wendt. pp. 145-154, 1990 (no
`month).
`Ref1.07: Title: Adaptive Codes for H.26L. From: ITU-Tele
`communications Standardization Sector. pp. 1-7, Jan. 9-12,
`2001.
`Ref. 1.08: Title: Further Results for CABAC Entropy Cod
`ing Scheme. From: ITU Telecommunications Standardiza
`tion Sector. pp.: 1-8, Apr. 2-9, 2001.
`Ref1.09: Title: Improved CABAC. From: Joint Video Team
`(JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/
`SC29/WG 11 and ITU-T SG16 Q.6). pp. 1-6, Jan. 29-Feb.
`1, 2002.
`Ref 1.10: Title: New Results in Improved CABAC. From:
`Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T
`VCEG (ISO/IEC JTC1/SC29/WG 11 and ITU-T SG16 Q.6).
`pp. 1-12, Mar. 2002.
`Ref 1.11: Title: Improved CABAC. From: ITU-Telecom
`munications Standardization Sector. pp. 1-9, Dec. 4-6,
`2001.
`Ref 1.12: Title: Fast Arithmetic Coding for CABAC. From:
`Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T
`VCEG (ISO/IEC JTC1/SC29/WG 11 and ITU-T SG16 Q.6).
`pp. 1-11, 1995 (no month).
`Ref1.13: Title: CABAC and Slices. From: Joint Video Team
`(JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/
`SC29/WG 11 and ITU-T SG16 Q.6). pp. 1-17, Jul. 2002.
`Ref 1.14: Title: Analysis and Simplification of Intra Predic
`tion. From: Joint Video Team (JVT) of ISO/IEC MPEG &
`ITU-T VCEG (ISO/IEC JTC1/SC29/WG 11 and ITU-T
`SG16 Q.6), Jul. 2002.
`Ref 1.15: Title: Proposed Cleanup Changes for CABAC.
`From: Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T
`VCEG (ISO/IEC JTC1/SC29/WG 11 and ITU-T SG16 Q.6).
`pp. 1-7, Oct. 2002.
`Ref 1.16: Title: CABAC Cleanup and Complexity Reduc
`tion. From: Joint Video Team (JVT) of ISO/IEC MPEG &
`ITU-T VCEG (ISO/IEC JTC1/SC29/WG 11 and ITU-T
`SG16 Q.6). pp. 1-20, Oct. 2002.
`Ref 1.17: Title: Final CABAC Cleanup. From: Joint Video
`Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC
`JTC1/SC29/WG 11 and ITU-T SG16 Q.6). pp. 1–24, Dec.
`2002.
`
`Ref 1.18: Title: Very Low Bit-Rate Video Coding Using
`Wavelet-Based Techniques. Author: Detlev Marpe and Hans
`L. Cycon, vol. 9, No. 1, Feb. 1999, pp.: 85–94.
`Ref 1.19: Title: Wavelet-Based Very Low Bit-Rate Video
`Coding Using Image Warping and Overlapped Block
`Motion Compensation. Author: G. Heising, D. Marpe, H.L.
`Cycon and A.P. Petukhov. pp. 93-101, Apr. 2001.
`Ref1.20: Title: Motion-Compensated 3-D Subband Coding
`of Video. Author: Seung-Jong Choi and John W. Woods,
`Fellow IEEE. pp. 155-167, vol. 8, No. 2, Feb. 1999.
`Ref 1.21: Title: A New Fast and Efficient Image Codec
`Based on Set Partitioning in Hierarchical Trees. Author:
`Amir Said (Faculty of Electrical Engineering) and William
`A. Pearlman (Department of Electrical, Computer, and Sys
`tems Engineering Renesselar Polytechnic Institute). pp.:
`1-15, May 1993.
`Ref 1.22: Title: Efficient Pre-Coding Techniques for
`Wavelet-Based Image Compression. Author: Detlev Marpe
`& Hans L. Cycon. pp.: 45-51, (no date).
`Ref 1.23: Title: Universal Modeling and Coding. Author:
`Jorma Rissanen and Glen G. Langdon, Jr., Senior Member,
`IEEE. pp. 12–23, vol. 27, No. 1, Jan. 1981.
`Ref 1.24: Title: Universal Coding Information, Prediction,
`and Estimation. Author: Jorma Rissanen, vol. 30, No. 4, Jul.
`1984, pp. 629–636.
`Ref1.27: Title: Applications of Universal Context Modeling
`to LOSSleSS Compression of Grey-Scale Images. Author:
`Marcelo J. Weinberger, Member, IEEE, Jorma J. Rissanen,
`Senior Member, IEEE, and Ronald B. Arps. pp. 575-586,
`vol. 5, No. 4, Apr. 1996.
`Ref 1.29: Title: A Compression Method for Clustered
`Bit-Vectors. Author: Jukka Teuhola (Department of Com
`puter Science, University of Turka). Application:
`XP-001000934, Oct. 1978.
`Ref 1.30: Title: Optimal Source Codes for Geometrically
`Distributed Integer Alphabets. Author: Robert G. Gallager,
`fellow, IEEE, David C. Vanvoorhis, member, IEEE. pp.:
`228-230, Mar. 1975.
`Ref 1.32: Title: An Overview of the Basic Principles of the
`Q-Coder Adaptive Binary Arithmetic Coder. Author: W.B.
`Pennebaker, J.L. Mitchell, G.G. Langdon, Jr., and R.B. Arps,
`vol. 32, No. 6, Nov. 1988, pp. 717–726.
`Ref 1.3.1: Title: A Context Modeling Algorithm and its
`Application in Video Compression. Author: Marta Mrak,
`Detlev Marpe, and Thomas Wiegand, (no date).
`Ref 1.33: Title: A Multiplication-Free Multialphabet Arith
`metic Code. Author: Jorma Rissanen and K.M. Mohiuddin,
`vol. 37, No. 2, pp.: 93–98, Feb. 1989.
`Ref 1.34: Title: Practical Implementations of Arithmetic
`Code. Author: Paul G. Howard and Jeffrey Scott Vitter. pp.:
`1–30, Oct. 16–18, 1991.
`Ref1.35: Title: Sample Data Coding. From: Chapter 12. pp.:
`474-484, (no date).
`Ref 1.37: Title: Arithmetic Code Revisited. Author: Alistair
`Moffat (The University of Melbourne), Radford M. Neal
`(University of Toronto), and Ian H. Witten (Zthe University
`of Waikato), vol. 16, No. 3, Jul. 1998, pp.: 257–294.
`Ref 1.38: Title: Rate-Constrained Coder Control and Com
`parison of Video Coding Standards. Author: IEEE Transac
`tions on Circuits and Systems for Video Technology, vol. 13,
`No. 7, Jul. 2003. Thomas Wiegand, Heiko Schwartz,
`Anthony Joch, Faouzi Kossentini, Senior Members, IEEE,
`and Gary J. Sullivan, Senior Member, IEEE, Vol. 13, No. 7,
`Jul. 2003, pp. 689–703.
`
`Unified Patents, Ex. 1001
`
`000002
`
`

`

`US 6,943,710 B2
`Page 3
`
`Ref 2.1: Title: Draft ITU-T Recommendation and Final
`Draft International Standard of Joint Video Specification
`(ITU-T rec. H.264 I ISO/IEC 14496-10 AVC). From: Joint
`Video Team (JVT) of SO/IEC MPEG & ITU-T VCEG
`(ISO/IEC JTC1/SC29/WG 11 and ITU-T SG 16 Q/6), pp.
`1-249, Mar. 7–14, 2003.
`Ref 2.03X: Title: Line Transmission of Non-Telephone
`Signals / Video Codec for Audiovisual Services AT p x 64
`kbit/s. From: International Telecommunication Union
`H.261. pp. 1–25, Jun. 1994.
`Ref 2.06x: Title: H.264/AVC Over IP. From: Stephan
`Wenger. pp. 645-656, vol. 13, No. 7, Jul. 2003.
`Ref 2.07: Title: H.264/AVC in Wireless Environments.
`Author: Thomas Stockhammer, Miska M. HannukSela, and
`Thomas Wiegand. pp.: 657-673, vol. 13, No. 7, Jul. 2003.
`Ref 2.08: Title: Motion-and Aliasing-Compensated Predic
`tion for Hybrid Video Coding. Author: Thomas Wedi and
`Hand Georg Musmann. pp. 577-586, vol. 13, No. 7, Jul.
`2003.
`Ref 2.9: Title: Long-Term Memory Motion-Compensated
`Prediction. Author: Thomas Wiegand, Xiaozheng Zhang,
`and Bernd Girod, Fellow, IEEE. pp. 70-84, vol. 9, No. 1,
`Feb. 1999.
`Ref 2.11: Title: A Locally Optimal Design Algorithm for
`Block-Based Multi-Hypothesis Motion-Compensated Pre
`diction. Author: Markus Flierl, Thomas Wiegand, and Bernd
`Girod Telecommunications Laboratory University of Erlan
`gen-Nürnberg, Germany. pp.: 1-10, Mar. 1998.
`Ref 2.12: Title: Generalized B Pictures and the Draft H.264/
`AVC Video-Compression Standard. Author: Markus Fierl,
`Student Member, IEEE, and Bernd Girod, Fellow, IEEE.
`pp. 587-597, vol. 13, No. 7, Jul. 2003.
`Ref 2.13: Title: Rate-Constrained Coder Control and Com
`pression of Video Coding Standards. From: Thomas Wie
`gand, Heiko Schwarz, Anthony Joch, Faouzi KoSSentini,
`Senior Member, IEEE, and Gary J. Sullivan, Senior Mem
`ber, IEEE. pp.: 688-703, vol. 13, No. 7, Jul. 2003.
`Ref 2.14: Title: H.264/AVC Over IP. Author: Stephan
`Wenger. pp. 645-656, vol. 13, No. 7, Jul. 2003.
`Ref 2.15: Title: The SP-and Si-Frames Design for H.264/
`AVC. Author: Marta Karcewicz and Ragip Kurceren, Mem
`ber, IEEE. pp.: 637-644, vol. 13, No. 7, Jul. 2003.
`Ref 2.16: Title: Context-Based Adaptive Binary Arithmetic
`Coding in the H/264/AVC Video Compression Standard.
`Author: Detlev Marpe, Member, IEEE, Heiko Sczwarz, and
`Thomas Wiegand. pp.: 620–636, vol. 13, No. 7, Jul. 2003.
`
`Ref 2.17: Title: Low-Complexity Transform and Quantiza
`tion in H.264/AVC. From: Henrique S. Malvar, Fellow,
`IEEE, Antti Hallapuro, Marta Karczewicz, and Louis Ker
`ofsky, Member, IEEE. pp. 598–603, vol. 13, No. 7, Jul.
`2003.
`Ref 2.18: Title: Adaptive Deblocking Filter. Author: Peter
`List, Anthony Joch, Jani Lainema, Gisle Bontegaard, and
`Marta Karczewicz. pp. 614-619, vol. 13, No. 7, Jul. 2003.
`Ref 2.19: Title: A Generlized Hypothetical Reference
`Decoder for H.264/AVC. Author: Jordi Ribas-Cobrera,
`Member, IEEE, Philip A. Chou, Senior Member, IEEE, and
`Shankar L. Regunathan. pp.: 674-687, vol. 13, No. 7, Jul.
`2003.
`RefA: Title: Draft ITU-T Recommendation and Final Draft
`International Standard of Joint Video Specification (ITU-T
`Rec. Zh.264 I ISO/IEC 14496-10 AVC). From: Joint Video
`Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO.IEC
`JTC1/SC29/WG 11 and ITU-T SG16 Q.6). pp. 1-253, May
`23-27, 2003.
`Ref B: Title: A Highly Efficient Multiplication-Free Binary
`Arithmetic Coder and its Application in Video Coding.
`Author: Detlev Marpe and Thomas Wiegand. pp. 1-4, Sep.
`14-17, 2003.
`Ref C: Title: Proposed Editorial Changes and Cleanup of
`CABAC. From: Joint Video Team (JVT) of ISO/IEC MPEG
`& ITU-T VCEG (ISO.IEC JTC1/SC29/WG 11 and ITU-T
`SG16 Q.6). pp. 1-10, Jul. 22–26, 2002.
`RefD: Title: Study of Final Committee Draft of Joint Video
`Specification (ITU-T Rec. H.264 I ISO/IEC 14496-10
`AVC). From: Joint Video Team (JVT) of ISO/IEC MPEG &
`ITU-T VCEG (ISO.IEC JTC1/SC29/WG 11 and ITU-T
`SG16 Q.6). pp. 1-239, Dec. 5–13, 2003.
`RefE: Title: Study of Final Committee Draft and Joint Video
`Specification (ITU-T Rec. H.264 I ISO/IEC 14496-10
`AVC). From: Joint Video Team (JVT) of ISO/IEC MPEG &
`ITU-T VCEG (ISO.IEC JTC1/SC29/WG 11 and ITU-T
`SG16 Q.6). pp. 1-227, Dec. 5–13, 2002.
`Ref F: Title: CABAC and Slices. From: Joint Video Team
`(JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO.IEC JTC1/
`SC29/WG 11 and ITU-T SG16 Q.6). pp. 1-17, Jul. 22–26,
`2002.
`
`* cited by examiner
`
`Unified Patents, Ex. 1001
`
`000003
`
`

`

`U.S. Patent
`
`Sep. 13, 2005
`
`Sheet 1 of 4
`
`US 6,943,710 B2
`
`1. Determination of the LPS
`2. Calculation of the Variables Rups and RMPs:
`Rites = R. PC Pres
`Rups s R - Rips
`3. Calculation of the new partial interval:
`if (bit = LPS) then
`L - L + Races
`R (- Rs
`
`else
`
`R - RPs
`4. Updating the probability estimation PFS
`5. Outputling the bits and renomalizing R
`
`F.G. 1
`
`
`
`. Determination. Of the LPS
`2. Ouantization of R:
`q index = Otaib (R.-->q
`3. Determination of RPS and RMPS:
`Rups = Rtab (g index, p state
`Rares s R - Rips
`4. Calculation of the new partial interval:
`if (bit s LPS) then
`4- I
`- Rops
`
`else
`
`p state (- Next State LPS (p state)
`R - Russ
`Patate ( - Next State MPs (p state)
`
`F.G. 2
`
`Unified Patents, Ex. 1001
`
`000004
`
`

`

`U.S. Patent
`
`Sep. 13, 2005
`
`Sheet 2 of 4
`
`US 6,943,710 B2
`
`
`
`1. Detenination Of the PS
`2. Ouantization of R:
`q indee s Otab (R2 >g)
`3. Determination of RPS and RMPS
`Rirs = Rtab Ig indec, patate)
`Res of R - Ries
`4. Determination of bit, depending of the position
`of the partial interval:
`if (V 2 Raps) then
`bit (- LPS
`V - V - Rs.
`R - Rs
`p state - Next State LPs (p state)
`
`bit - MOPS
`R - Rops
`p state (- Next State MPs (p statel
`5. Renormalization of R, readingotta bit and updating V
`
`FG. 3
`
`Unified Patents, Ex. 1001
`
`000005
`
`

`

`U.S. Patent
`
`Sep. 13, 2005
`
`Sheet 3 of 4
`
`US 6,943,710 B2
`
`
`
`1. Calculating the new partial interval:
`R {- R as
`if (bit = ) then
`(- ,
`4- R.
`2. Outputting bits and renomalizing R
`
`DeCOder:
`1. Determination of bit, depending on the position
`of the partial interval:
`if (V 2 R) then
`bit -- l
`V - V - R.
`
`else
`
`bit {- O
`2. Reading Out a bit, renomalizing Rand updating V
`
`F.G. 4
`
`Unified Patents, Ex. 1001
`
`000006
`
`

`

`U.S. Patent
`
`Sep. 13, 2005
`
`Sheet 4 of 4
`
`US 6,943,710 B2
`
`
`
`1. Calculating the new partial interval:
`(- ,
`(C-C
`if (bit s l) then
`L (- L + R
`
`2. Outputting a bit and renormatizing using doubled determination threshold values
`(without doubling Rand )
`
`DeCOder.
`1. Reading Outa bit and updating V
`2. Determination of bit depending on the position
`of the partial interval:
`if (V 2 R) then
`bit {- l
`V - V - R.
`it
`o
`
`l. prestate = unin (max (, l, ( (in
`2. if (preState <= 63) then
`p state = 63 - prestate
`vaMPS = O
`
`SliceQP ) >>4) +n) , 126)
`
`else
`
`p state = prestate - 64
`= 1
`
`Unified Patents, Ex. 1001
`
`000007
`
`

`

`US 6,943,710 B2
`
`2
`as the product of the individual probabilities of the occurring
`events is proportional to the probability of the Sequence of
`individual events. As every event S, adds a contribution of
`H(S)=-log(P(S)) of the theoretical information content
`H(S) of S, to the overall rate by the probability P(S), a
`relation between the number N of bits for illustrating the
`partial interval and the entropy of the Sequence of individual
`events results, which is given by the right Side of the
`following equation:
`
`5
`
`1
`METHOD AND ARRANGEMENT FOR
`ARTHMETC ENCODING AND DECODING
`BINARY STATES AND A CORRESPONDING
`COMPUTER PROGRAMANDA
`CORRESPONDING COMPUTER-READABLE
`STORAGE MEDUM
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`This application is a continuation of copending Interna
`tional Application No. PCT/EP03/04654, filed May 2, 2003,
`which designated the United States and was not published in
`English.
`
`BACKGROUND OF THE INVENTION
`
`15
`
`1. Field of the Invention
`The invention relates to a method and an arrangement for
`arithmetically encoding and decoding binary States and to a
`corresponding computer program and a corresponding
`computer-readable Storage medium which may in particular
`be used in digital data compression.
`2. Description of the Related Art
`The present invention describes a new efficient method
`for binary arithmetic coding. There is a demand for binary
`arithmetic coding in most different application areas of
`digital data compression; here, in particular applications in
`the fields of digital image compression are of Special inter
`est. In numerous Standards for image coding, like e.g. JPEG,
`JPEG-2000, JPEG-LS and JPIG, methods for a binary
`arithmetic coding were defined. Newer Standardization
`activities make also the future use of Such coding technolo
`gies obvious in the field of video coding (CABAC in H.
`264/AVC) 1).
`The advantages of arithmetic coding (AC) in contrast to
`the Huffman coding 2 which has up to now been used in
`practice, may basically be characterized by three features:
`1. By using the arithmetic coding, by Simple adaptation
`mechanisms a dynamic adaptation to the present Source
`Statistic may be obtained (adaptivity).
`2. Arithmetic coding allows the allocation of a non
`integer number of bits per Symbol to be coded and is
`therefore Suitable to achieve coding results which illus
`trate an approximation of the entropy as the theoreti
`cally given lower bound (entropy approximation) 3.
`3. Using Suitable context models Statistical bindings
`between symbols for a further data reduction may be
`used with arithmetic coding (interSymbol redundancy)
`4.
`As a disadvantage of an application of the arithmetic
`coding, generally the increased calculation effort compared
`to Huffman coding is regarded.
`The concept of the arithmetic coding goes back to the
`basic documentation for information theory by Shannon 5).
`First conceptional construction methods were firstly pub
`lished by Elias 6). A first LIFO (last-in-first-out) variant of
`the arithmetic coding was designed by Rissanen 7 and later
`modified 89 10 by different authors to the FIFO
`implementations (first-in-first-out).
`All of those documents have the basic principle of recur
`Sive partial interval decomposition in common. Correspond
`ing to the given probabilities P(“0”) and P(“1”) of two
`results “0”, “1” of a binary alphabet a primarily given
`interval, e.g. the interval 0, 1), is recursively decomposed
`into partial intervals depending on the occurrence of indi
`vidual events. Here, the Size of the resulting partial interval
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`The basic principle, however, first of all requires a
`(theoretically) unlimited accuracy in the illustration of the
`resulting partial interval and apart from that it has the
`disadvantage that only after the coding of the last result may
`the bits for a representation of the resulting partial interval
`be output. For practical application purposes it was therefore
`decisive to develop mechanisms for an incremental output of
`bits with a simultaneous representation with numbers of a
`predetermined fixed accuracy. These were first introduced in
`the documents 3711).
`In FIG. 1, the basic operations for a binary arithmetic
`coding are indicated. In the illustrated implementation the
`current partial interval is represented by the two values L
`and R, wherein L indicates the offset point and R the size
`(width) of the partial interval, wherein both quantities are
`respectively illustrated using b-bit integers. The coding of a
`bit 6{0, 1} is thereby basically performed in five substeps:
`In the first step using the probability estimation the value of
`the less probable symbol is determined. For this symbol,
`also referred to as LPS (least probable symbol), in contrast
`to the MPS (most probable symbol), the probability estima
`tion P,
`is used in the Second step for calculating the width
`Res of the corresponding partial interval. Depending on the
`value of the bit to be coded Land Rare updated in the third
`Step. In the forth Step the probability estimation is updated
`depending on the value of the just coded bit and finally the
`code interval R is Subjected to a So-called renormalization in
`the last Step, i.e. R is for example rescaled So that the
`condition Re2, 2) is fulfilled. Here, one bit is output
`with every Scaling operation. For further details please refer
`to 10).
`The main disadvantage of an implementation, as outlined
`above, now lies in the fact that the calculation of the interval
`width Rs requires a multiplication for every Symbol to be
`coded. Generally, multiplication operations, in particular
`when they are realized in hardware, are cost- and time
`intensive. In Several research documents methods were
`examined to replace this multiplication operation by a
`suitable approximation 11 12 1314). Hereby, the
`methods published with reference to this topic may gener
`ally be separated into three categories.
`The first group of proposals for a multiplication-free,
`binary arithmetic coding is based on the approach to
`approximate the estimated probabilities Prs So that the
`multiplication in the second step of FIG.1 may be replaced
`by one (or several) shift and addition operation(s) 1114).
`For this, in the Simplest case the probabilities Prs are
`approximated by values in the form of 27 with the integer
`q>0.
`In the Second category of approximative methods it is
`proposed to approximate the value range of R by discrete
`values in the form (%-r), wherein re{0}U{2k>0, k
`integer} is selected 1516).
`The third category of methods is only known from the fact
`that here any arithmetic operations are replaced by table
`accesses. To this group of methods on the one hand the
`
`Unified Patents, Ex. 1001
`
`000008
`
`

`

`US 6,943,710 B2
`
`5
`
`15
`
`25
`
`35
`
`40
`
`3
`Q-coder used in the JPEG standard and related methods,
`such as the QM- and MQ-coder 12, and on the other hand
`the quasi-arithmetic coder 13 belong. While the latter
`method performs a drastic limitation of the number b of bits
`used for the representation of R in order to obtain acceptably
`dimensioned tables, in the Q-coder the renormalization of R
`is implemented So that R may at least approximately be
`approximated by 1. This way the multiplication for deter
`mining R, s is prevented. Additionally, the probability
`estimation using a table in the form of a finite State machine
`is operated. For further details please see 12).
`SUMMARY OF THE INVENTION
`It is the object of the present invention to provide a
`method and an arrangement for an arithmetic encoding and
`decoding of binary States and a corresponding computer
`program and a corresponding computer-readable Storage
`medium which eliminate the mentioned disadvantages and
`in particular (a) do not require a multiplication, (b) allow a
`probability estimation without calculation effort and (c)
`Simultaneously guarantee a maximum coding efficiency
`over a wide range of typically occurring Symbol probabili
`ties.
`In accordance with a first aspect, the present invention
`provides a method for an arithmetic encoding and decoding
`of binary States, wherein in a first Step a presetable value
`range for the Specification of the interval width R is sepa
`rated in K representative interval widths {Q, . . . , Q}, a
`presetable value range for the Specification of the probabili
`ties is separated in N representative probability States
`{P, . . . , P} and allocation regulations are given, which
`allocate one Q (1sks K) to every interval width R and one
`P. (1snsN) to every probability, and that in a second step
`the encoding or decoding of the binary States take place by
`performing the calculation of the new interval width to be
`derived in the encoding or decoding process, respectively,
`using a representative interval width Q (1sks K) and a
`representative probability state P, (1snsN) by arithmetic
`operations other than multiplication and division, wherein
`the representative interval width Q is determined by the
`basic basis interval of the width R and the representative
`probability state P, is determined by the probability estima
`tion underlying the symbol to be encoded or to be decoded
`according to the given allocation regulations.
`In accordance with a Second aspect, the present invention
`provides an arrangement having at least one processor
`and/or chip, which is/are implemented Such that a method
`for an arithmetic encoding and decoding of binary States is
`may be performed, wherein in a first Step a presetable value
`range for the Specification of the interval width R is sepa
`rated in K representative interval widths {Q, . . . , Q}, a
`presetable value range for the Specification of the probabili
`ties is separated in N representative probability States
`{P, . . . , P} and allocation regulations are given, which
`allocate one Q (1sks K) to every interval width R and one
`P. (1snsN) to every probability, and wherein in a second
`Step the encoding or decoding of the binary States take place
`by performing the calculation of the new interval width to be
`derived in the encoding or decoding process, respectively,
`using a representative interval width Q (1sks K) and a
`representative probability state P, (1snsN) by arithmetic
`operations other than multiplication and division, wherein
`the representative interval width Q is determined by the
`basic basis interval of the width R and the representative
`probability state P, is determined by the probability estima
`tion underlying the symbol to be encoded or to be decoded
`according to the given allocation regulations.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`In accordance with a third aspect, the present invention
`provides a computer program which enables a computer
`after it has been loaded into the Storage of the computer to
`perform a method for an arithmetic encoding and decoding
`of binary States, wherein in a first Step a presetable value
`range for the Specification of the interval width R is sepa
`rated in K representative interval widths {Q, . . . , Q}, a
`presetable value range for the Specification of the probabili
`ties is separated in N representative probability States
`{P, . . . , P} and allocation regulations are given, which
`allocate one Q (1sks K) to every interval width R and one
`P. (1snsN) to every probability, and wherein in a second
`Step the encoding or decoding of the binary States take place
`by performing the calculation of the new interval width to be
`derived in the encoding or decoding process, respectively,
`using a representative interval width Q (1sks K) and a
`representative probability state P, (1snsN) by arithmetic
`operations other than multiplication and division, wherein
`the representative interval width Q is determined by the
`basic basis interval of the width R and the representative
`probability state P, is determined by the probability estima
`tion underlying the symbol to be encoded or to be decoded
`according to the given allocation regulations.
`In accordance with a fourth aspect, the present invention
`provides A computer-readable Storage medium on which a
`computer program is Stored which enables a computer after
`it has been loaded into the Storage of the computer to
`perform a method for an arithmetic encoding and decoding
`of binary States, wherein in a first Step a presetable value
`range for the Specification of the interval width R is sepa
`rated in K representative interval widths {Q, . . . , Q}, a
`presetable value range for the Specification of the probabili
`ties is separated in N representative probability states
`{P, . . . , P} and allocation regulations are given, which
`allocate one Q (1sks K) to every interval width R and one
`P. (1snsN) to every probability, and wherein in a second
`Step the encoding or decoding of the binary States take place
`by performing the calculation of the new interval width to be
`derived in the encoding or decoding process, respectively,
`using a representative interval width Q (1sks K) and a
`representative probability state P, (1snsN) by arithmetic
`operations other than multiplication and division, wherein
`the representative interval width Q is determined by the
`basic basis interval of the width R and the representative
`probability state P, is determined by the probability estima
`tion underlying the symbol to be encoded or to be decoded
`according to the given allocation regulations.
`One method for an arithmetic encoding and decoding of
`binary States is advantageously performed So that in a first
`Step a presetable value range for the Specification of the
`interval width R is separated in K representative interval
`widths {Q, . . . , Qk}, a presetable value range for the
`Specification of the probabilities is separated in N represen
`tative probability States {P, . . . , P} and allocation
`regulations are given, which allocate one Q (1sks K) to
`every interval width R and one P. (1snsN) to every
`probability, and that in a Second Step the encoding or
`decoding of the binary States take place by performing the
`calculation of the new interval width to be derived in the
`encoding or decoding process, respectively, using a repre
`Sentative interval width Q (1sks K) and a representative
`probability state P, (1snsN) by arithmetic operations other
`than multiplication and division, wherein the representative
`interval width Q is determined by the basic basis interval
`of the width R and the representative probability state P, is
`determined by the probability estimation underlying the
`Symbol to be encoded or to be decoded according to the
`given allocation regulations.
`
`Unified Patents, Ex. 1001
`
`000009
`
`

`

`S
`Another preferred implementation of the invention is
`characterized by the fact that based on the interval currently
`to be evaluated with a width R for determining the associ
`ated interval width Q an indeX q indeX is determined by
`a shift and bit masking operation applied to the computer
`internal/binary representation of R.
`It is also advantageous when based on the interval cur
`rently to be evaluated with a width R for determining the
`asSociated interval width Q an indeX q indeX is deter
`mined by a shift operation applied to the computer-internal/
`binary representation of R and a downstream access to a
`table Otab, wherein the table Otab contains the indices of
`interval widths which correspond to the values of R which
`were pre-quantized by the Shift operation.
`It is in particular advantageous when the probability
`estimation underlying the Symbol to be encoded or decoded
`is associated to a probability State P, using an indeX p state.
`It is also an advantage when the determination of the
`interval width Rs corresponding to the LPS is performed
`by an access to the table Rtab, wherein the table Ritab
`contains the values corresponding to all K quantized values
`of R and to the N different pro