Информатика / Цифровая обработка сигналов

Циклическая свёртка через дискретное преобразование Фурье

Циклическая свёртка возвращает N значений, обращаясь к индексам по модулю N. Она равна обратному ДПФ произведения спектров, а дополнение нулями позволяет получить линейную свёртку.

Опубликовано: 12 ноября 2026 г.Обновлено: 12 ноября 2026 г.

Формула

\begin{aligned}y[n]&=\sum_{m=0}^{N-1}x[m]\,h[(n-m)\bmod N],\\Y[k]&=X[k]H[k].\end{aligned}

Схема Где хвост линейной свёртки накладывается на начало

Значение 3 с линейным индексом 3 переходит в циклический индекс 0. Остальные столбцы совпадают.

Обозначения

$x[m], h[m]$: два блока длины N, ед. входов
$y[n]$: результат циклической свёртки, произведение ед. входов
$N$: общая длина блоков, отсчёты
$X[k], H[k], Y[k]$: ДПФ входов и результата, ед. соответствующих блоков
n, m, k: индексы блока или спектра, —

Условия применения

Обе последовательности приведены к общей длине N. Индекс по модулю берётся из 0,…,N−1. Произведение спектров верно для прямого ДПФ без множителя и обратного ДПФ с 1/N. Нули при дополнении ставятся после исходного блока.

Ограничения

Линейная свёртка последовательностей длины L и M может занимать L+M−1 отсчётов. Если блок короче, хвост накладывается на начало. Непрерывную обработку длинного потока дополнительно организуют блоковыми методами с перекрытием.

Подробное объяснение

Индекс h[(n−m) mod N] определяет, какой коэффициент импульсной характеристики умножить на x[m]. Когда n−m отрицателен, к индексу добавляется N. Благодаря этому начало результата может зависеть от последних значений входного блока.

Комплексная экспонента ДПФ периодична по индексу. Если подставить сумму свёртки в прямое преобразование, замена индекса по модулю сохраняет набор всех N слагаемых. Сумма распадается на два множителя, X[k] и H[k].

Для конечных последовательностей циклический результат равен линейной свёртке, свёрнутой по остаткам индексов. Например, отсчёт линейной свёртки с индексом N попадёт в индекс 0. Поэтому вклад за правой границей может как увеличить, так и уменьшить начало результата.

Чтобы восстановить линейную свёртку, выбирают длину ДПФ не меньше L+M−1 и дополняют обе последовательности нулями. Тогда все ненулевые отсчёты линейного результата уже помещаются до границы блока, а сворачиванию по модулю нечего переносить.

Как пользоваться формулой

Для циклической задачи задайте N и приведите обе последовательности к одной длине, сохранив порядок отсчётов.
При ручном подсчёте для каждого n переберите m и замените n−m остатком в диапазоне от 0 до N−1.
При частотном подсчёте выполните прямые ДПФ одной длины, перемножьте коэффициенты и возьмите обратное ДПФ.
Если нужна линейная свёртка, сначала вычислите L+M−1 и дополните входы нулями до длины не меньше этого числа.

Историческая справка

Появление быстрых алгоритмов ДПФ сделало частотный расчёт свёртки практичным для длинных цифровых блоков. В публикации 1965 года Кули и Тьюки описали разложение вычисления комплексных коэффициентов на преобразования меньших размеров. Для применения такого вычисления к фильтрам нужно было согласовать периодичность ДПФ и протяжённость линейного отклика.

В курсе MIT по цифровой обработке сигналов Алан Оппенгейм показывает циклическую свёртку, дополнение нулями и применение ДПФ к линейной фильтрации. Современная запись через индекс по модулю явно указывает, где возникает наложение хвоста, и работает независимо от выбранной реализации быстрого преобразования.

Историческая линия формулы

Циклическая свёртка следует из свойства преобразования на конечном периоде. Работу Кули и Тьюки приводят как источник по вычислительной реализации ДПФ. Связь с дополнением нулями и фильтрацией разобрана в учебном курсе Оппенгейма.

Пример

Пусть x=[1, 2, 3], а фильтр h=[1, 1]. Найдём циклическую свёртку длины 3 и сравним её с линейной. Для общей длины 3 берём h=[1, 1, 0]. По формуле y[n]=x[n]+x[(n−1) mod 3]. Получаем y[0]=1+3=4, y[1]=2+1=3, y[2]=3+2=5. Ответ [4, 3, 5]. При линейной свёртке значение x[−1] равно нулю, а после x[2] остаётся хвост фильтра. Результат [1, 3, 5, 3]. Последнее число 3 наложилось на первое 1 в циклическом варианте. Если выполнить ДПФ длины 4 с нулевым дополнением, оба числа займут отдельные позиции. Сумма отсчётов равна 12 в обоих вариантах.

Частая ошибка

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

Практика

Задачи с решением

Циклический сдвиг на один отсчёт

Условие. x=[2, 4, 6, 8], h=[0, 1, 0, 0]. Найдите результат длины 4.

Решение. Фильтр оставляет только x[(n−1) mod 4]. При n=0 берём x[3]=8, затем идут 2, 4, 6.

Ответ. [8, 2, 4, 6].

Полное взаимное уничтожение

Условие. x=[1, −1] и h=[1, 1]. Найдите линейный результат и циклический длины 2.

Решение. Линейная свёртка [1, 0, −1]. Отсчёт −1 с индексом 2 складывается с 1 в позиции 0, поэтому циклический результат [0, 0].

Ответ. Линейная [1, 0, −1], циклическая [0, 0].

Дополнительные источники

https://sigproc.mit.edu/_static/spring25/lectures/Quiz_Review.pdf
https://ocw.mit.edu/courses/res-6-008-digital-signal-processing-spring-2011/pages/readings/
https://www.ams.org/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf

Связанные формулы

Информатика

Равенство Парсеваля для энергии блока ДПФ

$\sum_{n=0}^{N-1}|x[n]|^2=\frac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2$

Равенство Парсеваля позволяет вычислить сумму квадратов отсчётов по всем коэффициентам ДПФ. Множитель 1/N применяется, если прямое преобразование записано без нормировки.

Информатика

Периодограмма спектральной плотности мощности

$P_2[k]=\frac{|X_w[k]|^2}{f_s\sum_{n=0}^{N-1}|w[n]|^2},\quad X_w[k]=\sum_{n=0}^{N-1}w[n]x[n]e^{-2\pi i kn/N}$

Периодограмма переводит квадраты модулей спектра в плотность мощности по частоте. Масштаб задают частота дискретизации и сумма квадратов отсчётов окна.

Информатика

Спектральная плотность мощности по методу Уэлча

$\widehat S_{\mathrm{Welch}}[k]=\frac{1}{M}\sum_{j=0}^{M-1}P_j[k],\quad P_j[k]=\frac{|\operatorname{DFT}(w\,x_j)[k]|^2}{f_s\sum_n w[n]^2}$

Метод Уэлча разбивает запись на сегменты, строит оконную периодограмму каждого сегмента и усредняет значения плотности по частотам. Сегменты могут перекрываться.

Информатика

Дискретное преобразование Фурье и обратная формула

$X_k=\sum_{n=0}^{N-1}x_n e^{-2\pi i kn/N},\qquad x_n=\frac1N\sum_{k=0}^{N-1}X_k e^{2\pi i kn/N}$

Дискретное преобразование Фурье переводит конечную последовательность в комплексные частотные коэффициенты. Обратная сумма восстанавливает все отсчёты; знак экспоненты и нормировку нужно выбирать согласованно.

Информатика

Линейная свёртка конечных последовательностей

$y_n=\sum_{k=-\infty}^{\infty}x_k h_{n-k},\qquad L_y=L_x+L_h-1$

Линейная свёртка складывает сдвинутые копии одной последовательности с весами другой. Для конечных массивов, продолженных нулями, полный результат содержит сумму их длин минус один отсчёт.