Binary arithmetic coding scheme

A binary arithmetic encoder for encoding a non-negative integer value into a bitstream, the binary arithmetic encoder being configured to use a binary unary representation of the non-negative integer value, which maps the non-negative integer value c onto a binary symbol sequence comprising a number of MPS's equal to the non-negative integer value, a current state of the binary arithmetic encoder being defined by a current interval defined by an interval width R and an interval offset L, the binary arithmetic encoder being configured to encode the number of MPS's of the non-negative integer value iteratively using an iteration comprising

• determining a maximum number cmps of MPS that can be encoded until a renormalization occurs with using 2s as a partial interval width RLPS corresponding to an LPS, by measuring a difference of R and Rmin with 2s, with Rmin denoting a minimum allowed value for R and being a power of 2;
• if c is greater than cmps,
• reducing R by cmps times 2s, thereby coding cmps of the MPS's of c;
• performing a renormalization by comprising increasing R and L using a renormalization factor being a predetermined power of 2, respectively, and writing a bit to the bitstream;
• if c is smaller than cmps,
• reducing R by c times 2s, thereby coding all c MPS's of c,
• wherein the binary arithmetic encoder is configured such that the binary symbol sequence comprises a number of MPS's equal to the non-negative integer value, followed by an LPS, wherein the binary arithmetic encoder is further configured to encode the LPS of the non-negative integer value by
• determining a renormalization number based on a difference of log2(Rmin) and s;
• updating L using a sum of L and a partial interval width RMPS corresponding to an MPS, multiplied with 2 to the power of the renormalization number;
• writing the renormalization number of bits to the bitstream;
• setting R to be Rmin or a predetermined function of Rmin.

A method for binary arithmetic decoding a non-negative integer value from a bitstream, the method using a binary unary representation of the non-negative integer value, which maps the non-negative integer value c onto a binary symbol sequence comprising a number of MPS's equal to the non-negative integer value, a current state of the method being defined by a current interval defined by an interval width R, and a value V from the interior of the current interval, the method comprising decoding the number of MPS's of the non-negative integer value iteratively using an iteration comprising

• determining a maximum number cmax of MPS that can be decoded until an LPS occurs with using 2s as a partial interval width RLPS corresponding to an LPS, by measuring a difference of R and V with 2s;
• determining a maximum number cmps of MPS that can be decoded until a renormalization occurs with using 2s as the partial interval width RLPS corresponding to the LPS, by measuring a difference of R and Rmin with 2s, with Rmin denoting a minimum allowed value for R and being a power of 2;
• if cmax is greater zero and cmax is greater than cmps,
• reducing R by cmps times 2s, thereby decoding cmps of the MPS's of c;
• performing a renormalization by comprising increasing R using a renormalization factor being a predetermined power of 2, reading a bit from the bitstream, and increasing V using the renormalization factor and subsequently adding the value of bit;
• if cmax is greater zero and cmax is smaller than cmps,
• reducing R by cmax times 2s, thereby decoding cmax of the MPS's of c,
• wherein the binary symbol sequence comprises a number of MPS's equal to the non-negative integer value, followed by an LPS, wherein the method further comprises decoding the LPS of the non-negative integer value by
• determining a renormalization number based on a difference of log 2(Rmin) and s;
• updating V using a difference of V and a partial interval width RMPS corresponding to an MPS, multiplied with 2 to the power of the renormalization number;
• reading the renormalization number of bits from the bitstream and adding same to V;
• setting R to be Rmin or a predetermined function of Rmin.

A method for binary arithmetic encoding a non-negative integer value into a bitstream, the method using a binary unary representation of the non-negative integer value, which maps the non-negative integer value c onto a binary symbol sequence comprising a number of MPS's equal to the non-negative integer value, a current state of the method being defined by a current interval defined by an interval width R and an interval offset L, the method comprising encoding the number of MPS's of the non-negative integer value iteratively using an iteration comprising

• determining a maximum number cmps of MPS that can be encoded until a renormalization occurs with using 2s as a partial interval width RLPS corresponding to an LPS, by measuring a difference of R and Rmin with 2s, with Rmin denoting a minimum allowed value for R and being a power of 2;
• if c is greater than cmps,
• reducing R by cmps times 2s, thereby coding cmps of the MPS's of c;
• performing a renormalization by comprising increasing R and L using a renormalization factor being a predetermined power of 2, respectively, and writing a bit to the bitstream;
• if c is smaller than cmps,
• reducing R by c times 2s, thereby coding all c MPS's of c,
• wherein the binary symbol sequence comprises a number of MPS's equal to the non-negative integer value, followed by an LPS, wherein the method further comprises encoding the LPS of the non-negative integer value by
• determining a renormalization number based on a difference of log2(Rmin) and s;
• updating L using a sum of L and a partial interval width RMPS corresponding to an MPS, multiplied with 2 to the power of the renormalization number;
• writing the renormalization number of bits to the bitstream;
• setting R to be Rmin or a predetermined function of Rmin.