Multidimensional polynomial transform algorithmfor multidimensional DFT
Lizhi Cheng, Yonghong Zeng · Electronics Letters · 2000
A method is presented for converting the m-dimensional discrete Fourier transform (MD-DFT) into a number of one-dimensional DFTs (1D-DFTs) by rearranging the order of the input sequence. The result of this conversion is that the number of multiplications for computing an m-dimensional DFT is only 1/m times that of the usually used row-column DFT algorithm. To reduce the number of additions, a multidimensional polynomial transform (MD-PT) is then used and a considerable saving in the number of addition operations is also achieved.