Page 258 - 4196

y  x r 2  x 0 , x 2 ,..., x n 2 ,
r
z  x r 2 1   x 1 , x 3 ,..., x n 1 ,
r
r  1 , 0 ,..., n 2  . 1
Дискретні перетворення Фур’є послідовностей
x r y , r z , r пов’язані між собою:

1    2 k   
X   Y  exp  j    Z k , 

k
k
2    n    

1    2 k   
X k 2 / n   Y  exp  j    Z k ,  (5.76)

k
2     n   

1 n 2 1   2 k r  
Y   y  exp  j   ,

r
k
2 / n r 0   2 / n  
1 n 2 1   2 k r  
Z   z  exp  j   ,

r
k
2 / n r 0   2 / n  
k  1 , 0 ,..., 2 / n  . 1
Таким чином, виконавши ДПФ двох часткових рядів y і
r
z можна отримати ДПФ всієї послідовності x . Проце-
r
r
дуру утворення 2-х часткових рядів із попереднього мо-
жна продовжити, якщо число членів попереднього ряду
m
являється парним. В загальному випадку, якщо n  2 ,
можна виконати m послідовних операцій утворення 2-х
часткових рядів з кожного попереднього так, що на
останньому кроці кожний з часткових рядів буде склада-
тися з одного елемента.
Алгоритм ШПФ виконується ітеративне. На пер-
шому кроці обчислюється n одно точкових перетворень,
які на наступному кроці попарно об’єднуються, утвори-
вши /n 2 двох точкових перетворень. Вони, у свою чер-
гу, об’єднуються, утворивши n 4 / чотирьох точкових

258