2.2.3. Циклическая свертка

В гл. 1 было показано, что Фурье-преобразование свертки двух последовательностей есть произведение их Фурье-преобразований.

В этом разделе мы выведем эквивалентное утверждение для ДПФ. Зададимся вопросом, какая последовательность является обратным ДПФ для произведения двух ДПФ?

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

. (2.46)

Найдем теперь . Начнем с рассмотрения периодически дополненных последовательностей , , , , и . Поскольку

, (2.47)

то можно использовать обратный дискретный ряд Фурье (2.3) и записать

. (2.48)

Выразив в виде

(2.49)

и подставив это выражение в (2.48), получим

(2.50)

За исключением пределов суммирования, это выражение имеет форму обычной (линейной) суммы двумерной свертки. Вместо суммирования по всем отсчетам произведения достаточно складывать только те отсчеты результирующей последовательности, которые лежат в области . Последовательность прямоугольно-периодична с периодами и .

Поскольку

(2.51)

можно записать

(2.52)

Назовем циклической сверткой и . Выражение «циклическая свертка», также взятое из цифровой обработки одномерных сигналов, означает, что испытывает циклический сдвиг по отношению к в противоположность обычной линейной свертке, где просто линейно сдвигается относительно . Циклическая свертка может быть также записана в ином виде:

. (2.53)

Как и обычная свертка, циклическая свертка обладает свойством коммутативности, ассоциативности и дистрибутивности относительно сложения. Используя символ для обозначения операции двумерной циклической свертки, можно записать

. (2.54)

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

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

Предположим, что имеет опорную область , a - . Обозначим через результат линейной свертки

. (2.55)

Последовательность имеет опорную область

(2.56)

Используя ДПФ размером и , можно найти циклическую свертку , которая записывается следующим образом:

для . (2.57)

Периодическое продолжение последовательности конечной протяженности можно записать в виде

. (2.58)

Подставив это выражение в (2.57) и сделав соответствующие преобразования, получим

для . (2.59)

Благодаря ограниченным размерам выражение в скобках есть линейная свертка, которую можно обозначить как . В результате получим

для . (2.60)

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

, , (2.61)

получим, что копии в равенстве (2.60) не будут перекрываться, и равенство (2.60) превращается в равенство

для . (2.62)

Следовательно, результат циклической свертки равен результату линейной свертки, что и требовалось.

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

1. Выбрать и удовлетворяющие условию (2.61).

2. Дополнить необходимым количеством нулей для заполнения области .

3. Дополнить таким же образом.

4. Вычислить -точечное ДПФ и .

5. Найти произведение .

6. Вычислить -точечное обратное ДПФ для . Результат этого вычисления и есть искомая линейная свертка.

В этой процедуре, как понимает читатель, шаги 4-6 обеспечивают выполнение круговой свертки , которая равна линейной свертке благодаря правильному выбору и .

Пример 4

В качестве численного примера рассмотрим особенно простой случай, когда и представляют собой последовательности размера

, . (2.63)

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

ДПФ размера можно записать следующим образом:

(2.64)

Подставив числа в (2.64), получим

, (2.65)

, (2.66)

. (2.67)

Взяв обратное ДПФ размера , получим циклическую свертку размера :

. (2.68)

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

, .

Рассчитаем -точечное ДПФ:

(2.69)

Взяв обратное ДПФ размера от , получим

. (2.70)

Если эту последовательность преобразовать в последовательность размера путем пространственного наложения, результат будет идентичен (2.68).

Если вы проверяли числа в этом примере, то вне сомнения убедились, что расчеты очень утомительны и что потрачено гораздо больше усилий, чем это было бы необходимо для прямого вычисления линейной свертки. В разд. 2.3 мы рассмотрим быстрый эффективный алгоритм выполнения -мерного ДПФ, который позволяет вычислить свертку с меньшим числом арифметических операций, чем это требуется для прямого расчета свертки в виде суммы.