§ 6. Преобразования сверток последовательностей

А. Круговая и линейная свертки. ДПФ сверток.

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

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

Рассмотрим сначала периодические последовательности с периодом каждая по отсчетов. Круговой сверткой зтих последовательностей является

Пусть для первой и второй из указанных последовательностей ДПФ

соответственно равны

ДПФ определяемой по формуле (3.81) свертки рассматриваемых функций, которое тоже -точечное, является произведением обоих исходных ДПФ :

Как выводится формула (3.84) будет в дальнейшем сказано.

При малых значениях возможно непосредственное вычисление свертки по формуле (3.81). Однако при последовательностях большой длительности это становится затруднительным. В § 5 уже упоминалось о том, что в области управления и связи часто возникает необходимость в обработке последовательностей большой длительности. При этом на практике применяется метод вычислений свертки (3.81), основанный на использовании формулы (3.84). Машинным способом выполняются следующие действия: определяются для заданных последовательностей отвечающие им полученные перемножаются; для найденных таким образом в соответствии с формулой производится ОДПФ по формуле (3.40), что дает

Если длительность одной из исходных последовательностей а другой то круговая свертка вычисляется для равного большему из чисел при этом последовательность меньшей длительности добавлением нулевых точек тоже преобразуется в последовательность длительности

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

при

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

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

Рассмотрим подробнее, что представляют собой круговая и линейная свертки, и проследим на простейших примерах за их получением. Прежде чем перейти к такому рассмотрению круговой свертки, укажем, как производится так называемый круговой сдвиг последовательности; укажем также, как получена формула (3.84).

Круговой сдвиг последовательности представляется следующим образом. Пусть имеется изображенная на рис. 3.10, с последовательность конечной длительности — -точечная последовательность. Ранее было отмечено, что, говоря имеют в виду преобразование для одного периода соответствующей периодической последовательности. В рассматриваемом случае она изображается так, как показано на рис. При сдвиге периодической последовательности на дискретных точек вдоль оси например на четыре точки, как представлено на рис. 3.10,в, получается смещенная последовательность. Рассматривая тот же, что и первоначально указанный, период длительностью от до включительно, получим последовательность, изображенную на рис. 3.10,г. Переход от последовательности, показанной на рис. 3.10,а, к последовательности, изображенной на рис. 3.10,г, называется круговым сдвигом последовательности. Выполнение его иногда представляют следующим образом. Можно закрепить на поверхности цилиндра лист бумаги с вычерченным на нем, показанным на рис. 3.10, а графиком -точечной

Рис. 3.10

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

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

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

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

Укажем, как получена основная формула (3.84). В соответствии с определением ДПФ-точечным представленной в виде (3.81) функции является

где

Сделаем следующие преобразования: изменим в правой части уравнения (3.90) порядок суммирования, подставим развернутое выражение умножим правую часть уравнения (3.80) на При этом приводится к следующему виду:

Выражение, взятое в квадратные скобки, представляет собой Это следует из того, что, рассматривая данное выражение вместе с выражением (3.81), можно привести его к виду (3.83). Вынося в (3.91)

за знак суммы, получаем

где Таким образом, приходим к формуле (3.84).

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

Рис. 3.11 (см. скан)

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

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

Приведем теперь пример, поясняющий получение линейной сверши. На простейшем примере покажем, как при свертывании последовательностей одна из которых -точечная, другая -точечная, образуется свертка длиной отсчета. Обратимся к последовательностям, представленным на рис. 3.12,а и 3.12,б, для которых соответственно Для заданы значения , равные , и для заданы значения равные 1, 1, 1. Рассчитаем по формуле (3.81) для величины

Расчеты сведены в табл. 3.1. Свертка заданных последовательностей представлена на рис.

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

Рис. 3.12

(см. скан)

Был приведен для пояснения вычислительной процедуры простейший пример: были взяты малые значения и На практике возникает необходимость в свертывании последовательностей большей длины. Быстрые свертки эффективны тогда, когда большая из величин или порядка 30 или более того. Особым является тот случай, когда какая-либо из свертываемых последовательностей очень большой длины, практически неограниченная. Он рассматривается отдельно в следующем разделе.