Цифровая обработка сигналов: Справочник - Гольденберг Л.М.
Скачать (прямая ссылка):
. N-1
l/(ft) = - 2 X(l)Y(k - I), ft = 0,..., N-I.
1=0
Сопряженная формула обращения. Обратное ДПФ (1.20) можно вычислять с
помощью формулы для прямого ДПФ (
1
N-1
х (пТ)-Р (пТ), где = я = 0,..., N-1
(черта сверху означает комплексное сопряжение).
1.3.3. Многомерное дискретное преобразование Фурье
Многомерным (/-мерным) ДПФ /-мерных последовательностей называется пара
еледующих преобразований:
к (klt k2 ki) = § У ... 2 X (я. Г, я2 Т Г) • • .vC'
п,=0 пг-0 О
fti = 0,..., A/j.- 1, • ¦., ki = 0,..., Ni- 1; (1.22)
1 A/,-1 Л',-1 "i-1
*("i7\ n2T, , niT)==-- - V у ... у .Xfa, &2,..., &/)Х
NiN2...Ni fa# ?L0 ^
"1 = 0,..., А^-1,..., Я1 =0 М/ - 1. (1.23)
Преобразование (1.22) называется прямым, а преобразование (1.23)-
обрат-
ным многомерным ДПФ.
1.3.4. Алгоритмы БПФ с основанием 2
Вычисление ДПФ непосредственно по формуле (1.19) требует весьма большого
числа операций: примерно N2 операций умножения и А/* операций сложения
комплексных чисел. Быстрым преобразованием Фурье (БПФ) называют набор
алгоритмов, позволяющих резко уменьшить число операций, необходимое для
вычисления ДПФ.
Алгоритмы с основанием 2 используются при N=2v, v>0, v - целое. Основная
идея, лежащая в их основе, заключается в сведении вычисления исходного N-
точечного ДПФ к вычислению нескольких /V,-точечных ДПФ, причем Ni=2vi и
A/jC/V. Алгоритмы, при реализации которых требуется перестановка отсчетов
х(пТ) входной последовательности (см. пример 1.6), называются алгоритмами
с прореживанием по времени. Алгоритмы, при реализации которых требуется
перестановка отсчетов X(k) выходной последовательности ( см. пример 1.7),
называются алгоритмами с прореживанием по частоте. По эффективности эти
две разновидности алгоритмов эквивалентны и позволяют уменьшить число
требуемых арифметических операций примерно в A//v раз по сравнению с
прямым методом вычисления ДПФ.
Алгоритм с прореживанием по времени. Если последовательности х(пТ) длиной
N=2v разделить на две А//2-точечные последовательности, состоящие из
х(пТ) с четными и нечетными номерами соответственно, то выражение для ДПФ
(1.19) можно записать в виде
IV/2-1 А//2-1
X(k)= 2 X(2nT)Wn*/2+WkN 2 x((2n+\)T)Wfl2, fe = 0,..., N-1.
п=0 л=0
(1-24)
14
\ (1-25)
Какдая из сумм в (1.24) является JV/2-точечным ДПФ, которое аналогичным
образом можно представить через X/4-точечные, а Лг/4-точечные через Х/8-
точбчиые и т. д., пока не останутся только 2-точечные. Таких ступеней
пре-образования всего v=log2X. На m-ступени (от=0,..., v-1) производится
пре* образование множества N комплексных чисел Хт(п) в множество N
комплекс" ных чисел Хто-и(я) в соответствии с базовой операцией
"бабочка", описываемой выражениями: - -
т+1>) = (^) "4" WN (?)•
v Хт+1 (q)=Xm(p)-WNXmi(q),
где р, q и г зависят от номера ступени от и могут быть определены из
выра* жений, аналогичных (1.24).
Входная последовательность нулевой ступени Х0(п) получается перестановкой
последовательности х(пТ) в соответствии с двоичной инверсией номеров, т.
е. число х(пТ) с номером (nv_j ..., п0) в двоичном представлении
запоминается на месте Хо ("о,... > nv~i) ¦
Направленный граф, реализующий "бабочку", изображен на рис. 1.5. Здесь
сигналы ветвей, входящих в узел, суммируются; сигнал ветви умножается на
Хт(р) о ^ ^тн (Р)
X w°----------
WN ~Г
Рис. 1.5
коэффициент, записанный рядом с ветвью. Если коэффициент не указан, то он
полагается равным 1.
Пример 1.6. Рассмотрим случай N-8=2S. Так как v=3, то от=0, 1, 2. Для
получения входного массива Хо(п) произведем двоично-инверсную
перестановку элементов последовательности х(пТ)=х(п), л=0, ..., 7:
X0 (0) = Х0 (ООО) = х (ООО) =х (0); Х0 (4) = Х0 (100) = х (001)
= х (1);
*о (1) = Х0 (001) = х (100) = х (4); Х0 (5) = Х0 (101) = х (101)
= * (5);
Х0 (2) == Хо (010) = х (010) = х (2); Х0 (6) = Х0 (110) = х (011)
= х (3);
Х0(3) = Х0 (011) = х (110)= х (6); Х0 (7) = Х0 (111) - х (111) = х
(7).
Направленный граф с использованием "бабочки" и выражения (1.24) изображен
на рис. 1.6.
Алгоритм с прореживанием по частоте. Исходная последовательность х(лГ)
разбивается на две подпоследовательности Xi(nT) =х(пТ) и х2(пТ) =х(("-{-•
-\-N/2)T), где и=0,..., N/2-1, и отдельно вычисляются четные и нечетные
отсчеты ДПФ: j
N/2-1
X (2k) - у (X, (п 7-) + х2 (пТ))
n-Q
NJ2-1
X(2A+l)= у (x,(nT)-x2(nT))WnNWnNk/2 n=0
15
(126)
Полученные Х/2-точечные ДПФ аналогичным образом можно представить/через
N/4-точечные и т. д., пока не останутся только двухточечные (цсего
v=logsX ступеней преобразования). На /л-й ступени (/л=0,..., v-1)
производится преобразование множества N комплексных чисел Хт(п) в
множество
Рис. 1.6
комплексных чисел Xm+t(n) в соответствии с базовой операцией "бабочка",
описываемой выражениями:
Xm+, (р) = Хт (р) -f- Хт (q)',
*т+1 (<?) ^ (Хт (Р) - Хт (<?))
Х^.(Р) где л q и г ДЛЯ каждой СТупени оп-
> т ' ределяются из выражений, аналогичных
Хт(Ц)о^-- (1.26). Направленный граф операции
"бабочка" изображен иа рис. 1.7. и В рассматриваемом алгоритме, в
