Швидке перетворення Фур'є: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
RLuts (обговорення | внесок) Скасування редагування № 16991922 користувача RLuts (обговорення) |
RLuts (обговорення | внесок) |
||
Рядок 51:
== Алгоритм Кулі-Тьюкі ==
{{детальніше|Алгоритм Кулі-Тьюкі}}
Найбільш розповсюдженим алгоритмом розрахунку FFT є алгоритм Кулі-Тьюкі, запропонований Джеймсом Кулі та Джоном Тьюкі в [[1965]] році. Як з'ясувалося згодом, цей алгоритм був винайдений [[Карл Фрідріх Гаус|Карлом Гаусом]] ще в [[1805]] році.
Рядок 58:
Дискретне перетворення Фур'є величини ''2n'' визначається як:
: <math>f_m = \sum_{k=0}^{2n-1} x_k \;e^{-\frac{2\pi i}{2n} mk }
\qquad
m = 0,\dots,2n-1. </math>
Якщо позначити вклади парних індексів як
: ''x'<sub>0</sub> = x<sub>1</sub>'', ''x'<sub>1</sub> = x<sub>2</sub>, …, x'<sub>n-1</sub> = x<sub>2n-2</sub>''
та їхні перетворення величини ''n'' як
: ''f'<sub>0</sub>, …, f'<sub>n-1</sub>'';
та вклади непарних індексів
: ''x"<sub>0</sub> = x<sub>1</sub>, x"<sub>1</sub> = x<sub>3</sub>, …, x"<sub>n-1</sub> = x<sub>2n-1</sub>''
та їхні перетворення величини ''n'' як
: ''f"<sub>0</sub>, …, f"<sub>n-1</sub>''.
тоді:
: <math>
\begin{align}
| |||