Быстрое преобразование Фурье: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
→Основной алгоритм: исправил формулы |
→Основной алгоритм: Если вторая формула не используется зачем она нужна? |
||
Строка 13:
Основной шаг алгоритма состоит в сведении задачи для <math>N</math> чисел к задаче с меньшим числом. Пусть <math>N=pq</math>, <math>p>1,q>1</math>. Действуем над полем комплексных чисел: <math>\varepsilon_\nu=e^{2\pi i/\nu}</math>, <math>\varepsilon_\nu^{\nu}=1</math>, где <math>\nu</math> - любое число.
Дискретное преобразование Фурье может быть представлено в виде <math>b_i=\sum_{k=0}^{p-1}\sum_{j=0}^{q-1}a_{kq+j}\varepsilon_N^{(kq
(Эти выражения могут быть легко получено, если исходную сумму разбить на меньшее число сумм с меньшим числом слагаемых, а после, полученные суммы привести к одинаковому виду, путём сдвига индексов и их последующего переобозначения).
: <math>b_i = \sum_{k=0}^{p-1}\sum_{j=0}^{q-1}a_{kq+j}\varepsilon_N^{(kq+j)i}=\sum_{j=0}^{q-1} \varepsilon_N^{ij} (\sum_{k=0}^{p-1}a_{kq+j}\varepsilon_N^{kiq})</math>.
| |||