Реферат Курсовая Конспект
Быстрое преобразование Фурье - раздел Математика, Быстрое преобразование Фурье В Соответствии С Формулой Прямого Дпф Для Определения N...
|
В соответствии с формулой прямого ДПФ для определения N значений X[k] требуется выполнить примерно N2 умножений и N2 сложений. С ростом N значительно возрастает время вычисления X[k]. Такая ситуация наблюдается и при вычислении ОДПФ. Для ускорения вычислений ДПФ разработаны алгоритмы быстрого преобразования Фурье (БПФ).
Рассмотрим алгоритмы БПФ с основанием 2, которые применяются к последовательностям длины N=2k, k – целое.
Основная идея БПФ состоит в следующем. Последовательность x[n] разбивают на две последовательности x1[n] и x2[n] длиной N/2 и находят для них X1[k] и X2[k]. Затем по значениям X1[k] и X2[k] определяют требуемое N – точечное ДПФ X[k]. Если последняя операция будет выполняться просто и не потребует сложных вычислений, то для вычисления N – точечного ДПФ потребуется выполнить (N/2)2+(N/2)2=N2/2 операций. Если продолжить процесс разбиения последовательностей x1[n] и x2[n] на две части и находить для каждой из них свои ДПФ, то можно существенно сократить количество операций.
Рассмотрим ДПФ последовательности x[n], полагая, что N равно степени 2:
(23)
Разобьем x[n] на две последовательности x1[n] и x2[n], содержащие соответственно четные и нечетные члены x[n]:
x1[n]=x[2n] , n=0,1,2,…..,(N/2 - 1);
x2[n]=x[2n+1], n=0,1,2,…..,(N/2 - 1).
Тогда
.
– Конец работы –
Эта тема принадлежит разделу:
Бит инверсный порядок Таблица N Двоичный номер бит инверсия бит инверсный номер... На всех этапах выполнения БПФ используются коэффициенты WNk k N Обычно указанные значения вычисляют до...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Быстрое преобразование Фурье
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов