Search

9.2: The Prime Factor Algorithm
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/09%3A_The_Prime_Factor_and_Winograd_Fourier_Transform_Algorithms/9.02%3A_The_Prime_Factor_Algorithm
When the short DFT's are calculated by the very efficient algorithms of Winograd discussed in Factoring the Signal Processing Operators, the PFA becomes a very powerful method that is as fast or faste...When the short DFT's are calculated by the very efficient algorithms of Winograd discussed in Factoring the Signal Processing Operators, the PFA becomes a very powerful method that is as fast or faster than the best Cooley-Tukey FFT's. As in the Cooley-Tukey program, the DO 10 loop steps through the M stages (factors of N) and the DO 20 loop calculates the N/N1 length-N1 DFT's.
10.6: Generating Small FFT Kernels
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/10%3A_Implementing_FFTs_in_Practice/10.06%3A_Generating_Small_FFT_Kernels
For example, it is known that when the input of a DFT is real (and the output is hence conjugate-symmetric), one can save a little over a factor of two in arithmetic cost by specializing FFT algorithm...For example, it is known that when the input of a DFT is real (and the output is hence conjugate-symmetric), one can save a little over a factor of two in arithmetic cost by specializing FFT algorithms for this case—with genfft , this specialization can be done entirely automatically, pruning the redundant operations from the dag, to match the lowest known operation count for a real-input FFT starting only from the complex-data algorithm.
4.2: Rader's Conversion of the DFT into Convolution
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/04%3A_The_DFT_as_Convolution_or_Filtering/4.02%3A_Rader's_Conversion_of_the_DFT_into_Convolution
In this section a method quite different from the index mapping or polynomial evaluation is developed. Rather than dealing with the DFT directly, it is converted into a cyclic convolution which must t...In this section a method quite different from the index mapping or polynomial evaluation is developed. Rather than dealing with the DFT directly, it is converted into a cyclic convolution which must then be carried out by some efficient means. Those means will be covered later, but here the conversion will be explained. This method requires use of some number theory.
Front Matter
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/00%3A_Front_Matter
7.3: Algebraic Derivation of the Cooley-Tukey FFT
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/07%3A_DFT_and_FFT_-_An_Algebraic_View/7.03%3A_Algebraic_Derivation_of_the_Cooley-Tukey_FFT
Knowing the polynomial algebra underlying the DFT enables us to derive the Cooley-Tukey FFT algebraically. This means that instead of manipulating the DFT definition, we manipulate the polynomial alge...Knowing the polynomial algebra underlying the DFT enables us to derive the Cooley-Tukey FFT algebraically. This means that instead of manipulating the DFT definition, we manipulate the polynomial algebra.
5.2: The FFT from Factoring the DFT Operator
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/05%3A_Factoring_the_Signal_Processing_Operators/5.02%3A_The_FFT_from_Factoring_the_DFT_Operator
\[ $\begin{bmatrix} C(0)\\ C(1)\\ C(2)\\ C(3)\\ C(4)\\ C(5)\\ C(6)\\ C(7) \end{bmatrix}$ =\begin{bmatrix} W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0}\\ W^{0} & W^{1} & W^{2} & W^{3} & W^...\[ $\begin{bmatrix} C(0)\\ C(1)\\ C(2)\\ C(3)\\ C(4)\\ C(5)\\ C(6)\\ C(7) \end{bmatrix}$ =\begin{bmatrix} W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0}\\ W^{0} & W^{1} & W^{2} & W^{3} & W^{4} & W^{5} & W^{6} & W^{7}\\ W^{0} & W^{2} & W^{4} & W^{6} & W^{8} & W^{10} & W^{12} & W^{14}\\ W^{0} & W^{3} & W^{6} & W^{9} & W^{12} & W^{15} & W^{18} & W^{21}\\ W^{0} & W^{4} & W^{8} & W^{12} & W^{16} & W^{20} & W^{24} & W^{28}\\ W^{0} & W^{5} & W^{10} & W^{15} & W^{20} & W^{25} & W^{30} & W^{3…
12.4: Direct Fast Convolution and Rectangular Transforms
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/12%3A_Convolution_Algorithms/12.04%3A_Direct_Fast_Convolution_and_Rectangular_Transforms
In the case of index mapping with convolution, the multiplications must be nested together in the center of the algorithm in the same way as for the WFTA. It would first seem that applying the index m...In the case of index mapping with convolution, the multiplications must be nested together in the center of the algorithm in the same way as for the WFTA. It would first seem that applying the index mapping and optimal short algorithms directly to convolution would be more efficient than using DFTs and converting them to convolution to be calculated by the same optimal algorithms.
10.8: Numerical Accuracy in FFTs
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/10%3A_Implementing_FFTs_in_Practice/10.08%3A_Numerical_Accuracy_in_FFTs
Specifically, the roundoff error when adding up $n$ floating-point numbers in sequence grows as O ( n 2 ) O ( n 2 ) " role="presentation" style="position:relative;" tabindex="0"> $O(n)$ in the wor...Specifically, the roundoff error when adding up $n$ floating-point numbers in sequence grows as O ( n 2 ) O ( n 2 ) " role="presentation" style="position:relative;" tabindex="0"> $O(n)$ in the worst case, or as $O(\sqrt{n})$ O ( n ) O ( n ) " role="presentation" style="position:relative;" tabindex="0"> on average for random inputs (where the errors grow according to a random walk), but simply reordering these n-1 additions into a cascade summation yields O ( log n ) O ( log n ) " role="pr…
4.3: The Chirp Z-Transform or Bluestein's Algorithm
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/04%3A_The_DFT_as_Convolution_or_Filtering/4.03%3A_The_Chirp_Z-Transform_or_Bluestein's_Algorithm
The DFT of x(n)x(n) evaluates the Z-transform of x(n)x(n) on N equally spaced points on the unit circle in the z plane. Using a nonlinear change of variables, one can create a structure which is e...The DFT of x(n)x(n) evaluates the Z-transform of x(n)x(n) on N equally spaced points on the unit circle in the z plane. Using a nonlinear change of variables, one can create a structure which is equivalent to modulation and filtering x(n) by a “chirp" signal.
12: Convolution Algorithms
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/12%3A_Convolution_Algorithms
1: Fast Fourier Transforms
https://eng.libretexts.org/Bookshelves/Electrical_Engineering/Signal_Processing_and_Modeling/Fast_Fourier_Transforms_(Burrus)/01%3A_Fast_Fourier_Transforms

Search

Text Color

Text Size

Margin Size

Font Type

Support Center

How can we help?