Категория
Информатика
Тип
реферат
Страницы
4 стр.
Дата
01.08.2013
Формат файла
.doc — Microsoft Word
Архив
860055.zip — 222.36 kb
  • bystroe-preobrazovanie-fure_860055_1.doc — 468.5 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Быстрое преобразование Фурье (БПФ) - это алгоритм вычисления преобразования Фурье для дискретного случая. В отличие от простейшего алгоритма, который имеет сложность порядка O(N
2 ), БПФ имеет сложность всего лишь O(Nlog
2 N). Алгоритм БПФ был впервые опубликован в 1965 году в статье Кули (Cooly) и Тьюки (Tukey).

Данное пособие содержит исходный код работающей программы для вычисления БПФ, подробное объяснение принципа ее работы и теоретическое обоснование. Все это можно найти и на других ресурсах, но трудно найти именно в таком комплекте: и программа, и объяснения, и теория, и на русском языке.

Если у вас нет времени и желания разбираться с теорией, то можете сразу скопировать текст программы на C++. Здесь находится заголовочный файл fft.h и исходник fft.cpp для быстрого преобразования Фурье для числа отсчетов, равного степени двойки. Вызывать надо функцию fft. А здесь находится заголовочный файл и исходник для произвольного (!) числа отсчетов. Он чуть медленнее, но скорость там тоже порядка Nlog
2 N. Вызывать надо функцию universal_fft.

Определение 1 .

Дана конечная последовательность x
0 , x
1 , x
2 ,...,x
N-1 (в общем случае комплексных). Дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности X
0 , X
1 , X
2 ,...,X
N-1 элементы которой вычисляются по формуле:

    (1).



Определение 2 .

Дана конечная последовательность X
0



Ваше мнение



CAPTCHA