Реферат Курсовая Конспект
Дискретное преобразование Фурье - раздел Математика, Преобразование Фурье Основная Статья: Дискретное Преобразование Фурье...
|
Основная статья: Дискретное преобразование Фурье
Дискретное преобразование Фурье — преобразование конечных последовательностей (комплексных) чисел, которое, как и в непрерывном случае, превращает свёртку в поточечное умножение. Используется в цифровой обработке сигналов и в других ситуациях, где необходимо быстро выполнять свёртку, например, при умножении больших чисел.
Пусть — последовательность комплексных чисел. Рассмотрим многочлен . Выберем какие-нибудь n точек на комплексной плоскости . Теперь многочлену f(t) мы можем сопоставить новый набор из n чисел: . Заметим, что это преобразование обратимо: для любого набора чисел существует единственный многочлен f(t) степени не выше n − 1 с такими значениями в соответственно(см. Интерполяция).
Набор {fk} и называется дискретным преобразованием Фурье исходного набора {xk}. В качестве точек zk обычно выбирают корни n-й степени из единицы:
.
Такой выбор продиктован тем, что в этом случае обратное преобразование принимает простую форму, а также тем, что вычисление преобразования Фурье может быть выполнено особенно быстро. Так, в то время как вычисление свёртки двух последовательностей длины n напрямую требует порядка n2 операций, переход к их преобразованию Фурье и обратно по быстрому алгоритму может быть выполнен за O(nlogn) операций. Для преобразований Фурье свёртке соответствует покомпонентное умножение, которое требует лишь порядка n операций.
– Конец работы –
Эта тема принадлежит разделу:
На сайте allrefs.net читайте: "Преобразование Фурье"
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Дискретное преобразование Фурье
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов