ES2316749T3 - PROCEDURE AND PROVISION FOR THE CODIFICATION AND ARITHMETIC DECODIFICATION OF BINARY STATES AS WELL AS A CORRESPONDING COMPUTER PROGRAM AND LEGIBLE STORAGE MEDIA BY CORRESPONDING COMPUTER. - Google Patents

Abstract

The method involves dividing a value range specifying the interval width into representative interval widths and a value range specifying probabilities into representative probability states, defining rules that associate each interval width and probability and computing new interval widths using a representative interval width and probability state, various arithmetic operations and a probability estimation according to the defined rules. The method involves dividing a defined value range for specifying the interval width into representative interval widths and a definable value range for specifying probabilities into representative probability states and defining association rules that associate each interval width and each probability, encoding or decoding the binary states by computing new interval widths using a representative interval width and probability state, various arithmetic operations and a probability estimation in accordance with the defined association rules. Independent claims are also included for the following: (a) an arrangement with at least one processor and/or chip for arithmetically encoding and decoding binary states (b) a computer program for arithmetically encoding and decoding binary states (c) a computer-readable memory medium for storing a computer program for arithmetically encoding and decoding binary states (d) a method of downloading a computer program from an electronic data network, e.g. Internet.

Description

Procedure and provision for coding and arithmetic decoding of binary states as well as corresponding computer program and storage medium corresponding computer readable.

The invention relates to a method and to an arrangement for coding and arithmetic decoding  from binary states as well as to a computer program corresponding and to a storage medium readable by corresponding computer, which can be used especially in the digital data compression

The present invention describes a new Effective procedure for binary arithmetic coding. The need for binary arithmetic coding arises in the most various fields of application of digital data compression; to this respect are interesting by way of example especially applications in the fields of digital image compression. In numerous standards for image coding, such as JPEG, JPEG-2000, JPEG-LS and JBIG are have defined procedures for binary arithmetic coding. New standardization activities also recognize the future use of this type of coding techniques in the field of Video encoding (CABAC in H.264 / AVC) [1].

The advantages of arithmetic coding (AK) against Huffman coding [2] used so far with frequency in practice can be characterized essentially by three characteristics:

1. Through the use of arithmetic coding can be achieved through simple adaptation mechanisms a dynamic adaptation to existing source statistics (adaptivity).

2. Arithmetic coding allows the assignment of a non-integer number of bits for each symbol that is going to be coded and thus is suitable to achieve results of coding that represent an approximation of entropy as the theoretically given lower limit (entropy approximation) [3].

3. With the help of appropriate context models combinations with arithmetic coding can be used cross-symbol statistics for additional data reduction (redundancy between symbols) [4].

As a disadvantage of an application of the arithmetic coding is considered the great calculation effort in overall compared to Huffman coding.

The concept of arithmetic coding is based on basic work with respect to Shannon's theory of information [5]. The first conceptual construction methods were published in [6] for the first time by Elias. Rissanen [7] designed a first LIFO ( last-in-first-out ) variant of arithmetic coding and was subsequently modified by different authors to obtain FIFO ( first-in-first-out ) configurations [8] [9] [10 ].

All these works have in common that based on the principle of recursive subintervals division: of corresponding to the probabilities P ("0") and P ("1") given from two events {"0", "1"} of an alphabet  binary is recursively divided into subintervals an interval initially given, for example the interval [0, 1), according to the appearance of individual events. In this respect the size of the resulting subinterval as a product of the probabilities individual events appeared is proportional to the sequence probability of individual events. Market Stall that each event S_ {i} with the probability P (S_ {i}) provides a contribution of H (S_ {i}) = -log (P (S_ {i})) of the theoretical information content H (S_ {i}) of S_ {i} at the compound rate, a relationship between the number N_ {Bit} of bits for representation of the subinterval and the entropy of the sequence of events individual indicated by the right side of the following equation

       \ vskip1.000000 \ baselineskip
    

100

       \ vskip1.000000 \ baselineskip
    

However, the basic principle requires in first of all an unlimited precision (theoretically) in the representation of the resulting subinterval and also has the disadvantage that only after the coding of the last event bits can be output for subinterval representation resulting. For practical application purposes it was decisive for both develop mechanisms for incremental bit output with simultaneous representation with fixed precision numbers preset These were presented for the first time in the works [3] [7] [11].

The essential operations for binary arithmetic coding are outlined in Figure 1. In the implementation shown, the current sub-interval is represented by the two values L and R, designating L as the starting point and R the size (width) of the sub-interval and representing both quantities in each case with whole numbers of b bits. The coding of a bit \ in {0, 1} is done in this respect essentially in five sub-stages: in the first stage the value of the least probable symbol is determined by the probability estimation. For this symbol, also called LPS ( least probable symbol ), as opposed to MPS ( most probable symbol ), the probability estimate P_ {LPS} is used in the second stage to calculate the width R_ {LPS} of the corresponding subinterval. Depending on the value of the bit, bit, to be encoded, L and R are updated in the third stage. In the fourth stage the probability estimate is updated according to the value of the bit that has just been encoded and finally the code range R is subjected to a so-called renormalization in the last stage, that is, R is reset to scale for example so that the condition R \ in [2 b-2, 2 b-1) is met. In this respect a bit is output in each scaling operation. For more details, reference is made to [10].

The essential disadvantage of an implementation, as outlined above, it is now that the calculation of the interval width R_ {LPS} requires a multiplication for each symbol to be encoded. Habitually multiplication operations are complicated and expensive, especially when they are made in hardware. In several works of investigation were therefore analyzed procedures to replace this multiplication operation by an appropriate approximation [11] [12] [13] [14]. In this regard the procedures published with Regarding this topic, they can be roughly classified into Three categories

The first group of proposals regarding a binary arithmetic coding without multiplication is based on the approach to approximate the estimated P_ {LPS} probabilities of so that multiplication in the 2nd stage of figure 1 can replaced by one (or several) operation (operations) of displacement and sum [11] [14]. For this they approach in the case simpler the probabilities P_ {LPS} by means of values in the form 2 - q with q> 0 integer.

In the second category of procedures approximate it is proposed to approximate the range of R values by discrete values in the form (1/2 - r), being chosen r \ in {0} \ cup {2 ^ {- k} | k> 0, k integer} [15] [16].

The third category of procedures is It is finally characterized because all the arithmetic operations by access to tables. To this group of procedures belong on the one hand the Q encoder used in JPEG standard and related procedures, such as the QM encoder and MQ [12], and on the other hand the almost arithmetic encoder [13]. While the last mentioned procedure performs a  drastic limitation of the number b of bits used for the representation of R to reach tables sized in a way acceptable, in the Q encoder the renormalization of R is designed from so that R can be approximated at least approximately by 1. This avoids multiplication for the determination of R_ {LPS}. Additionally, the estimation of probability using a table in the form of a state machine finite For additional details in this regard reference is made to [12].

Document US5592162 describes a procedure to carry out an arithmetic coding, limiting the number of possible interval widths. By using a index that refers to these interval widths can achieve an arithmetic coding without multiplication with a reduced storage effort

A procedure for coding and arithmetic decoding of binary states is done so advantageous so that in a first stage a range of values that can be preset for the specification of the interval width R in K interval widths {Q_ {1}, ..., Representative Q_ {K}}, a range of values that can preset for the specification of the probabilities in N probability states {P_ {1}, ..., P_ {N}} representative and indicate allocation rules that at each width of interval R assign a Q_ {k} (1 \ leq k \ leq K) and to each probability a P_ {n} (1 \ leq n \ leq N), in a second stage the coding or decoding of binary states, performing  the calculation of the new interval width to be derived in the coding or decoding process using a width of interval Q_ {k} (1 ≤ k ≤ K) representative and a representative probability state P_ {n} (1 \ leq n \ leq N) by different arithmetic operations of multiplication and division, determining the interval width Q_ {k} representative using the basic interval that is taken as the basis of the width R and the probability state P_ {n} representative by estimating the probability on which the symbol is based to be encoded or decoded according to the allocation rules indicated.

Another preferred embodiment of the procedure is characterized because, starting from the interval that  is going to be currently evaluated with width R for the determination of the interval width Q_ {k} assigned, an index is determined q_index through a bit masking operation and displacement applied to the binary / internal representation of the R. computer

It is also advantageous if, starting from interval to be currently evaluated with width R for the determination of the interval width Q_ {k} assigned, is determine a q_index index by an operation of displacement applied to the binary / internal representation of the R computer and a downstream access to a Qtab table, the Qtab table containing the interval width indices that correspond to prequantified R values by operation of displacement.

Especially advantageous when the probability estimate on which the symbol that is going to be based is based Encode or decode is assigned with the help of an index p_state to a probability state P_ {n}.

It is also advantageous when determining the interval width R_ {LPS} corresponding to the LPS is realized by accessing an Rtab table, containing the Rtab table the values of the interval width R_ {LPS} corresponding to all K quantified values of R and N states of different probabilities as product values (Q_ {k} * P_ {n}). The calculation effort is reduced especially when the determination of the corresponding width of interval R_ {LPS} The LPS is done by accessing the Rtab table, using for the evaluation of the table the quantification index q_index and the index of the probability state p_state.

It is also planned that for the N states of different representative probability preset rules of transition, indicating the transition rules what new state is use starting from the currently encoded symbol or decoded for the next symbol to be encoded or decode In this respect it is advantageous when set a Next_State_LPS table that, with respect to index n of the probability state P_ {n} currently given, contains the index m of the new probability state P_ {m} when a symbol appears less likely (LPS), and / or a Next_State_MPS table is established that, with respect to the index n of the probability state P_ {n} currently given, it contains the index m of the new state of probability P_ {m} when a more probable symbol (MPS) appears.

An optimization of the procedure for table-based binary arithmetic coding and decoding it is achieved especially because the width values of R_ {LPS} interval corresponding to all K widths of interval and to all N different probability states are deposit as product values (Q_ {k} * P_ {n}) in a table Rtab

An additional optimization is achieved when the number K of quantification values and / or number N of states Representative are chosen based on the preset accuracy of coding and / or depending on memory space available.

       \ vskip1.000000 \ baselineskip
    

A special embodiment of the coding comprises the following stages:

1. Determination of the LPS

2. Quantification of R:

\ hskip0,3cm one

3. Determination of R_ {LPS} and R:

\ hskip0,4cm 2

4. Calculation of the new subinterval:

\ hskip0,3cm 3

5. Renormalization of L and R, deed of bits,

describing

q_index, the index of a quantization value extracted by reading Qtab,

p_state, the current state,

R_ {LPS}, the interval width that corresponds to the LPS and

ValMPS, the bit that corresponds to the MPS.

       \ vskip1.000000 \ baselineskip
    

Decoding in an embodiment Special includes the following stages:

1. Determination of the LPS

2. Quantification of R:

\ hskip0,3cm 4

3. Determination of R_ {LPS} and R:

\ hskip0,3cm 5

4. Bit determination, according to the position of the subinterval:

\ hskip0,3cm 6

5. Renormalization of R, extraction by One bit reading and V update,

describing

q_index, the index of a quantization value extracted by reading Qtab,

p_state, the current state,

R_ {LPS}, the interval width that corresponds to the LPS,

valMPS, the bit that corresponds to the MPS and

V, a value inside the subinterval current.

       \ vskip1.000000 \ baselineskip
    

In an embodiment of the procedure according to the invention it is provided that in the coding and / or decoding the calculation of the quantification index is performed q_index in the second sub-stage according to the calculation rule:

q_index = (R >> q) & Qmask

Qmask representing a bit mask chosen adequately based on K.

It is also advantageous when the initialization of the probability models is performed based on of a SliceQP quantification parameter and model parameters m and n preset, SliceQP describing the parameter of quantification preset at the beginning of a sector and m and n the model parameters.

       \ newpage
    

It is also advantageous when initialization of the probability models includes the following stages:

\ hskip0,3cm 7

describing valMPS the bit that corresponds to the MPS, SliceQP the quantification parameter preset at the beginning of a sector and m and n the parameters of model.

A provision for coding and arithmetic decoding of binary states comprises at least a processor that is configured so that it can perform a procedure for coding and decoding arithmetic, subdividing a range of values in a first stage which can be preset for the width specification of interval R in K interval widths {Q_ {1}, ..., Q_ {k}} representative, a range of values that can be preset to the specification of the probabilities in N states of probability {P_ {1}, ..., P_ {N}} representative and indicating allocation rules that at each interval width R assign a Q_ {k} (1 \ leq k \ leq K) and at each probability a P_ {n} (1 \ leq n \ leq N), in a second stage the coding is carried out or decoding of the binary states, performing the calculation of the new interval width to be derived in the process of encoding or decoding using an interval width Q_ {k} (1 \ leq k \ leq K) representative and a state of probability P_ {n} (1 \ leq n \ leq N) representative by different arithmetic operations of multiplication and division, determining the representative width Q_ {k} by the basic interval that is taken as the basis of the width R and the representative probability state P_ {n} through the probability estimate on which the symbol that is going to be based is based be encoded or decoded according to the allocation rules indicated.

A computer program for coding and arithmetic decoding of binary states enables a computer, once loaded into the computer memory, perform a procedure for coding and arithmetic decoding, subdividing in a first stage a range of values that can preset for the interval width specification R in K representative interval widths {Q_ {1}, ..., Q_ {K}}, a range of values that can be preset for the specification of the probabilities in N representative probability states {P_ {1}, ..., P_ {N}} and indicating allocation rules, which assign to each interval width R a Q_ {k} (1 \ leq k \ leq K) and at each probability a P_ {n} (1 \ leq n \ leq N), occurring in a second stage the coding or decoding of the binary states, performing the calculation of the new interval width to be derived in the process of encoding or decoding using an interval width Representative Q_ {k} (1 \ leq k \ leq K) and a state of representative probability P_ {n} (1 \ leq n \ leq N) by different arithmetic operations of multiplication and division, determining the representative width Q_ {k} by the basic interval that is taken as the basis of the width R and the representative probability state P_ {n} through the probability estimate on which the symbol to be based is based be encoded or decoded according to the assignment rules indicated.

For example, such computer programs (paying fees or for free, with free access or protected with password) can be provided with the possibility of downloading in a data or communication network. Computer programs like this provided can then be made useful by procedure, in which a computer program is downloaded from a network for data transmission such as from Internet to a data processing medium connected to the net.

To carry out a procedure for coding and arithmetic decoding of binary states are advantageously use a storage medium readable by computer, in which a program is stored, which enables a computer, once loaded into the computer memory, perform a procedure for coding and decoding arithmetic, subdividing a range of values in a first stage  which can be preset for the width specification of interval R in K interval widths {Q_ {1}, ..., Q_ {k}} representative, a range of values that can be preset to the specification of the probabilities in N states of probability {P_ {1}, ..., P_ {N}} representative and indicating assignment rules, which at each interval width R assign a Q_ {k} (1 \ leq k \ leq K) and at each probability a P_ {n} (1 \ leq n \ leq N), occurring in a second stage the encoding or decoding of binary states, performing the calculation of the new interval width that is going to derive in the coding or decoding process using an interval width Q_ {k} (1 \ leq k \ leq K) representative and a probability state P_ {n} (1 \ leq n ≤ N) representative by different arithmetic operations of multiplication and division, determining the width of representative Q_ {interval} by the basic interval that it is taken as the basis of the width R and the probability state P_ {n} representative by estimating probability in the that the symbol to be encoded or decoded is based on the allocation rules indicated.

       \ newpage
    

The new procedure is characterized by the combination of three characteristics. First, similar to the Q encoder, the probability estimation is produced by a finite state machine (FSM), generating the N representative states of the FSM offline. The corresponding transition rules are deposited in this respect in the form of tables.

The second feature of the invention is a prequantification of the interval width R up to a number of K previously defined quantification values. This allows, with an adequate sizing of K and N the elaboration of a table, which contains all combinations K x N of product values R x P_ {LPS} previously calculated for a determination without multiplication of R_ {LPS}.

For the use of the present invention in a environment, in which different context models are used, Among those are also those with a distribution of (almost) uniform probabilities, expected as an additional element (optional) a separate branch in the coding machine, in the that assuming a uniform distribution clearly reduces another time the determination of the magnitudes L and R as well as the renormalization regarding the calculation effort.

They show:

Figure 1 a representation of the essential operations for binary arithmetic coding;

Figure 2 a modified scheme for the arithmetic coding based on tables;

figure 3 the decoding principle table-based arithmetic;

Figure 4 the principle of coding or decoding for binary data with uniform distribution;

Figure 5 an alternative embodiment of the encoding or decoding for binary data with distribution uniform.

Figure 6 the initialization of the models of probability based on a SliceQP quantification parameter and the preset m and n model parameters

However, in the first place the theoretical basis in a somewhat more detailed way:

Probability estimation based on tables

As explained in more detail previously, the mode of action of arithmetic coding is based on a best possible estimate of the probability of appearance of the symbols to be encoded. To enable an adaptation to non-stationary source statistics should update this estimate throughout the process of coding. As a general rule they are usually used for this procedures, which operate with the help of frequency counters scaled to encoded events [17]. If C_ {LPS} and C_ {MPS} designate counters for the frequencies of occurrence of LPS and MPS, then through these counters can be carried out the estimate

8

and thus perform the operation outlined in figure 1 of the interval subdivision. Disadvantageous for practical purposes it is the necessary division in equation (1). However, it is often convenient and necessary to overcome a preset threshold value C_ {max} of the total counter C_ {Total} = C_ {MPS} + C_ {LPS} carry out a reset to scale of the counter states. (In this context it will be considered that in a representation of b bits of L and R the least probability, which can still be represented correctly, amounts to 2 - b + 2, so that to avoid being below this lower limit if necessary, a readjustment at scale of the states of the accountant). With an appropriate choice of C_ {max} they can be presented  in table form the reciprocal values of C_ {Total}, so that the necessary division in equation (1) can be replaced by an access to the table as well as a multiplication operation and displacement. However, to also avoid these operations arithmetic, in the present invention a method is used based entirely on tables for estimating probability.

For this purpose they are previously chosen in one phase of training representative probability states {P_ {k} | 0 \ leq k <N_ {max}}, depending on the choice of states by one side of the statistics of the data to be encoded and by other side of the secondary condition of the maximum number N_ {max} preset states. Additionally, rules of transition, which indicates which new state should be used starting of the currently coded symbol for the next symbol that goes to be codified. These transition rules are provided in the form of two tables: {Next_State_LPS_ {k} | 0 \ leq k <N_ {max}} and {Next_State_MPS_ {k} | 0 ≤ k <N_ {max}}, providing the tables for index n of the state of probability P_ {n} currently given the index m of the new state of probability P_ {m} when an LPS or MPS appears. In this point it should be noted that for the estimation of probability in the arithmetic encoder or decoder as proposed in this case, an explicit presentation in the form of a table is not required  the states of probability. Rather the states are addressed only by means of their corresponding indices implicitly, such as described in the following paragraph. Additionally at transition rules must be specified in what states of Probability should change the value of LPS and MPS. As a rule In general there will only be a state marked such that you can then Identify yourself using your p_state index.

Table-based interval subdivision

Figure 2 shows the modified scheme for arithmetic coding based on tables, as proposed in this case. After determining the LPS, the first R interval width given by Qtab mapping presented in table shape and proper scrolling operation (why bit) with a quantified Q value. Alternatively, the quantification can also be done in special cases without resort to a Qtab mapping presented as a table only with help of a combination of scroll operations and masking As a general rule, a relatively approximate quantification up to K = 2 ... 8 values representative. Nor in this case, similar to the case of the probability estimate, a determination occurs explicit of Q; rather, only a q_index index is transmitted to Q. This index is now used together with the p_state index to characterize the current probability state to determine the interval width R_ {LPS}. The entry is used for this corresponding from the Rtab table. In this the K are deposited \ Nd {max} corresponding product values R x P_ {LPS} to all K quantified values of R and N_ {max} states of different probabilities as integer values with a accuracy of in general b-2 bits. For practical implementations in this case there is a possibility of weigh between the need for memory for table size and arithmetic accuracy, which ultimately also determines coding efficiency Both target quantities are determined by the granularity of the representation of R and P_ {LPS}.

In the fourth stage of figure 2 it is shown how the probability status update is carried out p_state based on the newly encoded bit event. In this case it use the Next_State_LPS and Next_State_MPS transition tables already mentioned in the previous paragraph "Probability estimation based on tables. "These operations correspond to the process of update indicated in figure 1 in the 4th stage, although not specified in more detail.

Figure 3 shows the development scheme corresponding arithmetic decoding based on tables. To characterize the current subinterval is used in the decoder the interval width R and a V value. The latter is within the sub-interval and is successively tuned with Each bit read. As can be deduced from Figure 3, the operations for probability estimation and width determination of interval R are corrected correspondingly to those of encoder

Coding with uniform probability distribution

In applications where they must be encoded by example signed values, whose probability distribution is symmetrically arranged with respect to zero, it may be split for coding of the sign information as a general rule of a uniform distribution Since this information must be entered on the one hand in the arithmetic bit stream, although on the other hand not It is useful in the case of a probability of P \ approx 0.5 use the still relatively complex apparatus of estimating probability and subdivision of interval based on tables, it proposes for this special case to optionally use a separate encoder / decoder procedure that is Represents as follows.

In the encoder it can be determined for this special case the interval width of the new subinterval by a simple scroll operation correspondingly to a division by half the width of the starting interval R. According to the value of the bit to be encoded then the upper or lower half of R is chosen as new sub-interval (see figure 4). Renormalization and exit subsequent bit is done as in the previous case of the solution based on tables.

In the corresponding decoder they are reduced the operations necessary to determine the bit that is going to be decoded by the value of V with respect to the width of Current R interval by a simple comparison operation. If the decoded bit is set, V will be reduced by amount of R. As shown in Figure 4, the decoding by renormalization and updating of V with the next bit to be entered by reading.

An alternative embodiment of coding of events with uniform probability distribution is represented  in figure 5. In this implementation as an example, you do not Modify the current R interval width. Instead it doubles in the first encoder V by an operation of displacement. According to the value of the bit to be encoded, of similar to the previous example, then half is chosen upper or lower R as new subinterval (see figure 5). Renormalization and subsequent output of bits occurs as in the previous case of the solution based on tables with the difference that the duplication of R and L is not carried out and it carry out the corresponding comparison operations with duplicate threshold values.

       \ newpage
    

In the corresponding decoder of the alternative embodiment first a bit is extracted by reading and update V. The second stage is carried out of the same way as stage 1 in figure 4, that is, the bit that goes to be decoded is determined by the value of V with respect to the current R interval width by a comparison operation simple and in case the decoded bit is set, it reduce V by the amount of R (see figure 5).

Addressing and initialization of the models of probability

Each probability model, as used in the present invention, it is characterized with the help of two parameters: 1) the p_state index, which characterizes the state of probability of the LPS, and 2) the valMPS value of the MPS. Each of these quantities must be initialized at the beginning of the coding or decoding of a finished coding unit (in video coding applications approximately one sector).  The initialization values can be derived in this respect to from control information, such as the parameter of quantification (of a sector), as represented by way of example in figure 6.

Forward Controlled Initialization Process

Another possibility of adapting Starter distributions of the models is provided by the following method. To ensure a better adaptation of Model initializations can be provided in the encoder a choice of preset start values of the Models. These models can be grouped into distribution groups start and address with indexes, so that in the encoder adaptive choice of a group of start values occurs and it is transmitted to the decoder in the form of an index like lateral information. This method is called the process of controlled initialization forward.

Bibliography

[1] T. Wiegand , G. Sullivan , "Draft Text of Final Draft International Standard (FDIS) of Joint Video Specification (ITUT Rec. H.264 | ISO / IEC 14496-10 AVC)", JVT-G050, March 2003

[2] DA Huffman , "A Method for Construction of Minimum Redundancy code", Proc. IRE , Vol. 40, p. 1098-1101, 1952 .

[3] IH Witten , RM Neal , JG Cleary , "Arithmetic Coding for Data Compression", Communication of the ACM , Vol. 30, No. 6, p. 520-540, 1987 .

[4] GG Langdon , J. Rissanen , "A Simple General Binary Source code", IEEE Transactions on Information Theory , Vol. 28, p. 800-803, 1982 .

[5] CE Shannon , "A Mathematical Theory of Communication", Bell Syst. Tech. Journal , vol. 27, p. 379-423, 623-656, 1948 .

[6] P. Elias , "in information Theory and Coding", N. Abramson (Ed.), New York, MC-Crawl-Hill , 1963 .

[7] J. Rissanen , "Generalized Kraft Inequality and Arithmetic Coding", IBM J. Res. Develop ., Vol. 20, p. 198-203. 1976

[8] RC Pasco , "Source Coding and Algorithms for Fast Data Compression", Ph. D. Dissertation , Stanford University, USA, 1976 .

[9] GG Langdon , "An Introduction to Arithmetic Coding", IBM J. Res. Develop ., Vol. 28, p. 135-149, 1984 .

[10] A. Moffat , RM Neal , IH Witten , "Arithmetic Coding Revisited", Proc. IEEE Data Compression Conference, Snowbird (USA), p. 202-211, 1996 .

[11] J. Rissanen , KM Mohiuddin , "A Multiplication-Free Multialphabet Arithmetic Arithmetic Code", IEEE Trans. on Communication , Vol. 37, p. 93-98, 1989 .

[12] WB Pennebaker , JL Mitchell , GG Langdon , RB Arps , "An Overview of the Basic Principles of the QCoder Adaptive Binary Arithmetic Coder", IBM J. Res. Develop ., Vol. 32, p. 717-726, 1988 .

[13] PG Howard , JS Vitter , "Practical Implementations of Arithmetic Coding", in "Image and Text Compression", J. Storer (Ed.), Norwell (USA), Kluwer, 1992 .

[14] L. Huynh , A. Moffat , "A Probability-Ratio Approach to Approximate Binary Arithmetic Coding", IEEE Trans. on Information Theory , Vol. 43, p. 1658-1662, 1997 .

[15] D. Chevion , ED Karnin , E. Walach , "High-Efficiency, Multiplication Free Approximation of Arithmetic Coding", Proc. IEEE Data Compression Conference , Snowbird (USA), p. 43-52, 1991 .

[16] G. Feygin , PG Gulak , P. Chow , "Minimizing Excess Code Length and VLSI Complexity in the Multiplication Free Approximation of Arithmetic Coding", Inform. Proc. Manag ., Vol. 30, p. 805-816, 1994 .

[17] DL Duttweiler , Ch. Chamzas , "Probability Estimation in Arithmetic and Adaptive-Huffman Entropy Coders", IEEE Trans. on Image Processing , Vol. 4, p. 237-246, 1995 .

Claims (38)

1. Procedure for arithmetic coding of a symbol to be encoded with binary state based on a current R interval width and a probability that represents an estimate of probability for the symbol that is going to be coded, the probability being represented by an index of probability for addressing a probability state from a plurality of probability states representative, presenting the procedure as follows stage:

encode the symbol to be encoded, carrying out the following subcaps:

map the Current interval width with a quantification index from of a plurality of representative quantification indices; Y

perform the interval subdivision through access, using the index of quantification and probability index, to a division table of interval, to obtain a width value of subinterval,

presenting the mapping subcap the application from a bit masking operation and shifting to a binary / internal computer representation of the width of current interval, specifically according to the following calculation rule q_index = (R >> q) & Qmask, representing Qmask a bit mask appropriately chosen based on the number of Representative quantification indices, R the interval width  current and q a number of bits. 2. Method according to claim 1, in which the coding also takes place by the following stage:

update it current interval width using the width value of interval, to obtain a new interval width updated.

3. Method according to claim 1 or 2, in which the subinterval width value indicates a width of a sub-interval for a symbol to be encoded with a state less likely from a current interval with the width of Current interval 4. Procedure according to one of the claims 1 to 3, wherein updating the width of current interval is also performed depending on the binary state of the symbol to be encoded. 5. Procedure according to one of the previous claims, which further presents the following stage:

adapt the probability estimation, presenting the adaptation of the query probability estimate, with the index of probability, in an LPS transition rule table (Next_State_LPS), to get a new probability index, if the symbol to be encoded has a less probable state, and the query, with the probability index, in a rule table MPS transition (Next_State_MPS), to obtain a new index of probability, if the symbol to be coded presents a state most likely.

6. Method according to claim 5, which it also presents the change of a value that indicates the most likely from a state originally indicated to the binary state of symbol to be encoded, if the probability index is similar to a predetermined probability index and the symbol that going to be coded presents a binary state different from the state originally indicated. 7. Procedure according to one of the claims 1 to 6, wherein the sub-stage of the update of The current interval width has the following stages:

match the new interval width with the difference in the interval width current minus the subinterval width value; Y

then, in case the symbol to be encoded has a state less likely, match the new interval width with the value of subinterval width.

8. Procedure according to one of the previous claims, wherein a current interval is represented by the current interval width and a point of current item, and the coding is also done by following sub-stage:

add the point current departure and a current interval width difference and subinterval width value, to obtain a new point of updated item, if the symbol to be coded presents a less likely state

         \ newpage
      

9. Decoding procedure arithmetic of a binary state coded symbol based on a current R interval width and a probability that represents an estimate of probability for the coded symbol, being represented the probability by a probability index of a state of probability from a plurality of states of representative probability, presenting the procedure the next stage:

decode the coded symbol, carrying out the following subcaps:

map the Current interval width with a quantification index from of a plurality of representative quantification indices; Y

perform the interval division by access, using the index of quantification and probability index, to a division table of interval, to obtain a width value of subinterval,

presenting the mapping subcap the application from a bit masking operation and shifting to a binary / internal computer representation of the width of current interval, specifically according to the following calculation rule q_index = (R >> q) & Qmask, representing Qmask a bit mask appropriately chosen based on the number of Representative quantification indices, R the interval width  current and q a number of bits. 10. Method according to claim 9, in which decoding also takes place through the following stage:

update it current interval width using the width value of subinterval, to obtain a new interval width updated.

11. Method according to claim 9 or 10, in which the subinterval width value indicates a width  of a sub-interval for a coded symbol with a less state probable from a current interval with the interval width current. 12. The method according to one of claims 9 to 11, wherein the update of the current interval width is further performed based on a value located within a new sub-interval, which is characterized by the current sub-interval width and the value located within a new subinterval. 13. Method according to claim 12, in which decoding is also performed by the following subcap:

match the binary state of the symbol coded with one of a non-state more likely and one more likely depending on whether the value located within the new subinterval is greater or less than a difference of the current interval width and the width value of subinterval.

14. Procedure according to one of the claims 12 or 13, wherein the coding is performed also by updating the value located within the new subinterval with a next bit to be entered by reading 15. Procedure according to one of the claims 12 to 14, further presenting the following stage: update the probability estimate, presenting the update of the probability estimate the query, with the probability index, in a rule table of LPS transition (Next_State_LPS), to get a new index of probability, if the value within the new sub-interval is greater than a difference in the current interval width and the subinterval width value, and the query, with the index of probability, in an MPS transition rule table (Next_State_MPS), to get a new probability index, if the value within the new subinterval is less than one difference of current interval width and width value of subinterval. 16. Procedure according to one of the claims 12 to 15, further presenting the change of a value which indicates the most probable state of the encoded symbol of a originally indicated state to a different binary state, if the probability index is similar to a probability index default and the value within the new sub-interval is greater than a difference in the current interval width and the subinterval width value. 17. Procedure according to one of the previous claims, wherein the interval width current is represented with a precision of b bits and the value of subinterval width obtained from the division table of interval with an accuracy of b-2 bits. 18. Procedure according to one of the previous claims, wherein the mapping sub-stage has the application of a move operation to a binary / internal computer representation of the width of current interval, to obtain a quantified value for the current interval width, and presents a downstream access to a table (Qtab), to obtain the quantification index.

         \ newpage
      

19. Procedure according to one of the previous claims, wherein in the division table of interval values are deposited for the interval width current corresponding to all quantification rates possible and to all probability indices as values of product between quantification index, and in a Rtab table. 20. Procedure according to one of the previous claims, which further presents the following stage:

update it probability estimation, performing the update of the probability estimation by transition rules, indicating the transition rules, what new probability state of the plurality of probability states is used, starting from symbol to be coded or coded, for a following symbol to be encoded or encoded.

21. Procedure according to one of the previous claims, which further presents the following stage:

update it probability estimation, presenting the update of the query probability estimate, with the index of probability, in a transition rule table (Next_State_LPS), to get a new probability index.

22. Procedure according to one of the previous claims, wherein the number of possible indexes of quantification and / or the number of probability states are choose based on the preset coding accuracy and / or depending on the available memory space. 23. Procedure according to one of the previous claims, which further presents the following subcap:

renormalize the new updated starting point and new interval width updated.

24. Procedure according to one of the previous claims, in which in case there is a uniform probability distribution

-

in the coding the following calculation rule is performed:

\ hskip1cm 9

or the following calculation rule:

\ hskip1cm 10

and as last alternatively a renormalization with threshold values of duplicate decision and no duplicate of L and R,

-

in the decoding according to claim 13 the following is performed slide rule:

\ hskip0,5cm eleven

or the next slide rule:

3.

extract by reading a bit and update V

         \ newpage
      

Four.

determine the bit, depending on the position of the subinterval:

\ hskip0,5cm 12 25. Procedure according to one of the previous claims, wherein the initialization of the Probability models are performed based on a parameter of SliceQP quantification and preset model parameters m and n, describing SliceQP the quantification parameter preset at the beginning of a sector and m and n the parameters of model. 26. Procedure according to one of the previous claims, wherein the initialization of the Probability models include the following stages: \ hskip0,3cm 13 describing valMPS the bit corresponding to the MPS, SliceQP the quantification parameter preset at the beginning of a sector and m and n the parameters of model. 27. A method according to one of the preceding claims, wherein the estimation of probability of the states is carried out by means of a finite state machine (FSM). 28. Procedure according to one of the previous claims, wherein the generation of the states Probability is done offline. 29. Procedure according to one of the previous claims, wherein the choice of states It depends on the statistics of the data to be encoded and / or of the number of states. 30. Arithmetic coding provision of a symbol to be encoded with binary state based on a current R interval width and a probability that represents an estimate of probability for the symbol that is going to be coded, the probability being represented by an index of probability for addressing a probability state from a plurality of probability states representative, presenting the device the following characteristic:

a means to coding of the symbol to be encoded, which presents the following means:

a means to him mapping the current interval width with an index of quantification from a plurality of indices of representative quantification; Y

a means to perform interval subdivision through access, using the quantification index and the probability index, at a interval division table, to obtain a width value of sub-interval, the mapping medium being configured to apply a bit masking operation and shifting to a binary / internal computer representation of the width of current interval, specifically according to the following calculation rule q_index = (R >> q) & Qmask, representing Qmask a bit mask appropriately chosen based on the number of Representative quantification indices, R the interval width current and q a number of bits.

31. Provision for decoding arithmetic of a binary state coded symbol based on a current R interval width and a probability that represents an estimate of probability for the coded symbol, being represented the probability by a probability index for the addressing a probability state from a plurality of representative probability states, presenting The device the following feature:

a means to decoding of the coded symbol, which has the following media:

a means to him mapping the current interval width with an index of quantification from a plurality of indices of Representative quantification: and

a means to perform interval subdivision through access, using the quantification index and the probability index, at a interval division table, to obtain a width value of sub-interval, the mapping medium being configured to apply a bit masking operation and shifting to a binary / internal computer representation of the width of current interval, specifically according to the following calculation rule q_index = (R >> q) & Qmask, representing Qmask a bit mask appropriately chosen based on the number of Representative quantification indices, R the interval width  current and q a number of bits.

32. Computer program, which allows a computer, once loaded into the computer memory, carry perform a procedure for the arithmetic coding of a symbol which is to be coded with binary state based on a width of current R interval and a probability representing an estimate of probability for the symbol to be encoded, being represented the probability by a probability index for the addressing a probability state from a plurality of representative probability states, presenting The procedure the next stage:

encode the symbol to be encoded, carrying out the following subcaps:

map the Current interval width with a quantification index from of a plurality of representative quantification indices; Y

perform the interval subdivision through access, using the index of quantification and probability index, to a division table of interval, to obtain a width value of subinterval,

presenting the mapping subcap the application of a masking operation bit and offset to a binary / internal representation of the computer of the current interval width, specifically according to the following calculation rule q_index = (R >> q) & Qmask, Qmask representing a bit mask appropriately chosen based on the number of representative quantification indices, R the current interval width and q a number of bits.

33. Computer program, which allows a computer, once loaded into the computer memory, perform a procedure for arithmetic decoding of a symbol encoded with binary state based on an interval width Current R and a probability that represents an estimate of probability for the coded symbol, the probability by a probability index of a state of probability from a plurality of probability states representative, presenting the procedure as follows stage:

decode the coded symbol, carrying out the following subcaps:

map the Current interval width with a quantification index from of a plurality of representative quantification indices; Y

perform the interval division by access, using the index of quantification and probability index, to a division table interval, to obtain a subinterval width value, presenting the mapping sub-stage the application of an operation of bit masking and moving to a representation binary / internal computer of the current interval width, specifically according to the following calculation rule q_index = (R >> q) & Qmask, representing Qmask a bit mask appropriately chosen based on the number of indices of Representative quantification, R the current interval width and q A number of bits

34. Storage medium readable by computer, in which a program is stored, which allows a computer, once loaded into the computer memory, perform a procedure for the arithmetic coding of a symbol that goes to be encoded with binary state based on a width of current R interval and a probability representing an estimate of probability for the symbol to be encoded, being represented the probability by a probability index for the addressing a probability state from a plurality of representative probability states, presenting The procedure the next stage:

encode the symbol to be encoded, carrying out the following subcaps:

map the Current interval width with a quantification index from of a plurality of representative quantification indices; Y

perform the interval subdivision through access, using the index of quantification and probability index, to a division table interval, to obtain a subinterval width value, presenting the mapping sub-stage the application of an operation of bit masking and moving to a representation binary / internal computer of the current interval width, specifically according to the following calculation rule q_index = (R >> q) & Qmask, representing Qmask a bit mask appropriately chosen based on the number of indices of Representative quantification, R the current interval width and q A number of bits

35. Storage media readable by computer, in which a program is stored, which allows a computer, once loaded into the computer memory, perform a procedure for arithmetic decoding of a symbol encoded with binary state based on an interval width Current R and a probability that represents an estimate of probability for the coded symbol, the probability by a probability index of a state of probability from a plurality of probability states representative, presenting the procedure as follows stage:

decode the coded symbol, carrying out the following subcaps:

map the Current interval width with a quantification index from of a plurality of representative quantification indices; Y

perform the interval division by access, using the index of quantification and probability index, to a division table interval, to obtain a subinterval width value, presenting the mapping sub-stage the application of an operation of bit masking and moving to a representation binary / internal computer of the current interval width, specifically according to the following calculation rule q_index = (R >> q) & Qmask, representing Qmask a bit mask appropriately chosen based on the number of indices of Representative quantification, R the current interval width and q A number of bits

36. Storage medium readable by computer, in which a program is stored, which allows a computer, once loaded into the computer memory, perform a method according to one of claims 32 and 33.