BINARY ARITHMETIC CODING SCHEME

• US 20140333458A1
• Filed: 07/30/2014
• Published: 11/13/2014
• Est. Priority Date: 01/30/2012
• Status: Active Grant

• Current Assignee: Fraunhofer Gesellschaft Zur Foerderung Der Angewandten Forsching E.V.
• Original Assignee: Fraunhofer Gesellschaft Zur Foerderung Der Angewandten Forsching E.V.
• Inventors: MARPE, Detlev, KIRCHHOFFER, Heiner, SIEKMANN, Mischa, BARTNIK, Christian
• Granted Patent: US 9,312,881 B2
• Time in Patent Office: Days
• US Class Current: 341/51
• CPC Class Codes: H03M 7/4012 Binary arithmetic codes
• CPC Class Codes: H03M 7/4018 Context adapative binary arithmetic codes [CABAC]
• CPC Class Codes: H03M 7/4081 Static prefix coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

A binary arithmetic coding scheme is extended by a functionality to encode and decode non-negative integer values with particular low computational complexity.

Claims

1. A binary arithmetic decoder for decoding a non-negative integer value from a bitstream, the binary arithmetic decoder 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 decoder being defined by a current interval defined by an interval width R, and a value V from the interior of the current interval, the binary arithmetic decoder being configured to decode the number of MPS'"'"'s of the non-negative integer value iteratively using an iteration comprising

determining a maximum number c_max of MPS that can be decoded until an LPS occurs with using 2^s as a partial interval width R_LPS corresponding to an LPS, by measuring a difference of R and V with 2^s;

determining a maximum number c_m, of MPS that can be decoded until a renormalization occurs with using 2^s as the partial interval width R_LPS corresponding to the LPS, by measuring a difference of R and R_min with 2^s, with R_min denoting a minimum allowed value for R and being a power of 2;

if c_max is greater zero and c_max is greater than c_mps,

reducing R by c_mps times 2^s, thereby decoding c_mps 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 bit from the bitstream, and increasing V using the renormalization factor and subsequently adding the value of bit;

if c_max is greater zero and c_max is smaller than c_mps,

reducing R by c_max times 2^s, thereby decoding c_mps of the MPS'"'"'s of c,

wherein the binary arithmetic decoder 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 decoder is further configured to decode the LPS of the non-negative integer value by

determining a renormalization number based on a difference of log 2(R_min) and s;

updating V using a difference of V and a partial interval width R_MPS 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 R_min or a predetermined function of R_min.

2. The binary arithmetic decoder according to claim 1, wherein the binary arithmetic decoder is configured such that the iteration comprises

if c_max is greater zero and c_max is equal to c_mps,

reducing R by c_max times 2^s, thereby decoding c_mps of the MPS'"'"'s of c.

3. The binary arithmetic decoder according to claim 1, wherein the binary arithmetic decoder is configured to, in iteratively decoding the number of MPS'"'"'s of the non-negative integer value, cycle the iteration until all c MPS'"'"'s of the non-negative integer value have been decoded.

4. The binary arithmetic decoder according to claim 1, further configured to initialize c with zero before the iterative decoding and increase c by c_mps if c_max is greater zero and c_max is greater than c_mps and increase c by c_max if c_max is greater zero and c_max is smaller than c_mps in the iterative decoding.

5. The binary arithmetic decoder according to claim 1, wherein the binary arithmetic decoder is configured such that the binary symbol sequence comprises the number of MPS'"'"'s equal to the non-negative integer value, followed by the LPS if c is smaller than a maximum value c_m, and not followed by an LPS if c is equal to the maximum value c_m, wherein the binary arithmetic decoder is further configured to, in determining the maximum number c_max, limit c_max to get not greater than c_m−

c

6. The binary arithmetic decoder according to claim 1, wherein the binary arithmetic decoder is configured to determine the renormalization number to be 1+log₂(R_min)−

s and to set R to be 2*(R_min−

1).

7. The binary arithmetic decoder according claim 1, wherein the binary arithmetic decoder is configured to determine the renormalization number to be log₂(R_min)−

s and to set R to be R_min.

8. The binary arithmetic decoder according to claim 1, wherein the binary arithmetic decoder is configured to, in updating V using a difference of V and a partial interval width R_MPS corresponding to an MPS, multiplied with 2 to the power of the renormalization number, perform a left shift of V−

R_MPS by the renormalization number of bit positions.

9. The binary arithmetic decoder according to claim 1, wherein the binary arithmetic decoder is configured to change s between consecutive iterations.

10. The binary arithmetic decoder according to claim 1, wherein the binary arithmetic decoder is configured to reduce s in a predetermined manner at an u_th performance of the renormalization.

11. The binary arithmetic decoder according to claim 1, wherein the binary arithmetic decoder is configured to reduce s in a predetermined manner at an u_th performance of the renormalization, provided s has not yet reached a minimum value s_min.

12. The binary arithmetic decoder according to claim 10, wherein the binary arithmetic decoder is configured to initially increase u_th by 1 in case of R being smaller than a threshold Rthr.

13. The binary arithmetic decoder according to claim 1, wherein s is between 3 and 7, both inclusively, and R_min is between 128 and 512, both inclusively.

14. 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 c_mps of MPS that can be encoded until a renormalization occurs with using 2^s as a partial interval width R_LPS corresponding to an LPS, by measuring a difference of R and R_min with 2^s, with R_min denoting a minimum allowed value for R and being a power of 2;

if c is greater than c_mps,

reducing R by c_mps times 2^s, thereby coding c_mps 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 c_mps,

reducing R by c times 2^s, 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 log₂(R_min) and s;

updating L using a sum of L and a partial interval width R_MPS 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 R_min or a predetermined function of R_min.

15. The binary arithmetic encoder according to claim 14, wherein the binary arithmetic encoder is configured such that the iteration comprises

if c is equal to c_mps,

reducing R by c_mps times 2^s, thereby coding c_mps of the MPS'"'"'s of c;

and

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.

16. The binary arithmetic encoder according to claim 14, wherein the binary arithmetic encoder is configured to, in iteratively encoding the number of MPS'"'"'s of the non-negative integer value, cycle the iteration until all c MPS'"'"'s of the non-negative integer value have been encoded.

17. The binary arithmetic encoder according to claim 14, further configured to initialize c to equal the non-negative integer value before the iterative encoding and decrease c by c_mps if c is greater than c_mps.

18. The binary arithmetic encoder according to claim 14, wherein the binary arithmetic encoder is configured such that the binary symbol sequence comprises the number of MPS'"'"'s equal to the non-negative integer value, followed by the LPS if c is smaller than a maximum value c_m, and not followed by an LPS if c is equal to the maximum value c_m.

19. The binary arithmetic encoder according to claim 14, wherein the binary arithmetic encoder is configured to determine the renormalization number to be 1+log₂(R_min)−

s and to set R to be 2*(R_min−

1).

20. The binary arithmetic encoder according to claim 14, wherein the binary arithmetic encoder is configured to determine the renormalization number to be log₂(R_min)−

s and to set R to be R_min.

21. The binary arithmetic encoder according to claim 14, wherein the binary arithmetic encoder is configured to, in updating L using a sum of L and a partial interval width R_MPS corresponding to an MPS, multiplied with 2 to the power of the renormalization number, perform a left shift of L+R_MPS by the renormalization number of bit positions.

22. The binary arithmetic encoder according to claim 14, wherein the binary arithmetic encoder is configured to change s between consecutive iterations.

23. The binary arithmetic encoder according to claim 14, wherein the binary arithmetic encoder is configured to reduce s in a predetermined manner at an u_th performance of the renormalization.

24. The binary arithmetic encoder according to claim 14, wherein the binary arithmetic encoder is configured to reduce s in a predetermined manner at an u_th performance of the renormalization, provided s has not yet reached a minimum value s_min.

25. The binary arithmetic encoder according to claim 23, wherein the binary arithmetic encoder is configured to initially increase u_th by 1 in case of R being smaller than a threshold Rthr.

26. The binary arithmetic encoder according to claim 14, wherein s is between 3 and 7, both inclusively, and R_min is between 128 and 512, both inclusively.

27. The binary arithmetic encoder according to claim 14, wherein the the binary arithmetic encoder is configured to binarize the non-negative integer value using the binary unary binarization.

28. 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 c_max of MPS that can be decoded until an LPS occurs with using 2^s as a partial interval width R_LPS corresponding to an LPS, by measuring a difference of R and V with 2^s;

determining a maximum number c_mps of MPS that can be decoded until a renormalization occurs with using 2^s as the partial interval width R_LPS corresponding to the LPS, by measuring a difference of R and R_min with 2^s, with R_min denoting a minimum allowed value for R and being a power of 2;

if c_max is greater zero and c_max is greater than c_mps,

reducing R by c_mps times 2^s, thereby decoding c_mps 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 bit from the bitstream, and increasing V using the renormalization factor and subsequently adding the value of bit;

if c_max is greater zero and c_max is smaller than c_mps,

reducing R by c_max times 2^s, thereby decoding c_mps 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(R_min) and s;

updating V using a difference of V and a partial interval width R_MPS 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 R_min or a predetermined function of R_min.

30. A computer program comprising a program code for performing, when running on a computer, a method according to claim 28.

32. A computer readable medium having stored thereon a computer program comprising a program code for performing, when running on a computer, a method according to claim 28.

29. 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 c_mps of MPS that can be encoded until a renormalization occurs with using 2^s as a partial interval width R_LPS corresponding to an LPS, by measuring a difference of R and R_min with 2^s, with R_min denoting a minimum allowed value for R and being a power of 2;

if c is greater than c_mps,

reducing R by c_mps times 2^s, thereby coding c_mps 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 c_mps,

reducing R by c times 2^s, 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 log₂(R_min) and s;

updating L using a sum of L and a partial interval width R_MPS 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 R_min or a predetermined function of R_min.

31. A computer program comprising a program code for performing, when running on a computer, a method according to claim 29.

33. A computer readable medium having stored thereon a computer program comprising a program code for performing, when running on a computer, a method according to claim 29.