Reduction of errors during computation of inverse discrete cosine transform

• US 8,385,424 B2
• Filed: 06/22/2007
• Issued: 02/26/2013
• Est. Priority Date: 06/26/2006
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Reznik, Yuriy
• Primary Examiner(s): Chai, Longbit
• Application Number:
  US11/767,444
• Publication Number:
  US 20070299897A1
• Time in Patent Office: 2,076 Days
• Field of Search: 375/240.2
• US Class Current: 375/240.2
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: H04N 19/45 performing compensation of the inverse transform mismatch, e.g. Inverse Discrete Cosine Transform [IDCT] mismatch
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

Techniques are described to reduce rounding errors during computation of discrete cosine transform using fixed-point calculations. According to these techniques, an inverse discrete cosine transform a vector of coefficients is calculated using a series of butterfly structure operations on fixed-point numbers. Next, a midpoint bias value and a supplemental bias value are added to a DC coefficient of the matrix of scaled coefficients. Next, an inverse discrete cosine transform is applied to the resulting matrix of scaled coefficients. Values in the resulting matrix are then right-shifted in order to derive a matrix of pixel component values. As described herein, the addition of the supplemental bias value to the DC coefficient reduces rounding errors attributable to this right-shifting. As a result, a final version of a digital media file decompressed using these techniques may more closely resemble an original version of a digital media file.

Claims

1. A method comprising:

using a series of butterfly structure operations on fixed-point numbers to apply a transform to a vector of source coefficients in order to generate a vector of transformed coefficients, wherein transformed coefficients in the vector of transformed coefficients are approximations of values that would be produced by transforming the vector of source coefficients using an ideal inverse discrete cosine transform;

causing a media presentation unit to output visible signals based on transformed coefficients in the vector of transformed coefficients, wherein differences between results generated by one of the butterfly structure operations and results that would be generated by an equivalent butterfly structure operation using unlimited precision arithmetic are centered around zero,

generating, with the device, a matrix of scaled coefficients by scaling each coefficient in a matrix of input coefficients;

generating, with the, device, a matrix of biased coefficients that includes the vector of source coefficients by adding one or more bias values to a DC coefficient of the matrix of scaled coefficients;

using the series of butterfly structure operations on the fixed-point numbers to apply the transform to each row vector in the matrix of biased coefficients in order to generate a matrix of intermediate coefficients;

using the series of butterfly structure operations on the fixed-point numbers to apply the transform to each column vector in the matrix of intermediate coefficients in order to generate a matrix of transformed coefficients; and

generating, with the device, a matrix of pixel component values by right-shifting coefficients in the matrix of transformed coefficients by a first magnitude.

2. The method of claim 1,

wherein generating the matrix of biased coefficients comprises adding a midpoint bias value to the DC coefficient of the matrix of scaled coefficients;

and

wherein the midpoint bias value is equal to 2<sup>(P+T−

1)</sup>, where P is equal to the first magnitude and T is a number of bits added by performing the transform.

3. The method of claim 2,

wherein generating the matrix of biased coefficients comprises adding a supplemental bias value to the DC coefficient of the matrix of scaled coefficients,

wherein the addition of the supplemental bias value to the DC coefficient causes positive errors and negative errors to be, on average, equal in magnitude and to be, on average, symmetric about zero, and

wherein the errors represent differences between values that result from right-shifting limited precision fixed-point representations of coefficients in the matrix of transformed coefficients by the first magnitude and results from dividing the coefficients in the matrix of transformed coefficients by 2^P, where P is equal to the first magnitude, without regard to precision.

4. The method of claim 3, wherein the supplemental bias value is equal to −

1 when the DC coefficient is negative and equal to 0 when the DC coefficient is non-negative.

5. The method of claim 3,

wherein the method further comprises selecting, on a pseudo-random basis, a value that is equal to either −

1 or 0; and

wherein adding the supplemental bias value comprises adding the selected value.

6. The method of claim 1,

wherein generating the matrix of scaled coefficients comprises left-shifting each coefficient in the matrix of input coefficients by a second magnitude;

wherein using the series of butterfly structure operations to apply the transform causes each coefficient in the matrix of transformed coefficients to include a number of extra bits of precision measured by a third magnitude; and

wherein the first magnitude is equal to the second magnitude plus the third magnitude.

7. The method of claim 6, wherein the second magnitude is equal to a number of mantissa bits of the fixed-point numbers used while applying the transform.

8. The method of claim 7,

wherein the second magnitude is three;

and

wherein, given the matrix of input coefficients, the pixel component values satisfy precision requirements of the Institute of Electrical and Electronics Engineers (IEEE) 1180 standard.

9. The method of claim 1, wherein the method further comprises:

constructing pixels that include pixel component values in the matrix of pixel component values; and

causing a display unit to display the pixels.

10. The method of claim 1, wherein the fixed-point numbers are 16-bit fixed-point numbers.

11. A device comprising:

one or more processors; and

an inverse transform module executed by the one or more that uses a series of butterfly structure operations on fixed-point numbers to apply a transform to a vector of source coefficients in order to generate a vector of transformed coefficients,wherein transformed coefficients in the vector of transformed coefficients are approximations of values that would be produced by transforming the vector of source coefficients using an ideal inverse discrete cosine transform;

wherein a media presentation unit is capable of presenting visible signals based on transformed coefficients in the vector of transformed coefficients, wherein differences between results generated by one of the butterfly structure operations and results that would be generated by an equivalent butterfly structure operation using unlimited precision arithmetic are centered around zero;

a scaling module executed by the one or more processors that generates a matrix of scaled coefficients by scaling each coefficient in a matrix of input coefficients;

a coefficient biasing module executed by the one or more processors that generates a matrix of biased coefficients that includes the vector of source coefficients by adding one or more bias values to a DC coefficient of the matrix of scaled coefficients; and

wherein the inverse transform module generates a matrix of intermediate coefficients by using the series of butterfly structure operations on the fixed-point numbers to apply the transform to each row vector in the matrix of biased coefficients;

wherein the inverse transform module generates a matrix of transformed coefficients by using the series of butterfly structure operations to apply the transform to each column vector in the matrix of intermediate coefficients; and

a right-shift module executed by the one or more processors that generates a matrix of pixel component values by right-shifting coefficients in the matrix of transformed coefficients by a first magnitude,

wherein the inverse transform module uses the series of butterfly structure operations to apply the transform to the vector of source coefficients.

12. The device of claim 11,

wherein the coefficient biasing module adds a midpoint bias value to the DC coefficient of the matrix of scaled coefficients,

wherein the midpoint bias value is equal to 2^(P+T−

1), where P is equal to the first magnitude and T is a number of bits added by performing the transform.

13. The device of claim 11,

wherein the coefficient biasing module adds a supplemental bias value to the DC coefficient of the matrix of scaled coefficients,

wherein the addition of the supplemental bias value to the DC coefficient causes positive errors and negative errors to be, on average, equal in magnitude and to be, on average, symmetric about zero, and

wherein the errors represent differences between values that result from right-shifting limited precision fixed-point representations of coefficients in the matrix of transformed coefficients by the first magnitude and results from dividing the coefficients in the matrix of transformed coefficients by 2^P, where P is equal to the first magnitude, without regard to precision.

14. The device of claim 13, wherein the supplemental bias value is equal to −

1 when the DC coefficient is negative and equal to 0 when the DC coefficient is non-negative.

15. The device of claim 13,

wherein the coefficient biasing module selects, on a pseudo-random basis, a value that is equal to either −

1 or 0; and

wherein the coefficient biasing module adds the selected value as the supplemental bias value.

16. The device of claim 11,

wherein the scaling module scales each coefficient in the matrix of input coefficients by left-shifting each coefficient in the matrix of input coefficients by a second magnitude;

wherein the inverse transform module causes each coefficient in the matrix of transformed coefficients to include a number of extra bits of precision measured by a third magnitude; and

wherein the first magnitude is equal to the second magnitude plus the third magnitude.

17. The device of claim 16, wherein the second magnitude is equal to a number of mantissa bits of the fixed-point numbers used while applying the transform.

18. A device comprising:

means for using a series of butterfly structure operations on fixed-point numbers to apply a transform to a vector of source coefficients in order to calculate a vector of transformed coefficients,

wherein transformed coefficients in the vector of transformed coefficients are approximations of values that would be produced by transforming the vector of source coefficients using an ideal inverse discrete cosine transform,

wherein a media presentation unit is capable of presenting visible signals based the transformed coefficients in the vector of transformed coefficients, and

wherein differences between results generated by one of the butterfly structure operations and results that would be generated by an equivalent butterfly structure operation using unlimited precision arithmetic are centered around zero;

means for generating a matrix of scaled coefficients by scaling each coefficient in a matrix of input coefficients;

means for generating a matrix of biased coefficients that includes the vector of source coefficients by adding one or more bias values to a DC coefficient of the matrix of scaled coefficients; and

means for generating a matrix of intermediate coefficients by using the series of butterfly structure operations to apply the transform to each row vector in the matrix of biased coefficients;

means for generating a matrix of transformed coefficients by using the series of butterfly structure operations to apply the transform to each column vector in the matrix of intermediate coefficients; and

means for generating a matrix of pixel component values by right-shifting coefficients in the matrix of transformed coefficients by a first magnitude,

wherein either the means for generating the matrix of intermediate coefficients or the means for generating the matrix of transformed coefficients comprises the means for using the series of butterfly structure operations to apply the transform to the vector of source coefficients.

19. The device of claim 18,

wherein the means for generating the matrix of biased coefficients comprises means for adding a midpoint bias value to the DC coefficient of the matrix of scaled coefficients,

wherein the midpoint bias value is equal to 2^(P+T−

1), where P is equal to the first magnitude and T is a number of bits added by performing the transform.

20. The device of claim 18,

wherein the means for generating the matrix of biased coefficients comprises means for adding a supplemental bias value to the DC coefficient of the matrix of scaled coefficients,

wherein the addition of the supplemental bias value to the DC coefficient causes positive errors and negative errors to be, on average, equal in magnitude and to be, on average, symmetric about zero, and

wherein the errors represent differences between values that result from right-shifting limited precision fixed-point representations of coefficients in the matrix of transformed coefficients by the first magnitude and results from dividing the coefficients in the matrix of transformed coefficients by 2^P, where P is equal to the first magnitude, without regard to precision.

21. The device of claim 20, wherein the supplemental bias value is equal to −

1 when the DC coefficient is negative and equal to 0 when the DC coefficient is non-negative.

22. The device of claim 20,

wherein the device comprises means for selecting on a pseudo-random basis a value that is equal to either −

1 or 0; and

wherein the means for adding the supplemental bias value adds the selected value as the supplemental bias value.

23. The device of claim 18,

wherein the means for generating the matrix of scaled coefficients comprises means for scaling each coefficient in the matrix of input coefficients by left-shifting each of the coefficients in the matrix of input coefficients by a second magnitude;

wherein the means for using the series of butterfly structure operations to apply the transform causes each coefficient in the matrix of transformed coefficients to include a number of extra bits of precision measured by a third magnitude; and

wherein the first magnitude is equal to the second magnitude plus the third magnitude.

24. The device of claim 23, wherein the second magnitude is equal to a number of mantissa bits of the fixed-point numbers used while applying the transform.

25. The device of claim 24,

wherein the second magnitude is three;

and

wherein, given the matrix of input coefficients, the pixel component values satisfy precision requirements of the Institute of Electrical and Electronics Engineers (IEEE) 1180 standard.

26. The device of claim 18,

wherein the device further comprises means for constructing pixels that include pixel component value in the matrix of pixel component values;

and

wherein the device further comprises means for causing a display unit to display the pixels.

27. The device of claim 18, wherein the fixed-point numbers are 16-bit fixed-point numbers.

28. A non-transitory computer-readable medium comprising instructions that when executed cause a processor to:

use a series of butterfly structure operations on fixed-point numbers to apply a transform to a vector of coefficients in order to generate a vector of transformed coefficients;

wherein transformed coefficients in the vector of transformed coefficients are approximations of values that would be produced by transforming the vector of source coefficients using an ideal inverse discrete cosine transform;

cause a media presentation unit to output visible signals based on transformed values in the vector of transformed values,

wherein differences between results generated by one of the butterfly structure operations and results that would be generated by an equivalent butterfly structure operation using unlimited precision arithmetic are centered around zero;

generate a matrix of biased coefficients that includes the vector of source coefficients by adding one or more bias values to a DC coefficients of the matrix of scaled coefficients;

use the series of butterfly structure operations on fixed-point numbers to apply the transform to each row vector in the matrix of biased coefficients in order to generate a matrix of intermediate coefficients;

use the series of butterfly structure operations on fixed-point to apply the transform to each column vector in the matrix of intermediate coefficients in order to generate a matrix of transformed coefficients; and

generate a matrix of pixel component values by right-shifting coefficients in the matrix of transformed coefficients by a first magnitude.

29. The computer-readable medium of claim 28,

wherein the instructions that cause the processor to generate the matrix of biased coefficients cause the processor to add a midpoint bias value to the DC coefficient of the matrix of scaled coefficients;

and

wherein the midpoint bias value is equal to 2<sup>(P+T−

1)</sup>, where P is equal to the first magnitude and T is a number of bits added by performing the transform.

30. The computer-readable medium of claim 28,

wherein the instructions that cause the processor to generate the matrix of biased coefficients cause the processor to add a supplemental bias value to the DC coefficient of the matrix of scaled coefficients,

wherein the addition of the supplemental bias value to the DC coefficient causes positive errors and negative errors to be, on average, equal in magnitude and to be, on average, symmetric about zero, and

wherein the errors represent differences between values that result from right-shifting limited precision fixed-point representations of coefficients in the matrix of transformed coefficients by the first magnitude and results from dividing the coefficients in the matrix of transformed coefficients by 2^P, where P is equal to the first magnitude, without regard to precision.

31. The computer-readable medium of claim 30, wherein the supplemental bias value is equal to −

1 when the DC coefficient is negative and equal to 0 when the DC coefficient is non-negative.

32. The computer-readable medium of claim 30,

wherein the instructions further cause the processor to select, on a pseudo-random basis, a value that is equal to either −

1 or 0; and

wherein the instructions that cause the processor to add the supplemental bias value cause the processor to add the selected value as the supplemental bias value.

33. The computer-readable medium of claim 28,

wherein the instructions that cause the processor to generate the matrix of scaled coefficients cause the processor to left-shift each coefficient in the matrix of input coefficients by a second magnitude;

wherein the instructions that cause the processor to use the series of butterfly structure operations cause each coefficient in the matrix of transformed coefficients to include a number of extra bits of precision measured by a third magnitude; and

wherein the first magnitude is equal to the second magnitude plus the third magnitude.

34. The non-transitory computer-readable medium of claim 33, wherein the second magnitude is equal to a number of mantissa bits of the fixed-point numbers used while applying the transform.

35. The non-transitory computer-readable medium of claim 34,

wherein the second magnitude is three;

and

wherein, given the matrix of input coefficients, the pixel component values satisfy precision requirements of the Institute of Electrical and Electronics Engineers (IEEE) 1180 standard.

36. The computer-readable medium of claim 28, wherein the instructions further cause the processor to:

construct pixels that include pixel component values in the matrix of pixel component values; and

display the pixels on a display unit.

37. The computer-readable medium of claim 28, wherein the fixed-point numbers are 16-bit fixed-point numbers.

38. A method for computation of an inverse discrete cosine transform comprising:

using, with a device, a series of butterfly structure operations on fixed-point numbers to apply a transform to a vector of source coefficients in order to generate a vector of transformed coefficients,

wherein transformed coefficients in the vector of transformed coefficients are approximations of values that would be produced by transforming the vector of source coefficients using an ideal inverse discrete cosine transform,

wherein using the series of the butterfly structure operations comprises performing a butterfly structure operation of the form;

u=((x*>

>

k)−

((y*−

S)>

>

k);

v=((x*S′

)>

>

k′

)−

((y*>

>

k), and

wherein u and v are resulting fixed-point numbers, C, S, k and k′

are constant integers, x and y are fixed-point variables, and C/2^k and S/2^k′

are rational number approximations of irrational constants.

39. The method of claim 38,

wherein the vector of source coefficients consists of eight coefficients:

x₀, x₁, x₂, x₃, x₄, x₅, x₆, and x₇;

wherein the vector of transformed coefficients consists of eight coefficients;

z₀, z₁, z₂, z₃, z₄, z₅, z₆, and z₇; and

performing any of the butterfly structure operations comprises;

performing a first butterfly structure operation in which x=x₀, y=x₄, C=1, S=1, u=x₀′

, and v=x₄′

;

performing a second butterfly structure operation in which x=x₂, y=x₆, C=α

, S =β

, u=x₆′

, and v=x₂′

;

performing a third butterfly structure operation in which x=x₇, y=x₁, C=1, S=1, u=x₇′

, and v=x₁′

;

performing a fourth butterfly structure operation in which x=1/√

{square root over (2)}*x₁′

, y=x₅, C=1, S=1, u=x₁″

, and v=x₅′

;

performing a fifth butterfly structure operation in which x=1/√

{square root over (2)}*x₇′

, y=x₃, C=1, S=1, u=x₇″

, and v=x₃′

;

performing a sixth butterfly structure operation in which x=x₀′

, y=x₆′

, C=1, S=1, u=x₀″

, and v=x₆″

;

performing a seventh butterfly structure operation in which x=x₄′

, y=x₂′

, C=1, S=1, u=x₄″

, and v=x₂″

;

performing an eighth butterfly structure operation in which x=x₁″

, y=x₇″

, C=ζ

, S=ε

, u=x₁′

″

, and v=x₇′

″

;

performing a ninth butterfly structure operation in which x=x₃′

, y=x₅′

, C=δ

, S=γ

, u=x₅″

, and v=x₃″

;

performing a tenth butterfly structure operation in which x=x₀″

, y=x₇″

, C=1, S=1, u=z₀, and v=z₇;

performing an eleventh butterfly structure operation in which x=x₄″

, y=x₅″

, C=1, S=1, u=z₁, and v=z₆;

performing a twelfth butterfly structure operation in which x=x₂″

, y=x₃″

, C=1, S=1, u=z₂, and v=z₅; and

performing a thirteenth butterfly structure operation in which x=x₆″

, y=x₁′

″

, C=1, S=1, u=z₃, and v=z₄.

40. The method of claim 39, wherein α

, β

, γ

, δ

, ε

, and ζ

are approximations of the irrational values √

{square root over (2)} cos(3π

/8), √

{square root over (2)} sin(3π

/8), √

{square root over (2)} cos(π

/16), √

{square root over (2)} sin(π

/16), √

{square root over (2)} cos(3π

/16), and √

{square root over (2)} sin(3π

/16), respectively.

41. The device of claim 40, wherein α

=8867/16384, β

=21407/16384, γ

=5681/4096, δ

=565/2048, ε

=9633/8192, ζ

=12873/16384.

42. The device of claim 38, wherein using the series of butterfly structure operations comprises using series of shift, addition, and subtraction operations that produce resulting values that approximate values that would result by performing multiplication operations in the butterfly structure operations.

43. A device for computation of an inverse discrete cosine transform comprising:

one or more processors; and

an inverse transform module executed by the one or more processors that uses a series of butterfly structure operations on fixed-point numbers to apply a transform to a vector of source coefficients in order to generate a vector of transformed coefficients,

wherein transformed coefficients in the vector of transformed coefficients are approximations of values that would be produced by transforming the vector of source coefficients using an ideal inverse discrete cosine transform, and

wherein the one of the butterfly structure operations performed by the inverse transform module is of the form;

u=((x*C)>

>

k)−

((y*−

S)>

>

k′

);

v=((x*S′

)>

>

k′

)−

((y*C)>

>

k), and

wherein u and v are resulting fixed-point values, C, S, k and k′

are constant integers, x and y are fixed-point variables, and C/2^k and S/2^k′

are rational number approximations of irrational constants.

44. The device of claim 43,

wherein the vector of source coefficients consists of eight coefficients:

x₀, x₁, x₂, x₃, x₄, x₅, x₆, and x₇;

wherein the vector of transformed coefficients consists of eight coefficients;

z₀, z₁, z₂, z₃, z₄, z₅, z₆, and z₇; and

wherein the inverse transform module performs the butterfly structure operations by;

performing a first butterfly structure operation in which x=x₀, y=x₄, C=1, S=1, u=x₀′

, and v=x₄′

;

performing a second butterfly structure operation in which x=x₂, y=x₆, C=α

, S=β

, u=x₆′

, and v=x₂′

;

performing a third butterfly structure operation in which x=x₇, y=x₁, C=1, S=1, u=x₇′

, and v=x₁′

;

performing a fourth butterfly structure operation in which x=1/√

{square root over (2)}*x₁′

, y=x₅, C=1, S=1, u=x₁″

, and v=x₅′

;

performing a fifth butterfly structure operation in which x=1/√

{square root over (2)}*x₇′

, y=x₃, C=1, S=1, u=x₇″

, and v=x₃′

;

performing a sixth butterfly structure operation in which x=x₀′

, y=x₆′

, C=1,S=1, u=x₀″

, and v=x₆″

;

performing a seventh butterfly structure operation in which x=x₄′

, y=x₂′

, C=1, S=1, u=x₄″

, and v=x₂″

;

performing an eighth butterfly structure operation in which x=x₁″

, y=x₇″

, C=ζ

, S=ε

, u=x₁′

″

, and v=x₇′

″

;

performing a ninth butterfly structure operation in which x=x₃′

, y=x₅′

, C=δ

, S=γ

, u=x₅″

, and v=x₃″

;

performing a tenth butterfly structure operation in which x=x₀″

, y=x₇′

″

, C=1, S=1, u=z₀, and v=z₇;

performing an eleventh butterfly structure operation in which x=x₄″

, y=x₅ ″

, C=1, S=1, u=z₁, and v=z₆;

performing a twelfth butterfly structure operation in which x=x₂″

, y=x₃″

, C=1, S=1, u=z₂, and v=z₅; and

performing a thirteenth butterfly structure operation in which x=x₆″

, y=x₁′

″

, C=1, S=1, u=z₃, and v=z₄.

45. The device of claim 44, wherein α

, β

, γ

, δ

, ε

, and ζ

are approximations of the irrational values √

{square root over (2)} cos(3π

/8), √

{square root over (2)} sin(3π

/8), √

{square root over (2)} cos(π

/16), √

{square root over (2)} sin(π

/16), √

{square root over (2)} cos(3π

/16), and √

{square root over (2)} sin(3π

/16), respectively.

46. The device of claim 45, wherein α

=8867/16384, β

=21407/16384, γ

=5681/4096, δ

=565/2048, ε

=9633/8192, ζ

=12873/16384.

47. The device of claim 44, wherein the inverse transform module performs the butterfly structure operations using a series of shift, addition, and subtraction operations that produce resulting values that approximate values that would result by performing multiplication operations in the butterfly structure operations.

48. A device for computation of an inverse discrete cosine transform comprising:

means for using a series of butterfly structure operations on fixed-point numbers to apply a transform to a vector of source coefficients in order to calculate a vector of transformed coefficients,

wherein transformed coefficients in the vector of transformed coefficients are approximations of values that would be produced by transforming the vector of source coefficients using an ideal inverse discrete cosine transform,

wherein the means for using a series of butterfly structure operations comprises a set of means for performing a butterfly structure operation,

wherein each of the means for performing a butterfly structure operation comprises means for performing a butterfly structure operation of the form;

u=((x*C)>

>

k)−

((y*−

S)>

>

k);

v=((x*S)>

>

k)−

((y*>

>

k), and

wherein u and v are resulting fixed-point values, C, S, k and k′

are constant integers, x and y are fixed-point variables, and C/2^k and S/2^k′

are rational number approximations of irrational constants.

49. The device of claim 48,

wherein the vector of source coefficients consists of eight coefficients:

x₀, x₁, x₂, x₃, x₄, x₅, x₆, and x₇;

wherein the vector of transformed coefficients consists of eight coefficients;

z₀, z₁, z₂, z₃, z₄, z₅, z₆, and z₇; and

wherein the set of means for performing of butterfly structure operations comprises;

means for performing a first butterfly structure operation in which x=x₀, y=x₄, C=1, S=1, u=x₀′

, and v=x₄′

;

means for performing a second butterfly structure operation in which x=x₂, y=x₆, C=α

, S=β

, u=x₆′

, and v=x₂′

;

means for performing a third butterfly structure operation in which x=x₇, y=x₁, C=1, S=1, u=x₇′

, and v=x₁′

;

means for performing a fourth butterfly structure operation in which x=1/√

{square root over (2)}*x₁, y=x₅, C=1, S=1, u=x₁″

, and v=x₅′

;

means for performing a fifth butterfly structure operation in which x=1/√

{square root over (2)}*x₇′

, y=x₃, C=1, S=1, u=x₇″

, and V=x₃′

;

means for performing a sixth butterfly structure operation in which x=x₀′

, y=x₆′

, C=1, S=1, u=x₀″

, and v=x₆″

;

means for performing a seventh butterfly structure operation in which x=x₄′

, y=x₂′

, C=1, S=1, u=x₄″

, and v=x₂″

;

means for performing an eighth butterfly structure operation in which x=x₁″

, y=x₇″

, C=ζ

, S=ε

, u=x₁′

″

, and v=x₇′

″

;

means for performing a ninth butterfly structure operation in which x=x₃′

, y=x₅′

, C=δ

, S=y, u=x₅″

, and v=x₃″

;

means for performing a tenth butterfly structure operation in which x=X₀″

, y=x₇′

″

, C=1, S=1, u=z₀, and v=z₇;

means for performing an eleventh butterfly structure operation in which x=x₄″

, y=x₅″

, C=1, S=1, u=z₁, and v=z₆;

means for performing a twelfth butterfly structure operation in which x=x₂″

, y=x₃″

, C=1, S=1, u=z₂, and v=z₅; and

means for performing a thirteenth butterfly structure operation in which x=x₆″

, y=x₁′

″

, C=1, S=1, u=z₃, and v=z₄.

50. The device of claim 49, wherein α

, β

, γ

, δ

, ε

, and ζ

are approximations of the irrational values √

{square root over (2)} cos(3π

/8), √

{square root over (2)} sin(3π

/8), √

{square root over (2)} cos(π

/16), √

{square root over (2)} sin(π

/16), √

{square root over (2)} cos(3π

/16), and √

{square root over (2)} sin(3π

/16), respectively.

51. The device of claim 50, wherein α

=8867/16384, β

=21407/16384, γ

=5681/4096, δ

=565/2048, ε

=9633/8192, ζ

=12873/16384.

52. The device of claim 48, wherein the means for using the series of butterfly structure operations performs the butterfly structure operations using a series of shift, addition, and subtraction operations that produce resulting values that approximate values that would result by performing multiplication operations in the butterfly structure operations.

53. A non-transitory computer-readable medium comprising instructions for computation of an inverse discrete cosine transform that when executed cause a programmable processor to:

use a series of butterfly structure operations on fixed-point numbers to apply a transform to a vector of source coefficients in order to generate a vector of transformed coefficients, wherein transformed coefficients in the vector of transformed coefficients are approximations of values that would be produced by transforming the vector of source coefficients using an ideal inverse discrete cosine transform;

wherein the instructions that cause the processor to perform the butterfly structure operations cause the processor to perform a butterfly structure operation of the form;

u=((x*C)>

>

k)−

(y*−

S)>

>

k′

);

v=((x*S′

)>

>

k′

)−

((y*C)>

>

k), and

wherein u and v are resulting fixed-point numbers, C, S, k and k′

are constant integers, x and y are fixed-point variables and C/2^k and S/2^k′

are rational number approximations of irrational constants.

54. The computer-readable medium of claim 53,

wherein the vector of source coefficients consists of eight coefficients:

x₀, x₁, x₂, x₃, x₄, x₅, x₆, and x₇;

wherein the vector of transformed coefficients consists of eight coefficients;

z₀, z₁, z₂, z₃, z₄, z₅, z₆, and z₇;

wherein the instructions that cause the processor to use the series of butterfly structure operations cause the programmable processor to;

perform a first butterfly structure operation in which x=x₀, y=x₄, C=1, S=1, u=x₀′

, and v=x₄′

;

perform a second butterfly structure operation in which x=x₂, y=x₆, C=α

, S=β

, u=x₆′

, and v=x₂′

;

perform a third butterfly structure operation in which x=x₇, y=x₁, C=1, S=1, u=x₇′

, and v=x₁′

;

perform a fourth butterfly structure operation in which x=1/√

{square root over (2)}*x₁′

, y=x₅, C=1, S=1, u=x₁″

, and v=x₅′

;

perform a fifth butterfly structure operation in which x=1/√

{square root over (2)}*x₇′

, y=x₃, C=1, S=1, u=x₇″

, and v=x₃′

;

perform a sixth butterfly structure operation in which x=x₀′

, y=x₆′

, C=1, S=1, u=x₀″

, and v=x₆″

;

perform a seventh butterfly structure operation in which x=x₄′

, y=x₂′

, C=1, S=

1, u=x₄″

, and v=x₂″

;

perform an eighth butterfly structure operation in which x=x₁″

, y=x₇″

, C=ζ

, S=ε

, u=x₁′

″

, and v=x₇′

″

;

perform a ninth butterfly structure operation in which x=x₃′

, y=x₅′

, C=6, S=γ

, u=x₅″

, and V=x₃″

;

perform a tenth butterfly structure operation in which x=X₀″

, y=x₇′

″

, C=1, S=1, u=z₀, and v=z₇;

perform an eleventh butterfly structure operation in which x=x₄″

, y=x₅″

, C=1, S=1, u=z₁, and v=z₆;

perform a twelfth butterfly structure operation in which x=x₂″

, y=x₃″

, C=1, S=1, u=z₂, and v=z₅; and

perform a thirteenth butterfly structure operation in which x=x₆″

, y=X₁′

″

, C=1, S=1, u=z₃, and v=z₄.

55. The non-transitory computer-readable medium of claim 54, wherein α

, β

, γ

, δ

, ε

, and ζ

are approximations of the irrational values √

{square root over (2)} cos(3π

/8), √

{square root over (2)} sin(3π

/8), √

{square root over (2)} cos(π

/16), √

{square root over (2)} sin(π

/16), √

{square root over (2)} cos(3π

/16), and √

{square root over (2)} sin(3π

/16), respectively.

56. The computer-readable medium of claim 55, wherein α

=8867/16384, β

=21407/16384, γ

=5681/4096, δ

=565/2048, ε

=9633/8192, ζ

=12873/16384.

57. The computer-readable medium of claim 53, wherein the instructions that cause the processor to use the series of butterfly structure operation cause the programmable processor to multiply values in the butterfly structure operation using a series of shift, addition, and subtraction operations that produce resulting values that approximate values that would result by performing multiplication operations.