Линейная фильтрация на основе дискретного преобразования Фурье
DFT обеспечивает эффективный способ вычисления свертки во времени во времени двух сигналов.
Одним из наиболее важных применений дискретного преобразования Фурье (ДПФ) является вычисление свертки сигналов во временной области. Это может быть достигнуто путем умножения ДПФ-представления двух сигналов и последующего вычисления обратного ДПФ результата.
Вы можете сомневаться в эффективности этого метода, потому что мы заменяем операцию свертки двумя ДПФ, одним умножением и обратной DFT-операцией. Однако, поскольку существуют эффективные методы вычисления ДПФ, которые в совокупности называются быстрым преобразованием Фурье (БПФ), мы можем получить значительную экономию вычислений, используя ДПФ для выполнения свертки во временной области.
Обратите внимание, что разностное уравнение фильтра конечной импульсной реакции (FIR), повторенное ниже для удобства, фактически вычисляет свертку входной последовательности $$ x (n) $$ с коэффициентами фильтра $$ b_k $$:
$$ у (п) = \ sum_ {k = 0} ^ {M-1} B_ {K} х (пк) $$
Следовательно, метод на основе DFT может быть особенно полезен при реализации FIR-фильтра. Для фильтра длиннее, чем почти 64 кранов, метод на основе DFT был бы более вычислительно более эффективным, чем структуры прямой или каскадной формы (см. Последний раздел главы 18 этой книги).
В этой статье мы вкратце рассмотрим линейную свертку. Затем, указав некоторые наблюдения о линейной свертке и ДПФ, мы увидим, как ДПФ можно использовать для выполнения линейной свертки. Мы также увидим, что обратный ДПФ произведения ДПФ двух сигналов соответствует операции во временной области, называемой круговой сверткой.
Линейная свертка
Линейная свертка двух сигналов $$ x (n) $$ и $$ h (n) $$ определяется формулой
$$ у (п) = \ sum_ {к = - \ infty} ^ {+ \ infty} х (к) ч (пк) $$
Уравнение 1
Это основное уравнение, которое позволяет анализировать реакцию линейной временной инвариантной системы на произвольную входную последовательность $$ x (n) $$, имея только импульсный отклик системы $$ h (n) $$, В качестве примера предположим, что $$ x (n) $$ и $$ h (n) $$, как показано на рисунках 1 и 2 соответственно. Свертка этих двух сигналов будет такой, как показано на рисунке 3. Вы можете использовать функцию MATLAB conv () для проверки этого результата без участия в математике.
Рисунок 1
фигура 2
Рисунок 3. Свертка $$ x (n) $$ с $$ h (n) $$
Предположим, что $$ x (n) = 0 $$, когда $$ n <0 $$ или $$ n \ geq L $$, кроме того, $$ h (n) = 0 $$ для $$ n <0 $$ или $$ n \ geq K $$. Рассмотрим эту сумму свертки уравнения 1 в этих условиях и посмотрим, какие значения $$ n $$ будут давать $$ y (n) = 0 $$. Это поможет нам определить максимальное количество ненулевых значений, которое может иметь сумма свертки.
$$ y (n) $$ в уравнении 1 будет равным нулю, если $$ x (k) $$ или $$ h (nk) $$ равны нулю для данного $$ n $$. $$ x (k) $$ может быть отличным от нуля, только если $$ 0 \ leq k \ leq L-1 $$. Для этих значений $$ k $$ нам нужно, чтобы $$ h (nk) $$ равнялся нулю, чтобы сделать $$ y (n) = 0 $$. Это произойдет, если $$ n-kK-1 $$. Условие $$ n-kK-1 + k $$ вместе с $$ 0 \ leq k \ leq L-1 $$ дает $$ y (n) = 0 $$ для $$ n \ geq K + L-1 $ $. Это наше первое наблюдение, которое приводится ниже:
Наблюдение 1:
Предположим, что $$ x (n) = 0 $$, когда $$ n <0 $$ или $$ n \ geq L $$, кроме того, $$ h (n) = 0 $$ для $$ n <0 $$ или $$ n \ geq K $$. Тогда $$ y (n) = x (n) star h (n) $$ может быть отличным от нуля только для $$ 0 \ leq n \ leq K + L-2 $$. Иногда мы говорим так: если $$ x (n) $$ и $$ h (n) $$ - два сигнала длины $$ L $$ и $$ K $$ соответственно, то свертка этих два сигнала будут иметь длину $$ L + K-1 $$.
Примером этого наблюдения являются сигналы, показанные на рис. 1, 2 и 3. В этом случае мы имеем $$ L = 3 $$ и $$ K = 4 $$. Свертка этих двух сигналов представляет собой сигнал с ненулевыми значениями $$ L + K-1 = 3 + 4-1 = 6 $$.
Свертка во временной области с использованием анализа Фурье
Мы можем использовать анализ Фурье для вычисления свертки во временной области в частотной области. Выражаясь математически, мы имеем
$$ F {x (n) star h (n) } = X ( omega) H ( omega) $$
Уравнение 2
где $$ F {. } $$ обозначает операцию преобразования Фурье с дискретным временем (DTFT). И $$ X ( omega) $$ и $$ H ( omega) $$ являются DTFT $$ x (n) $$ и $$ h (n) $$ соответственно. С теоретической точки зрения уравнение 2 является очень важным результатом; однако мы не можем использовать это свойство на цифровом компьютере, потому что DTFT последовательности является непрерывной функцией $$ \ omega $$. Очевидным решением будет использование выборок DTFT, который называется ДПФ.
Чтобы применить ДПФ, мы должны иметь сигналы с конечной длительностью. Можем ли мы использовать на рис. 4 и 5 сигналы конечной длительности $$ x_1 (n) $$ и $$ h_1 (n) $$ для представления $$ x (n) $$ и $$ h (n) $$ Рисунок 1 и 2 соответственно «text-align: center;»> $$ X ( omega) = \ sum \ limits_ {n = - \ infty} ^ {+ \ infty} {x (n) {{e} ^ {-j \ omega n}}} = 1 + e ^ {- j \ omega} + e ^ {- j2 \ omega} $$
Уравнение 3
с трехточечным ДПФ $$ x_1 (n) $$, который
$$ X_ {1} (k) = \ sum \ limits_ {n = 0} ^ {2} {x (n) {{e} ^ {- j \ tfrac {2 \ pi} {3} kn}}} = 1 + {e} ^ {- j \ tfrac {2 \ pi} {3} k \ times 1} + {e} ^ {- j \ tfrac {2 \ pi} {3} k \ times 2} $$
Уравнение 4
Очевидно, что суммы уравнений 3 и 4 равны для $$ \ omega = \ tfrac {2 \ pi} {3} k $$, $$ k = 0,; 1,; 2 $$. Поскольку ДПФ последовательности с конечной длительностью дает образцы DTFT $$ x (n) $$, мы можем использовать $$ x_1 (n) $$ при применении ДПФ.
Рисунок 4. Конечная версия $$ x (n) $$
Рисунок 5. Конечная версия $$ h (n) $$
Чтобы использовать образцы DTFT в уравнении 2, нам нужно умножить данный образец $$ X ( omega) $$ на частоту $$ \ omega_i $$ на образец $$ H ( omega) $$ при той же частоты, то есть $$ H ( omega_i) $$. Следовательно, DFT $$ x (n) $$ должен давать те же частотные точки, что и DFT $$ h (n) $$.
Поскольку частотные точки N-точечного DFT являются нормированными частотами $$ \ tfrac {2 \ pi} {N} k $$, для $$ k = 0, 1, \ dots, N-1 $$, длина DFT должны быть одинаковыми как для $$ x (n) $$, так и для $$ h (n) $$. Однако, как показано на рис. 4 и 5, два сигнала $$ x_1 (n) $$ и $$ h_1 (n) $$ не обязательно имеют одинаковую длину. Чтобы сделать два сигнала одинаковой длины, мы можем вставлять нули в конец более короткого сигнала. Это называется нулевым дополнением.
Мы представляем нулевую версию $$ x_1 (n) $$ с $$ x_2 (n) $$, которая показана на следующем рисунке.
Рисунок 6. Нулевая версия $$ x_1 (n) $$
Сравнивая ДПФ $$ x_2 (n) $$ с DTFT $$ x (n) $$, мы можем легко проверить, что ДПФ сигнала с нулевым запасом дает четыре выборки DTFT в отличие от ДПФ $$ x_1 (n) $$, который дает только три выборки. Следовательно, метод нулевого заполнения увеличивает количество выборок, которые мы получаем от конкретного DTFT. В некоторых учебниках это делается так: zero-padding увеличивает вычислительное разрешение DFT.
Наблюдение 2:
Чтобы использовать образцы DTFT в уравнении 2, нам нужно умножить данный образец $$ X ( omega) $$ на частоту $$ \ omega_i $$ на образец $$ H ( omega) $$ при той же частоты, то есть $$ H ( omega_i) $$. Следовательно, длина DFT должна быть одинаковой как для $$ x (n) $$, так и для $$ h (n) $$. Если два сигнала не имеют одинаковой длины, мы можем вставить соответствующие нули в конце более короткого сигнала.
В приведенном выше примере мы вставили один ноль и достигли двух сигналов длиной четыре. Теперь мы можем вычислить четырехточечный ДПФ $$ h_1 (n) $$ и $$ x_2 (n) $$ и умножить их на поиск ДПФ свертки $$ h_1 (n) star x_2 (n) $$?
Чтобы ответить на этот вопрос, нам нужно рассмотреть важное свойство анализа DFT: предположим, что мы вычисляем N-точечный DFT конечной последовательности, такой как $$ x (n) $$, и получаем $$ X (k) $$. Хотя мы получаем $$ X (k) $$ как представление для конечной последовательности $$ x (n) $$, можно показать, что сигнал во временной области, соответствующий $$ X (k) $$ на самом деле является периодическим сигналом с периодом $$ N $$. Этот периодический сигнал может быть достигнут путем повторения значений конечной последовательности $$ x (n) $$ с периодом $$ N $$. Другими словами, один период этого периодического сигнала дает те же значения, что и $$ x (n) $$. (Пожалуйста, ознакомьтесь с этой статьей для подробного обсуждения периодического характера ДПФ.)
Основываясь на этом свойстве ДПФ, мы знаем, что четырехточечный ДПФ соответствует периодическому сигналу во временной области с периодом четыре. Следовательно, если мы умножим четырехточечный DFT $$ h_1 (n) $$ и $$ x_2 (n) $$, результат $$ H_1 (k) X_2 (k) $$ будет соответствовать времени - постоянный периодический сигнал с периодом четыре. Первоначально мы ожидали, что $$ H_1 (k) X_2 (k) $$ будет ДПФ $$ h_1 (n) x_2 (n) $$; однако это невозможно, потому что $$ h_1 (n) star x_2 (n) $$ является сигналом длины $$ L + K-1 = 3 + 4-1 = 6 $$ и, как правило, он не может быть представленный периодическим сигналом с периодом четыре.
Как вы могли догадаться, нам нужно вычислить N-точечный DFT $$ h_1 (n) $$ и $$ x_2 (n) $$ для $$ N \ geq L + K-1 = 6 $$, чтобы быть способный получить свертку $$ h_1 (n) star x_2 (n) $$ путем применения обратного DFT к произведению ДПФ $$ h_1 (n) $$ и $$ x_2 (n) $$. Ясно, что нам нужно будет вставить достаточно нулей, чтобы сделать как $$ x_2 (n) $$, так и $$ h_1 (n) $$ длины $$ N $$.
Наблюдение 3:
Если $$ x (n) $$ и $$ h (n) $$ - два сигнала длины $$ L $$ и $$ K $$ соответственно, то свертка этих двух сигналов будет иметь длину $ $ L + K-1 $$. Учитывая периодический характер анализа ДПФ, для вычисления свертки во временной области необходимы DFT более длинны, чем $$ L + K-1 $$, $$ x (n) star h (n) $$, с методом ДПФ, Обратите внимание, что мы не дали доказательства вышеуказанного утверждения, мы только показываем, что метод DFT для вычисления свертки во временной области требует, чтобы DFT были длиннее, чем $$ L + K-1 $$. Вы можете увидеть доказательство этого утверждения в учебниках (см. Раздел 3.4.1 этой книги).
Фактически, обратный ДПФ произведения ДПФ двух сигналов соответствует операции, называемой круговой сверткой во временной области. В остальной части статьи мы кратко рассмотрим круговую свертку.
Круговая свертка
Предположим, что $$ y_1 (n) $$ и $$ y_2 (n) $$ являются двумя сигналами конечной длительности длины $$ N $$. Тогда круговая свертка этих двух сигналов определяется как
$$ y_ {3} (n) = \ sum_ {n = 0} ^ {N-1} y_ {1} (n) y_ {2} big ((mn); по модулю; N \ big) $ $
Уравнение 4
где $$ m = 0, 1, \ dots, N-1 $$ и $$ (mn); modulo; N $$ представляет собой остаток деления $$ (mn) $$ на $$ N $$.
Предположим, что N-точечная DFT $$ y_1 (n) $$ и $$ y_2 (n) $$ равна $$ Y_1 (k) $$ и $$ Y_2 (k) $$ соответственно. Тогда можно показать, что $$ Y_1 (k) Y_2 (k) $$ является N-точечным ДПФ круговой свертки $$ y_1 (n) $$ и $$ y_2 (n) $$.
Теперь мы можем переформулировать наши выводы на основе круговой свертки: предположим, что $$ x (n) $$ и $$ h (n) $$ имеют длину $$ L $$ и $$ K $$ соответственно. Применяя N-точечный DFT к этим сигналам, получаем $$ X (k) $$ и $$ H (k) $$. Произведение $$ X (k) H (k) $$ является N-точечным DFT круговой свертки $$ x (n) $$ с $$ h (n) $$. Если $$ N \ geq L + K-1 $$, то круговая свертка приведет к значениям линейной свертки. Следовательно, мы можем вычислить N-точечный обратный DFT $$ X (k) H (k) $$ для вычисления линейной свертки $$ x (n) $$ с $$ h (n) $$.
Пример свертки на основе DFT
Предположим, что $$ x_1 (n) $$ и $$ h_1 (n) $$ показаны на рисунке 4 и 5. Мы будем применять метод на основе DFT для вычисления свертки этих двух сигналов. Чтобы избежать участия в математике, мы можем использовать функции MftLAB fft () и ifft () для вычисления DFT и обратного DFT. Как обсуждалось выше, нам нужны DTF длиннее $$ L + K-1 = 6 $$. Следующие строки кода будут вычислять свертку во временной области:
x = (1 1 1 0 0 0); % Эта строка определяет нулевую версию x1 (n)
h = (1 1 1 1 0 0); % Эта строка определяет нулевую версию h1 (n)
IFFT (. FFT (х) * FFT (ч)); % Эта строка вычисляет IDFT продукта ДПФ
Результатом будет:
1.0000 2.0000 3.0000 3.0000 2.0000 1.0000
который соответствует линейной свертке, которая была ранее показана на рисунке 3.
Резюме
- Одним из наиболее важных применений ДПФ является вычисление свертки сигналов во временной области.
- Для FIR-фильтра длиннее, чем около 64 кранов, метод на основе DFT будет более эффективен по сравнению с структурами прямой и каскадной формы.
- Если $$ x (n) $$ и $$ h (n) $$ - два сигнала длины $$ L $$ и $$ K $$ соответственно, то свертка этих двух сигналов будет иметь длину $ $ L + K-1 $$. Учитывая периодический характер анализа ДПФ, для расчета свертки во временной области с методом ДПФ требуются ДПФ, превышающие $$ L + K-1 $$.
Вспомогательная информация
Дизайн цифрового фильтра:
- FIR Filter Design by Windowing: концепции и прямоугольное окно
- Нежелательные эффекты функции окна в конструкции КИХ-фильтра
- Бартлетт против прямоугольного окна
- От параметров фильтра до оконных параметров в конструкции FIR Filter
- Проектирование FIR-фильтров с использованием метода выборки частоты
- Структуры для реализации конечных импульсных фильтров
Дискретное преобразование Фурье:
- Введение в дискретное преобразование Фурье
- Анализ результатов анализа DFT в обработке цифровых сигналов
- Утечка DFT и выбор функции окна
- Введение в быстрое преобразование Фурье