Таким образом
,
необходимо
3
N
элементарных сложений в независимо
-
сти от длины
K
.
Сравнение с известными методами
.
В работах
[1, 3]
рассматрива
-
ются два подхода непосредственной свертки
(
метод перекрытия с сум
-
мированием и метод перекрытия с накоплением
)
и три подхода быстрой
свертки
.
Методы быстрой свертки различаются требуемым объемом
вычислительных операций и памяти
,
а также степенью точности
,
свя
-
занной с ошибками округления
.
Первый подход
,
основанный на быстром преобразовании Фурье
(
БПФ
),
приводит к существенному сокращению требуемого количе
-
ства арифметических операций для
K >
32
[4, 5].
Недостатки этого
метода
—
значительные ошибки округления
,
большой объем памяти
,
требуемый для хранения комплексных экспоненциальных коэффици
-
ентов
,
и все еще значительный объем вычислений
.
В лучшем случае
метод сокращает число операций до
2
N
log
2
N
+
N
,
что необходимо для
прямого и обратного преобразований и перемножения коэффициентов
.
Второй подход
,
использующий теоретико
-
числовые преобразова
-
ния
(
ТЧП
),
является точным
,
так как служит для преобразования по
-
следовательностей в кольце целых чисел
.
Существенный недостаток
,
ограничивающий его применение в реальных системах
, —
зависимость
между длиной последовательности
N
и требуемой длиной кодового
слова
,
что приводит к длинным кодовым словам для больших
N
.
Третий подход основан на методах модульной арифметики в кольце
полиномов
,
обеспечивающих высокие эффективность и точность вы
-
числений
.
Недостаток этих методов заключается в сложности програм
-
мирования вычислений
,
которая зависит от длины обрабатываемой по
-
следовательности
.
Локальная свертка
.
Общим недостатком трех рассмотренных бы
-
стрых методов является сложность локального интегрирования
“
на
месте
”.
Практические приложения
,
такие как распознавание образов
с сегментированием
,
часто требуют локальную обработку сигнала в
некоторой области
S
,
часто заданной бинарной маской
:
s
n
=
n
∈
S
f
n
c
n
−
n
.
В методах
,
основанных на преобразованиях
(
БПФ
,
ТЧП
),
происходит
дополнение области до прямоугольной нулевыми или средними значе
-
ниями
.
Это приводят к искажению исходного сигнала и существенным
ошибкам на границах
.
Преимущества метода свертки с вычислением разностей
:
высокая
эффективность для свертки больших последовательностей с повторя
-
ющимися значениями
;
высокая точность для последовательностей це
-
60 ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. “
Приборостроение
”. 2005.
№
3
