Показать меню

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

12.06.2021
14

Секционная (секционированная) свёртка — метод вычисления свёртки, используемый, когда количество элементов одной из входных последовательностей во много раз больше, чем количество элементов другой. Основные методы вычисления секционной свёртки — метод перекрытия с суммированием (англ. Overlap–add method) и метод перекрытия с накоплением (англ. Overlap–save method).

Вычисление

Пусть x = { x ( 1 ) , x ( 2 ) , … } {displaystyle x={x(1),x(2),ldots }} — неограниченная последовательность, h = { h ( 1 ) , … , h ( N ) } {displaystyle h={h(1),ldots ,h(N)}} — последовательность длины N {displaystyle N} , L {displaystyle L} — некоторое натуральное число.

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

Для вычисления линейной свёртки y = x ∗ h {displaystyle y=x*h} методом перекрытия с суммированием необходимо разделить последовательность x {displaystyle x} на смежные секции длины L {displaystyle L} :

x ( n ) = ∑ k = 0 + ∞ x k ( n ) , {displaystyle x(n)=sum limits _{k=0}^{+infty }x_{k}(n),}

где

x k ( n ) = { x ( n ) , n ∈ [ k L , ( k + 1 ) L − 1 ] , 0 , n ∉ [ k L , ( k + 1 ) L − 1 ] . {displaystyle x_{k}(n)=left{{egin{array}{rl}x(n),&nin [kL,,(k+1)L-1],,&n otin [kL,,(k+1)L-1].end{array}} ight.}

Тогда

y ( n ) = ∑ m = 0 N − 1 [ h ( m ) ∑ k = 0 + ∞ x k ( n − m ) ] = ∑ k = 0 + ∞ h ( n ) ∗ x k ( n ) = ∑ k = 0 + ∞ y k ( n ) . {displaystyle y(n)=sum limits _{m=0}^{N-1}[h(m)sum limits _{k=0}^{+infty }x_{k}(n-m)]=sum limits _{k=0}^{+infty }h(n)*x_{k}(n)=sum limits _{k=0}^{+infty }y_{k}(n).}

Длина каждой из частичных свёрток в данной сумме равна L + N − 1 {displaystyle L+N-1} , то есть имеется участок длины N − 1 {displaystyle N-1} , на котором k {displaystyle k} -я и ( k + 1 ) {displaystyle (k+1)} -я частичные свёртки перекрываются, поэтому их отсчёты на участке перекрытия нужно сложить. Отсюда и происходит название данного метода.

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

Пусть теперь длина секций x k {displaystyle x_{k}} последовательности x {displaystyle x} равна L + N − 1 {displaystyle L+N-1} и у этих секций есть участки перекрытия длиной N − 1 {displaystyle N-1} . Для каждой секции вычисляется циклическая свёртка h {displaystyle h} и x k {displaystyle x_{k}} , содержащая L + N − 1 {displaystyle L+N-1} отсчёт и обозначаемая y k {displaystyle y_{k}} . Необходимо отбросить последние N − 1 {displaystyle N-1} отсчётов этой последовательности, а остальные присоединить к последовательности y k − 1 {displaystyle y_{k-1}} . После выполнения этой процедуры для каждого k {displaystyle k} получится искомая последовательность y = x ∗ h {displaystyle y=x*h} .

Замечания

Число L {displaystyle L} удобно выбирать так, чтобы число L + N − 1 {displaystyle L+N-1} было степенью двойки. Тогда каждую из частичных свёрток можно эффективно выполнять с помощью быстрых алгоритмов, значительно снижая вычислительную сложность.

Еще по этой теме:
Теорема Миттаг-Леффлера
13:00, 18 апрель
Теорема Миттаг-Леффлера
Теорема Миттаг-Леффлера о разложении мероморфной функции — одна из основных теорем теории аналитических функций, дающая для мероморфных функций аналог разложения рациональной функции на простейшие
Среднее кубическое
04:36, 17 декабрь
Среднее кубическое
Среднее кубическое (также средняя кубическая) — число x {displaystyle x} , равное кубическому корню из среднего арифметического кубов данных чисел
Нётерово пространство
01:20, 15 декабрь
Нётерово пространство
Нётерово пространство (по имени Эмми Нётер) — топологическое пространство X, удовлетворяющее условию обрыва убывающих цепей замкнутых подмножеств. То есть для каждой последовательности замкнутых
Группа Гейзенберга
12:26, 14 декабрь
Группа Гейзенберга
Группа Гейзенберга — группа, состоящая из квадратных матриц вида ( 1
Среднее арифметическое взвешенное
11:33, 13 декабрь
Среднее арифметическое взвешенное
Среднее арифметическое взвешенное — математическое понятие, обобщающее среднее арифметическое. Среднее арифметическое взвешенное набора чисел x
Вариационный ряд
08:23, 03 декабрь
Вариационный ряд
Вариационный ряд (упорядоченная выборка) — последовательность X ( 1 ) ⩽
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent