Цифровая обработка сигналов: Справочник - Гольденберг Л.М.
Скачать (прямая ссылка):
= W:
9 w6
^9 (r)9
x(0)
x(3 T)
-X (6 T)
Последовательности X(k) и X(k) такие, что
34
хо) X(l) X(l)
X(2) x (2) X(2)
X (4) + 5(4) = X (4)
X (8) X(8) X (8)
X(7) X(7) X (7)
-X (5) _ _X(5),_ -X (5)_
т;
Таким образом, вычисление 9-точечного ДПФ свелось к вычислению 6-точечной
круговой свертки и двух 3-точечных ДПФ, которые, в свою очередь, можно
определить с помощью 2-точечной круговой свертки.
3. Пусть N=2a, а>2-целое. В этом случае вычисление ДПФ сводится к
вычислению двух 2"-'-точечных ДПФ и двумерной 2Х2а_2-точечной круговой
свертки, матрица которой имеет вид
W
2 а-2
W
2а-2
W
2а-1
где W'2"-2 и W"2a-2 представляют собой циклические матрицы размера 2a-2 X
Х2а-2. Взаимно-однозначное соответствие между показателями степени qt и
9* элементов матриц W'2"_2 и W"2a -2 и индексами элементов матрицы (1.43)
имеет вид [1-12]-
qx = 5" (mod 2a); q2 = -5" ( mod 2а), n = 0, ... , 2" 2 - 1. Пример 1.22.
Пусть N=23. Соответствия (1.74) запишутся так:
(1.74)
Тогда:
Х(1) Х(5)
X (7)
_Х(3)_
щью 4-точечного ДПФ:
2*
1 5' q2- 1
w2 =
W\ W\
wl w.
w2 =
8 "¦ 8_ Wj1 U7-51
W75 vr-11
К wl WJ5
К к 1 00 W-'
V Wj* wi к
Г-5 w~l w\ w\
fe=0, .... 3, и X(k) , k=
35
x{T) x<5 T) x (7 T)
-X(3T)_
,, 7, вычисляются с по MO-
-Х(0) - " 1 1
X (2) I w\
Х(4) 1 wl
_Х(6) _ 1 оо о
-I 1 1
1 i -1
1 - 1 1
_1 - i -1
Х(0) X (4)
Х(1) X (5)
Х(2) Х(б)
1 00, и* 1 - X (7) _
I
к
1
w\
к
к
8__
х (0) + * (4 Т) х(Т) +*(5 Г) х (2 Г)+ *(6 Г) х(ЗТ) + х( 7 Т) х (0) +
х (4 ТУ
х{Т) +*(5Г)
*(2Т) + *(6 Т) х(ЗТ) + х(7 Г)_
1 1
i -1 1 1
-i -1
I
х(0) х (2 Т) х (4 Т) _*(6 Т)_
Последователькости X(k) к X (/г) такие, что
X (1) X (1) X (1)
Х(5) + X (5) X (5)
-
X (7) X (7) X (7)
_ X (3) _ -X (3)_ _ х (3) _
Вычисление ДПФ рассматриваемым методом не требует умножения на
комплексные коэффициенты, т. е. коэффициенты являются либо чисто
действительными, либо чисто мнимыми. Вычисление ДПФ комплексных
последовательностей требует вдвое больше операций умножения и сложения.
В [1.12] приведены алгоритмы вычисления ДПФ коротких последовательностей
для N-2, 3, 4, 5, 7, 8, 9, 16. В табл. 1.6 приводится число требуемых при
этом арифметических операций.
Вычисление ДПФ длинных последовательностей. Пусть N=*NfN2 и Л7] и N2 -
взаимно-простые числа. Если сделать перестановку входной и выходной
последовательностей, как и в алгоритме взаимно-простых делителей (см.
1.3.5), то
Таблица 1.6
N Число операций N Число операций
умноже- ния умножения на W0 сложения умноже- ния умножения
на W0 сложения
2 0 2 2 1 ; 7 8 1 36
3 2 1 6 ! 8 2 6 26
4 0 4 8 i 9 10 1 45
5 5 1 17 j 16 10 8 74
36
Go ~ ~w°3 w5 w°3 w5 w°3 ws_ 1 S a 1
= ^3 w5 ""в Wg wl Wg (1.75)
U, _ .*t Wg W\ Wg Wg_ -Щ -
матрицу исходного ДПФ можно представить в виде прямого произведения
матриц N1- и ЛГ2-точечных ДПФ:
Пример 1.23. Пусть N=lb; Ni=3; N2=5. Из уравнений (1.37) и (1.38) Si-3=1
(mod 5); S2-5=l (mod3), т. е. Si=S2=2. Переставим элементы х(пТ) согласно
(1.35):
х (("1-5+ п2) Т) = х (("г-З + ^-б) (mod 5)-Г), ^ = 0, 1, 2 ; п2 = 0, ...
, 4. Введем векторы:
uft = {х'((Of-5k) Т),х ((1 + 5k) Т), х ((2 + 5 k) Т), х ((3 + 5k) Г),
x((4 + 5k) Т)]Т;
Uft=[X(0 + 5?),X(l + 5?), Х(2 + 5?), X (3 + 5 ft), X(4 + 5ft)]T, ft =
0,1,2. Тогда искомое ДПФ преобразуется к виду
X =
где Ц73=е~12л/3; W - матрица 5-точечного ДПФ.
Матрица выражения (1.75) и есть прямое произведение W3(r)W5.
Для вычисления векторов Uo, Ui и U2 воспользуемся алгоритмом вычисления
3-точечного ДПФ [1.12]:
§i = ux + u2; S2 = ux-u2 ; S3 = Sx + u" ;
- - / 2 л \ - 2л -
m0 = Ws S3 ; т* = I cos -- lj W5 Sx ; т2 = i sin - W5 S2 ;
S4 = m0 -j- mj; S2, 7 - S,. -j- m2; S(; = S_. - m2 ;
U0 -- H!q ; Uj = S5 j U2 = S6.
Для вычисления векторов mo, mi и m2 необходимо использовать алгоритм 5-
точечного ДПФ. Элементы полученного массива следует переставить согласно
(1.36) для получения искомого массива:
X ((6?2+10/у (mod 15)) = Х (fci-5 + fcg), /^ = 0, 1, 2; ftg = 0,...,4.
Таким образом, Ni-точечное ДПФ требует ai операций сложения и tni
операций умножения, включая fti умножений на 117°; Л'2-точечное ДПФ
требует а2 операций сложения и т2 операций умножения, включая k2
умножений на Wc. Тогда число требуемых операций сложения А и умножения М
для Х-точечного ДПФ составит:
(1.76)
(1.77)
Пример 1.24. Пусть N=15; Ni=3; Л2=5. Согласно табл. 1.6 m,=3; fc|=l; 01 =
6; т2=6; a2=17. Пользуясь формулами (1.76) и (1.77), находим: М= 17;
Л=87.
Теперь пусть Nt=5; N2=3. Тогда число операций умножения не изменится, а
число операций сложения станет равным /4=81.
37
М = т1 т2-kx ft2 ; A - N-l аг-\-тг a1.
1.5.2. Алгоритм Винограда с использованием ТЧП
Теоретико-числовые преобразования (см. 1.4.7) могут быть использованы для
эффективного вычисления круговой свертки в алгоритме Винограда. В [1.14,
1.15] предлагается так называемый гибридный алгоритм с использованием ТЧП
Мерсенна (см. 1.4.6). В табл. 1.7 приведено число требуемых
