3.2. Свертка с использованием БПФ
Для фильтрации сигналов с помощью нерекурсивного фильтра используется операция свертки исходного сигнала с импульсной характеристикой фильтра. Свертка представляет собой математический способ комбинирования двух сигналов для формирования третьего сигнала. Результирующим сигналом при свертке с ядром фильтра будет отфильтрованный сигнал [1-3].
Свертка является формальной математической операцией, такой же, как, например, умножение или сложение. Только оперирует она не с двумя числами, а с целыми массивами – сигналами.
Чаще всего сверткой пользуются для импульсного разложения сигналов, то есть рассматривают отдельные точки сигналов как импульсы. В этом случае длина выходного сигнала будет определяться как сумма длины входного сигнала и длины импульсной характеристики фильтра минус один отсчет. Формула для вычисления свертки таким способом следующая:
(5)
где x – входной сигнал из N отсчетов, h – импульсная характеристика линейной системы (в данном случае фильтра) длиной M точек, индекс i задается в интервале [0; N+M-1].
Несмотря на простоту программной реализации такого вычисления свертки, время расчета для достаточно больших выборок сигнала и ядра фильтра (как уже было сказано ранее, при свертке сигналов длительностью более 64-х точек) будет существенным, что немало важно для цифрового фильтра, работающего в режиме реального времени. Как было принято ранее, ядро разрабатываемого фильтра состоит из 511 точек. Поэтому эффективнее будет использовать другой метод вычисления свертки сигналов – с использованием быстрого преобразования Фурье [1].
Свертка с применением БПФ дает тот же результат, что и другие алгоритмы расчета свертки, но время выполнения вычислений значительно сокращается для больших выборок сигналов. Алгоритм БПФ-свертки значительно сложнее из-за необходимости программной реализации БПФ.
Свертка с использованием БПФ обрабатывает сигналы не во временной области, а в частотной. В этом случае используется такое свойство свертки, что перемножение частотных спектров сигналов по точкам дает в результате спектр сигнала, являющегося результатом свертки. Таким образом, если найти обратное преобразование Фурье от полученного спектра, то получится результирующий отфильтрованный сигнал во временной области.
Алгоритм свертки с использованием БПФ можно описать следующим образом. Исходный сигнал разбивается на сегменты длительностью, равной длине ядра фильтра M. Каждый такой временной отрезок увеличивается вдвое, и вторая половина заполняется нулями. То же самое применяется и к импульсной характеристике фильтра. За тем с помощью преобразования Фурье вычисляются спектры сегмента исходного сигнала и ядра фильтра, после чего полученные массивы перемножаются. Применение обратного преобразования Фурье к полученному массиву даст результат свертки сигналов. Но так как полученный результат вдвое больше исходного сегмента сигнала, то на выход фильтра подается только первая его половина, а вторую в дальнейшем необходимо суммировать с первой половиной результата свертки для следующего сегмента. Это так называемая свертка-БПФ с перекрытием. Описание быстрого преобразования Фурье дано в следующем разделе.
Из сравнения свертки сигналов во временной области и свертки с применением БПФ предпочтение для разработки данного проекта отдано второму способу. Это позволит использовать высокое быстродействие при фильтрации сигналов, предоставляемое алгоритмом БПФ.
В упрощенном виде схема алгоритма свертки сигналов с применением БПФ приведена на рис.5.
Рис. . Схема алгоритма БПФ-свертки сигналов
3.3. Алгоритм БПФ
Дискретное преобразование Фурье (далее ДПФ) заключается в определении по последовательности из N временных отсчетов сигнала {x0,x1,…,xN-1} (в общем случае комплексных) соответствующего частотного спектра {X0,X1,…,XN-1} – набора комплексных чисел, характеризующих сигнал в частотной области. Общая формула для вычисления ДПФ выглядит следующим образом:
(6)
Обратное ДПФ преобразует сигнал из частотной области во временную, то есть восстанавливает по спектру исходную последовательность дискретных отсчетов. Формула (7) задает общий вид обратного ДПФ:
(7)
Алгоритм БПФ – это оптимизированный по скорости способ вычисления ДПФ. Существуют различные варианты такого алгоритма. Но наибольшее распространение получил алгоритм БПФ для последовательности из N отсчетов, где N является степенью двойки. Его особенность заключается в том, что исходная последовательность разбивается определенным образом на два равных сегмента. Каждый полученный сегмент также делится пополам, и так до тех пор, пока не будут получены сегменты, состоящие из двух точек. ДПФ вычисляется последовательно для каждого отдельного сегмента по две точки, и результаты используются для подсчета ДПФ сегментов более высокого уровня, то есть тех, которые использовались до разбиения. Так, последовательно вычисляя ДПФ для меньших по размеру сегментов, получается преобразование для исходного сигнала. Высокая скорость алгоритма БПФ достигается за счет того, что вычисляется преобразование меньших по сравнению с исходной последовательностью сегментов. Доказано, что число комплексных умножений для применения такого алгоритма к последовательности из N отсчетов составит всего:
(8)
в то время как вычисление обычного ДПФ для той же последовательности потребовало количество умножений, равное
(9)
Видно, что для больших выборок (порядка тысячи точек и выше) преимущество в быстроте вычисления у алгоритма БПФ существенное.
Для разбиения исходной последовательности отсчетов на равные подмножества применяют два равноценных метода: прореживание по времени и прореживание по частоте [4]. Первый метод предполагает разбиение исходного множества в соответствии с номерами выборок (четные и нечетные). Второй метод использует разбиение сигнала на два равных подмножества строго по середине. Но в этом случае после проведенных вычислений возникает необходимость в правильной перестановке элементов полученного массива. Такая перестановка получила название двоичного реверсирования, так как чтобы определить правильный порядковый номер элемента в полученной последовательности, достаточно представить его индекс в двоичной форме и поменять местами биты в номере симметрично центра. Например, для 8-ми точек такая двоичная перестановка бит выглядит следующим образом:
000 001 010 011 100 101 110 111 (исходные номера)
000 100 010 110 001 101 011 111 (реверсированные номера)
В данном проекте принято решение о применении БПФ с прореживанием по частоте, то есть второй способ.
Базовой операцией при вычислении БПФ для двух точек А и В (в общем случае комплексных) является так называемая «бабочка». Схема вычисления такой операции в случае прореживания по частоте показана на рис.6.
Рис. . Операция "бабочка"
На рис.6 коэффициент определяется по формуле (10), где N – размер исходной выборки, k – номер по порядку операции «бабочка», применяемой последовательно к множеству отсчетов, начиная с 0:
(10)
Алгоритм БПФ с прореживанием по частоте можно описать следующим образом.
-
Разбить условно выборку на два сегмента и применить операцию «бабочка» (см. рис.6) попарно для всех элементов из первой половины и соответствующих им из второй половины, увеличивая коэффициент k (см. формулу (10)) на число 2i, где i – номер уровня разбиения сигнала на подмножества, начиная с 0.
-
Разбить каждое из полученных в п.1 множеств на две подвыборки, перейдя к новому уровню.
-
Увеличить номер уровня разбиения i на 1.
-
Повторять п.п.1-3 для каждого из полученных подмножеств до тех пор, пока не будут найдены ДПФ для подмножеств, состоящих из двух точек.
-
Провести прореживание по частоте для полученного множества элементов.
На рис.7 приведен пример БПФ с прореживанием по частоте для 8-точечного сигнала. Этот пример наглядно поясняет используемый алгоритм.
Рис. . Пример БПФ с прореживанием по частоте
Алгоритм обратного ПБФ аналогичен прямому и может быть реализован той же процедурой. Разница заключается только в том, что перед преобразованием необходимо в мнимой части каждого отсчета поменять знак на противоположный, а после преобразования разделить каждый элемент на количество отсчетов N (см. формулу 7).
|
