FAST FOURIER TRANSFORM (FFT) OPERATIONS
Fast Fourier Transform (FFT) operations are commonly used in DSPs. They were developed in the 1970s to reduce the number of operations in the multiplication of numbers [CRAN97], [4] which is a common operation in digital telephony. Consider two D-digit numbers x and y. The conventional multiplication of x and y consists of multiplying each successive digit of x by every digit of y and then adding the resulting columns. The process takes D2 operations. FFT reduces the number of operations to D log D. For example, if x and y were 1000-digit numbers, the conventional multiplication would take more than 1,000,000 operations. FFT reduces the number of operations to about 50,000.
[4] [CRAN97]. Crandall, Richard ...
Get Voice Over IP now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
