Lossless adaptive encoding and decoding of integer data

1. A method for encoding digital data, comprising:

selecting between a first encoding mode and a second encoding mode to encode the digital data into an encoded bitstream, the first mode using a first type of entropy encoder other than a Run-Length encoder and the second mode using the first type of entropy encoder combined with the Run-Length encoder; and

adapting the encoders of the first mode and the second mode based on the encoded bitstream using a backward-adaptive technique.

2. The method as set forth in claim 1 , wherein the first type of entropy encoder is a Golomb/Rice encoder that combines with the Run-Length encoder in the second mode to generate a Run-Length Golomb/Rice (RLGR) encoder.

3. The method as set forth in claim 2 , further comprising using an encoding mode parameter to select between the first and second modes.

4. The method as set forth in claim 3 , further comprising encoding in the first mode if the encoding mode parameter equals zero.

5. The method as set forth in claim 4 , further comprising updating the encoding mode parameter, comprising:

adding a first integer constant to the encoding mode parameter if the absolute value of the digital data is approximately zero; and

subtracting a second integer constant from the encoding mode parameter if the absolute value of the digital data is greater than zero.

6. The method as set forth in claim 2 , further comprising updating a Golomb/Rice parameter, comprising:

defining an adaptation value in terms of the Golomb/Rice parameter;

decreasing the Golomb/Rice parameter by a third integer constant if the adaptation value equals zero;

leaving the Golomb/Rice parameter unchanged if the adaptation value equals one; and

increasing the Golomb/Rice parameter by the adaptation value if the adaptation value is greater than one.

7. The method as set forth in claim 3 , further comprising encoding in the second mode if the encoding mode parameter is greater than zero.

8. The method as set forth in claim 7 , further comprising:

defining adjacent zero values in the digital data as a run;

defining a complete run as a run having a number of zero values equal to 2 raised to the power of the encoding mode parameter; and

encoding the complete run using the Run-Length encoder.

9. The method as set forth in claim 8 , further comprising representing the complete run as a codeword equal to zero.

10. The method as set forth in claim 8 , further comprising:

defining an incomplete run as a run having a number of zero values equal to less than two raised to the power of the encoding mode parameter and followed by a value not equal to zero;

encoding the incomplete run by:

placing a value of one at the beginning of a codeword representing the incomplete run;

representing a length of the incomplete run in the codeword; and

representing a value of the digital data following the incomplete run using the Golomb/Rice encoder.

11. The method as set forth in claim 8 , further comprising updating the encoding mode parameter by adding a fourth integer constant to the encoding mode parameter.

12. The method as set forth in claim 8 , further comprising updating a Golomb/Rice parameter, comprising:

defining an adaptation value in terms of the Golomb/Rice parameter;

decreasing the Golomb/Rice parameter by a fifth integer constant if the adaptation value equals zero;

leaving the Golomb/Rice parameter unchanged if the adaptation value equals one; and

increasing the Golomb/Rice parameter by the adaptation value if the adaptation value is greater than one.

13. The method as set forth in claim 10 , further comprising updating the encoding mode parameter by subtracting a fifth integer constant from the encoding mode parameter.

14. The method as set forth in claim 10 , further comprising updating a Golomb/Rice parameter, comprising:

defining an adaptation value in terms of the Golomb/Rice parameter;

decreasing the Golomb/Rice parameter by a fifth integer constant if the adaptation value equals zero;

leaving the Golomb/Rice parameter unchanged if the adaptation value equals one; and

increasing the Golomb/Rice parameter by the adaptation value if the adaptation value is greater than one.

15. The method as set forth in claim 2 , further comprising adapting the encoders of the first mode and the second mode after every codeword that is generated.

16. A computer-readable medium having computer-executable instructions for performing the method recited in claim 1 .

17. A computer-implemented process for encoding digital integer data, comprising:

switching between a first encoder mode performing Golomb/Rice (G/R) encoding only and a second encoder mode performing Run-Length encoding and G/R encoding;

defining an encoding mode parameter s to control which of the first and second encoder modes is used; and

updating the encoding mode parameter s after each codeword is generated using a backward-adaptive technique.

18. The computer-implemented process of claim 17 , further comprising:

defining a Golomb/Rice (G/R) parameter k to control the G/R encoding of both the first and the second encoding modes; and

updating the G/R parameter k after each codeword is generated using a backward-adaptive technique.

19. The computer-implemented process of claim 18 , further comprising switching to the first encoding mode if s=0.

20. The computer-implemented process of claim 19 , further comprising encoding an input value x of the digital integer data using an adaptive G/R encoder having the G/R parameter k.

21. The computer-implemented process of claim 20 , further comprising:

determining whether |x|=0;

if so, then increasing s by a first integer constant, A1; and

if not, then decreasing s by a second integer constant, B1.

22. The computer-implemented process of claim 21 , further comprising:

defining an adaptation value, p;

decreasing k by a fifth integer constant if p=0;

leaving k unchanged if p=1; and

increasing k by the adaptation value if p>0.

23. The computer-implemented process of claim 18 , further comprising switching to the second encoding mode if s>0.

24. The computer-implemented process of claim 23 , further comprising:

defining a run ras a string of adjacent zeros in the digital integer data;

designating a run r as a complete run if r=2 s ; and

designating a run r as an incomplete run if r<2 s .

25. The computer-implemented process of claim 24 , further comprising using Run-Length encoding to encode a complete run as a codeword=0.

26. The computer-implemented process of claim 24 , further comprising using Run-Length encoding to encode an incomplete run as a codeword=1.

27. The computer-implemented process of claim 26 , further comprising appending to the codeword a binary value having s number of bits to represent a length of the incomplete run r.

28. The computer-implemented process of claim 27 , further comprising:

using adaptive G/R encoding having the G/R parameter k to encode a value immediately following the incomplete run; and

appending the encoded value to the codeword.

29. The computer-implemented process of claim 24 , further comprising:

increasing s by a third integer constant, A2, if the run r is a complete run; and

decreasing s by a fourth integer constant, B2, if the run r is an incomplete run.

30. The computer-implemented process of claim 23 , further comprising:

defining an adaptation value, p;

decreasing k by a fifth integer constant if p=0;

leaving k unchanged if p=1; and

increasing k by the adaptation value if p>0.

31. The computer-implemented process of claim 18 , further comprising:

defining a scaling parameter, L;

defining a scaled encoding mode parameter as S=s multiplied by L;

defining a scaled G/R parameter as K=k multiplied by L; and

updating the scaled encoding mode parameter S and the scaled G/R parameter K instead of s and k after each codeword is generated using the backward-adaptive technique and adaptation rules.

32. A computer-readable medium having computer-executable instructions for performing the computer-implemented process recited in claim 17 .

33. A method for encoding digital integer data having integer values, comprising:

receiving an input string x of the digital integer data;

using an encoding mode parameter s to select between using one of the following: (a) a first mode that uses an adaptive Golomb/Rice (G/R) encoder only; (b) a second mode that uses an adaptive Run-Length encoder and the adaptive G/R encoder;

defining a scaled encoding mode parameter as S=s*L, where L is a scaling parameter;

using a scaled G/R parameter K in the adaptive G/R encoder of the first and the second modes; and

updating the scaled encoding mode parameter S and the scaled G/R parameter K using a backward-adaptive technique.

34. The method of claim 33 , further comprising:

encoding the input string in the first mode if s=0;

increasing S by a first integer constant, A1, if |x|=0; and

decreasing S by a second integer constant, B1, if |x|>0.

35. The method of claim 33 , further comprising:

encoding the input string in the second mode if s>0;

increasing S by a third integer constant, A2, if x contains a run r of zeros such that r=2 S ; and

decreasing S by a fourth integer constant, B2, if x contains a run r of zeros such that r<2 s .

36. The method of claim 35 , further comprising:

defining an adaptation value, p;

decreasing K by a fifth integer constant, B3, if p=0;

leaving K unchanged if p=1; and

increasing K by p if p>1.

37. An adaptive Run-Length and Golomb/Rice (RLGR) encoder for encoding digital integer data containing integer values, comprising:

a Golomb/Rice (G/R) encoder for encoding the integer values;

a Run-Length encoder for encoding the integer values;

a means for using an encoding mode parameter s to switch between a first mode containing the G/R encoder only and a second mode containing both the Run-Length encoder and the G/R encoder; and

a means for updating the encoding mode parameter s using a backward adaptive technique having adaptation rules.

38. The adaptive RLGR encoder as set forth in claim 37 , further comprising:

a Golomb/Rice (G/R) parameter k for encoding the integer values using the G/R encoder of both the first and second modes;

a means for updating the G/R parameter k using the backward adaptation technique having the adaptation rules.

39. The adaptive RLGR encoder as set forth in claim 38 , wherein the adaptation rules further comprise:

a means for updating the encoding mode parameters s as follows:

increasing s by a first integer constant, A1, if s=0;

decreasing s by a second integer constant, B1, if s>0;

increasing s by a third integer constant, A2, if a run r of zeros is a complete run such that r=2 s ;

decreasing s by a fourth integer constant, B2, if a run r of zeros is an incomplete run such that r<2 S ; and

a means for updating the G/R parameter k as follows:

defining an adaptation value, p;

decreasing k by a fifth integer constant if p=0;

keeping k the same if p=1;

increasing k by p if p>1.

40. The adaptive RLGR encoder as set forth in claim 39 , further comprising:

a means for defining a scaled encoding mode parameter S and a scaled G/R parameter K, as follows:

defining a scaling parameter, L;

defining S=s*L;

defining K=k*L; and

a means for updating S and K instead of s and k using the respective adaptation rules.