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 мы рассмотрим быстрый эффективный алгоритм выполнения -мерного ДПФ, который позволяет вычислить свертку с меньшим числом арифметических операций, чем это требуется для прямого расчета свертки в виде суммы.