Быстрое преобразование Фурье: различия между версиями
| [отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Bezik (обсуждение | вклад) стилевые правки (дедидактизация, деаббревация, внос См. также и проч.), литература (-личные сайты и совсем прикладное) |
|||
Строка 8:
Дискретное преобразование Фурье преобразует набор чисел <math>a_0, \dots, a_{n-1}</math> в набор чисел <math>b_0, \dots, b_{n-1}</math>, такой, что <math>b_i=\sum_{j=0}^{n-1}a_j\varepsilon^{ij}</math>, где <math>\varepsilon^n=1</math> и <math>\varepsilon^k\neq 1</math> при <math>0<k<n</math>.
Казалось бы, причем тут какой-то епсилон с одним верхним индексом, но автор думает, что все телепаты и сами догадаются. Основной шаг алгоритма состоит в сведении задачи для <math>N</math> чисел к задаче с меньшим числом. Для <math>N=pq, 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+j)i} </math>. (Эти выражения могут быть легко получены, если исходную сумму разбить на меньшее число сумм с меньшим числом слагаемых, а после полученные суммы привести к одинаковому виду путём сдвига индексов и их последующего переобозначения).
Таким образом:
| |||