Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 28
Текст из файла (страница 28)
Если данные во временной области имеют действительные значения, мы можем воспользоваться преимуществами метода 2Ж-точечного действительного БПФ, описанного в разделе 13.5, для ускорения обработки; т. е. 2М-точечная действительная последовательность может быть преобразована с помощью одного М-точечного комплексного БПФ по основанию 2.
Таким образом, мы можем получить частотное разрешение 2Ж-точечного БПФ по цене стандартного А1-точечного БПФ. Другая возможность ускорения БПФ состоит в применении взвешивания окном в частотной области, описанного в разделе 13З. Если нам нужно БПФ невзвешенных данных и одновременно мы хотим иметь БПФ тех же данных, взвешенных окном, нам нет необходимости выполнять два разных БПФ.
Мы можем вычислить БПФ невзвешенных данных, а затем выполнить взвешивание в частотной области, чтобы уменьшить утечку на всех илн на некоторых бинах БПФ. 4.2.4. Интерпретация результатов БПФ Х(т) =Х а~(т) ч-1Х'таз(т) ' (4-4) А все модули отсчетов БПФ Первый шаг при интерпретации результатов БПФ состоит в вычислении абсолютных частот центров бинов. Как и в случае ДПФ, расстояние по частоте между бинами БПФ равно частоте дискретизации 1а, деленной на количество точек БПФ, или 1; /М Обозначим результат Б ПФ как Х(т), где т = О, 1, 2, 3, ..., А( — 1, при этом абсолютная частота центра и-го бина равна т1; /Х. Если отсчеты входной последовательности БПФ действительны, только отсчеты Х(т) с индексами от и = О до т = №2 независимы. Следовательно, в этом случае нам необходимо определить только частоты бинов для т в диапазоне О < и < М/2.
Если же входные отсчеты комплексные, все Ж отсчетов БПФ независимы, и нам потребуется вычислить частоты бинов для ш во всем диапазоне О < и < У вЂ” 1. Если необходимо, мы можем определить истинные амплитуды сигналов по их спектрам. Для этого мы должны помнить, что выходные отсчеты БПФ по основанию 2 — комплексные величины вида 144 Гпавал. Быст оеп еоб азоааниеф ье в результате преобразования, когда входные отсчеты действительны, оказываются умноженными на Ж/2, как сообщалось в разделе 3.4.
Если же входные отсчеты комплексные, масштабирующий коэффициент равен Н. Следовательно, чтобы определить правильные амплитуды синусоидальных составляющих, нам необходимо разделить модули отсчетов БПФ на соответствующий коэффициент: М/2 для действительных последовательностей и иодля комплексных последовательностей. Если исходные данные были взвешены окном, некоторые входные отсчеты оказываются ослабленными. Это уменьшает уровень выходных отсчетов БПФ. Чтобы вычислить правильные амплитуды синусоидальных составляющих в этом, случае, мы должны разделить модули отсчетов БПФ еще и на некоторый коэффициент потерь, соответствующий используемому окну. Коэффициенты потерь для наиболее популярных окон приведены в [3].
В случае, когда мы хотим определить спектр мощности Х,(т), нам необходимо вычислить квадрат модуля БПФ, используя соотношение Х,(т) = )Х(т) ) =Х„,ы(т) +Хьввх(т) . (4-6) Это позволит нам вычислить спектр мощности в логарифмическом масштабе Х,~(т) = 10 ° 1о81О( ~ Х(т) ) ) дБ (4-7) Нормированный спектр мощности в логарифмическом масштабе можно вычислить с помощью выражения НормированныйХ~в(т) = 10 ° 1о81в( ! Х(т) ! /( ~ Х(т) ~ ) ) или НормированныйХщ(т) =20 ' 1о81о( ~ Х(т) ~ /( ! Х(т) ~ )) (4 9) В (4-8) и (4-9) член 1Х(т)! представляет собой максимальный модуль отсчета. На практике график Хвв(т) очень информативен благодаря улучшенному разрешению составляющих низкого уровня при использовании логарифмического масштаба, как показано в приложении Е. Если используется (4-8) или (4-9), описанная выше компенсация масштаба БПФ и поте~ь, связанных с окном, не нужна.
Нормирование путем деления на (1Х(т)~ ) или 1Х(т)~ устраняет влияние всех масштабных коэффициентов. Зная, что фазы Х (т) отдельных отсчетов БПФ вычисляются по формуле Х~(т) = сап' '(Х;,„, (т)/Х„„~(т)), (4-10) мы должны особое внимание обратить на те отсчеты, для которых Х„„,(т) равны нулю. В этом случае вычисление фазы по (4-10) невозможно из-за деления на ноль. На практике необходимо, чтобы программа расчета обнаруживала отсчеты, длякоторыхХы ~т) =О,иустанавливалаХ (т) =90'еслиХ,, (т) >О,Х (т) = 0' если Х,„„(т) = О, и Х (т) = — 90' если 7(ы, (т) < О. Рассматривая фазовые углы отсчетов БПФ, имейте ввиду, что шумовйе компоненты высокого уровня могут вызвать значительные флуктуации вычисленных Х (т). Это значит, что отсчеты Х (т) имеют смысл только тогда, когда соответствующий ~Х(т) ) намного превьп~ает средний уровень шума. 145 4.3.
П ог аммыБПФ 4.3. Программы БПФ Для тех читателей, которые хотят получить программы БПФ без необходимости платить за дорогостоящие пакеты обработки сигналов, имеется ряд бесплатных программ, реализующих БПФ по основанию 2. В 14-7] приведен листинг программы на Фортране, реализующей стандартный алгоритм БПФ. В (8] представлена эффективная программа, написанная на Фортране, для действительных последовательностей. В 19] предлагается стандартная программа БПФ, написанная на НР ВА81С™, а в 110] представлена процедура БПФ, написанная на Арр!езо(( ВА81С™.
Читатели, интересующиеся языком А(]а, могут найти процедуры, связанные с БПФ, в работе [11]. 4.4. Разработка алгоритма БПФ по основанию 2 Этот н следующие разделы содержат подробное описание внутренних структур данных и операций БПФ по основанию 2 для тех читателей, которые интересуются разработкой программ БПФ или проектированием аппаратурных процессоров БПФ. Чтобы увидеть, как БПФ вырастает из ДПФ, напомним формулу Жточечного ДПФ: Ь»-1 Х(щ) = ~» х(п)е 2 (4-11) п-0 Простой и понятный способ получения алгоритма БПФ состоит в том, что исходная последовательность данных х(п) делится на две части. Выделив отсчеты х(п) с четными и нечетными индексами в две отдельные последовательности, мы можем разбить (4-11) на две части вида (Х/2) — 1 (У/2) — 1 Х(п)) = ~» х(2п)е — 12л(2п)т/)»( + ~> х(2п + 1)е — /2л(2п»1)т/У (4-12) л=о п=о Вынося за знак второй суммы экспоненту с постоянным показателем степени, получаем (1»»»'2) — 1 ())(,»2) - 1 Х(щ) '»» х(2п)е — Я2л(2п)т/М ( е'и лак» ~~~»~ х(2п» 1)е — 32л(2п)т/™ (,1 18) и=-О .=о Для упрощения этих длинных и сложных выражений мы используем стандартные обозначения.
Пусть И'~, = е '2' ~~обозначает комплексный поворачивающий множитель, который постоянен для заданного А». Тогда (4-13) приобретает вид (У,»2) — 1 (М/2) — 1 Х(щ) ~~~»~ х(2п)(И1 )2лт-» (Иг )т 'с~»~ х(2п -» 1)(Иг )2ит (4 14) =о л=о Поскольку (И' )2 = е 1»("» = е 1 "' ( У ) мы можем в формулу (4-14) подставить Иг,у2 вместо ( И'и) 146 Глава 4. Быст ое преоб азоаание Ф ье (й/2) — 1 ()л/2) -1 Х(т) - ~1~ х(2п)(И~/2)6™+ (%~) ~, х(2п + 1)(ИЛ„2)лт.
(4-15) л=О п=-О (У/2) — 1 Х(т+Ж/2) = ~ х(2п)(% /2)"( +'и~2)+ п-0 (т/2) -1 + (% )( + Ю Ух(2п+ 1)(И' )л( №3) =о (4-16) Кажется, мы усложнили нашу задачу? Ничего, потерпите немного. Мы можем упростить поворачивающие множители под знаками сумм, потому что )л(т+Х/2) (% )тл(% )п№2 (% )пт( твлп2№211) = (% /2)" (') =(%п/2)" (4-17) для любого целого и. Внимательно проанализировав поворачивающий множитель перед второй суммой в (4-16), мы можем упростить его как (И, )(т ~№2) (И, )т (% )У~'3 (И )т ( — 12и№2У) =(%ч) (-1) = -(%ч) (4-18) Далее, используя (4-17) и (4-18), мы представляем Х(тч-№2) из (4-16) как (М/2) — 1 (1л/2) - 1 Х(т+?ч/2) = ~~> х(2п)(%п/~)лт — (%п)~,Я х(2п + 1)(%п/2)"~.
(4-19) п=О п=0 Теперь повторим (4-15) и (4-19), чтобы увидеть, насколько они схожи: (№2)-1 (М/2) — 1 Х(т) = ~~> х(2п)(% 2)'™ + (И) ),Я х(2п + 1)(И' /~)пм, (4-20) и=О л=О (Ж/2) — 1 (М/2) — 1 Х(тччч/2) = ),х(2п)(%п/2))"' — (%ч) ~~,х(2п+ 1)(%п/л)" . (4-20') и=0 л=.0 Итак, мы имеем две суммы Ж/2 слагаемых, результаты которых можно объединить в Л(-точечное ДПФ. В (4-15) мы сократили количество операций над данными по сравнению с (4-11), потому что множители И' в обеих суммах уравнения (4-15) идентичны. Дополнительный выигрыш от разбиения Л(-точечного ДПФ на две части мы получаем благодаря тому, что вторая половина отсчетов ДПФ вычисляется очень просто.
Рассмотрим отсчет Х(т+У/2). Если мы подставим т->М/2 вместо т в (4-15), то 147 4.4. Раз аботка алго итма БПФпо основанию 2 Ну вот, мы и получили то, что хотели. Для вычисления Х(т+)у/2) нам не нужно выполнять никаких умножений на синусы и косинусы. Мы просто изменяем знак поворачивающего множителя (И'Ч) и используем две суммы, полученные для Х(т), для вычисления Х(т+Ж/2). Конечно, в (4-20) т принимает значения от 0 до (Х/2) — 7, а это значит, что для Ж-точечного ДПФ мы выполняем два )х/2-точечных ДПФ, получая первые М/2 отсчетов, а затем используем уже полученные результаты для вычисления последних М/2 отсчетов.