Реферат: Алгоритм фильтрации, пример на основе БПФ

Применение алгоритмов БПФ позволяет выполнить эффективное вычисление выходной последовательности у(пТ) ЦФ. С этой целью следует определить ДПФ H(k) и X(k) в N+M-1 точках для последовательностей h(пТ) и х(пТ), затем определить ДПФ Y(k)=H(k)X(k) выходной последовательности у(пТ). Вычисление у (пТ) по ОДПФ Y(k) выполняется, например, по алгоритму (5.3). Для вычисления ДПФ и ОДПФ используются алгоритмы БПФ. Отметим, что если длина М последовательности х(пТ) велика, то реализация упомянутого выше алгоритма вычисления у(пТ) связана со значительной временной задержкой (для накопления всех М выборок х(пТ) ). С целью уменьшения этой задержки можно входную последовательность х(пТ) разбить на отрезки x_i (пТ) каждый длиной L и обрабатывать каждый из них независимо от других. Представим

(6.2)

Тогда можно (6.1) записать в виде

(6.3)

Где частная свертка

(6.4)

Таким образом можно начинать расчет методами БПФ частных сверток и формировать у(пТ) путем соответствующего суммирования элементов частных сверток [2].

7. ДРУГИЕ БЫСТРЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

Кроме рассмотренных выше классических алгоритмов БПФ известных как алгоритмы Кули-Тьюки по основанию 2, известно множество других. Некоторые из них позволяют существенно повысить эффективность вычисления дискретного преобразовании Фурье. Так, алгоритмы Винограда при равном числе сложении требуют примерно в 5 раз меньше умножений, чем алгоритмы Кули-Тьюки.

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

Кратко рассмотрим только некоторые, наиболее важные алгоритмы, на основе которых впоследствии возникло множество различных эффективных модификаций. Это: 1) обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота; 2) алгоритм простых множителей Гуда-Винограда; 3) алгоритм Винограда.

Для простоты изложения везде будем полагать N=N₁ N₂ , где N - длина преобразования. Очевидно, приводимые ниже положения легко могут быть перенесены на более общий случай, когда

Обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота. Итак, пусть N=N₁ N₂ , гдеN₁ и N₂ - положительные целые. Покажем, что в этом случае вычисление исходного N-точечного ДПФ можно свести к вычислению N₁ N ₂ -точечных и N₂ N₁ -точечных ДПФ и N умножениям на множители поворота . Для этого в выражения для ДПФ (1.1)

(7.1)

где , необходимо сделать подстановку:

k=k₁ +k₂ N_2, k₁ =0, …., N₂ -1; k₂ =0, …., N₁ -1; (7.2)

n=n₁ +n₂ N_2, n₁ =0, …., N₂ -1; n₂ =0, …., N₂ -1. (7.3)

Рисунок 6 - Сигнальный граф алгоритма

Тогда ДПФ (7.1) преобразуется к виду

(7.4)

Таким образом, полученный алгоритм включает в себя две основные ступени: на первой ступени переставленные в соответствии с (7.3) входные выборки подвергаются N₂ -точечному преобразованию Фурье. На второй ступени производится вычисление N₁ -точечных ДПФ. Между первой и второй ступенями осуществляется операция поворота путем умножения на поворачивающие множители. Полученная последовательность на выходе ДПФ должна быть переставлена в соответствии с (7.2).

Пример 4. Пусть N=6, N₁ =3, N₂ =2. Положим k=k₁ +k₂ *2; n=n₁ + +n₂ *3; n₁ k₂ =0, 1,2; n₂ k₁ =0, 1.

Тогда

Соответствующий сигнальный граф алгоритма изображен на рис.6.

Рассмотренный подход может быть положен в основу синтеза алгоритмов БПФ Кули-Тьюки с произвольным постоянным основанием. Наибольшую популярность получили алгоритмы с основаниями 4 и 8, позволяющие повысить эффективность вычисления ДПФ по сравнению с классическими алгоритмами по основанию 2. Отметим, что алгоритмы с основанием 2 также могут быть получены с использованием рассмотренного подхода. Таким образом, рассмотренный метод синтеза является общим и позволяет синтезировать различные модификации алгоритма Кули - Тьюки с произвольными постоянным и смешанным основаниями.

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

В случае, когда N представимо произведением взаимно простых множителей, имеется возможность избавиться от поворачивающих множителей в разложении (7.4). Тем самым можно достигнуть еще большей экономии числа операций.