Vector coding algorithms for multidimensional discrete Fourier transform (Q2475397): Difference between revisions

A new fast algorithm for the multidimensional discrete Fourier transform (DFT) is presented, based on vector coding (VC) technique. Let \(N=2^n\) and \[ D^m_N := \{\alpha = (p_1, \ldots , p_m) : p_k \in \mathbb N_0, \;0 \leq p_k < N,\; k = 1 , \ldots , n \}. \] Then the \(m\)-dimensional DFT of length \(N\) has the form \[ X (\alpha ) = \sum_{\beta \in D_N^m }x(\beta) w^{\alpha \cdot \beta}_N , \quad w_N = \exp (-2\pi i/N). \] The vector coding technique is based on the observation that any vector \(\alpha \in D^m_N \) can be uniquely represented by \( \alpha = 2^0 \alpha_0 + 2^1 \alpha_1 + \ldots + 2^{n-1}\alpha_{n-1}\) where \(\alpha_k \in D^m_2\). The resulting algorithm can be seen as a direct generalization of the algorithm of \textit{J. W. Cooley} and \textit{J. W. Tukey} [Math. Comput. 19, 297--301 (1965; Zbl 0127.09002)], and it has a very simple structure. The radix-2 VC algorithm needs \(mN^m \log_2N\) additions and at most \((1-1/2^m) N^m \log_2 N \) multiplications. The radix-4 VC algorithm requires the same number of additions and only \({1 \over 2}(1-1/4^m)N^m\log_2N\) multiplications.