Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Глава 6 - Свертка 12
Свертка
Свертка есть математический способ комбинирования двух сигналов для формирования третьего сигнала. Это есть один из самых важных приемов в Цифровой Обработке Сигналов. Используя стратегию импульсного разложения, система описывается сигналом, называемым импульсный отклик. Свертка важна потому, что она представляет соотношение между тремя интересными сигналами: входным сигналом, выходным сигналом и импульсным откликом. Эта глава представляет свертку с двух точек зрения: с входной стороны алгоритма и выходной стороны алгоритма. Свертка дает математические рамки для ЦОС; нет ничего более важного в этой книге.
Дельта функция и импульсный отклик
В предыдущей главе было описано, как сигнал может быть разложен на группу компонентов, называемых импульсами. Импульс есть сигнал, состоящий из всех нулей, за исключением одной ненулевой точки. Действительно, импульсное разложение дает возможность анализа сигналов по одному отсчету. В предыдущей главе также была представлена фундаментальная концепция ЦОС: разложение входного сигнала на сумму составляющих, пропускания каждой составляющей через линейную систему, и суммирования полученных выходных сигналов. Сигнал, полученный из этой процедуры «разделяй и властвуй», идентичен сигналу, полученному прямым пропусканием исходного сигнала через систему. Хотя возможны многие виды разложения, только два являются базовыми в цифровой обработке: импульсное разложение и разложение Фурье. Когда используется импульсное разложение, процедура может быть описана математической операцией, называемой свертка. В этой главе (и большинстве следующих глав) мы будем иметь дело только с дискретными сигналами. Свертка также применяется и для непрерывных сигналов, но математика там более сложна. Мы рассмотрим обработку непрерывного сигнала в главе 13.
Рисунок 6-1 определяет два важных термина, используемых в ЦОС. Первый - дельта функция, [n]. Дельта функция есть нормализованный импульс, т.е. отсчет с номером 0 имеет единичную величину, а остальные отсчеты равны нулю. По этой причине дельта функция часто называется единичным импульсом.
Второй термин, определяемый рисунком 6-1, есть импульсный отклик. Как следует из его названия, импульсный отклик есть сигнал, который появляется на выходе системы, когда на ее вход поступает дельта функция (единичный импульс). Если две системы отличаются друг от друга каким-либо образом, то они будут иметь разные импульсные отклики. Так как входные и выходные сигналы обычно обозначаются как x[n] и y[n], то импульсный отклик обычно обозначается символом h[n]. Конечно, это обозначение может быть изменено, если возможно более описательное имя, например, f[n] может использоваться для описания импульсного отклика фильтра.
Любой импульсный отклик может быть представлен как сдвиг и масштабирование дельта функции. Предположим, что сигнал a[n] состоит из всех нулей за исключением отсчета номер 8, который равен –3. Это то же самое, что и дельта функция, сдвинутая на 8 отсчетов вправо и умноженная на –3. В формульном виде: a[n] = -3[n-8]. Убедитесь, что вы понимаете эту запись, она используется во всех ближайших формулах ЦОС.
Если на вход системы подан импульс такой, как -3[n-8], что будет на выходе системы? Здесь используются свойства однородности и инвариантности сдвига. Масштабирование и сдвиг входного сигнала приводят к идентичному масштабированию и сдвигу выходного сигнала. Если [n] дает h[n], то -3[n-8] даст –3h[n-8]. Другими словами, выход есть версия импульсного отклика, который сдвинут и промасштабирован на ту же самую величину, что и дельта функция на входе. Если вы знаете импульсный отклик системы, то вы знаете и ее реакцию на любой импульс.
Свертка
Давайте просуммируем наше рассмотрение преобразования входного сигнала системы в выходной. Во-первых, входной сигнал может быть разложен на набор входных импульсов, каждый из которых может рассматриваться как промасштабированная и сдвинутая дельта функция. Во-вторых, выход от каждого импульса есть промасштабированный и сдвинутый импульсный отклик. В-третьих, целиком выходной сигнал может быть найден суммированием этих промасштабированных и сдвинутых импульсных откликов. Другими словами, если мы знаем импульсный отклик системы, то мы можем вычислить выходной сигнал для любого входного сигнала. Это означает, что мы знаем все о системе. Больше ничего нет, что можно было бы изучать о характеристиках линейных систем (однако в последующих главах мы покажем, что эта информация может быть представлена и в других формах).
Импульсный отклик имеет различные названия в некоторых публикациях. Если рассматриваемая система есть фильтр, то импульсный отклик называется ядро фильтра, свертка ядра или просто ядро. При обработке изображений импульсный отклик называется функцией расширения точки. Хотя эти термины используются при немного различных подходах, все они означают то же самое, сигнал, вырабатываемый системой, когда на ее вход поступает дельта функция.
Свертка есть формальная математическая операция такая же, как умножение, сложение и интегрирование. Сложение берет два числа и производит третье число, свертка также берет два сигнала и производит третий сигнал. Свертка используется во многих областях математики таких, как теория вероятности и статистика. В линейных системах свертка используется для описания соотношения между тремя важными сигналами: входным сигналом, импульсным откликом и выходным сигналом.
РИСУНОК 6-1
Определение дельта функции и импульсного отклика (Impulse Response). Дельта функция есть нормализованный импульс. Все отсчеты имеют величину равную нулю за исключением отсчета номер 0, который имеет величину равную единице. Маленькая греческая буква [n] используется для обозначения дельта функции. Импульсный отклик системы обычно обозначается h[n], это есть выходной сигнал системы, когда на ее входе дельта функция.
Рисунок 6-2 показывает обозначение свертки в линейных системах. Входной сигнал x[n] поступает на линейную систему с импульсным откликом h[n], на выходе получается выходной сигнал y[n]. В формульном виде x[n] * h[n] = y[n]. Выражаясь словами, свертка входного сигнала с импульсным откликом равна выходному сигналу. Сложение обозначается знаком плюс +, а свертка обозначается знаком звездочка *. К сожалению, большинство языков программирования используют звездочку для обозначения умножения. Звездочка в компьютерных программах обозначает умножение, звездочка в формулах обозначает свертку.
РИСУНОК 6-2
Как свертка используется в ЦОС. Выходной сигнал линейной системы равен свертке входного сигнала с импульсным откликом системы. Свертка обозначается звездочкой, когда записывается в виде формулы.
РИСУНОК 6-3
Пример низкочастотного (а) и высокочастотного (b) фильтров, использующих свертку. В этом примере входной сигнал есть несколько циклов синусоиды плюс пилообразный сигнал с медленным подъемом. Две компоненты разделяются, с помощью правильно выбранного импульсного отклика.
Рисунок 6-3 показывает свертку, применяемую для низкочастотной и высокочастотной фильтрации. В этом примере входной сигнал состоит из двух компонент: три цикла синусоиды (представляют высокую частоту) и медленно поднимающийся пилообразный сигнал (представляет низкую частоту). Импульсный отклик для низкочастотного фильтра (а) – сглаженная арка, в результате только пилообразный сигнал проходит на выход. Подобно этому высокочастотный фильтр (b) позволяет проходить на выход только быстро изменяющимся синусоидам.
Рисунок 6-4 представляет два дополнительных примера использования свертки в обработке сигналов. Инвертирующий аттенюатор (а) перебрасывает сигнал сверху вниз и уменьшает его амплитуду. Дискретная производная (также называется первая разность), показанная в (b), дает выходной сигнал относительно наклона входного сигнала
Обратите внимание на длину сигналов на рисунках 6-3 и 6-4. Входной сигнал имеет длину из 81 отсчета, а каждый импульсный отклик имеет длину 31 отсчет. В большинстве приложений ЦОС входной сигнал имеет длину из сотен, тысяч или даже миллионов отсчетов. Импульсный отклик обычно много короче, скажем, несколько точек или несколько сотен точек. Математика свертки не ограничивает длину этих сигналов. Однако длина выходного сигнала специфична. Длина выходного сигнала равна длине входного сигнала плюс длина импульсного отклика минус один. Для сигналов на рисунках 6-3 и 6-4 длина каждого выходного сигнала равна 81+31-1=111 отсчетов. Номера отсчетов во входном сигнале меняются от 0 до 80, в импульсном отклике – от 0 до 30, в выходном сигнале – от 0 до 110.
РИСУНОК 6-4
Пример сигналов, обрабатываемых с использованием свертки. Многие задачи сигнальной обработки используют очень простой импульсный отклик. Как показывают эти примеры, колоссальные изменения могут быть достигнуты только с несколькими ненулевыми точками.
Теперь мы подошли к математическим деталям свертки. Использование свертки в Цифровой Обработке Сигналов может быть понято двумя способами. Вначале рассмотрим свертку с токи зрения входного сигнала. Это анализ того, какой вклад вносит каждый отсчет входного сигнала во многие точки выходного сигнала. Затем мы рассмотрим свертку с точки зрения выходного сигнала. Это проверка того, как каждый отсчет выходного сигнала получает информацию от многих точек входного сигнала.
Имейте в виду, что эти две точки зрения всего лишь различные способы представления об одной и той же математической операции. Первая точка зрения важна потому, что она дает концептуальное понимание принадлежности свертки к ЦОС. Вторая точка зрения описывает математику свертки. Это типичный образец одной из самых трудных задач, с которой вы будете встречаться в ЦОС: выработать собственное концептуальное понимание, соответствующее глубинам математики, которые используются для представления этих идей.
Входная сторона алгоритма
Рисунок 6-5 показывает простую проблему свертки: 9-точечный входной сигнал, x[n], проходит через систему с 4-точечным импульсным откликом, h[n], и дает выходной сигнал, y[n], из 9+4-1=12 точек. В математических терминах: свертка x[n] с h[n] дает y[n]. Этот первый взгляд на свертку основывается на базовой концепции ЦОС: разложение входного сигнала, пропускания его компонентов через систему, и синтез выхода. В этом примере каждый из девяти отсчетов входного сигнала вносит вклад из сдвинутой и промасштабированной версии импульсного отклика в выходной сигнал. Эти девять сигналов показаны на рисунке 6-6. Сложение этих девяти сигналов производит выходной сигнал, y[n].
Давайте рассмотрим некоторые из этих девяти сигналов в деталях. Начнем с отсчета номер четыре входного сигнала, x[4]. Этот отсчет имеет индекс четыре и величину равную 1,4. Когда сигнал раскладывается, он представляется как импульс 1,4[n-4]. После прохождения через систему он даст выходные компоненты 1,4h[n-4]. Этот сигнал показан в центральном квадратике из девяти на рисунке 6-6. Заметим, что это есть импульсный отклик h[n], умноженный на 1,4 и сдвинутый на четыре отсчета вправо. Нули добавлены как отсчеты 0-3 и отсчеты 8-11 для сохранения длины. Делая это более наглядным, на рисунке 6-6 используются квадраты для представления точек, полученных сдвигом и масштабированием импульсного отклика, и ромбы для представления нулей.
Теперь проверим отсчет x[8], последнюю точку во входном сигнале. Этот отсчет имеет индекс номер восемь и величину –0,5. Как показано в правой нижней части рисунка 6-6, этот отсчет дает импульсный отклик, который сдвинут вправо на восемь точек и умножен на -0,5. Для сохранения длины добавлены нулевые точки 0-7. Наконец, проверим эффект от точек x[0] и x[7]. Оба эти отсчета имеют величину равную нулю, и поэтому они производят выходные компоненты, состоящие из одних нулей.
РИСУНОК 6-5
Пример свертки. Девять точек входного сигнала свертываются с четырьмя точками импульсного отклика и производят двенадцать точек выходного сигнала. Каждая точка входного сигнала вносит вклад в выходной сигнал, состоящий из промасштабированного и сдвинутого импульсного отклика. Эти девять промасштабированных и сдвинутых импульсных откликов показаны на рисунке 6-6.
РИСУНОК 6-6
Компоненты выходного сигнала для свертки рисунка 6-5. На этих рисунках результат сдвига и масштабирования импульсного отклика представлен квадратиками. Добавочные точки представлены ромбиками, они состоят из нулей и нужны для сохранения длины.
В этом примере x[n] есть 9-точечный сигнал и h[n] есть 4-точечный сигнал. В нашем следующем примере, показанном на рисунке 6-7, мы будем рассматривать ситуацию, когда x[n] 4-точечный сигнал, а h[n] 9-точечный сигнал. Используются те же сигналы, только их поменяли местами. Как видно из компонентов выходного сигнала, четыре отсчета из x[n] дают сдвинутую и промасштабированную версию 9-точечного импульсного отклика. Так же как и раньше добавлены нули для сохранения длины.
Подождите один момент! Выходной сигнал на рисунке 6-7 идентичен выходному сигналу на рисунке 6-5. Это не ошибка, но важное свойство. Свертка коммутативна, то есть a[n] * b[n] = b[n] * a[n]. Математики не разбирают где здесь входной сигнал, а где импульсный отклик, важно только, что два сигнала свертываются друг с другом. Хотя математики и следуют этому правилу, но перемена местами двух сигналов не имеет физического смысла в теории систем. Входной сигнал и импульсный отклик две совершенно разные вещи, и перемена их местами, с этой точки зрения, не имеет смысла. Таким образом, свойство коммутативности есть математический инструмент манипуляции формулами для достижения каких-либо целей.
Программа для вычисления свертки, использующая входную сторону алгоритма, приведена в таблице 6-1. Помните, программы в этой книге предназначены для представления алгоритмов в простейшей форме, даже ценой хорошего стиля программирования. Например, все входы и выходы управляются воображаемыми подпрограммами (линии 160 и 280), это означает, что мы не определяем, как осуществляется управление этими операциями. Не пропускайте эти программы, они являются ключевой частью материала, и вам необходимо понимать их в деталях.
Программа свертывает 81-точечный сигнал, который содержится в массиве X[ ], с 31-точечным импульсным откликом, который хранится в массиве H[ ], и производит 111 точечный выходной сигнал, который хранится в массиве Y[ ]. Эти же длины показаны на рисунках 6-3 и 6-4. Заметьте, что имена этих массивов используют заглавные буквы. Это нарушает соглашение об именах, которое обсуждалось раньше, потому что заглавные буквы зарезервированы для сигналов частотной области. К сожалению, простой Бейсик, используемый в этой книге, не позволяет применять строчные буквы в именах переменных. Также обратите внимание, что линия 240 использует звездочку для умножения. Помните, звездочка в программах означает умножение, в то время как в формулах звездочка означает свертку. Звездочка в тексте (документация или программные комментарии) может означать и то и другое.
Воображаемая подпрограмма в линии 160 помещает входной сигнал в массив X[ ] и импульсный отклик в массив H[ ]. Линии 180-200 устанавливают все величины массива Y[ ] в ноль. Это необходимо потому, что Y[ ] используется как аккумулятор для суммирования выходных компонент по мере их вычисления. Линии 220-260 сердце программы. Выражение FOR в линии 220 контролирует цикл, который проходит через все точки входного сигнала X[ ]. Для каждого отсчета входного сигнала внутренний цикл (линии 230-250) вычисляет промасштабированную и сдвинутую версию импульсного отклика и суммирует его в массив, аккумулирующий выходной сигнал, Y[ ]. Эта структура вложенных циклов (один цикл внутри другого) есть ключевая характеристика программы для вычисления свертки, познакомьтесь с ней ближе.
100 'СВЕРТКА, ИСПОЛЬЗУЮЩАЯ ВХОДНУЮ СТОРОНУ АЛГОРИТМА
110 '
120 DIM X[80] 'Входной сигнал из 81 точки
130 DIM H[30] 'Импульсный отклик, 31 точка
140 DIM Y[110] 'Выходной сигнал, 111 точек
150 '
160 GOSUB XXXX 'Воображаемая подпрограмма загрузки X[ ] и H[ ]
170 '
180 FOR I% = 0 TO 110 'Установка нулей в выходной массив
190 Y(I%) = 0
200 NEXT I%
210 '
220 FOR I% = 0 TO 80 'Цикл для каждой точки массива X[ ]
230 FOR J% = 0 TO 30 'Цикл для каждой точки массива H[ ]
240 Y[I%+J%] = Y[I%+J%] + X[I%]*H[J%]
250 NEXT J%
260 NEXT I% '(помните, * есть умножение в программе!)
270 '
280 GOSUB XXXX 'Воображаемая подпрограмма для хранения Y[ ]
290 '
300 END
ТАБЛИЦА 6-1
РИСУНОК 6-7
Второй пример свертки. Входной сигнал и импульсный отклик поменялись местами по сравнению с примером на рисунке 6-5. поскольку свертка коммутативна, выходной сигнал для двух примеров идентичен.
Соблюдение правильной индексации в линии 240 может свести вас с ума! Давайте предположим, что мы находимся на полпути нашей программы, и рассмотрим, какие мы делаем действия с отсчетом X[40], т.е. I%=40. Внутренний цикл проходит через каждую точку импульсного отклика, делая три вещи. Первое, импульсный отклик масштабируется путем умножения на величину входного сигнала. Если это была бы единственная акция внутреннего цикла, то линию 240 можно было бы записать, как Y[J%]=X[40]*H[J%]. Второе, промасштабированный импульс сдвигается на 40 отсчетов вправо путем добавления этого номера к индексу выходного сигнала. Эта вторая акция должна изменить линию 240 следующим образом: Y[J%+40]=X[40]*H[J%]. Третье, Y[ ] должен аккумулировать (синтезировать) все результаты, полученные от каждого отсчета входного сигнала. Поэтому новая информация должна добавляться к информации, уже существующей в массиве. В результате получается Y[J%+40]=Y[J%+40]+X[40]*H[J%]. Изучите это внимательно, это очень запутано, но очень важно.
Выходная сторона алгоритма
Первая точка зрения на свертку анализирует, как каждый отсчет входного сигнала воздействует на многие отсчеты выходного сигнала. Со второй точки зрения мы будем рассматривать индивидуальные отсчеты выходного сигнала и найдем вклад от точек входного сигнала. Это важно и с математической, и с практической точек зрения. Предположим, что мы получили некоторый входной сигнал и импульсный отклик, и хотим найти их свертку. Большинство прямых методов требует написать программу, которая петляет через выходной сигнал, вычисляя один отсчет на каждом цикле петли. Похожим образом, формула запишется в виде: y[n] = некоторой комбинации из каких-то величин. То есть, отсчет n выходного сигнала равен некоторой комбинации из многих величин входного сигнала и импульсного отклика. Это требует знания, как каждый отсчет выходного сигнала может быть вычислен независимо от других отсчетов выходного сигнала. Выходная сторона алгоритма и дает эту информацию.
Давайте рассмотрим пример того, как одна точка выходного сигнала подвергается влиянию нескольких точек входного сигнала. В качестве примера мы будем использовать точку y[6] из рисунка 6-5. Эта точка равна сумме всех шестых точек девяти выходных компонентов, показанных на рисунке 6-6. Теперь посмотрим внимательнее на эти девять выходных компонентов и определим, которые из них воздействуют на y[6]. То есть, найдем, которые из этих девяти сигналов содержат ненулевые отсчеты в шестой позиции. Пять из выходных компонентов имеют только добавленные нули (ромбические маркеры) в шестом отсчете, и поэтому игнорируются. Только четыре из девяти выходных компонентов имеют ненулевую величину в шестой позиции. Эти выходные компоненты получаются из входных отсчетов x[3], x[4], x[5] и x[6]. Путем сложения шестых отсчетов этих выходных компонентов, y[6] определяется как y[6] = x[3]h[3] + x[4]h[2] + x[5]h[1] + x[6]h[0]. То есть, четыре отсчета из входного сигнала умножаются на четыре отсчета импульсного отклика и результаты складываются.
Рисунок 6-8 иллюстрирует выходную сторону алгоритма, как механизм свертки, диаграмму выполнения свертки. Считайте, что входной сигнал x[ ] и выходной сигнал y[ ] зафиксированы на странице. Механизм свертки (то, что показано внутри пунктирного квадрата) свободно двигается вправо и влево, как требуется. Механизм свертки расположен так, что его выход совпадает с тем отсчетом выходного сигнала, который сейчас вычисляется. Четыре отсчета из входного сигнала поступают на вход механизма свертки. Эти величины умножаются на указанные отсчеты импульсного отклика, и результаты умножения складываются. Это дает величину выходного сигнала, который попадает в свое правильное место. Например, y[6] показан в процессе вычисления из четырех входных отсчетов: x[3], x[4], x[5] и x[6].
Для вычисления y[7] механизм свертки сдвинулся на один отсчет вправо. В результате этого другие четыре отсчета поступают на механизм, от x[4] до x[7], и величина y[7] попадает в соответствующее место. Этот процесс повторяется для всех точек выходного сигнала, которые необходимо вычислить.
РИСУНОК 6-8
Механизм свертки. Эта диаграмма показывает, как каждый отсчет выходного сигнала подвергается влиянию входного сигнала и импульсного отклика. Детали в тексте.
Порядок импульсного отклика внутри механизма свертки очень важен. Импульсный отклик переброшен слева на право. Это устанавливает отсчет номер 0 справа, и номера отсчетов возрастают налево. Сравните это с нормальным импульсным откликом на рисунке 6-5 для понимания геометрии этого переброса. Почему этот переброс необходим? Это вытекает из математики. Импульсный отклик описывает, как каждая точка входного сигнала воздействует на выходной сигнал. В результате, каждая точка выходного сигнала подвергается воздействию точек входного сигнала, взвешенных перебросанным импульсным откликом.
РИСУНОК 6-9
Механизм свертки в действии. Рисунки от (а) до (d) показывают механизм свертки, установленный для вычисления четырех разных отсчетов выходного сигнала y[0], y[3], y[8] и y[11].
Рисунок 6-9 показывает механизм свертки, используемый для вычисления нескольких отсчетов выходного сигнала. Эта диаграмма также иллюстрирует реальные нюансы свертки. В (а) механизм свертки расположен полностью слева с выходом, нацеленным на y[0]. В этой позиции, механизм пытается получить отсчеты входного сигнала x[-3], x[-2], x[-1] и x[0]. Проблема в том, что три из этих отсчетов, x[-3], x[-2] и x[-1], не существуют! Та же самая дилемма проявляется в (d), где механизм свертки пытается получить отсчеты правее, чем определен вход, точки x[9], x[10] и x[11].
Один способ решения этой проблемы заключается в изобретении несуществующих отсчетов. При этом добавляются отсчеты к концам входного сигнала с нулевой величиной. Это называется дополнением (padding) сигнала нулями. Вместо попытки получить несуществующие отсчеты, механизм свертки получит отсчеты с нулевой величиной. Поскольку эти нули пропадают при умножении, то математически это то же самое, что и игнорирование несуществующих отсчетов.
РИСУНОК 6-9 (продолжение)
Важный момент заключается в том, что крайние левые и крайние правые выходные отсчеты базируются на некомплектной информации. На жаргоне ЦОС это означает, что импульсный отклик не полностью погружен во входной сигнал. Если импульсный отклик имеет длину равную М точек, то первые и последние М-1 отсчетов выходного сигнала базируются на меньшей информации, чем отсчеты между ними. Это аналогично электронной цепи, которая требует определенное время для стабилизации (выхода на режим) после включения. Но разница между ними в том, что этот переходный период легко игнорировать в электронике, но он очень значителен в ЦОС.
Рисунок 6-10 показывает пример, где этот оконечный эффект может проявляться. Входной сигнал есть синусная волна плюс постоянный уровень. Задача заключается в удалении постоянного уровня при сохранении синусоиды без изменений. Для этого применяется высокочастотный фильтр с импульсным откликом, показанным на этом рисунке. Проблема заключается в том, что первые и последние 30 точек испорчены! Форма этих оконечных областей может быть понята путем добавления воображаемого сигнала с 30 нулями с левой стороны, отсчеты от x[-1] до x[-30], и 30 нулей справа, отсчеты от x[81] до x[110]. Выходной сигнал может затем рассматриваться как фильтрация этой удлиненной версии сигнала. Этот «оконечный эффект» является проблемой, которая широко распространена в ЦОС. В качестве общего правила, ожидайте, что начальные и конечные отсчеты при обработке сигналов будут бесполезными.
РИСУНОК 6-10
Оконечные эффекты свертки. Когда входной сигнал свертывается с M-точечным импульсным откликом, первые и последние М-1 точек входного сигнала могут быть негодными. В этом примере импульсный отклик высокочастотного фильтра используется для удаления постоянной составляющей из входного сигнала.
Теперь математика. Использую механизм свертки как руководящую линию, мы сможем написать стандартную формулу для свертки. Если x[n] есть N-точечный сигнал с номерами от 0 до N-1, и h[n] есть M-точечный сигнал с номерами от 0 до М-1, свертка этих сигналов, y[n] = x[n] * h[n], будет сигнал из N+M-1 точек с номерами от 0 до N+M-2, определяемый следующей формулой:
Эта формула называется сумма свертки (convolution sum). Она позволяет вычислить каждую точку выходного сигнала независимо от всех остальных точек выходного сигнала. Индекс i определяет номер отсчета выходного сигнала, который вычисляется, и поэтому соответствует позиции, отсчитываемой слева направо механизма свертки. В компьютерных программах, выполняющих свертку, цикл, соответствующий этому индексу, проходит через каждый отсчет выходного сигнала. Для вычисления одного выходного отсчета используется индекс j внутри механизма свертки. j меняется от 0 до М 1, так же как и отсчеты импульсного отклика h[j], умножается на соответствующий отсчет входного сигнала x[i-j]. Результаты умножения складываются для получения вычисляемого отсчета выходного сигнала. Изучайте формулу 6-1 до тех пор, пока полностью не поймете, как она выполняется с помощью механизма свертки. Многое в ЦОС базируется на этой формуле. (Не смущайтесь индексом n в выражении y[n] = x[n] * h[n]. Это всего лишь обозначение некоторого места в массиве. Иногда формула записывается в виде y[ ] = x[ ] * h[ ], чтобы избежать путаницы в символах.)
Таблица 6-2 представляет программу для выполнения свертки, используя выходную сторону алгоритма, прямое использование формулы 6-1. Эта программа дает тот же самый результат, что и программа, использующая входную сторону алгоритма согласно таблице 6-1. Разница между двумя программами заключается в том, что программа, использующая входную сторону алгоритма, петляет через каждый отсчет входного сигнала (линия 220 таблицы 6-1), в то время как программа, использующая выходную сторону алгоритма, петляет через каждый отсчет выходного сигнала (линия 180 таблицы 6-2).
Рассмотрим работу этой программы. Цикл FOR-NEXT в линиях 180-250 проходит через каждый отсчет выходного сигнала, используя индекс I%. Для каждой из этих величин внутренний цикл в линиях 200-230 вычисляет величину выходного отсчета Y[I%]. Величина Y[I%] устанавливается в ноль в линии 190, позволяя аккумулировать результаты вычисления внутри механизма свертки. Цикл FOR-NEXT в линиях 200-240 осуществляет прямое вычисление по формуле 6-1. Индекс J% обеспечивает прохождение через каждый отсчет импульсного отклика. Линия 230 обеспечивает перемножение каждого отсчета импульсного отклика H[J%] на соответствующий отсчет входного сигнала X[I%-J%] и суммирование результатов в аккумуляторе.
В линии 230 берется отсчет из входного сигнала X[I%-J%]. Линии 210 и 220 предотвращают выход за границы массива X[0] - X[80]. Другими словами эта программа игнорирует неопределенные отсчеты входного сигнала. Альтернативный способ может заключаться в определении входного массива от X[-30] до X[110], с добавлением 30 нулей с каждой стороны истинных данных. Как третья альтернатива, цикл FOR-NEXT в линии 180 может вычисляться от 30 до 80, вместо от 0 до 110. То есть, программа будет вычислять только те отсчеты выходного сигнала, для которых импульсный отклик полностью погружен во входной сигнал. Важно чтобы вы использовали один из этих трех способов. Если вы про них забудете, программа рухнет, когда она попытается прочитать граничные данные.
100 'СВЕРТКА, ИСПОЛЬЗУЮЩАЯ ВЫХОДНУЮ СТОРОНУ АЛГОРИТМА
110 '
120 DIM X[80] 'Входной сигнал, 81 точка
130 DIM H[30] 'Импульсный отклик, 31 точка
140 DIM Y[110] 'Выходной сигнал, 111 точек
150 '
160 GOSUB XXXX 'Воображаемая подпрограмма загрузки X[ ] и H[ ]
170 '
180 FOR I% = 0 TO 110 'Цикл для каждой точки в Y[ ]
190 Y[I%] = 0 'Обнуление отсчетов выходного массива
200 FOR J% = 0 TO 30 'Цикл для каждой точки в H[ ]
210 IF (I%-J% < 0) THEN GOTO 240
220 IF (I%-J% > 80) THEN GOTO 240
230 Y(I%) = Y(I%) + H(J%) * X(I%-J%)
240 NEXT J%
250 NEXT I%
260 '
270 GOSUB XXXX 'Воображаемая подпрограмма для хранения Y[ ]
280 '
290 END
ТАБЛИЦА 6-2
Сумма взвешенных входов
Характеристики линейной системы полностью описываются импульсным откликом. Это есть основа входной стороны алгоритма: каждая точка входного сигнала вносит вклад в выходной сигнал в виде масштабированной и сдвинутой версии импульсного отклика. Математические выводы приводят нас к выходной стороне алгоритма: каждая точка выходного сигнала получается от вклада многих точек входного сигнала, умноженных на переброшенный импульсный отклик. Хотя это все справедливо, это полностью не объясняет, почему свертка так важна при обработке сигналов.
Давайте вернемся назад к механизму свертки на рисунке 6-8, и не будем рассматривать сигналы внутри пунктирного квадрата, как импульсный отклик. Давайте их считать набором весовых коэффициентов, которые вставлены в диаграмму. С этой точки зрения каждый выходной отсчет является суммой взвешенных входов. Каждый отсчет выходного сигнала подвержен влиянию некоторой области отсчетов входного сигнала, это влияние определяется выбранными весовыми коэффициентами. Например, представьте, что имеется десять весовых коэффициентов, каждый величиной одна десятая. Тогда каждый отсчет выходного сигнала будет являться усреднением десяти входных отсчетов.
Двигаясь дальше в этом направлении, можно сказать, что весовые коэффициенты не требуют ограничения с левой стороны вычисляемого отсчета выходного сигнала. Например, рисунок 6-8 показывает вычисление y[6] из x[3], x[4], x[5], x[6]. Рассматривая механизм свертки как сумму взвешенных входов, можно расположить весовые коэффициенты симметрично относительно выходного отсчета. Например, y[6] можно получить из x[4], x[5], x[6], x[7], x[8]. Используя такую же запись для индексации, как на рисунке 6-8, весовые коэффициенты для этих пяти входов должны содержаться в h[2], h[1], h[0], h[-1], h[-2]. Другими словами, импульсный отклик, который соответствует нашему выбору симметричных весовых коэффициентов, требует отрицательной индексации. Мы вернемся к этому в следующей главе.
С математической точки зрения здесь имеется только одна концепция: свертка, определенная формулой 6-1. Однако научные и инженерные проблемы подходят к этой единственной концепции с двух разных направлений. Иногда вы будет желать рассматривать систему в терминах импульсного отклика. В другой раз вы будете понимать систему как набор весовых коэффициентов. Вам необходимо ближе ознакомиться с этими двумя взглядами, и понимать, как переключаться с одного на другой.