Составители:
Рубрика:
Покомпонентное произведение a и b обозначается a · b.
Теорема 5. Пусть
a = (a
0
, a
1
, . . . , a
k−1
, 0, . . . , 0)
T
, (6.4)
b = (b
0
, b
1
, . . . , b
k−1
, 0, . . . , 0)
T
(6.5)
– векторы размерности 2k, пусть n = 2k и
ba = F (a),
b
b = F (b) (6.6)
– их дискретные преобразования Фурье, т.е.
ba = (ba
0
, ba
1
, . . . , ba
n−1
)
T
, (6.7)
b
b = (
b
b
0
,
b
b
1
, . . . ,
b
b
n−1
)
T
, (6.8)
ba
j
=
n−1
X
i=0
a
i
ω
ij
,
b
b
j
=
n−1
X
i=0
b
i
ω
ij
, (6.9)
ω – первообразный корень n-ой степени из единицы (в кольце K).
Тогда
a ∗ b = F
−1
(ba ·
b
b). (6.10)
Д о к а з а т е л ь с т в о. Ввиду соотношений (6.4),(6.5)
ba
j
=
k−1
X
i=0
a
i
ω
ij
,
b
b
j
=
k−1
X
s=0
b
s
ω
sj
, (6.11)
и значит
ba
j
b
b
j
=
k−1
X
i=0
k−1
X
s=0
a
i
b
s
ω
(i+s)j
, (6.12)
Введём в рассмотрение свёртку
c = a ∗ b, (6.13)
По определению свёртки
3
c = (c
p
), c
p
=
X
i
a
i
b
p−i
, (6.14)
3
Проверить, что представление (6.14), (6.15) с учётом формул (5.5), (5.6) соответствуют
определениям преобразования Фурье и свёртки, данным ранее в пунктах 3 и 5 соответствен-
но.
13
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
