LERNER AND GREENBERG, P.A.
`PATENT ATTORNEYS AND ATTORNEYS AT LAW
`2445 Hollywood Boulevard
`Hollywood, Florida 33020
`Tel: (954) 925-1100
`Fax: (954) 925-1101
`
`PATENTUSA®
`www.patentusa.com
`patents@patentusa.com
`
`Mailing Address:
`Post Office Box 2480
`Hollywood, FL 33022-2480
`
`New York Satellite Office
`153 E 57th St., Suite 15G
`New York, NY 10022
`
`Of Counsel:
`Herbert L. Lemer (NY Bar)
`
`Laurence A. Greenberg (FL Bar)
`Werner H. Sterner (FL Bar)
`Ralph E. Locher (FL, IL, MO Bars)
`Gregory L. Mayback (FL Bar)
`
`Manfred Beck (US & German Pat Agent)
`Mark P. Weichselbaum (TN Bar)
`Markus Nolff (FL Bar)
`Loren Donald Pearson (FL Bar)
`Otto S. Kauder (Reg. Pat. Agent)
`Denise A. Lettau (DC Bar)
`Yonghong Chen (Chinese Pat. Agent)
`F. Donald Paris (NY, NJ, DC Bars)
`Alfred K. Dassler (Reg. Pat Agent)
`Kyle H. Flindt (UT Bar)
`
`"Express Mail" mailing label number: EL974067755US
`Date of Deposit December 4, 2003
`
`I hereby certify that this paper or fee is being deposited with the United States Postal Service
`"Express Mail Post Office to Addressee" service under 37 CFR 1.10 on the date indicated above and
`is addressed to the Commissioner for Patents, P.O. Box 1450, Alexandria, VA 22313-1450.
`
`MICHAEL BURNS
`
`Docket No.: S&ZFH030508
`
`Date: December 4, 2003
`
`Mail Stop Patent Application
`Commissioner for Patents
`P.O. Box 1450
`Alexandria, VA 22313-1450
`
`Sir:
`
`Enclosed herewith are the necessary papers for filing the following application for
`Letters Patent:
`
`Applicant
`
`DETLEF MARPE ET AL.
`
`Title
`
`METHOD AND ARRANGEMENT FOR ARITHMETIC ENCODING
`AND DECODING BINARY STATES AND A CORRESPONDING
`COMPUTER PROGRAM AND A CORRESPONDING
`COMPUTER-READABLE STORAGE MEDIUM
`
`4 sheets of drawings.
`The payment in the amount of $928.00 covering the filing fee.
`PCT Cover Sheet WO 03/094355 A2
`
`This application is being filed without a signed oath or declaration under the
`provisions of 37 CFR 1.53(f). Applicants await notification of the date by which the
`oath or declaration and the surcharge are due, pursuant to this rule.
`
`Unified Patents, Ex. 1002
`
`000001
`
`

`

`The Patent and Trademark Office is hereby given authority to charge Deposit
`Account No. 12-1099 of Lerner and Greenberg, P.A. for any fees due or deficiencies
`of payments made for any purpose during the pendency of the above-identified
`application.
`
`Respec
`
`submitte
`
`plicants
`AG:kf
`
`LAURENCE A.
`GREENBERG
`REG. NO. 29,308
`
`Unified Patents, Ex. 1002
`
`000002
`
`

`

`S&ZFH030508
`
`Method and Arrangement for Arithmetic Encoding and Decoding
`
`Binary States and a Corresponding Computer Program and a
`
`Corresponding Computer-readable Storage Medium
`
`5
`
`Cross-Reference to Related Application:
`
`This
`
`application is a
`
`continuation
`
`of copending
`
`International Application No. PCT/E203/04654, filed May 2,
`
`10 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
`
`20 computer-readable storage medium which may in particular be
`
`used in digital data compression.
`
`2. Description of the Related Art:
`
`25 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
`
`30 interest. 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
`
`technologies obvious in the field of video coding (CABAC in
`
`35 H. 264/AVC) [1].
`
`Unified Patents, Ex. 1002
`
`000003
`
`

`

`- 2 -
`
`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:
`
`5 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-
`
`10
`
`integer number of bits per symbol to be coded and is
`
`therefore suitable to achieve coding results which
`
`illustrate an approximation of the entropy as the
`
`theoretically given lower bound (entropy approximation)
`
`[3].
`
`15
`
`20
`
`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.
`
`25 The concept of the arithmetic coding goes back to the basic
`
`documentation for information theory by Shannon [5]. First
`
`conceptional construction methods were firstly published by
`
`Elias [6]. A first LIFO (last-in-first-out) variant of the
`
`arithmetic coding was designed by Rissanen [7] and later
`
`30 modified [8] [9] [10] by different authors to the FIFO
`
`implementations (first-in-first-out).
`
`All of those documents have the basic principle of
`
`recursive partial interval decomposition in common.
`
`35 Corresponding 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
`
`Unified Patents, Ex. 1002
`
`000004
`
`

`

`- 3 -
`
`occurrence of individual events. Here, the size of the
`
`resulting partial interval as the product of the individual
`
`probabilities of the occurring events is proportional to
`
`the probability of the sequence of individual events. As
`
`5 every event Si adds a contribution of H(Si) = -log(P(Si)) of
`
`the theoretical information content H(S1) of Si to the
`
`overall rate by the probability P(Si), a relation between
`
`the number NBit of bits for illustrating the partial
`interval and the entropy of the sequence of individual
`
`10 events results, which is given by the right side of the
`
`following equation:
`
`NB„ = -log if P(Si) = -E, log P (Si)
`
`15 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
`
`20 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 [3]
`
`25 [7] [11].
`
`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
`
`30 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 E {0, 1} is thereby basically performed in
`
`five substeps: In the first step using the probability
`
`35 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 estimation PLPS is used in the
`
`Unified Patents, Ex. 1002
`
`000005
`
`

`

`- 4 -
`
`second step
`
`corresponding
`
`for calculating the width RLPS
`partial interval. Depending on the value of
`
`of the
`
`the bit to be
`
`coded L and R are updated in the third step.
`
`In the forth
`
`step the probability estimation is updated
`
`5 depending on the value of the just coded bit and finally
`
`the code interval R is subjected to a so-called
`
`rescaled so that the condition Re [2b-z, 2 b-1] j is fulfilled.
`
`renormalization in the last step, i.e. R is for example
`
`Here, one bit is output with every scaling operation. For
`
`10 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 RLPS
`15 symbol to be coded. Generally, multiplication operations,
`
`requires a multiplication for every
`
`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] [13] [14]. Hereby, the
`
`20 methods published with reference to this topic may
`
`generally be separated into three categories.
`
`The first group of proposals for a multiplication-free,
`
`binary arithmetic coding is based on
`
`the approach to
`
`25 approximate the estimated probabilities
`
`PLPS so that the
`multiplication in the second step of Fig. 1 may be replaced
`
`by one (or several) shift and addition operation(s) [11]
`
`[14]. For this, in the simplest case the probabilities ELps
`
`are approximated by values in the form of 2-q with the
`
`30 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 (1/2 - r), wherein r E {0} L) {2-k 1 k >
`
`35 0, k integer} is selected [15] [16].
`
`The third category of methods is only known from the fact
`
`that here any arithmetic operations are replaced by table
`
`Unified Patents, Ex. 1002
`
`000006
`
`

`

`- 5 -
`
`accesses. To this group of methods on the one hand the 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
`
`5 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
`10 determining RLPS 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].
`
`15
`
`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
`
`20 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 probabilities.
`
`25
`
`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
`
`30 is separated in K representative interval widths WI,
`QK}, a presetable value range for the specification of the
`probabilities is separated in N representative probability
`PN} and allocation regulations are given,
`states {PI,
`which allocate one QK (1
`35 and one Pn (1
`n
`N) to every probability, and that in a
`
`K) to every interval width R
`
`k
`
`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
`
`Unified Patents, Ex. 1002
`
`000007
`
`

`

`process, respectively, using a representative interval
`width QK (1
`n
`
`k
`
`K) and a representative probability state
`
`N) by arithmetic operations other than
`
`2n (1
`multiplication and division, wherein the representative
`5 interval width QK is determined by the basic basis interval
`of the width R and the representative probability state Fin
`
`is determined by the probability estimation underlying the
`
`symbol to be encoded or to be decoded according to the
`
`given allocation regulations.
`
`10
`
`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
`
`15 may be performed, wherein in a first step a presetable
`
`value range for the specification of the interval width R
`is separated in K representative interval widths {41,
`(20, a presetable value range for the specification of the
`
`probabilities is separated in N representative probability
`20 states {P1, ..., PO and allocation regulations are given,
`which allocate one QK (1
`k
`K) to every interval width R
`and one Pn (1
`n
`N) 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
`
`25 interval width to be derived in the encoding or decoding
`
`k
`
`process, respectively, using a representative interval
`width QK (1
`K) and a representative probability state
`n < N) by arithmetic operations other than
`
`Pn (1
`multiplication and division, wherein the representative
`30 interval width QK is determined by the basic basis interval
`of the width R and the representative probability state Pfl
`
`is determined by the probability estimation underlying the
`
`symbol to be encoded or to be decoded according to the
`
`given allocation regulations.
`
`35
`
`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
`
`Unified Patents, Ex. 1002
`
`000008
`
`

`

`- 7 -
`
`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
`separated in K representative interval widths {Q1, -, QK},
`5 a presetable value range for the specification of the
`
`probabilities is separated in N representative probability
`states 1131, ..., PN} and allocation regulations are given,
`which allocate one QK (1 5_ k 5 K) to every interval width R
`and one Pn (1
`n
`N) to every probability, and wherein in
`
`10 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 QK (1
`15 Pr, (1 5 n __ N) by arithmetic operations other than
`
`K) and a representative probability state
`
`k
`
`multiplication and division, wherein the representative
`interval width QK is determined by the basic basis interval
`of the width R and the representative probability state Pn
`
`is determined by the probability estimation underlying the
`
`20 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
`
`25 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
`30 separated in K representative interval widths {41, -, 40 ,
`a presetable value range for the specification of the
`
`probabilities is separated in N representative probability
`states {P1, ..., PN} and allocation regulations are given,
`which allocate one QK (1
`35 and one Pr, (1
`n
`N) to every probability, and wherein in
`
`k __ K) to every interval width R
`
`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
`
`Unified Patents, Ex. 1002
`
`000009
`
`

`

`process, respectively, using a representative interval
`width QK (1
`n
`
`Pn (1
`
`N) by arithmetic operations other than
`
`k
`
`K) and a representative probability state
`
`multiplication and division, wherein the representative
`5 interval width QK is determined by the basic basis interval
`
`of the width R and the representative probability state Pn
`
`is determined by the probability estimation underlying the
`
`symbol to be encoded or to be decoded according to the
`
`given allocation regulations.
`
`10
`
`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
`15 interval widths {(21, -, 40, a presetable value range for
`the specification of the probabilities is separated in N
`
`representative probability states
`and
`PN1
`allocation regulations are given, which allocate one QK (1
`k S K) to every interval width R and one Pn (1
`n S N)
`
`20 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 QK (1
`25 representative probability state Pn (1
`
`K) and a
`
`N) by
`
`k
`
`n
`
`arithmetic operations other than multiplication and
`division, wherein the representative interval width QK is
`determined by the basic basis interval of the width R and
`
`the representative probability state Pn is determined by
`
`30 the probability estimation underlying the symbol to be
`
`encoded or to be decoded according to the given allocation
`
`regulations.
`
`Another preferred implementation of the invention is
`
`35 characterized by the fact that based on the interval
`
`currently to be evaluated with a width R for determining
`the associated interval width QK an index qindex is
`
`Unified Patents, Ex. 1002
`
`000010
`
`

`

`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
`
`5 currently to be evaluated with a width R for determining
`the associated interval width QK an index qindex is
`determined by a shift operation applied to the computer-
`
`internal/binary representation of
`R and a downstream access
`
`to a table Qtab, wherein the
`
`table Qtab contains the
`
`10 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
`
`15 is associated to a probability state
`
`Pn using an index
`
`p_state.
`
`It is also an advantage when the determination of the
`interval width RLPS corresponding to the LPS is performed by
`20 an access to the table Rtab, wherein the table Rtab
`
`contains the values corresponding to all K quantized values
`
`of R and to the N
`
`different probability states of
`
`the
`
`interval width
`
`calculation
`
`as product values (41( *
`RLPS
`effort is reduced in
`particular
`
`Pn) •
`when
`
`The
`
`the
`
`25 determination of the interval width
`
`corresponding to
`RLPS
`the LPS is performed by an access to the table Rtab,
`
`wherein for evaluating the table the quantization index
`
`q_index and the index of the probability state p_state are
`
`used.
`
`30
`
`It is further provided that in the inventive method for the
`
`N different representative probability states transition
`
`rules are given, wherein the transition rules indicate
`
`which new state is used based on the currently encoded or
`
`35 decoded symbol for the next symbol to be encoded or
`
`decoded. It is hereby of an advantage when a table
`
`Next State LPS is created which contains the index m of the
`
`new probability state Pm when a least probable symbol (LPS)
`
`Unified Patents, Ex. 1002
`
`000011
`
`

`

`- 10 -
`
`occurs in addition to the index n of the currently given
`
`probability state Pn, and/or when a table Next State MPS is
`
`created which contains the index m of the new probability
`
`state P. when a most probable symbol (MPS) occurs in
`
`5 addition to the index n of the currently given probability
`
`state Pn.
`
`An optimization of the method for a table-aided binary
`
`arithmetic encoding and decoding is achieved in particular
`
`10 by the fact that the values of the interval width RLes
`corresponding to all K interval widths and to all N
`
`different probability states are filed as product values
`(41( * Pn) in a table Rtab.
`
`15 A further optimization is achieved when the number K of the
`
`quantization values and/or the number N of the
`
`representative states are selected depending on the preset
`
`accuracy of the coding and/or depending on the available
`
`storage room.
`
`20
`
`One special implementation of the encoding in the inventive
`
`method includes the following steps:
`
`1. Determination of the LPS
`
`25 2. Quantization of R:
`
`qindex = Qtab [R>>q]
`
`3. Determination of RLps and R:
`
`RLPS = Rtab [cLindex, p_atate]
`R = R - Run
`
`30 4. Calculation of the new partial interval:
`
`if (bit : LPS) then
`
`L +- L + R
`
`R +- RLPS
`p_atate +- Next_StatejaPS [p_state]
`
`35
`
`if (p_state = 0) then valMPS +- 1 - vaiMPS
`
`else
`
`p_atate +- Next State MPS [p_state]
`
`Unified Patents, Ex. 1002
`
`000012
`
`

`

`5. Renormalization of L and R, writing bits, wherein
`
`q_index
`
`describes the index of a quantization value
`
`read out of Qtab,
`
`p state
`
`describes the current state,
`
`5
`
`RLPS
`
`describes the interval width corresponding
`
`to the LPS and
`
`valMPS
`
`describes the bit corresponding to the MPS.
`
`The decoding in a special implementation of the inventive
`
`10 method includes the following steps:
`
`1. Determination of the LPS
`
`2. Quantization of R:
`
`qindex = Qtab[R>>q]
`
`3. Determination of RLPS and R:
`
`15
`
`RLPS = Rtab [q_index, p_state]
`
`R = R - RLPS
`4. Determination of bit depending on the position of the
`
`partial interval:
`
`if (V R) then
`
`20
`
`bit 4-- LPS
`
`V 4-- V - R
`
`R
`
`RLPS
`if (p_state = 0) valMPS +- 1 - valMPS
`
`p_state 4-- Next State LPS [p_state]
`
`25
`
`else
`
`bit +- MPS
`
`p_state +- Next State MPS [p_state]
`
`5. Renormalization of R, reading out one bit and updating
`
`30
`
`V, wherein
`
`q_index
`
`describes the index of a quantization value
`
`read out of Qtab,
`
`p_state
`
`describes the current state,
`
`RLPS
`
`describes the interval width corresponding
`
`35
`
`to the LPS,
`
`valMPS
`
`describes the bit corresponding to the MPS,
`
`and
`
`V
`
`describes a value from the interior of the
`
`Unified Patents, Ex. 1002
`
`000013
`
`

`

`- 12 -
`
`current partial interval.
`
`In another special implementation of the inventive method
`
`it is provided that in encoding and/or decoding the
`
`5 calculation of the quantization index q_index is performed
`
`in the second substep after the calculation regulation:
`
`qindex = (R >> q) & Qmask
`
`10 wherein Qmask illustrates a bit mask suitably selected
`
`depending on K.
`
`If a uniform probability distribution is present a further
`
`optimization of the method for a table-aided binary
`
`15 arithmetic encoding and decoding may be achieved by the
`
`fact that in the encoding according to claim 12 the
`
`substeps 1 to 4 are performed according to the following
`
`calculation regulation:
`
`R +- R >> 1
`
`20 if (bit = 1) then
`
`L +- L + R
`
`or
`
`that the substeps 1 to 4 of the encoding according to claim
`
`12 are performed according to the following calculation
`
`25 regulation:
`
`L +- L << 1
`
`if (bit = 1) then
`
`L +- L + R
`
`and wherein in the last alternative the renormalization
`
`30 (substep 5 according to claim 12) is performed with doubled
`
`decision threshold values and no doubling of L and R is
`
`performed, and
`
`that in the decoding according to claim 13 the substeps 1
`
`to 4 are performed according to the following calculation
`
`35 regulation:
`
`R+- R>>1
`
`if (V
`
`R) then
`
`bit +- 1
`
`Unified Patents, Ex. 1002
`
`000014
`
`

`

`- 13 -
`
`V 4-- V - R
`
`else
`
`bit +- 0,
`
`or
`
`5 the substeps 1 to 5 of the decoding according to claim 13
`
`are performed according to the following calculation
`
`regulation:
`
`1. Reading out one bit and updating V
`
`2. Determination of bit according to the position of the
`
`10
`
`partial interval:
`
`if (V
`
`R) then
`
`bit 4-- 1
`
`V *- V - R
`
`else
`
`15
`
`bit 4-- 0.
`
`It further turns out to be advantageous when the
`
`initialization of the probability models is performed
`
`depending on a quantization parameter SliceQP and preset
`
`20 model parameters m and n, wherein SliceQP describes the
`
`quantization parameter preset at the beginning of a slice
`
`and m and n describe the model parameters.
`
`It is also advantageous when the initialization of the
`
`25 probability models includes the following steps:
`
`1. preState = min(max(1, ((m * SliceQP) >>4)+n), 2*N)
`
`2. if (preState <=N) then
`
`p_state = N+1 - preState
`
`valMPS = 0
`
`30
`
`else
`
`p_state = preState - N
`
`valMPS = 1,
`
`wherein valMPS describes the bit corresponding to the MPS,
`
`SliceQP describes the quantization parameter preset at the
`
`35 beginning of a slice and m and n describe the model
`
`parameters.
`
`Unified Patents, Ex. 1002
`
`000015
`
`

`

`- 14 -
`
`One arrangement for an arithmetic encoding and decoding of
`
`binary states includes at least one processor which is/are
`
`implemented such that a method for an arithmetic encoding
`
`and decoding may be performed, wherein in a first step a
`
`5 presetable value range for the specification of the
`
`interval width R is separated in K representative interval
`
`widths {41,
`specification of the probabilities is separated in N
`
`a presetable value range for the
`
`representative probability states
`
`PN}
`10 allocation regulations are given, which allocate one QK (1
`
`and
`
`k
`
`K) to every interval width R and one P, (1
`to every probability, and wherein in a second step the
`
`n
`
`N)
`
`encoding or decoding of the binary states take place by
`performing the calculation of the new interval width to be
`
`15 derived in the encoding or decoding process, respectively,
`using a representative interval width QK (1
`
`K) and a
`
`k
`
`representative probability state P, (1
`
`n 5 N) by
`
`arithmetic operations other than multiplication and
`
`division, wherein the representative interval width QK is
`20 determined by the basic basis interval of the width R and
`
`the representative probability state Pn is determined by
`the probability estimation underlying the symbol to be
`
`encoded or to be decoded according to the given allocation
`
`regulations..
`
`25
`
`One computer program for an arithmetic encoding and
`
`decoding of binary states allows a computer, after it has
`been loaded into the storage of the computer, to perform an
`
`method for an arithmetic encoding and decoding, wherein in
`30 a first step a presetable value range for the specification
`
`of the interval width R is separated in K representative
`interval widths {Q1,
`
`QK I , a presetable value range for
`
`the specification of the probabilities is separated in N
`PN} and
`
`representative probability states
`
`35 allocation regulations are given, which allocate one QK (1
`k
`K) to every interval width R and one P, (1
`n
`N)
`to every probability, and wherein in a second step the
`encoding or decoding of the binary states take place by
`
`Unified Patents, Ex. 1002
`
`000016
`
`

`

`- 15 -
`
`performing the calculation of the new interval width to be
`
`derived in the encoding or decoding process, respectively,
`
`using a representative interval width QK (1 S k 5 K) and a
`
`representative probability state Pi, (1
`
`n
`
`N) by
`
`5 arithmetic operations other than multiplication and
`
`division, wherein the representative interval width QK is
`
`determined by the basic basis interval of the width R and
`the representative probability state Pn is determined by
`
`the probability estimation underlying for the symbol to be
`10 encoded or to be decoded according to the given allocation
`
`regulations.
`
`For example, such computer programs may be provided
`(against a certain fee or for free, freely accessible or
`
`15 password-protected) which may be downloaded into a data or
`
`communication network. The thus provided computer programs
`
`may then be made useable by a method in which a computer
`
`program according to claim 22 is downloaded from a network
`for data transmission, like for example from the Internet
`20 to a data processing means connected to the network.
`
`For performing a method for an arithmetic encoding and
`
`decoding of binary states preferably a computer-readable
`
`storage medium is used on which a program is stored which
`25 allows a computer, after it has been loaded into the
`
`storage of the computer, to perform a method for an
`arithmetic encoding or decoding, wherein in a first step a
`
`presetable value range for the specification of the
`
`interval width R is separated in K representative interval
`30 widths {Q1, —, QK}, a presetable value range for the
`specification of the probabilities is separated in N
`representative probability states (PI, ...,
`PO and
`allocation regulations are given, which allocate one QK (1
`IS k 5_ K) to every interval width R and one Pn (1
`35 to every probability, and wherein in a second step the
`
`N)
`
`n
`
`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,
`
`Unified Patents, Ex. 1002
`
`000017
`
`

`

`- 16 -
`
`using a representative interval width QK
`representative probability state Pn (1
`
`(1
`
`k
`
`n
`
`K) and a
`
`N) by
`
`arithmetic operations other than multiplication and
`division, wherein the representative interval width QK is
`5 determined by the basic basis interval of the width R and
`
`the representative probability state Pn
`
`is determined by
`
`the probability estimation underlying as
`
`the basis for the
`
`symbol to be encoded or to be decoded
`
`according to the
`
`given allocation regulations.
`
`10
`
`The new method is distinguished by the combination of three
`
`features. First of all, similar to the Q-coder the
`
`probability estimation is performed using a finite state
`
`machine (FSM), wherein the generation of the
`
`N
`
`15 representative states of the FSM is performed offline. The
`
`corresponding transition rules are thereby filed in the
`
`form of tables.
`
`A second characteristic feature of the invention is a
`
`20 prequantization of the interval width R to a number of K
`
`predefined quantization values. This allows, with a
`
`suitable dimensioning of K an N, the generation of a table
`
`which contains all K x N combinations of precalculated
`
`product values R x
`
`PLPS
`
`for a multiplication-free
`
`25 determination of RLps•
`
`For the use of the presented invention in an environment in
`
`which different context models are used among which also
`
`such with (almost) uniform probability distribution are
`
`30 located, as an additional (optional) element a separated
`
`branch is provided within the coding machine in which
`
`assuming an equal distribution the determination of the
`
`variables L and R and the renormalization regarding the
`
`calculation effort is again substantially reduced.
`
`35
`
`As a whole the invention in particular provides the
`
`advantage that it allows a good compromise between a high
`
`Unified Patents, Ex. 1002
`
`000018
`
`

`

`- 17 -
`
`coding efficiency on the one hand and a low calculating
`
`effort on the other hand.
`
`5
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These and other objects and features of the present
`
`invention
`
`will become clear from the following description
`
`taken in
`
`conjunction with the accompanying drawings, in
`
`which:
`
`10
`
`Fig. 1
`
`shows an illustration of the basic operations
`
`for a binary arithmetic coding;
`
`Fig. 2
`
`shows a modified scheme for a table-aided
`
`arithmetic encoding;
`
`15
`
`Fig. 3
`
`shows the principle of the table-aided
`
`arithmetic decoding;
`
`Fig. 4
`
`shows the principle of .encoding or decoding,
`
`respectively, binary data having a uniform
`
`distribution;
`
`20
`
`Fig. 5
`
`shows an alternative realization of encoding or
`
`decoding, respectively, for binary data with a
`
`uniform distribution; and
`
`Fig. 6
`
`shows the initialization of the probability
`
`models depending on a quantization parameter
`
`25
`
`SliceQP and preset model parameters m and n.
`
`DESCRIPTION OF THE PREFERRED EMBODIMENTS
`
`30 First of all, however, the theoretical background is to be
`
`explained in more detail:
`
`Table-aided probability estimation
`
`35 As it was already mentioned above, the effect of the
`
`arithmetic coding relies on an estimation of the occurrence
`
`probability of th