Computationally efficient transforms for video coding

This paper describes the construction of computationally efficient transforms which can significantly reduce the complexity of a video decoder without loss in compression efficiency. In particular, these inverse transforms can be implemented using purely 16-bit arithmetic with similar rate-distortion performance to a 32-bit or floating point transform. To allow for variable block size coding, four 2D transforms are considered: one each for 8&8, 8&4, 4&8 and 4&4 blocks respectively. The design criteria for a pure 16 bit arithmetic implementation of the inverse transform are introduced, and used to derive the only useful set of transforms under these conditions. These transforms have been used in the WMV9/VC-1 codec to achieve significant reduction in computational complexity.