Составители:
Рубрика:
Лемма доказана.
Пример. При n = 8 имеем k = 3. Составим список c
0
, c
1
, . . . , c
7
следуя правилу (8.17). Для этого найдём j = rev
3
(j) для j =
0, 1, 2, 3, 4, 5, 6, 7. Нетрудно видеть, что
rev
3
(0) = rev
3
(000) = 000 = 0,
rev
3
(1) = rev
3
(001) = 100 = 4,
rev
3
(2) = rev
3
(010) = 010 = 2,
rev
3
(3) = rev
3
(011) = 110 = 6
и т.д., так что приходим к списку
ω
0
, ω
4
, ω
2
, ω
6
, ω
1
, ω
5
, ω
3
, ω
7
.
Соответствующие многочлены q
l,m
имеют вид (8.18). Их удобно
изображать в виде дерева.
Для БПФ в этом случае последовательно вычисляются остатки:
при m = 2 – остатки r
0,2
, r
4,2
от деления p(x) на x
4
− ω
0
и на
x
4
− ω
4
(степень 3),
при m = 1 остатки r
0,1
, r
2,1
от деления r
0,2
(x) на x
2
− ω
0
и на
x
2
− ω
4
(степень 1),
при m = 1 остатки r
4,1
, r
6,1
от деления r
4,2
(x) на x
2
− ω
2
и на
x
2
− ω
6
(степень 1),
при m = 0 остатки r
0,0
, r
1,0
от деления r
0,1
(x) на x − ω
0
и на
x − ω
4
(степень 0),
при m = 0 остатки r
2,0
, r
3,0
от деления r
2,1
(x) на x − ω
2
и на
x − ω
6
(степень 0) и т.д.
Заметим, что ввиду леммы 1 те же остатки получились бы, если
бы каждый раз делился бы многочлен p(x), но делить остатки эко-
номнее, ибо их степень меньше (здесь в примере степени остатков
3, 1 и 0, а в общем случае степень r
l,m
равна 2
m
− 1).
Заметим также, что в этой схеме остаток r
l,m
(имеющий, как
отмечено выше, степень 2 ∗ 2
m−1
− 1) приходится делить на бином
вида x
2
m−1
− c. Оказывается, многочлен степени 2t − 1 достаточно
просто разделить на бином x
t
− c (в интересующем нас случае t =
2
m−1
).
21
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
