В.В. Сюзев
6
причем реальное число умножений можно уменьшить за счет исклю-
чения умножений на тривиальные множители
1
±
. Кроме того, как
уже указывалось, нетривиальные умножения можно заменить на бо-
лее простые операции сдвига.
Пример 1.
Записать полный статический БТЧП Рейдера для
8
N
=
, построить его сигнальный граф и оценить сложность.
Решение.
В этом случае
3
n
=
и полный алгоритм будет содер-
жать два уровня прореживания (
1, 2
m
=
). Начальными его значения-
ми будут промежуточные выборки
1 2
2
, (
)
x
j i
λ λ
−
при
1 2
,
0
λ λ =
,1;
2
0,1
i
=
. Они будут равны:
{
}
0,0
2
(
)
( ), ( 4)
x j i
x j x j
− =
−
;
{
}
0,1
2
(
)
( 2), ( 6)
x j i
x j
x j
− = −
−
;
{
}
1,0
2
(
)
( 1), ( 5)
x j i
x j
x j
− = −
−
;
{
}
1,1
2
(
)
( 3), ( 7)
x j i
x j
x j
− = −
−
.
Далее в соответствии с общим алгоритмом (4)–(6) получаем:
• на втором уровне прореживания
1 2
2
( ,
0, 1;
0, 1)
k
λ λ =
=
:
2
2
(0)
(0,0)
(0,1)
2
2
2
2
(0)
(0,0)
(0,1)
2
2
2
2
( )
( ) 2
( );
(
2)
( ) 2
( );
k
j
j
j
k
j
j
j
X k X k
X k
X k
X k
X k
=
+
+ =
−
2
2
(1)
(1,0)
(1,1)
2
2
2
2
(1)
(1,0)
(1,1)
2
2
2
2
( )
( ) 2
( );
(
2)
( ) 2
( ),
k
j
j
j
k
j
j
j
X k X k
X k
X k
X k
X k
=
+
+ =
−
где
1 2
2
1 2
1 2
( , )
2
,
,
( )
( ) ( 1)
( 1)
k
j
X k x
j
x
j
λ λ
λ λ
λ λ
=
+ −
−
;
• на первом уровне прореживания
2
(
0, 1, 2, 3) :
k
=
1
1
(0)
(1)
(0)
(1)
1
2
2
1
1
1
( )
( ) 2 ( );
(
4)
( ) 2 ( )
k
k
j
j
j
j
j
j
X k X k
X k X k
X k
X k
=
+
+ =
−
.
Все операции в этих выражениях выполняются по модулю 17.
Сигнальный граф этого алгоритма приведен на рис. 1. Непосред-
ственно из него следует, что для реализации такого восьмиточечного
алгоритма необходимо выполнить 24 сложения и 5 умножений на
множители 2, 4 и 8. Число умножений на графе меньше, чем получа-
ется по оценке (7) при
3
n
=
, поскольку на нем исключены умноже-
ния на тривиальные множители, равные
1
±
.
Скользящие БТЧП Рейдера.
Для вывода алгоритма скользя-
щих БТЧП обратимся к первому уровню прореживания статиче-
