Combined polynomial transform and radix-q algorithm for MD discrete W transform

The type-II r-dimensional discrete CV transform (rD-DWT-II) with size q(1)( l) X q(2)(l) X ... X q(r)(l), where q is an odd prime number, is converted into a series of one-dimensional (1-D) reduced DWT-IIs by using the multidi mensional polynomial transform and an index permutation. Then, a radix-q al gorithm and a cyclic convolution algorithm are presented for the computatio n of the I-D reduced DWT-IIs, The new fast algorithm substantially reduces the overall computational complexity compared with the row-column method. E specially, the number of multiplications required by the proposed algorithm for computing an rD-DWT-II is only 1/r times that needed by the commonly u sed row-column method.