Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Быстрое преобразование Фурье





Быстрое преобразование Фурье(БПФ, fast Fourier transform – FFT). Он базируется на том, что при вычислениях среди множителей (синусов и косинусов) есть много периодически повторяющихся значений (в силу периодичности функций). Алгоритм БПФ группирует слагаемые с одинаковыми множителями в пирамидальный алгоритм, значительно сокращая число умножений за счет исключения повторных вычислений. В результате быстродействие БПФ в зависимости от N может в сотни раз превосходить быстродействие стандартного алгоритма. При этом следует подчеркнуть, что алгоритм БПФ даже точнее стандартного, т.к. сокращая число операций, он приводит к меньшим ошибкам округления.

Допустим, что массив чисел sk содержит N = 2r отсчетов (r - целое). Разделим исходный массив на два первых промежуточных массива с четными и нечетными отсчетами:

sk' = s2k, sk" = s2k+1, 0 £ k £ N/2-1.

Выполним ДПФ каждого массива с учетом того, что шаг функций равен 2 (при Dt=1), а период промежуточных спектров будет соответственно равен N/2:

sk' Þ Sn', sk" Þ Sn", 0 £ n £ N/2-1.

Для получения одной половины искомого спектра Sn сложим полученные спектры с учетом теоремы запаздывания, т.к. отсчеты функции sk" сдвинуты относительно sk' на один шаг дискретизации:

Sn = Sn'+Sn"×exp(-j2pn/N). (8.6)

Вторая половина спектра, комплексно сопряженная с первой, с учетом периода повторения N/2 промежуточных спектров определяется выражением:

Sn+N/2 = Sn'+Sn"×exp(-j2p(n+N/2)/N) = Sn'- Sn"×exp(-j2pn/N). (8.7)

Нетрудно видеть, что для вычисления полного спектра в данном случае потребуется N2/4 операций для вычисления промежуточных спектров плюс еще N операций комплексного умножения и сложения, что создает ощутимый эффект по сравнению с ДПФ.

Но деление массивов на две части может быть применено и к первым промежуточным массивам, и ко вторым, и т.д. до тех пор, пока в массивах не останется по одному отсчету, фурье - преобразование которых равно самому отсчету. Тем самым, алгоритм преобразования превращается в пирамидальный алгоритм перестановок со сложением/вычитанием и с единичным умножением на значение exp(-j2pn/N) соответствующего уровня пирамиды. Первый алгоритм БПФ на данном принципе (из множества модификаций, существующих в настоящее время) был разработан Кули-Тьюки в 1965 г. и позволил повысить скорость вычислений в N/r раз по сравнению с ДПФ. Чем больше N, тем больше эффект БПФ. Так, при N = 1024 имеем r = 10 и соответственно N/r »100. Что касается условия по количеству точек N = 2r, то оно рассматривается в варианте Nk £ 2r, где r - минимальное целое. Массивы с Nk < 2r дополняется до 2r нулями, что не изменяет форму спектра. Изменяется только шаг Dw по представлению спектра (Dw = 2p/2r < 2p/N), который несколько избыточен по адекватному представлению сигнала в частотной области. В настоящее время существуют и алгоритмы БПФ с другими основаниями и их комбинациями, при которых не требуется дополнения сигналов нулями до 2r. Пример выполнения БПФ приведен на рис. 8.5.



Рис. 8.5. Пример БПФ

Заметим, что в соответствии с (8.7) отсчеты, сопряженные с правой половиной главного частотного диапазона (0, p), относятся не к диапазону (-p,0), а к диапазону (p,2p), что, учитывая периодичность спектра дискретных данных, значения не имеет. Т.е. выходной частотный диапазон БПФ равен (0, 2p). Общее количество отсчетов комплексного спектра в этом условно главном диапазоне равно количеству точек исходного сигнала (с учетом нулевых точек при дополнении сигнала до N=2r). Алгоритм быстрого обратного преобразования (ОБПФ) тождественен алгоритму прямого БПФ.

Алгоритмы прямого и обратного БПФ широко используются в современном программном обеспечении для анализа и обработки цифровых данных.





Дата добавления: 2014-01-03; Просмотров: 1393; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.018 сек.