Магистерская диссертация на тему: Алгоритм фильтрации, пример на основе БПФ

Введение

В основе преобразования Фурье <http://n-t.ru/tр/in/ucv.htm> (ПФ) лежит чрезвычайно простая, но исключительно плодотворная идея - почти любую периодическую функцию можно представить суммой отдельных гармонических составляющих (синусоид и косинусоид с различными амплитудами А, периодами Т и, следовательно, частотами ω).

Неоспоримым достоинством ПФ является его гибкость - преобразование может использоваться как для непрерывных функций времени, так и для дискретных.

ПФ часто применяется при решении задач, возникающих в теории автоматического регулирования и управления, в теории фильтрации и т.д. Разберем один из примеров. Имеется некий линейный фильтр - изготовленный то ли в виде набора спаянных между собой резисторов, конденсаторов и катушек индуктивности, то ли в виде модульной конструкции интегральных микросхем. Известен также входной сигнал (на рис. 1 в качестве входного сигнала изображена дельта-функция, то есть импульс исчезающе короткой длительности и бесконечно большой амплитуды). Необходимо определить, какой сигнал появится на выходе нашего фильтра.

Рисунок 1 - Исследование линейного фильтра

Ход решения этой задачи зависит от того, какую позицию мы предпочтем. Выберем временной путь решения (верхняя половина рис. 2) - придется входной сигнал записать как функцию времени SBX(t) и использовать импульсную характеристику фильтра h(t), то есть математическую запись его работы во времени. Отправимся по частотному пути (нижняя половина рис. 2) - нужно будет оперировать уже не с самим входным сигналом, а с его спектром gbx(ω). Δа и алгоритм работы нашего фильтра потребуется представить в частотной области - в виде частотной характеристики К(ω). Δля этого воспользуемся помощью "магического стекла" ПФ.

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

Итак, два пути - какой из них избрать? По-видимому, тот, который проще. Во всяком случае, в большинстве практических задач предпочтение отдается частотному направлению.

Если выполнять ДПФ входной последовательности, впрямую - строго по исходной формуле, то потребуется много времени (особенно если количество входных отсчетов велико). Конструктивнее использовать принцип "разделяй и властвуй", лежащий в основе алгоритма БПФ. Согласно ему входная последовательность делится на группы (например, четные и нечетные отсчеты), и для каждой из них выполняется ДПФ, а затем полученные результаты объединяются. В итоге получается ДПФ входной последовательности - и существенная экономия времени. Поэтому описанный алгоритм так и назвали - быстрое преобразование Фурье.

В данном реферате рассмотрим более подробно быстрое преобразование Фурье.

Оглавление

- Введение

- Основы алгоритмов БПФ

- Алгоритм БПФ с прореживанием по времени

- Программа и пример реализации алгоритма БПФ с прореживанием по времени

- Алгоритм БПФ с прореживанием по частоте

- Применение метода БПФ для вычисления обратного ДПФ ОДПФ

- Применение БПФ для вычисления реакции ЦФ

- Другие быстрые алгоритмы вычисления дискретного преобразования Фурье

- Обобщенный алгоритм Кули-тьюки с произвольным основанием с множителями поворота

- Алгоритм простых множителей

- Алгоритм винограда

- Анализ точности реализации алгоритмов БПФ Заключение

- Список использованных источников

Список литературы

1. Цифровая обработка сигналов: Учебн. Пособие для вузов/Л. М. Гольденберг, Б.Д. Матюшкин, М. Н. Поляк. - 2изд., перераб. и доп. - М.: Радио и связь, 1990. - 256 с.: ил.

2. Рабинер Л., Гоулд Б. Теория и применения цифровой обработки сигналов. - М.:Мир, 1978.-848с.

3. Макклеплан Д.Х., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов: Пер. с англ. - М.: Радио и связь, 1983.-264с.

4. Гольденберг Л.М., Матюшкин Б.Д., Поляк М. Н. Цифровая обработка сигналов: Справочник.- М.: Радио и связь, 1985. - 312с., ил.