DSP - круговая свертка DFT

Возьмем две последовательности конечной длительности x 1 (n) и x 2 (n), имеющие целую длину как N. Их ДПФ равны X 1 (K) и X 2 (K) соответственно, что показано ниже -

$$ X_1 (K) = \ sum_ {n = 0} ^ {N-1} x_1 (n) e ^ {\ frac {j2 \ Pi kn} {N}} \ quad k = 0,1,2 .. .N-1 $$ $$ X_2 (K) = \ sum_ {n = 0} ^ {N-1} x_2 (n) e ^ {\ frac {j2 \ Pi kn} {N}} \ quad k = 0 , 1,2 ... N-1 $$

Теперь мы попытаемся найти ДПФ другой последовательности x 3 (n), которая задается как X 3 (K)

$ X_3 (K) = X_1 (K) \ раз X_2 (K) $

Взяв IDFT из вышеизложенного, мы получаем

$ x_3 (n) = \ гидроразрыва {1} {N} \ displaystyle \ sum \ limits_ {n = 0} ^ {N-1} X_3 (K) e ^ {\ frac {j2 \ Pi kn} {N}} $

После решения вышеуказанного уравнения, наконец, мы получаем

$ x_3 (n) = \ displaystyle \ sum \ limits_ {m = 0} ^ {N-1} x_1 (m) x_2 [((nm)) _ N] \ quad m = 0,1,2 ... N- 1 $

Пункты сравнения Линейная свертка Круговая свертка
Смещение Линейное переключение Круговое переключение
Образцы в результате свертки $ N_1 + N_2−1 $ $ Макс (N_1, N_2) $
Поиск отклика фильтра Возможный Возможно с нулевым отступом

Методы круговой свертки

Как правило, есть два метода, которые используются для выполнения круговой свертки, и они:

  • Метод концентрического круга,
  • Матричный метод умножения.

Метод концентрического круга

Пусть $ x_1 (n) $ и $ x_2 (n) $ - две заданные последовательности. Шаги, выполняемые для круговой свертки $ x_1 (n) $ и $ x_2 (n) $, следующие:

  • Возьмите два концентрических круга. Нанесите N образцов $ x_1 (n) $ на окружность внешнего круга (сохраняя равное расстояние между точками) в направлении против часовой стрелки.

  • Для построения $ x_2 (n) $ постройте N выборок $ x_2 (n) $ по часовой стрелке на внутреннем круге, начальный образец помещен в ту же точку, что и 0- й образец $ x_1 (n) $.

  • Умножьте соответствующие образцы на двух кругах и сложите их, чтобы получить результат.

  • Поворачивайте внутренний круг против часовой стрелки по одному образцу за раз.

Матричный метод умножения

Матричный метод представляет две заданные последовательности $ x_1 (n) $ и $ x_2 (n) $ в матричной форме.

  • Одна из заданных последовательностей повторяется посредством циклического сдвига по одной выборке за раз, чтобы сформировать матрицу NXN.

  • Другая последовательность представлена ​​как матрица столбцов.

  • Умножение двух матриц дает результат круговой свертки.