WikiSort.ru - Не сортированное

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

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

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

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

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

Типы свёрток

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

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

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

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

Теорема об уменьшении размерности пространства при свёртке

Теорема. Пусть в пространстве ${\displaystyle \mathbb {R} ^{n}}$ заданы последовательности ${\displaystyle f[\mathbb {R} ^{n}]}$ и ${\displaystyle h[\mathbb {R} ^{n}]}$ , выберем одно произвольное измерение ${\displaystyle X_{k}}$ из ${\displaystyle \mathbb {R} ^{n}}$ , тогда результат операции свёртка ${\displaystyle y[\mathbb {R} ^{n}]=f[\mathbb {R} ^{n}]*h[\mathbb {R} ^{n}]}$ , с последующим суммированием по ${\displaystyle X_{k}}$ есть ${\displaystyle y[\mathbb {R} ^{n}-X_{k}]=\sum \limits _{X_{k}}y[\mathbb {R} ^{n}]}$ эквивалентен предварительному суммированию ${\displaystyle f[\mathbb {R} ^{n}-X_{k}]=\sum \limits _{X_{k}}f[\mathbb {R} ^{n}]}$  и ${\displaystyle h[\mathbb {R} ^{n}-X_{k}]=\sum \limits _{X_{k}}h[\mathbb {R} ^{n}]}$ с последующей свёрткой ${\displaystyle y[\mathbb {R} ^{n}-X_{k}]=f[\mathbb {R} ^{n}-X_{k}]*h[\mathbb {R} ^{n}-X_{k}]}$ . ^[1]

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

Ниже приведён пример реализации свертки, написанный на 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 + M - 1; i++)
    {
        for (int j = 0; j < N + M - 1; j++)
        {
            result[i] += x[j] * h[M-1-j]; // Kern_Rich.pdf
        }
    }

    return result;
}

См. также

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

Примечания

Литература

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