COMPUTING EVEN-SIZED DISCRETE COSINE TRANSFORMS

• US 20100266008A1
• Filed: 04/13/2010
• Published: 10/21/2010
• Est. Priority Date: 04/15/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Reznik, Yuriy
• Granted Patent: US 9,110,849 B2
• Time in Patent Office: Days
• US Class Current: 375/240.200
• 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/122 Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
• CPC Class Codes: H04N 19/134 characterised by the element, parameter or criterion affecting or controlling the adaptive coding
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/625 using discrete cosine transform [DCT]

Abstract

In general, techniques are described for computing even-sized discrete cosine transforms (DCTs). For example, a coding device may implement these techniques. The coding device includes a DCT-II unit that first determines whether a DCT-II to perform is a multiple of two, and in response to determining that the DCT-II to perform is a multiple of two, performs the DCT-II. To perform the DCT-II, the DCT-II unit computes a butterfly and reverses an order of a first sub-set of the outputs of the butterfly. The DCT-II unit then recursively subtracts the reverse-ordered first sub-set of the butterfly outputs. The DCT-II unit computes a sub-DCT-II for a second sub-set of the butterfly outputs and a sub-DCT-III for the recursively subtracted first set of butterfly outputs. The DCT-II unit reorders the outputs produced by the sub-DCT-II and sub-DCT-III to generate output values of the DCT-II.

Claims

1. A method of performing a scaled discrete cosine transform of type II (DCT-II), the method comprising:

determining, with an apparatus, whether a size of the scaled DCT-II to perform is a multiple of two; and

in response to determining that the size of the scaled DCT-II to perform is a multiple of two, performing, with the apparatus, the scaled DCT-II,

wherein performing the scaled DCT-II includes;

computing a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

reversing an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

computing a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

computing a scaled sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

computing a full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs; and

reordering the first and second set of outputs produced by the respective scaled sub-DCT-II and full sub-DCT-III to generate scaled output values of the DCT-II.

2. The method of claim 1, wherein computing the butterfly, reversing the order, computing the series of recursive subtractions, computing the scaled sub-DCT-II, and computing the full DCT-II occurs recursively with respect to the sub-DCT-II until a size of any additional sub-DCTs-II produced through the recursion is not a multiple of two.

3. The method of claim 1, further comprising:

determining whether the scaled sub-DCT-II is of a size that is a multiple of two;

in response to the determination that the scaled sub-DCT-II is of a size that is a multiple of two, performing the scaled sub-DCT-II,

wherein performing the scaled sub-DCT-II includes;

computing another butterfly that includes cross-additions and cross-subtractions of inputs to the scaled sub-DCT-II, wherein the butterfly includes a first portion that generates a first sub-set of the inputs to the scaled sub-DCT-II and a second portion that generates a second sub-set of the inputs to the scaled sub-DCT-II;

reversing an order of the second sub-set of cross-subtracted inputs that input the scaled sub-DCT-II to generate a reverse-ordered second sub-set of the inputs to the scaled sub-DCT-II;

computing a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs that input to the scaled sub-DCT-II to generate a recursively subtracted second sub-set of the inputs to the scaled sub-DCT-II;

computing an additional scaled sub-DCT-II that receives the first sub-set of the inputs to the sub-DCT-II and generates a first set of outputs based on the first sub-set of the inputs to the sub-DCT-II;

computing an additional full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs to the sub-DCT-II and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs to the sub-DCT-II; and

reordering the first and second set of outputs produced by the respective additional scaled sub-DCT-II and full sub-DCT-III to generate scaled output values of the DCT-II.

4. The method of claim 1, further comprising configuring quantization coefficients of a quantization matrix to account for factors inherently removed when computing the scaled DCT-II without increasing an implementation complexity of the quantization matrix.

5. The method of claim 1, wherein computing the scaled sub-DCT-II comprises computing the scaled sub-DCT-II in a manner that inherently removes factors so as to reduce an implementation complexity of the scaled DCT-II unit.

6. The method of claim 1,

wherein the apparatus comprises a video coder,

wherein determining whether the size of the scaled DCT-II to perform is a multiple of two comprises:

receiving a block of residual video data;

determining whether the size of the block of residual video data is of a size that is a multiple of two; and

determining, based on the size of the block of residual video data, whether the size of the scaled DCT-II to perform is a multiple of two,

wherein the scaled output values comprise DCT coefficients, and

wherein the method further comprises performing quantization with a quantization unit of the video coder to quantize the DCT coefficients in accordance with quantization coefficients that account for factors inherently removed when computing the performing the scaled DCT-II without increasing an implementation complexity of the video coder.

7. The method of claim 1, wherein the apparatus comprises one or more of a video encoder, a video decoder, an audio encoder, an audio decoder, an image encoder and an image decoder.

8. The method of claim 1, further comprising, in response to determining that the size of the scaled DCT-II to perform is not a multiple of two, computing the scaled DCT-II directly to generate additional outputs without computing a butterfly, reversing the order of the second sub-set of cross-subtracted inputs, computing the series of recursive subtractions, computing the scaled sub-DCT-II, computing the full sub-DCT-III, and reordering the first and second set of outputs.

9. A media coding device comprising:

a scaled DCT-II unit that determines whether a size of a scaled DCT-II to perform is a multiple of two, and in response to determining that the size of the scaled DCT-II to perform is a multiple of two, performs the scaled DCT-II,

wherein the scaled DCT-II unit includes;

a butterfly unit that computes a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly unit includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

an order reversal unit that reverses an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

a recursive subtraction unit that computes a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

a scaled sub-DCT-II unit that computes a scaled sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs; and

a full sub-DCT-III unit that computes a full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs,

wherein the scaled DCT-II unit reorders the first and second set of outputs produced by the respective scaled sub-DCT-II and full sub-DCT-III to generate scaled output values of the DCT-II.

10. The media coding device of claim 9, wherein the scaled DCT-II unit computes the butterfly, reverses the order, computes the series of recursive subtractions, computes the scaled sub-DCT-II, and computes the full DCT-II recursively with respect to the sub-DCT-II until a size of any additional sub-DCTs-II produced through the recursion is not a multiple of two.

11. The media coding device of claim 9,

wherein the scaled sub-DCT-II unit determines whether the scaled sub-DCT-II is of a size that is a multiple of two, and in response to determining that the scaled sub-DCT-II is of a size that is a multiple of two, performs the scaled sub-DCT-II,

wherein the scaled sub-DCT-II unit includes:

an additional butterfly unit computes another butterfly that includes cross-additions and cross-subtractions of inputs to the scaled sub-DCT-II, wherein the butterfly includes a first portion that generates a first sub-set of the inputs to the scaled sub-DCT-II and a second portion that generates a second sub-set of the inputs to the scaled sub-DCT-II;

an additional order reversal unit reverses an order of the second sub-set of cross-subtracted inputs that input the scaled sub-DCT-II to generate a reverse-ordered second sub-set of the inputs to the scaled sub-DCT-II;

an additional recursive subtraction unit computes a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs that input to the scaled sub-DCT-II to generate a recursively subtracted second sub-set of the inputs to the scaled sub-DCT-II;

an additional scaled sub-DCT-II unit computes an additional scaled sub-DCT-II that receives the first sub-set of the inputs to the sub-DCT-II and generates a first set of outputs based on the first sub-set of the inputs to the sub-DCT-II;

an additional full sub-DCT-II unit computes an additional full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs to the sub-DCT-II and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs to the sub-DCT-II, and

wherein the sub-DCT-II unit reorders the first and second set of outputs produced by the respective additional scaled sub-DCT-II unit and full sub-DCT-III unit to generate scaled output values of the DCT-II.

12. The media coding device of claim 9, further comprising a quantization unit that includes a quantization matrix that account for factors inherently removed when computing the scaled DCT-II without increasing an implementation complexity of the quantization matrix.

13. The media coding device of claim 9, wherein the scaled sub-DCT-II unit computes the scaled sub-DCT-II in a manner that inherently removes factors so as to reduce an implementation complexity of the scaled DCT-II unit.

14. The media coding device of claim 9,

wherein the media coding device comprises a video coder,

wherein the scaled DCT-II unit receives a block of residual video data, determines whether the size of the block of residual video data is of a size that is a multiple of two and determines, based on the size of the block of residual video data, whether the size of the scaled DCT-II to perform is a multiple of two,

wherein the scaled output values comprise DCT coefficients, and

wherein the media coding device further comprises a quantization unit that quantizes the DCT coefficients in accordance with quantization coefficients that account for factors inherently removed when computing the performing the scaled DCT-II without increasing an implementation complexity of the video coder.

15. The media coding device of claim 9, wherein the media coding device comprises one or more of a video encoder, a video decoder, an audio encoder, an audio decoder, an image encoder and an image decoder.

16. The media coding device of claim 9, wherein the scaled DCT-II unit, in response to determining that the size of the scaled DCT-II to perform is not a multiple of two, computes the scaled DCT-II directly to generate additional outputs without computing a butterfly, reversing the order of the second sub-set of cross-subtracted inputs, computing the series of recursive subtractions, computing the scaled sub-DCT-II, computing the full sub-DCT-III, and reordering the first and second set of outputs.

17. A non-transitory computer-readable medium comprising instructions for causing a processor to:

determine whether a size of a scaled DCT-II to perform is a multiple of two; and

in response to determining that the size of the scaled DCT-II to perform is a multiple of two, perform the scaled DCT-II,

wherein the instructions that cause the processor to perform the scaled DCT-II include instructions that cause the processor to;

compute a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

reverse an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

compute a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

compute a scaled sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

compute a full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs; and

reorder the first and second set of outputs produced by the respective scaled sub-DCT-II and full sub-DCT-III to generate scaled output values of the DCT-II.

18. The non-transitory computer-readable medium of claim 17, wherein the instruction cause the processor to compute the butterfly, reverse the order, compute the series of recursive subtractions, compute the scaled sub-DCT-II, and compute the full DCT-II in a recursive manner with respect to the sub-DCT-II until a size of any additional sub-DCTs-II produced in the recursive manner is not a multiple of two.

19. The non-transitory computer-readable medium of claim 17, wherein the instructions cause the processor to:

determine whether the scaled sub-DCT-II is of a size that is a multiple of two;

in response to the determination that the scaled sub-DCT-II is of a size that is a multiple of two, perform the scaled sub-DCT-II,

wherein the instructions that cause the processor to perform the scaled sub-DCT-II include instructions that cause the processor to;

compute another butterfly that includes cross-additions and cross-subtractions of inputs to the scaled sub-DCT-II, wherein the butterfly includes a first portion that generates a first sub-set of the inputs to the scaled sub-DCT-II and a second portion that generates a second sub-set of the inputs to the scaled sub-DCT-II;

reverse an order of the second sub-set of cross-subtracted inputs that input the scaled sub-DCT-II to generate a reverse-ordered second sub-set of the inputs to the scaled sub-DCT-II;

compute a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs that input to the scaled sub-DCT-II to generate a recursively subtracted second sub-set of the inputs to the scaled sub-DCT-II;

compute an additional scaled sub-DCT-II that receives the first sub-set of the inputs to the scaled sub-DCT-II and generates a first set of outputs based on the first sub-set of the inputs to the scaled sub-DCT-II;

compute an additional full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs to the sub-DCT-II and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs to the sub-DCT-II; and

reorder the first and second set of outputs produced by the respective additional scaled sub-DCT-II and full sub-DCT-III to generate scaled output values of the DCT-II.

20. The non-transitory computer-readable medium of claim 17, wherein the instructions further cause the processor to compute the scaled sub-DCT-II in a manner that inherently removes factors so as to reduce an implementation complexity of the scaled DCT-II unit.

21. The non-transitory computer-readable medium of claim 17, wherein the instructions further cause the processor to:

receive a block of residual video data

determine whether the size of the block of residual video data is of a size that is a multiple of two; and

determine, based on the size of the block of residual video data, whether the size of the scaled DCT-II to perform is a multiple of two,

wherein the scaled output values comprise DCT coefficients, and

wherein the instructions further cause the processor to quantize the DCT coefficients in accordance with quantization coefficients that account for factors inherently removed when computing the performing the scaled DCT-II without increasing an implementation complexity of the video coder.

22. The non-transitory computer-readable medium of claim 17, wherein the instructions further cause the processor to, in response to determining that the size of the scaled DCT-II to perform is not a multiple of two, compute the scaled DCT-II directly to generate additional outputs without computing a butterfly, reversing the order of the second sub-set of cross-subtracted inputs, computing the series of recursive subtractions, computing the scaled sub-DCT-II, computing the full sub-DCT-III, and reordering the first and second set of outputs.

23. An apparatus comprising:

means for determining whether a size of a scaled DCT-II to perform is a multiple of two; and

means for performing, in response to determining that the size of the scaled DCT-II to perform is a multiple of two, the scaled DCT-II,

wherein the means for performing the scaled DCT-II includes;

means for computing a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

means for reversing an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

means for computing a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

means for computing a scaled sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

means for computing a full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs; and

means for reordering the first and second set of outputs produced by the respective scaled sub-DCT-II and full sub-DCT-III to generate scaled output values of the DCT-II.

24. The apparatus of claim 23, wherein the means for performing the scaled DCT-II recursively performs the scaled DCT-II with respect to the sub-DCT-II until a size of any additional sub-DCTs-II produced through the recursion is not a multiple of two.

25. The apparatus of claim 23, further comprising:

means for determining whether the scaled sub-DCT-II is of a size that is a multiple of two;

means for performing, in response to the determination that the scaled sub-DCT-II is of a size that is a multiple of two, the scaled sub-DCT-II,

wherein the means for performing the scaled sub-DCT-II includes;

means for computing another butterfly that includes cross-additions and cross-subtractions of inputs to the scaled sub-DCT-II, wherein the butterfly includes a first portion that generates a first sub-set of the inputs to the scaled sub-DCT-II and a second portion that generates a second sub-set of the inputs to the scaled sub-DCT-II;

means for reversing an order of the second sub-set of cross-subtracted inputs that input the scaled sub-DCT-II to generate a reverse-ordered second sub-set of the inputs to the scaled sub-DCT-II;

means for computing a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs that input to the scaled sub-DCT-II to generate a recursively subtracted second sub-set of the inputs to the scaled sub-DCT-II;

means for computing an additional scaled sub-DCT-II that receives the first sub-set of the inputs to the sub-DCT-II and generates a first set of outputs based on the first sub-set of the inputs to the sub-DCT-II;

means for computing an additional full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs to the sub-DCT-II and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs to the sub-DCT-II; and

means for reordering the first and second set of outputs produced by the respective additional scaled sub-DCT-II and full sub-DCT-III to generate scaled output values of the DCT-II.

26. The apparatus of claim 23, further comprising means for configuring quantization coefficients of a quantization matrix to account for factors inherently removed when computing the scaled DCT-II without increasing an implementation complexity of the quantization matrix.

27. The apparatus of claim 23, wherein the means for computing the scaled sub-DCT-II comprises means for computing the scaled sub-DCT-II in a manner that inherently removes factors so as to reduce an implementation complexity of the scaled DCT-II unit.

28. The apparatus of claim 23,

wherein the apparatus comprises a video coder,

wherein the means or determining whether the size of the scaled DCT-II to perform is a multiple of two comprises:

means for receiving a block of residual video data;

means for determining whether the size of the block of residual video data is of a size that is a multiple of two; and

means for determining, based on the size of the block of residual video data, whether the size of the scaled DCT-II to perform is a multiple of two,

wherein the scaled output values comprise DCT coefficients, and

wherein apparatus comprises means for quantizing the DCT coefficients in accordance with quantization coefficients that account for factors inherently removed when computing the performing the scaled DCT-II without increasing an implementation complexity of the video coder.

29. The apparatus of claim 23, wherein the apparatus comprises one or more of a video encoder, a video decoder, an audio encoder, an audio decoder, an image encoder and an image decoder.

30. The apparatus of claim 23, further comprising means for computing, in response to determining that the size of the scaled DCT-II to perform is not a multiple of two, the scaled DCT-II directly to generate additional outputs without computing a butterfly, reversing the order of the second sub-set of cross-subtracted inputs, computing the series of recursive subtractions, computing the scaled sub-DCT-II, computing the full sub-DCT-III, and reordering the first and second set of outputs.

31. A method of performing a full discrete cosine transform of type II (DCT-II), the method comprising:

determining, with an apparatus, whether a size of the full DCT-II to perform is a multiple of two; and

in response to determining that the size of the full DCT-II to perform is a multiple of two, performing, with the apparatus, the full DCT-II,

wherein performing the full DCT-II includes;

computing a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

reversing an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

computing a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

computing a full sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

computing a full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs;

multiplying the first set of outputs by one or more scale factors to generated a first full set of outputs; and

reordering the first full set of outputs and the second set of outputs to generate output values of the DCT-II.

32. A media coding device comprising:

a full DCT-II unit that determines whether a size of a full DCT-II to perform is a multiple of two, and in response to determining that the size of the full DCT-II to perform is a multiple of two, performs the full DCT-II,

wherein the full DCT-II includes;

a butterfly unit that computes a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly unit includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

an order reversal unit that reverses an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

a recursive subtraction unit that computes a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

a full sub-DCT-II unit that computes a full sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

a full sub-DCT-III unit that computes a full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs; and

a scaling unit that multiples output of sub-DCT-III by one or more scale factors to generate a first full set of outputs;

wherein the full DCT-II unit reorders the first full set of outputs and the second set of outputs to generate output values of the DCT-II.

33. A non-transitory computer-readable medium comprising instructions for causing a processor to:

determine whether a size of a full DCT-II to perform is a multiple of two; and

in response to determining that the size of the full DCT-II to perform is a multiple of two, perform the full DCT-II,

wherein the instructions that cause the processor to perform the full DCT-II include instructions that cause the processor to;

compute a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

reverse an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

compute a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

compute a full sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

compute a full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs;

multiply the first set of outputs by one or more scale factors to generated a first full set of outputs; and

reorder the first full set of outputs and the second set of outputs to generate output values of the DCT-II.

34. An apparatus comprising:

means for determining whether a size of a full DCT-II to perform is a multiple of two; and

means for performing, in response to determining that the size of the full DCT-II to perform is a multiple of two, the full DCT-II,

wherein the means for performing the full DCT-II includes;

means for computing a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

means for reversing an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

means for computing a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

means for computing a full sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

means for computing a full sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs;

means for multiplying the first set of outputs by one or more scale factors to generated a first full set of outputs; and

means for reordering the first full set of outputs and the second set of outputs to generate output values of the DCT-II.

35. A method of performing a discrete cosine transform of type III (DCT-III), the method comprising:

determining, with an apparatus, whether a size of the DCT-III to perform is a multiple of two; and

in response to determining that the size of the DCT-III to perform is a multiple of two, performing, with the apparatus, the DCT-III,

wherein performing the DCT-III includes performing an inverse of a DCT of type II (DCT-II), and

wherein performing the DCT-II includes;

computing a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

reversing an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

computing a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

computing a sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

computing a sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs; and

reordering the first and second set of outputs produced by the respective sub-DCT-II and sub-DCT-III to generate output values of the DCT-II.

36. A media coding device comprising:

a DCT-III unit that determines whether a size of a DCT-III to perform is a multiple of two, and in response to determining that the size of the DCT-III to perform is a multiple of two, performs the DCT-III,

wherein the DCT-III unit performs an inverse of a DCT of type II (DCT-II) performed by a DCT-II unit,

wherein, to perform the DCT-II, the DCT-II unit includes;

a butterfly unit that computes a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly unit includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

an order reversal unit that reverses an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

a recursive subtraction unit that computes a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

a sub-DCT-II unit that computes a sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

and

a sub-DCT-III unit that computes a sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs,

wherein the DCT-II unit reorders the first and second set of outputs produced by the respective sub-DCT-II and sub-DCT-III to generate scaled output values of the DCT-II.

37. A non-transitory computer-readable medium comprising instructions for causing a processor to:

determine whether a size of the DCT-III to perform is a multiple of two; and

in response to determining that the size of the DCT-III to perform is a multiple of two, perform the DCT-III,

wherein the instructions cause the processor to perform the DCT-III by performing an inverse of a DCT of type II (DCT-II) performed by;

computing a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

reversing an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

computing a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

computing a sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

computing a sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs; and

reordering the first and second set of outputs produced by the respective sub-DCT-II and sub-DCT-III to generate output values of the DCT-II.

38. An apparatus comprising:

means for determining whether a size of a DCT-III to perform is a multiple of two; and

means for performing, in response to determining that the size of the scaled DCT-II to perform is a multiple of two, the DCT-III,

wherein the means for performing the DCT-III includes means for performing an inverse of a DCT-II performed by;

computing a butterfly that includes cross-additions and cross-subtractions of inputs to the DCT-II, wherein the butterfly includes a first portion that cross-adds a first sub-set of the inputs and a second portion that cross-subtracts a second sub-set of the inputs;

reversing an order of the second sub-set of cross-subtracted inputs to generate a reverse-ordered second sub-set of the inputs;

computing a series of recursive subtractions that each recursively subtract the reverse-ordered second sub-set of the inputs to generate a recursively subtracted second sub-set of the inputs;

computing a sub-DCT-II that receives the first sub-set of the inputs and generates a first set of outputs based on the first sub-set of the inputs;

computing a sub-DCT-III that receives the recursively subtracted second sub-set of the inputs and generates a second set of outputs based on the recursively subtracted second sub-set of the inputs; and

reordering the first and second set of outputs produced by the respective sub-DCT-II and sub-DCT-III to generate output values of the DCT-II.