Методы обработки сигналов

Размещено на http://www.allbest.ru/

Федеральное государственное образовательное учреждение Высшего профессионального образования

«Южный федеральный университет»

Учебно-методическое пособие

Методы обработки сигналов

М.М. Анишин

Оглавление

1. Алгоритм быстрого преобразования Фурье

2. БПФ с прореживанием по времени

3. БПФ с прореживанием по частоте

1. Алгоритм быстрого преобразования Фурье

Для вычисления одного коэффициента ДПФ по формуле (6) необходимо выполнить N комплексных умножений и сложений. Таким образом, расчет всего ДПФ, содержащего N коэффициентов, потребует N² пар операций «умножение-сложение». Число операций возрастает пропорционально квадрату размерности ДПФ. Однако, если N не является простым числом и может быть разложено на множители, процесс вычислений можно ускорить, разделив анализируемый набор отсчетов на части, вычислив их ДПФ и объединив результаты. Такие способы вычисления ДПФ называются быстрым преобразованием Фурье (БПФ) и повсеместно используются на практике.

При реализации БПФ возможно несколько вариантов организации вычислении в зависимости от способа деления последовательности отсчетов на части (прореживание по времени либо по частоте) и от того, на сколько фрагментов производится разбиение последовательности на каждом шаге (основание БПФ).

2. БПФ с прореживанием по времени

Рассмотрим идею БПФ с прореживанием по времени на примере деления набора отсчетов пополам.

Итак, пусть N -- четное число. Выделим в формуле (6) два слагаемых, соответствующих элементам исходной последовательности с четными и нечетными номерами:

(8)

Введем обозначения и , а также вынесем из второй суммы общий множитель

(9)

Две суммы в (9) представляют собой ДПФ последовательностей {у(т)} (отсчеты с четными номерами) и {z(m)} (отсчеты с нечетными номерами). Каждое из этих ДПФ имеет размерность N/2. Таким образом,

(10)

где и -- ДПФ соответственно последовательностей отсчетов с четными и нечетными номерами.

Так как ДПФ размерности N/2 дает лишь N/2 спектральных коэффициентов, непосредственно использовать формулу (10) можно только при 0 < n < N/2. Для остальных n (N/2 < n < N) следует воспользоваться периодичностью спектра дискретного сигнала (и, соответственно, периодичностью результатов ДПФ):

,

Следовательно при n ? N/2 формула (10) представляется в виде:

(11)

Процесс вычисления 8-точечного ДПФ путем разбиения его на два 4-точечных ДПФ иллюстрируется на рис. 5.

Рис. 5. Вычисление 8-точечного ДПФ с помощью двух 4-точечных ДПФ

Блоки, выполняющие на рис. 5. объединение результатов двух ДПФ, требуют дополнительных комментариев. Каждый такой блок имеет два входных и два выходных сигнала. Один из входных сигналов умножается на комплексную экспоненту , после чего суммируется со вторым входным сигналом и вычитается из него, формируя таким образом два выходных сигнала. Это соответствует реализации формул (10) и (11). Данная операция получила название «бабочки». Расшифровка ее структуры представлена на рис. 6.

Рис. 6. Условное обозначение «бабочки» БПФ с прореживанием по времени (слева) и ее структурная схема (справа)

Оценим количество операций, необходимое для вычисления ДПФ указанным способом. Каждое из двух ДПФ половинной размерности требует N²/4 операций. Кроме того, при вычислении окончательных результатов каждый спектральным коэффициент Z(n) умножается на экспоненциальный комплексный множитель. Это добавляет еще N/2 операций. Итого получается 2N²/4 + N/2 = N(N + l)/2, что почти вдвое меньше, чем при вычислении ДПФ прямым способом. преобразование фурье алгоритм сигнал

Если N/2 тоже является четным числом (то есть если N делится на 4), можно продолжить описанную процедуру, выразив результат через четыре ДПФ размерности N/4. Это позволяет еще больше сократить число требуемых вычислительных операций.

Наибольшая степень ускорения вычислений может быть достигнута при N = 2^k, в этом случае деление последовательностей на две части можно продолжать до тех пор, пока не получатся двухэлементные последовательности, ДПФ которых рассчитывается вообще без использования операций умножения (достаточно вычислить сумму и разность двух отсчетов). Число требуемых при этом пар операций «умножение -- сложение» можно оценить как Nlog₂(N). Таким образом, вычислительные затраты по сравнению с непосредственным использованием формулы (6) уменьшаются в N/log₂(N) раз.

3. БПФ с прореживанием по частоте

Формулы прямого и обратного ДПФ (6) и (7) отличаются только знаком в показателе экспоненты и множителем перед суммой. Поэтому можно получить еще один вариант алгоритма БПФ, выполнив преобразования, показанные на схеме рис. 5, в обратном порядке. Этот способ вычислений называется прореживанием по частоте. Покажем, как получить описание этого метода на основе формулы прямого ДПФ (6).

Разделим исходную последовательность {x(k)} на две следующие друг за другом половины (как и в предыдущем случае, N должно быть четным числом):

Из второй суммы можно выделить множитель

Этот множитель равен 1 или - 1 в зависимости от четности номера вычисляемого спектрального отсчета n, поэтому дальше рассматриваем четные и нечетные n по отдельности. После выделения множителя ±1 комплексные экспоненты в обеих суммах становятся одинаковыми, поэтому выносим их за скобки, объединяя, две суммы:

, (12)

(13)

Фигурирующие здесь суммы представляют собой ДПФ суммы и разности половин исходной последовательности, при этом разность перед вычислением ДПФ умножается на комплексные экспоненты ехр(-j2m/N). Каждое из двух используемых здесь ДПФ имеет размерность N/2.

Итак, при прореживании по частоте вычисления организуются следующим образом:

1. Из исходной последовательности {x(k)} длиной N получаются две последовательности {у(m)} и {z(m)} длиной N/2 согласно следующим формулам:

2. ДПФ последовательности {у(m)} дает спектральные отсчеты с четными номерами, ДПФ последовательности {z(m)} - с нечетными:

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

Процесс вычисления 8-точечного ДПФ путем разбиения его на два 4-точечных ДПФ с прореживанием по частоте показан на рис. 7.

Рис. 7. Вычисление 8-точечного ДПФ с помощью двух 4-точечных ДПФ путем прореживания по частоте

Поскольку комплексный экспоненциальный множитель в данном алгоритме применяется к результату вычитания двух сигналов, «бабочка» БПФ с прореживанием по частоте имеет несколько иную структурную схему (рис. 8.).

Рис. 8. Условное обозначение «бабочки» БПФ с прореживанием по частоте (слева и ее структурная схема (справа)

Размещено на Allbest.ru