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

Author

Yonghong Zheng ; Bi, Guoan ; Kot, Alex C.

Author_Institution

Sch. of Electr. & Electron. Eng., Nanyang Technol. Inst., Singapore

Volume

49

Issue

3

fYear

2001

fDate

3/1/2001 12:00:00 AM

Firstpage

634

Lastpage

641

Abstract

The type-II r-dimensional discrete W transform (rD-DWT-II) with size q^l1×q^l2×···×^lr q where q is an odd prime number, is converted into a series of one-dimensional (1-D) reduced DWT-IIs by using the multidimensional polynomial transform and an index permutation. Then, a radix-q algorithm and a cyclic convolution algorithm are presented for the computation of the 1-D reduced DWT-IIs. The new fast algorithm substantially reduces the overall computational complexity compared with the row-column method. Especially, 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 used row-column method

Keywords

computational complexity; convolution; discrete Hartley transforms; polynomials; 1D reduced DWT-II; MD discrete W transform; computational complexity reduction; cyclic convolution algorithm; fast algorithm; index permutation; multidimensional discrete Hartley transform; multidimensional generalized discrete Hartley transform; multidimensional polynomial transform; multiplications; polynomial transform; radix-q algorithm; row-column method; Bismuth; Computational complexity; Discrete Fourier transforms; Discrete transforms; Discrete wavelet transforms; Motion analysis; Multidimensional signal processing; Multidimensional systems; Polynomials; Signal processing algorithms;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.905893

Filename

905893