August 1999
Intermediate to advanced
328 pages
8h 50m
English
Content preview from Voice Over IPBecome an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
Start your free trial
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 ...