Content deleted Content added
Citation bot (talk | contribs) Alter: journal, pages. Add: bibcode, url, doi, authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:FFT algorithms | #UCB_Category 17/17 |
m task, replaced: journal = IEEE Trans. On Acoustics, Speech and Signal Processing (ASSP) → journal = IEEE Trans. On Acoustics, Speech and Signal Processing |
||
Line 53:
By the construction of the factorization of ''z''<sup>''2''<sup>''n''</sup></sup>-''1'', the polynomials ''p''<sub>''s'',''m''</sub>(''z'') each encode 2<sup>''n''-''s''</sup> values
<math display="block">X_k=p(e^{2\pi i\tfrac{k}{2^n}})</math>
of the Fourier transform, for ''m''=0, the covered indices are ''k''=''0'', 2<sup>''k''</sup>, 2∙2<sup>''s''</sup>, 3∙2<sup>''s''</sup>,
During the transition to the next stage, the polynomial <math>p_{s,\ell}(z)</math> is reduced to the polynomials <math>p_{s+1,\ell}(z)</math> and <math>p_{s+1,2^s-\ell}(z)</math> via polynomial division. If one wants to keep the polynomials in increasing index order, this pattern requires an implementation with two arrays. An implementation in place produces a predictable, but highly unordered sequence of indices, for example for ''N''=16 the final order of the 8 linear remainders is (0, 4, 2, 6, 1, 7, 3, 5).
Line 81:
==References==
{{refbegin}}
* {{cite journal | first = Georg | last = Bruun | title = ''z''-Transform DFT filters and FFTs | journal = IEEE Trans. On Acoustics, Speech and Signal Processing
* {{cite book | first = H. J. | last = Nussbaumer | title = Fast Fourier Transform and Convolution Algorithms | publisher = Springer-Verlag | ___location = Berlin | year = 1990 }}
* {{cite journal | first = Yuhang | last = Wu | title = New FFT structures based on the Bruun algorithm | journal = IEEE Trans. ASSP | volume = 38 | issue = 1 | pages = 188–191 | year = 1990 | doi = 10.1109/29.45572 | url = https://backend.orbit.dtu.dk/ws/files/4601557/Wu.pdf }}
| |||