Секционная свёртка
Секционная (секционированная) свёртка — метод вычисления свёртки, используемый, когда количество элементов одной из входных последовательностей во много раз больше, чем количество элементов другой[1]. Основные методы вычисления секционной свёртки — метод перекрытия с суммированием[англ.] и метод перекрытия с накоплением[англ.].
Вычисление
правитьПусть — неограниченная последовательность, — последовательность длины , — некоторое натуральное число.
Метод перекрытия с суммированием
правитьДля вычисления линейной свёртки методом перекрытия с суммированием необходимо разделить последовательность на смежные секции длины :
где
Тогда
Длина каждой из частичных свёрток в данной сумме равна , то есть имеется участок длины , на котором -я и -я частичные свёртки перекрываются, поэтому их отсчёты на участке перекрытия нужно сложить. Отсюда и происходит название данного метода[2].
Метод перекрытия с накоплением
правитьПусть теперь длина секций последовательности равна и у этих секций есть участки перекрытия длиной . Для каждой секции вычисляется циклическая свёртка и , содержащая отсчёт и обозначаемая . Необходимо отбросить последние отсчётов этой последовательности, а остальные присоединить к последовательности . После выполнения этой процедуры для каждого получится искомая последовательность [3].
Замечание
правитьЧисло удобно выбирать так, чтобы число было степенью двойки. Тогда каждую из частичных свёрток можно эффективно выполнять с помощью быстрых алгоритмов, значительно снижая вычислительную сложность.
Примечания
править- ↑ Рабинер, Гоулд, 1978, с. 76.
- ↑ Рабинер, Гоулд, 1978, с. 76—78.
- ↑ Рабинер, Гоулд, 1978, с. 78—81.
Литература
править- Рабинер, Л., Гоулд, Б.. Теория и применение цифровой обработки сигналов. — М.: Мир, 1978.
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |