Сергиенко А.Б. Цифровая обработка сигналов (2002) (1095939), страница 46
Текст из файла (страница 46)
Спектральный анализ Горизонтальные оси на спектральных графиках проградуированы в долях частоты дискретизации. Из рис. 5.1 видно, что после увеличения длины сигнала вдвое за счет добавления нулевых отсчетов результат ДПФ стал содержать вдвое больше значений, соответствующих в два раза чаще расположенным частотам. Таким образом, дополнение сигнала нулями позволяет повысить спектральное разрешение при вычислении ДПФ.
Алгоритм быстрого преобразования Фурье Для вычисления одного коэффициента ДПФ по формуле (5.3) необходимо выполнить Ж комплексных умножений и сложений. Таким образом, расчет всего ДПФ, содержащего гт' коэффициентов, потребует У' пар операций «умножение— сложение». Число операций возрастает пропорционально квадрату размерности ДПФ.
Однако, если гт' не является простым числом и может быть разложено на множители, процесс вычислений можно ускорить, разделив анализируемый набор отсчетов на части, вычислив их ДПФ и объединив результаты. Такие способы вычисления ДПФ называются бьнтрыл преобразованием Фурье (БПФ; английский термин — Разг Роиг(ег Тгапз(опп, РРТ) и повсеместно используются на практике. При реализации БПФ возможно несколько вариантов организации вычислений в зависимости от способа деления последовательности отсчетов на части (прореживапие по времени либо по частоте) и от того, на сколько фрагментов производится разбиение последовательности на каждом шаге (основание БПФ).
БПФ с прореживанием по времени Рассмотрим идею БПФ с прореживапиюн по времени (с1есппаг1оп !и шпе, 01Т) на примере деления набора отсчетов пополам. Итак, пусть М вЂ” четное число. Выделим в формуле (5.3) два слагаемых, соответствуюших элементам исходной последовательности с четными и нечетными номерами: Мг-! гю ° тг-2 2 (ге+О Х(п) = 2 х(2т)е и + 2' х(2т«1)е Введем обозначения у(т) - х(2т) и -(т) = х(2т+1), а также вынесем из второй суммы общий множитель е """г"', тг-г гкк ЛП г гктк Х(п) = ~ у(т)е кд +е '" ~ -(т)е (5.13) т О Две суммьг в (5.13) представляют собой ДПФ последовательностей (у(тл)) (отсчеты с четными номерами) и (а(т)) (отсчеты с нечетными номерами).
Каждое из этих ДПФ имеет размерность Лг/2. Таким образом, 2кл Х(п)=У(п)+е "' х(п), (5.14) 257 Алгоритм быстрого преобразования Фурье где У(п) и 4(п) — ДПФ соответственно последовательностей отсчетов с четными и нечетными номерами: М/2-! -/ У(п) = ч~, у(пт)е в 0 Н/2-1 4(п) = ~ -(/и) е н/2 . Так как ДПФ размерности /тг/2 дает лишь /ьг/2 спектральных коэффициентов, непосредственно использовать формулу (5.14) можно только при О < и < Х/2.
Для остальных л (12//2 < п < 2т/) следует воспользоваться периодичностью спектра дискретного сигнала (и, соответственно, периодичностью результатов ДПФ): У' пч -)=У(п), 2~я+-)=2(п). 2х~ (, 2/ С учетом этого при п е /тг/2 формула (5.14) представляется в виде .2 хи Х(п) = У п - — + е "' 2' п -— и =У п — — — е '4 п- —. (5.15) Процесс вычисления 8-точечного ДПФ путем разбиения его на два 4-точечных ДПФ иллюстрируется на рис. 5.2. х(о) л(1) 42) л(5) л(4) Х(5) 46) Х(7) Блоки, выполняюшие на рис. 5.2 объединение результатов двух ДПФ, требуют дополнительных комментариев.
Каждый такой блок имеет два входных и два выходных сигнала. Один из входных сигналов умножается на комплексную экспоненту ге, после чего суммируется со вторым входным сигналом и вычитается х(0) к(1) х(2) х(3) х(4) х(5) х(6) к(7) Рис. 8.2. Вычисление 8-точечного ДПФ с помощью двух 4-точечных ДПФ 258 Глава б. Спектральный анализ из него, формируя таким образом два выходных сигнала. Это соответствует реа- лизации формул (5.14) и (5.15). Данная операция получила название «бабочки» (Ьцггегйу).
Расшифровка ее структуры представлена на рис. 5.3, Х(к) р(к) у(ь) х(ь) й(ы ' х(в+ф) х(в+ф) -1 й(ь) нт рис. 5.3. условное обозначение бабочки» БПФ с прореживанием по времени (слева) и ее отруктурнал схема (справа) Оценим количество операций, необходимое для вычисления ДПФ указанным способам. Каждое из двух ДПФ половинной размерности требует Ж /4 операций.
2 Кроме того, при вычислении окончательных результатов каждый спектральный коэффициент х(п) умножается на экспоненциальный комплексный множитель. Это добавляет еше Ж/2 операций. Итого получается 2)у'з/4+ Ж/2 = )у()т)'+ 1)/2, что почти вдвое меньше, чем при вычислении ДПФ прямым способом.
Если )у/2 тоже является четным числом (то есть если Ж делится на 4), можно продолжить описанную процедуру, выразив результат через четыре ДПФ размерности Ж/4. Это позволяет еше больше сократить число требуемых вычислительных операций. ЗАМЕЧАНИЕ Делить исходную последовательность можно на любое количество частей. Таким образом, приведенный алгоритм позволяет уменьшить число операций в случае любого Ж не яв- ляющегося простым числом, Степень ускорения вычислений зависит от числа фрагментов последовательности и является максимальной при делении на лве части, как в рассмот- ренном примере. БПФ с прореживанием по частоте Формулы прямого и обратного ДПФ (5.3) и (5.4) отличаются только знаком в показателе экспоненты и множителем перед суммой.
Поэтому можно получить еше один вариант алгоритма БПФ, выполнив преобразования, показанные на схеме рис. 5.2, в обратном порядке. Этот способ вычислений называется проре- Наибольшая степень ускорения вычислений может быть достигнута прн М- 2, в этом случае деление последовательностей на две части можно продолжать до тех пор, пока не получатся двухэлементные последовательности, ДПФ которых рассчитывается вообще без использования операций умножения (достаточно вычислить сумму и разность двух отсчетов). Число требуемых при этом пар операций «умножение — сложение» можно оценить как )т( 1ойз(й)). Таким образом, вычислительные затраты по сравнению с непосредственным использованием формулы (5.3) уменьшаются в )()/)ойз()т() раз.
При больших А( это отношение становится весьма велико (например, 1024/1оят(1024) - 102,4, то есть прн )т) - 1024 достигается более чем 100-кратное ускорение). Алгоритм быстрого преобразования Фурье живанием по частоте (с)ес!шаг)оп!и 1гецпепсу, П! Е).
Покажем, как получить описание этого метода на основе формулы прямого ДПФ (5.3). Разделим исходную последовательность (х(гг)) на две следующие друг за другом половины (как и в предыдущем случае, г'г'должно быть четным числом): тг-~ 22~~пн тг 2иГв+нггги Х(п)= ~ х(т)е и + ~ х(т+ — )е ь О я О 2 Из второй суммы можно выделить множитель .2ММ2М е " =е гь" =(-1)".
Этот множитель равен 1 или -1 в зависимости от четности номера вычисляемого спектрального отсчета и, поэтому дальше рассматриваем четные и нечетные п по отдельности. После выделения множителя х1 комплексные экспоненты в обеих суммах становятся одинаковыми, поэтому выносим их за скобки, объединяя две суммы: М 2-1 т2 22ма Х(222) = $; (х(т)+х(т+ — )1е я 01 2 ! ггг-гг т2 Х(2е+1) = ~ ~ х(т)-х(т+ — )(е т' е ы О 2 г~ Фигурирующие здесь суммы представляют собой ДПФ суммы и разности половин исходной последовательности, при этом разность перед вычислением ДПФ умножается на комплексные экспоненты ехр(-) 2ят,/Ф). Каждое из двух используемых здесь ДПФ имеет размерность Уг2.
Итак, при прореживании по частоте вычисления организуются следующим образом: 1. Иэ исходной последовательности (х(я)) длиной Лг получаются две последовательности (у(т)) и (;(т)) длиной М/2 согласно следующим формулам: у(т) = х(т) + х т+ — ~, М~ 2! ;(т) = х(т)-х т+ — е 2. ДПФ последовательности (у(т)) дает спектральные отсчеты с четными номерами, ДПФ последовательности (2(т)) — с нечетными: л~г-~ Х(2я) =Г(гг) = ~ у(т)е т О тг-~ г ,г ь Х(2/г+1) = У(гг) = 2' -(т)е Все сказанное в предыдущем разделе о возможности деления последовательности на иное, отличное от двух, число частей и об уменьшении числа опера- гео Глава б. Спектральный анализ ций, требуемых для расчетов, относится и к алгоритму с прореживанием по час- тоте.
Процесс вычисления 8-точечного ДПФ путем разбиения его на два 4-точечных ДПФ с прореживанием по частоте показан на рис. 5.4. к(0) х(1) х(2) (з) (4) х(5) з(6) к(7) Поскольку комплексный экспоненциальный множитель в данном алгоритме при- меняется к результату вычитания двух сигналов, «бабочка» БПФ с прорежива- нием по частоте имеет несколько иную структурную схему (рис. 5.5), Рис. 6.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
