Свёртка последовательностей

Свёртка последовательностей — это результат перемножения элементов двух заданных числовых последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции).

Свёртка последовательностей — это частный случай свёртки функций.

Свёртка является линейным преобразованием входящих в неё последовательностей.

Свёртку двух заданных последовательностей можно получить, если, сначала, использовать для каждой последовательности дискретное преобразование Фурье (ДПФ), затем, перемножить результаты преобразования и произвести обратное дискретное преобразование Фурье (обратное ДПФ). Это важное свойство находит своё широкое применение в цифровой обработке сигналов.

Различают периодическую и линейную свёртки, которые используются для периодических и конечных последовательностей соответственно.

Типы сверток

К традиционным типам сверток относятся:

• линейная свертка;
• круговая свертка (периодическая);
• круговая свертка (апериодическая);
• свертка с помощью дискретного преобразования Фурье (ДПФ).

Расчет сверток

Рассмотрим правила и последовательность расчета каждого вида свертки.

Расчет линейной свертки

Для расчета линейной свертки необходимо выполнить такую последовательность действий:

• произвести расчет количества элементов выходной последовательности по формуле:

$N_{out}=N_1+N_2-1,$

где:

$N_{out}$ — количество элементов в выходной последовательности;

$N_1$ — количество элементов в первой последовательности;

$N_2$ — количество элементов во второй последовательности;

• дополнить нулями обе последовательности так, чтобы количество элементов в этих последовательностях была равна $N_{out}$;

• симметрично отобразить одну из последовательностей относительно оси ординат;

• произвести перемножение этих двух последовательностей.

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

Расчет периодической круговой свертки

Для получения круговой свертки (периодической) необходимо представить, что две последовательности располагаются на двух окружностях. Одна окружность находится внутри другой. Значения каждой из этих последовательностей равноудалены друг от друга. Для получения каждого значения круговой свертки необходимо представить, что одна из последовательностей движется по окружности относительно другой по часовой стрелке. К примеру, возьмем первое значение последовательности, которая вращается, последовательно умножим на значения другой последовательности и просуммируем результаты умножений — так получим первое значение выходной последовательности, которое было получено при помощи круговой свертки. Данные действия повторить для каждого значения последовательности, которая вращается относительно другой. Количество элементов в выходной последовательности будет равно количеству элементов последовательности, которая вращается.

Полученная последовательность эквивалентна свертке двух периодических сигналов.

Расчет апериодической круговой свертки

Для получения круговой свертки (апериодической) выполняется все те же операции, что и для получения круговой свертки, но при этом увеличить количество элементов до количества $N_{out}$. Входные последовательности необходимо дополнить нулями до этого количества. При выполнении данного вида свертки устраняется эффект кругового наложения, который возникает при круговой свертке.

Выполнение свертки с помощью ДПФ

Для выполнения свертки с помощью дискретного преобразования Фурье необходимо дополнить нулями обе входные последовательности так, чтобы количество элементов в этих последовательностях равнялось $N_{out}$. Далее необходимо произвести прямое ДПФ по формуле прямого преобразования Фурье.

Далее производится поочередное умножение элементов первой последовательности с элементами второй последовательности. После производится обратное преобразование по формуле обратного преобразования Фурье, в результате которого получаем свертку, рассчитанную с помощью ДПФ.

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

Пример программы

Ниже приведен пример реализации свертки, написанный на C++:

/*
 * Размер выходной последовательности равен M + N - 1 
 */
double * conv(double * x, int N, double * h, int M)
{
    double * result = new double[N + M - 1];
    memset(result, 0, sizeof(double) * (N + M - 1));
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            result[i + j] += x[i] * h[j];
        }
    }
 
    return result;
}

См. также

• Периодическая свёртка
• Секционная свертка

Литература

1. Рабинер Л., Гоулд Б. Глава 2. Теория линейных дискретных систем // Теория и применение цифровой обработки сигналов. — М.: Мир, 1978. — С. 72—81. — 848 с.