Брза Фуријеова трансформација — разлика између измена
Садржај обрисан Садржај додат
м Bot: Migrating 25 interwiki links, now provided by Wikidata on d:q623950 (translate me) |
м reference; козметичке измене |
||
Ред 3:
За брзу Фуријеову трансформацију постоји и алгоритам у супротном смеру - [[инверзна брза Фуријеова трансформација]].
== Неформалан опис Кули-Туки алгоритма ==
Кули-Туки алгоритам се базира на идеји подели-па-владај (divide-and-conquer, енг.). Предуслов за његово извршавање је да број тачака (тачке измерене за неки сигнал, на пример) на којима се врши трансформација буде степен двојке. Како често можемо сами да изаберемо колико тачака хоћемо да узмемо, ово и не представља велику препреку.
Ред 9:
ДФТ израчунавамо тако што наше тачке (вектор) прво поделимо на два вектора, један који одговара компонентама изворног вектора са парним индексима, а други са непарним. Онда израчунамо ДФТ оба вектора и спојимо резултате. Притом користимо особине јединичног корена Фуријеове матрице. После понављамо [[рекурзија|рекурзивно]] поступак. Тиме можемо да ДФТ на крају израчунамо према сложености <math>O(\log(n) )</math> у времену.
== Формалан опис Кули-Туки алгоритма ==
Присетимо се дефиниције дискретне Фуријеове трансформације:
Ред 125:
* -{S. G. Johnson and M. Frigo, 2007. "[http://www.fftw.org/newsplit.pdf A modified split-radix FFT with fewer arithmetic operations]," ''IEEE Trans. Signal Processing'' '''55''' (1): 111–119.}-
* -{T. Lundy and J. Van Buskirk, 2007. "A new matrix approach to real FFTs and convolutions of length 2<sup>k</sup>," ''Computing'' '''80''' (1): 23-45.
* Kent, Ray D. and Read, Charles (2002). ''Acoustic Analysis of Speech''. ISBN 0-7693-0112-6. Cites Strang, G. (1994)/May–June). Wavelets. ''American Scientist, 82,'' 250-255.}-
* {{cite journal
|author=Jacques Morgenstern
Ред 160:
* -{Christos H. Papadimitriou, 1979, {{doi-inline|10.1145/322108.322118|Optimality of the fast Fourier transform}}, ''J. ACM'' '''26''': 95-102.}-
* -{D. Potts, G. Steidl, and M. Tasche, 2001. "[http://www.tu-chemnitz.de/~potts/paper/ndft.pdf Fast Fourier transforms for nonequispaced data: A tutorial]", in: J.J. Benedetto and P. Ferreira (Eds.), ''Modern Sampling Theory: Mathematics and Applications'' (Birkhauser).}-
* {{Cite book | author=Press WH, Teukolsky SA, Vetterling WT, Flannery BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | publication-place=New York | isbn=978-0-521-88068-8 | chapter=Chapter 12. Fast Fourier Transform | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=600|ref=harv}}
* {{cite journal
|author=Vladimir Rokhlin, Mark Tygert
Ред 216:
[[Категорија:Математичка анализа]]
[[Категорија:Дигитална обрада
| |||