Citation
Abstract
Computational savings in hardware and software mechanizations of the Fast Fourier Transform (FFT) can be obtained by two methods: the first method, generalizable for N a power of 2, exploits the intrinsic simplicity of multiplication by j (unit imaginary), in addition to the periodicity and half-period negation identities usually employed. The second method, outlined for the case N = 16 only, exploits the quadrantal symmetries of the real cosine and sine functions in an implementation of the complex FFT which uses only real multiplications. The first method requires N/2 log. N/8 + 2 nontrivial complex multiplications, or 10 complex multiplications at N = 16. The second method requires only 12 realcoefficient multiplications at N = 16 to achieve the same result, but a generalization to higher N is not presently known. N even of —j) nf 20/N (NIA) — 5 (3)
Details
- Volume
- 42-32
- Published
- April 15, 1976
- Pages
- 123–138
- File Size
- 1.3 MB