Секционная свертка

Свертка – основной процесс в цифровой обработке сигналов. Поэтому важно уметь эффективно ее вычислять.

Уравнение дискретной свертки двух функций (сигналов) может быть получено непосредственно из интегрального уравнения свертки при замене интегрирования суммированием мгновенных значений функций с шагом Dt:

y(kDt) = Dth(nDt) s(kDt-nDt). (8.11)

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

y(k) =h(n) s(k-n) ºh n s k-n º y k . (8.11")

y(k) = h(n) * s(k-n) º s(k) * h(n) º s k * h n .

Техника свертки приведена на рис. 8.8. Для вычисления свертки массив одной из функций (s k - входного сигнала) располагается по ходу возрастания номеров. Массив второй функции (h n - более короткой, оператор свертки), строится параллельно первому массиву в обратном порядке (по ходу уменьшения номеров, в режиме обратного времени). Для вычисления y k значение h 0 располагается против s k , все значения s k-n перемножаются с расположенными против них значениями h n и суммируются. Результаты суммирования являются выходным значением функции y k , после чего оператор h n сдвигается на один номер k вперед (или функция s k сдвигается ему навстречу) и вычисление повторяется для номера k+1 и т.д.

Рис. 8.8. Техника дискретной свертки

В начальный момент свертки при вычислении значений y k оператор h n , построенный в режиме обратного времени, "зависает" для значений k-n при n>k против отсутствующих отсчетов входной функции. "Зависание" исключают либо заданием начальных условий - дополнительных отсчетов, чаще всего нулевых или равных первому отсчету входной функции, либо началом свертки с отсчета входной функции k = n с соответствующим сокращением интервала выходной функции. Для операторов со значениями -n (вперед по времени) такой же момент может наступать и в конце входного массива.

Пример. Уравнение свертки: y k =b n x k-n = b o x k + b 1 x k-1 + b 2 x k-2 .

Значения оператора bn: b o = 5, b 1 = 3, b 2 = 2.

Входной сигнал: x k = {0,1,0,0,0}, начальные условия: x - n = 0.

Расчет выходного сигнала:

y o = 5x o + 3x -1 + 2 x -2 = 5 · 0 + 3 · 0 + 2 · 0 = 0, y 1 = 5x 1 + 3x o + 2x -1 = 5 · 1 + 3 · 0 + 2 · 0 = 5,

y 2 = 5x 2 + 3x 1 + 2x o = 5 · 0 + 3 · 1 + 2 · 0 = 3, y 3 = 5x 3 + 3x 2 + 2x 1 = 5 · 0 + 3 · 0 + 2 · 1 = 2,

y 4 = 5x 4 + 3x 3 + 2x 2 = 5 · 0 + 3 · 0 + 2 · 0 = 0, y 5 = 5x 5 + 3x 4 + 2x 3 = 5 · 0 + 3 · 0 + 2 · 0 = 0

Выходной сигнал: yk = {0, 5, 3, 2, 0}

Заметим: свертка функции оператора с единичным входным сигналом представляет собой повторение функции оператора свертки на выходе.

На рис. 8.9 приведен пример выполнения дискретной свертки каузальным (односторонним) и четным (симметричным, двусторонним) оператором одного и того же сигнала.

Рис. 8.9. Примеры выполнения дискретной свертки

Прямое вычисление свертки требует K·N умножений, где K – длина исходного сигнала, а N – длина ядра свертки. Как длина сигнала, так и длина ядра свертки может достигать нескольких тысяч точек, и число умножений становится огромным.

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

s(k) Û S(w), h(n) Û H(w), Y(w) = S(w)×H(w), Y(w) Û y(k).

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

Выполнение произведения спектров может производиться только при одинаковой их длине, и оператор h(n) перед ДПФ необходимо дополнять нулями до размера функции s(k).

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

На рис. 8.10 приведены результаты свертки сигнала s k , заданного на интервале k=(0-50), с функцией h n = a×exp(-a×n), a = 0.1. Свертка, выполненная через ДПФ, в левой части интервала резко отличается от линейной свертки. Характер искажения становится понятным, если дополнить главный интервал с левой стороны его периодическим продолжением (на рисунке показана часть левого бокового периода, свертка с которым заходит в главный период). Для операторов h n со значениями n, вперед по положению, аналогичные искажения появятся и в правой части главного периода. Для устранения таких искажений сигнальная функция должна продлеваться нулями на размер оператора h(n), что исключит наложение боковых периодов главной трассы функции.

Рис. 8.10. Результаты двух видов свертки

При выполнении свертки через БПФ ощутимое повышение скорости вычислений появляется только при большой длине функций и операторов (например, M>1000, N>100). Следует также обращать внимание на разрядность результатов, т.к. перемножение чисел дает увеличение разрядности в 2 раза. При ограниченной разрядности числового представления с соответствующим округлением это может приводить к погрешностям суммирования.

В системах оперативной обработки данных часто возникает потребность вычислить свертку сигнала, поступающего на вход системы последовательными порциями (например, от датчиков скважинных приборов). В таких случаях применяется секционная свертка . Суть ее состоит в том, что каждая из этих частей сворачивается с ядром отдельно, а полученные части объединяются. Для объединения достаточно размещать их друг за другом с перекрытием в N-1 точку (N – длина ядра свертки), и производить суммирование в местах перекрытия.

Во многих практических задачах необходимо вычислять свертку двух конечных последовательностей, когда одна из них гораздо длиннее другой (скажем, или). Конечно, всегда можно выбрать равным , но такой подход неэффективен и по ряду причин неудобен. Во-первых, перед вычислением свертки нужно иметь всю более длинную последовательность. На практике, например в радиолокации или при обработке речевых сигналов, это условие не всегда выполнимо. Во-вторых, поскольку обработка начинается только после приема всей последовательности, то результат получается с большой задержкой. И наконец, при слишком больших вычисление ДПФ значительно усложняется, так как для этого требуется большой объем памяти и возникают некоторые другие, чисто практические трудности, связанные с алгоритмами БПФ. От перечисленных недостатков свободны следующие два метода вычисления свертки. Они основаны на разбиении более длинной последовательности на секции и вычислении частичных сверток, из которых затем формируется искомая выходная последовательность.

Первый из них называется методом перекрытия с суммированием. Сущность этого метода иллюстрируется на фиг. 2.32. Для простоты положим, что последовательность не ограничена, a содержит отсчетов. Разделим последовательность на смежные секции длиной по отсчетов (фиг. 2.32). Выбор довольно сложен, но хорошие результаты получаются, если является величиной того же порядка, что и .Итак, входная последовательность представляется в виде

(2.166)

Фиг. 2.32. Метод перекрытия с суммированием.

(2.167)

Линейная свертка последовательностей и равна

(2.168)

(2.169)

Фиг. 2.33. Формирование выходных значений свертки при использовании метода перекрытия с суммированием.

Длина каждой из частичных сверток в сумме (2.169) равна отсчетам, т. е. имеется участок длиной в отсчетов, на котором -я и -я частичные свертки перекрываются, поэтому их отсчеты на участке перекрытия нужно сложить. На фиг. 2.33 показано, как расположены и как суммируются соседние частичные свертки . Каждая из них вычисляется методом быстрой свертки, описанным в разд. 2.24. Рассмотренный метод был назван методом перекрытия с суммированием именно потому, что промежуточные частичные свертки перекрываются и для получения конечного результата их необходимо сложить.

Фиг. 2.34. Метод перекрытия с накоплением.

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

Кафедра ВТ

РЕФЕРАТ

по дисциплине: «Цифровая обработка сигналов»

на тему: «Линейная свертка детерминированных последовательностей»

Выполнил:

Проверил:

г. Санкт-Петербург, 2014 г.

1. Введение 3

2. Линейная свертка 4

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

4. Секционированные свертки 7

5. Литература 11

Введение

Операция свертки:

s(t) = x(t) * h(t) = (1)

В дискретном случае различают два вида сверток: линейную (или апериодическую) и циклическую. Циклическую свертку еще часто называют круговой или периодической.

Линейная свертка

Рассмотрим линейную свертку. Пусть имеется два дискретных сигнала a(n), n=0..N-1, и b(n), n=0..M-1. В общем случае длины этих сигналов N и M могут отличаться. Линейной сверткой сигналов a(n) и b(n) называется дискретный сигнал вида:

s(n) = a*b = (2)

Для вычисления линейной свертки сигналы a(n) и b(n) сдвигают относительно друг друга почленно перемножают и складывают. При этом предполагается, что a(n) = 0 при n<0 и n>N, а также b(n)=0 при n<0 и n>M

Графическое представление линейной свертки представлено на рисунке 1.

Рисунок 1: Графическое представление линейной свертки

Отсчеты сигнала b(n) сдвигаются относительно отсчетов последовательности a(n) все возможные перекрывающиеся отсчеты почленно перемножаются и складываются.

На рисунке 2 приведен пример вычисления линейной свертки двух сигналов a(n) = длиной 4 отсчета и b(n)=[-1,1,2] длиной 3 отсчета.

Рисунок 2: Пример вычисления линейной свертки.

Необходимо отметить, что сигнал b(n) при вычислении свертки отражается слева-направо, поскольку b(0)=-1 самый первый отсчет (самый ранний по времени) и обрабатываться он также должен первым.

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

Рассмотрим теперь циклическую свертку. В случае циклической свертки предполагается, что дискретные сигналы a(n) и b(n) - периодические с одинаковым периодом N отсчетов. Тогда круговой сверткой сигналов a(n) и b(n) называется сигнал вида:

s(n) = (3)

Результат циклической свертки также имеет длину N отсчетов.

Рассмотрим циклическую свертку на примере двух сигналов a(n)= и b(n)=[-1,3,2,1] . Графически вычисление циклической свертки представлено на рисунке 3.

Рисунок 3: Вычисление циклической свертки

Красной линией отмечены границы периодов повторения сигнала b(n-m). Заметим, что в силу периодичности сигналов b(-m)=b(N-m).

Вычислим свертку пошагово:

Теперь рассчитаем s(1):

Приведем пример вычисления линейной свертки через циклическую для a(n)= длиной 4 отсчета и b(n)=[-1,1,2] длиной 3 отсчета (этот пример был рассмотрен выше).

Дополним нулями a(n)= и b(n)=[-1,1,2,0,0,0], так чтобы в каждой последовательности было по 6 отсчетов.

Вычислим циклическую свертку как это показано на рисунке 4.

Рисунок 4: Вычисление линейной свертки через циклическую <

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

Секционированные свертки

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

Первый из них называется методом перекрытия с суммированием. Сущность этого метода иллюстрируется на рис.5. Для простоты положим, что последовательность x(n) не ограничена, a h(n) содержит отсчетов. Разделим последовательность x(n) на смежные секции длиной по отсчетов (рис. 5). Выбор довольно сложен, но хорошие результаты получаются, если является величиной того же порядка, что и .Итак, входная последовательность x(n) представляется в виде

рис.5. - Метод перекрытия с суммированием.

Линейная свертка последовательностей x(n) и h(n) равна

рис.6. - Формирование выходных значений свертки при использовании метода перекрытия с суммированием.

Длина каждой из частичных сверток в сумме (4) равна () отсчетам, т. е. имеется участок длиной в () отсчетов, на котором k-я и (k+1)-я частичные свертки перекрываются, поэтому их отсчеты на участке перекрытия нужно сложить. На рис. 6 показано, как расположены и как суммируются соседние частичные свертки . Рассмотренный метод был назван методом перекрытия с суммированием именно потому, что промежуточные частичные свертки перекрываются и для получения конечного результата их необходимо сложить.

рис.7 -. Метод перекрытия с накоплением.

Другой метод вычисления линейной свертки последовательностей, одна из которых значительно длиннее другой, также основан на секционировании более длинной последовательности. Его называют методом перекрытия с накоплением, причем в данном случае перекрываются входные, а не выходные секции. Ошибочные отсчеты круговых сверток отдельных секций отбрасываются. Остальные отсчеты накапливаются и из них формируется конечный результат. Рассмотрим конкретный пример (рис. 7). Последовательность h(n) содержит отсчетов, а последовательность x(n) разделена на секции длиной по ()отсчетов, перекрывающиеся друг с другом на участках длиной по отсчетов. (Отметим, что участок перекрытия находится в конце последовательности . Это удобно для вычисления круговой свертки с помощью ДПФ.)

рис. 8. - Формирование выходных значений свертки при использовании метода перекрытия с накоплением.

Для каждой секции вычисляется круговая свертка последовательностей h(n) и , содержащая ()отсчет. В результате получается набор последовательностей ), изображенных па рис.8. Последние () отсчетов каждой из последовательностей отбрасываются (они неверны из-за циклического характера свертки), а остальные присоединяются к правильным отсчетам последовательности и т. д. В результате получается искомая последовательность, тождественная свертке y(n). Итак, используя метод перекрытия с суммированием или метод перекрытия с накоплением, можно сравнительно легко найти свертку короткой и очень длинной последовательностей, причем результат получается в виде отдельных небольших секций, которые объединяются соответствующим образом в одну последовательность.

Литература

1. Цифровая обработка сигналов изображений: учеб. пособие / С.М. Ибатуллин; Санкт-Петербургский государственный электротехнический университет им. В.И. Ульянова (Ленина) "ЛЭТИ" . - СПб. : Изд-во СПбГЭТУ "ЛЭТИ", 2006.

2. Цифровая обработка сигналов: учеб. пособие для вузов / А.Б.Сергиенко; - СПб. : Питер, 2002.

3. Алгоритмы и процессоры цифровой обработки сигналов: Учеб. пособие для вузов / А. И. Солонина, Д. А. Улахович, Л. А. Яковлев. - СПб. : БХВ-Петербург, 2001.

4. Цифровая обработка сигналов = Understanding digital signal processing / Р. Лайонс; пер. с англ. под ред. А. А. Бритова. - 2-е изд. - М. : Бином, 2007.

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

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

Простейший для понимания метод секционированной свертки носит название метода перекрытия с суммированием. Разделим двумерный массив на -точечные секции, определив секцию с индексами следующим образом:

Опорная область для одной такой секции изображена на рис. 3.1,а. Опорные области секций не перекрываются, и все вместе покрывают всю опорную область массива , поэтому

. (3.13)

Рис. 3.1. Метод перекрытия с суммированием.

а - секция входной последовательности ; б - опорная область результата свертки этой секции с .

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

(3.14)

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

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

Другой разновидностью секционированной свертки является метод перекрытия с накоплением. Взглянув еще раз на рис. 3.1, можно заметить, что если размер секции существенно превышает размер опорной области отклика , то отсчеты в центре каждой секции не перекрываются отсчетами из соседних секций. Точно так же при циклической свертке последовательности с другой последовательностью , имеющей гораздо меньшую опорную область, только часть отсчетов циклической свертки будет испытывать эффект пространственного наложения. Остальные отсчеты будут идентичны отсчетам линейной свертки. Расположение этих отсчетов показано на рис. 3.2. Таким образом, если выполнить циклическую свертку -точечной секции последовательности с -точечным импульсным откликом с использованием -точечного ДПФ, результат этой свертки будет содержать область, состоящую из отсчетов, идентичных отсчетам линейной свертки . Полный выходной массив можно составить из этих «хороших» отсчетов при правильном выборе опорных областей входных секций. Если входные секции перекрываются, можно добиться того, чтобы «хорошие» области соседних секций примыкали друг к другу. Таким образом, метод перекрытия с накоплением требует перекрытия входных секций, в то время как при использовании метода перекрытия с суммированием перекрываются выходные секции.

Рис. 3.2. Метод перекрытия с накоплением. Заштрихованная область содержит отсчеты , для которых циклическая свертка с периодом и линейная свертка с дают идентичные результаты.

Для процедур перекрытия как с суммированием, так и с накоплением выбор размеров секций сильно влияет на эффективность реализации. Прежде всего этот выбор очевидным образом влияет на объем требуемой памяти, а также и на объем вычислений. Из рис. 3.2 видно, что доля полезных отсчетов циклической свертки возрастает по мере увеличения размеров секции по отношению к размерам импульсного отклика. Хотя какие-то общие утверждения относительно того, сколь велики должны быть входные секции, затруднены из-за сильной зависимости результатов от конкретной ЭВМ, эксперименты Тугуда и др. показали, что для фильтров с размерами опорной области от до выборок требуется размер секций . Это слишком много для большинства мини-ЭВМ. Таким образом, получается, что быстродействие алгоритма ограничивается доступной памятью. Если это так, то следует выбирать входные секции максимально возможного размера.

Секционная свертка

Для реализации этого типа свёртки нужно выполнить следующие действия:

1. поделить большую последовательность на секции, желательно чтоб в каждой секции было одинаковое количество элементов;

2. произвести подсчет количества значений частичной выходной последовательности (чвп) по формуле:

N чвп =N с +N-1 где N чвп - количество значении в частичной выходной последовательности; Nс - количество:значении в данной секции; N - количество значении во второй последовательности.

3. произвести свёртку каждой секции первой последовательности со второй последовательностью. Количество сверток должно совпадать с количеством секций в первой последовательности.

Для секционной свёртки методом перекрытия с суммированием могут применяться такие виды свертки как:

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

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

Для секционной свертки методом перекрытия с наложением применяется только круговая свертка. Для секционной свертки методом перекрытия с суммированием сборка осуществляется так: на отрезке от (N-1) до N чвп произвести суммирование значений от секции 1 и 2 до секции Z-1 и Z (где Z - количество секции). А для секционной свертки методом перекрытия с накопления: последние значения на отрезке (N - 1) до N чвп нужно отбросить, то есть их не учитывают при сборке выходной последовательности, и так от секции 1 до секции Z-1.

Wikimedia Foundation . 2010 .

Секхукхуне
Секционные ворота

Смотреть что такое "Секционная свертка" в других словарях:

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

Цифровая обработка сигналов - (ЦОС, DSP англ. digital signal processing) преобразование сигналов, представленных в цифровой форме. Любой непрерывный (аналоговый) сигнал может быть подвергнут дискретизации по времени и квантованию по уровню (оцифровке), то… … Википедия

Снование - так называется подготовительная операция в ткацком производстве, имеющая целью приготовить основу (см.). Она состоит, вообще говоря, в том, что требуемое для основы количество нитей перематывается с отдельных катушек на общий большой вал, наз.… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона