FAST MULTIPLIERLESS INTEGER INVERTIBLE TRANSFORMS

This invention relates to the design and implementation of a large family of fast, efficient, hardware-friendly fixed-point multiplierless inverse discrete cosine transforms (IDCT) and the corresponding forward transform counterparts. All of the proposed structures comprises of butterflies and dyadic-rational lifting steps that can be implemented using only shift-and-add operations. The approach also allows the computational scalability with different accuracy-versus-complexity trade-offs. Furthermore, the lifting construction allows a simple construction of the corresponding multiplierless forward DCT, providing bit-exact reconstruction if properly pairing with our proposed IDCT. With appropriately-chosen parameters, all of the disclosed structures can easily pass IEEE-1180 test. The high-accuracy algorithm of the present invention is over 100 times more accurate than IEEE-1180 specifications, leading to practically drifting-free reconstruction in popular MPEG-2 and MPEG-4 codecs even at the lowest quantization setting.