Vector coding algorithms for multidimensional discrete Fourier transform
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.
- scientific article; zbMATH DE number 11434
- A fast algorithm for the \(n\)-D discrete cosine transform
- scientific article; zbMATH DE number 4164117
- A new two-dimensional fast cosine transform algorithm
- A generalized fast algorithm for n-D discrete cosine transform and its application to motion picture coding
- scientific article; zbMATH DE number 4009772
- The structure of vector radix fast Fourier transforms
- An efficient algorithm for the computation of the multidimensional discrete Fourier transform
- The vector-radix fast cosine transform: Pruning and complexity analysis
- scientific article; zbMATH DE number 3864463
- A new radix-6 FFT algorithm
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Effective implementations of multi-dimensional radix-2 FFT
- Extendible look-up table of twiddle factors and radix-8 based fast Fourier transform
- Fast computation of discrete Fourier transforms using polynomial transforms
- Fast Fourier transforms: A tutorial review and a state of the art
- Fault-tolerant algorithm for Fast Fourier Transform on hypercubes
- scientific article; zbMATH DE number 3155184 (Why is no real title available?)
- scientific article; zbMATH DE number 3967873 (Why is no real title available?)
- scientific article; zbMATH DE number 3584892 (Why is no real title available?)
- In-place butterfly-style FFT of 2-D real sequences
- On Computing the Discrete Fourier Transform
- Split vector-radix fast Fourier transform
- Vector computation of the discrete Fourier transform
- A 2-D vector excitation coding technique
- A fast vector quantization encoding algorithm using multiple projection axes
- An efficient algorithm for the computation of the multidimensional discrete Fourier transform
- Lossless coding of multichannel signals using optimal vector hierarchical decomposition
- The structure of vector radix fast Fourier transforms
This page was built for publication: Vector coding algorithms for multidimensional discrete Fourier transform
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2475397)
