Навигация
Алгоритм фильтрации, пример на основе БПФ
36424
знака
11
таблиц
11
изображений
РЕФЕРАТ
по дисциплине «Анализ временных рядов»
на тему:
«Алгоритм фильтрации, пример на основе БПФ»
СОДЕРЖАНИЕ
Введение
1. Основы алгоритмов БПФ
2. Алгоритм БПФ с прореживанием по времени
3. Программа и пример реализации алгоритма БПФ с прореживанием по времени
4. Алгоритм БПФ с прореживанием по частоте
5. Применение метода БПФ для вычисления обратного ДПФ (ОДПФ)
6. Применение БПФ для вычисления реакции ЦФ
7. Другие быстрые алгоритмы вычисления дискретного преобразования Фурье
7.1 Обобщенный алгоритм Кули-тьюки с произвольным основанием с множителями поворота
7.2 Алгоритм простых множителей
7.3 Алгоритм винограда
8. Анализ точности реализации алгоритмов БПФ
Заключение
Список использованных источников
ВВЕДЕНИЕ
В основе преобразования Фурье (ПФ) лежит чрезвычайно простая, но исключительно плодотворная идея – почти любую периодическую функцию можно представить суммой отдельных гармонических составляющих (синусоид и косинусоид с различными амплитудами A, периодами Т и, следовательно, частотами ω).
Неоспоримым достоинством ПФ является его гибкость – преобразование может использоваться как для непрерывных функций времени, так и для дискретных.
ПФ часто применяется при решении задач, возникающих в теории автоматического регулирования и управления, в теории фильтрации и т.д. Разберем один из примеров. Имеется некий линейный фильтр – изготовленный то ли в виде набора спаянных между собой резисторов, конденсаторов и катушек индуктивности, то ли в виде модульной конструкции интегральных микросхем. Известен также входной сигнал (на рис. 1 в качестве входного сигнала изображена дельта-функция, то есть импульс исчезающе короткой длительности и бесконечно большой амплитуды). Необходимо определить, какой сигнал появится на выходе нашего фильтра.
Рисунок 1 - Исследование линейного фильтра
Ход решения этой задачи зависит от того, какую позицию мы предпочтем. Выберем временной путь решения (верхняя половина рис. 2) – придется входной сигнал записать как функцию времени SBX(t) и использовать импульсную характеристику фильтра h(t), то есть математическую запись его работы во времени. Отправимся по частотному пути (нижняя половина рис. 2) – нужно будет оперировать уже не с самим входным сигналом, а с его спектром gbx(ω). Δа и алгоритм работы нашего фильтра потребуется представить в частотной области – в виде частотной характеристики K(ω). Δля этого воспользуемся помощью «магического стекла» ПФ.
Рисунок 2 - Быстрое преобразование Фурье
Итак, два пути – какой из них избрать? По-видимому, тот, который проще. Во всяком случае, в большинстве практических задач предпочтение отдается частотному направлению.
Если выполнять ДПФ входной последовательности, впрямую – строго по исходной формуле, то потребуется много времени (особенно если количество входных отсчетов велико). Конструктивнее использовать принцип «разделяй и властвуй», лежащий в основе алгоритма БПФ. Согласно ему входная последовательность делится на группы (например, четные и нечетные отсчеты), и для каждой из них выполняется ДПФ, а затем полученные результаты объединяются. В итоге получается ДПФ входной последовательности – и существенная экономия времени. Поэтому описанный алгоритм так и назвали – быстрое преобразование Фурье.
В данном реферате рассмотрим более подробно быстрое преобразование Фурье.
1. ОСНОВЫ АЛГОРИТМОВ БПФ
Дискретное преобразование Фурье (ДПФ) X(k) конечной последователъности х(пТ), п=О, 1,..., N-1 определяется согласно (1.1), (1.2):
(1.1)
(1.2)
 |
причем является 
периодической последовательностью с периодом N, так как 
т=О, 
1, 2… Непосредственное вычисление ДПФ (5.1) при комплексных значениях х(пТ) требует для каждого значения k (N - 1) умножений и (N - 1) сложений комплексных чисел или 4 (N -1) умножений и (2N - 2) сложений действительных чисел, а для всех N значений k=0, 1,…, N -1 требуется примерно N2 умножений и N2 сложений комплексных чисел. Таким образом, для больших значений N (порядка нескольких сотен или тысяч) прямое вычисление ДПФ (1.1) требует выполнения весьма большого числа арифметических операций умножения и сложения, что затрудняет реализацию вычисления в реальном масштабе времени процессов и спектров.
Быстрым преобразованием Фурье называют набор алгоритмов, реализация которых приводит к существенному уменьшению вычислительной сложности ДПФ (1.1). Исходная идея этих алгоритмов состоит в том, что N-точечная последовательность разбивается, на две более короткие, например на две (N/2)точечные последовательности, вычисляются ДПФ для этих более коротких последовательностей и из этих ДПФ конструируется ДПФ исходной последовательности. Для двух (N/2)-точечных последовательностей требуется примерно 
умножений комплексных чисел, т. е. число умножений (а также сложений) уменьшается примерно в 2 раза. Аналогично вместо вычисления ДПФ (Н/2)-точечной последовательности можно вычислить ДПФ для двух (Н/4)-точечных последовательностей и таким образом вновь уменьшить требуемое число умножений и сложений. Если N=2v, v>O и целое, то процесс уменьшения размера ДПФ может быть продолжен до тех пор, пока не останутся только 2-точечные ДПФ. При этом общее число этапов вычисления ДПФ будет равно v=log2 N, а число требуемых арифметических операций для вычисления N-точечной ДПФ будет порядка Nv, т.е. уменьшается примерно в N/log2N раз. Так, при N=1000 для прямого вычисления ДПФ согласно (1.1) требуется примерно N2 = 106 операций комплексных умножений и сложений, а при использовании алгоритмов БПФ таких операций требуется всего порядка 104, т. е. объем вычислений сокращается примерно на два порядка.
Рассмотрим два алгоритма БПФ: с прореживанием по времени (в которых требуется перестановка отсчетов входной последовательности х(пТ)) и с прореживанием по частоте (в которых требуется перестановка отсчетов выходной последовательности Х(k)).
Похожие работы
... учесть введением в блок-схему дополнительного .источника шума [11]. Расстояние между отсчетами должно удовлетворять теореме Найквиста для двумерных колебаний [1]. Устройства для дискретизации и квантования изображений основаны на технике микроденситометрии. В подобных системах на пленку проектируется луч света с интенсивностью I1. Интенсивность I2 света, прошедшего сквозь пленку (или отраженного ...
... Интересным примером применения спецпроцессора СПФ СМ явилась обработка радиолокационных сигналов зондирования поверхности планеты Венера, которое проводилось со спутника. Глава 3. Применение цифровой обработки сигналов. 3.1 Шумоподавление для звука Звуковой сигнал, записываемый в реальных акустических условиях, часто содержит нежелательные шумы, которые могут порождаться окружающей средой ...
... , расположенной напротив одного из ушей, к точке, расположенной перед человеком. Дилэй применяется, прежде всего, в том случае, когда запись голоса или акустического музыкального инструмента, выполненную с помощью единственного микрофона, встраивают в стереофоническую композицию. Этот эффект служит основой технологии создания стереозаписей. Подробные рекомендации по применению задержки в этих ...
... построения оптических систем и сетей связи В результате изучения данной дисциплины студент должен: знать: принципы построения инфокоммуникационных сетей (ПК-1); основные характеристики первичных сигналов связи (ПК-3); принципы построения проводных и радиосистем передачи с частотным и временным разделением каналов (ПК-1); основные характеристики каналов и трактов (ПК-3); принципы построения ...
0 комментариев