1990/01/01 by Pierre Duhamel · 3 citations
Computer Science · #Digital Filter Design and Implementation #Numerical Methods and Algorithms #Cryptography and Residue Arithmetic
paper · doi:10.1109/29.60070
openalex publication_date 1990/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In a previous work (see Electron. Lett., vol.20, no.17, p.690, 1984), the author described an algorithm that computes a length-2/sup n/ discrete Fourier transform using 2/sup 2+1/-2n/sup 2/+4n-8 nontrivial (i.e. not=+or-j=+or- square root -1) complex multiplications. In the present work, it is first shown that this algorithm actually provides the attainable lower bound on the number of complex multiplications. A slight modification of the last step of this algorithm is also shown to provide the attainable lower bound on the number of real multiplications. A connection with the split-radix FFT algorithm (SRFFT) is then explained, showing that SRFFT is another variation of these optimal algorithms, where the last step is computed recursively from shorter FFTs in a suboptimal manner. Finally, once the connection between the minimal complexity and SRFFT (which is the best known practical algorithm) is understood, it provides useful information on the possibility of further improvements of the SRFFT.>