Число действительных умножений при вычислении свертки двух n-точечных последовательностей

№	Прямой метод	Быстрая свертка	Прямой метод / Быстрая свертка
8	64	448	0,14
16	256	1088	0,24
32	1024	2560	0,40
64	4096	5888	0,70
128	16 384	13 312	1,23
256	65 536	29 636	2,21
512	262 144	65 536	4,00
1024	1 048 576	143 360	7,31
2048	4 194 404	311 296	13,47

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

19. Вычисление линейной свертки с секционированием.

Существует два метода с секционированием свертки: метод перекрытия с суммированием и метод перекрытия с накоплением.

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

(1.180)

где

Линейная свертка последовательностей и будет определяться следующим образом:

(1.181)

Меняя порядок суммирования и учитывая то, что последовательности и имеют конечную длину, получим

(1.182)

Отсюда следует, что в самом начале вычисляется k-я частичная линейная свертка последовательностей и Длина каждой из частич­ных сверток в данной сумме равна () отсчетам (рис. 1.32 д, е), т. е. имеется участок, состоящий из () = () отсчетов, на котором k-я и (k + 1)-я частичные свертки перекрываются, поэтому согласно выражения для соответствующие отсчеты на участке перекрытия необходимо сложить (рис. 1.32 ж). Отсюда и название данного метода: метод перекрытия с суммированием (промежуточные частичные свертки перекрываются и для получения конечного результата их необходимо сложить).

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

В этом методе неограниченная последовательность (рис. 1.33 б) де­лится на секции k = 0, 1, … длиной отсчетов с участками перекрытия длиной Последовательность (рис. 1.33 а) дополняется нулями до длины в N отсчетов

(1.183)

x₁(n)

n

N₁

а

б

в

г

д

ж

е

x₂(n)

N₂

N₂

N₂

N₂

N₂

N₁ + N₂ – 1

N₁ + N₂ – 1

N₁ – 1

Рис. 1.32. Вычисление свертки методом перекрытия суммированием

После этого вычисляются секционированные круговые свертки содержащие () отсчет (рис. 1.33 д, е):

(1.184)

(1.185)

Следует отметить, что в этом случае

Представим последовательности и в виде сумм:

(1.186)

(1.187)

где и – последовательности на участках перекрытия длиной ().

Тогда частичные свертки и можно представить в виде

(1.188)

(1.189)

где и – не представляющие интереса свертки длиной (), обусловленные вкладом отсчетов и на участках перекрытия.

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

Рис. 1.33. Вычисление свертки методом перекрытия с накоплением

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