M1 N1

The forward or inverse Fourier transform of an Nx N image, computed directly with the preceding definitions, requires a number of complex multiplications and additions proportional to N2. By decomposing the expressions and eliminating redundancies, the fast Fourier transform (FFT) algorithm reduces the number of operations to the order of N log2N [5]. The computational advantage of the FFT is significant and increases with increasing N. When N = 64 the number of operations are reduced by an order of magnitude and when N = 1024, by two orders of magnitude.

0 0

Post a comment