Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095938), страница 29
Текст из файла (страница 29)
(Метод дополнения нулями более подробно обсуждается в разделе 3.11.) БПФ подвержено тем же эффектам утечки спектра, которые мы обсуждали в раздеде 3.8 для ДПФ. Для уменьшения утечки мы можем умножить исходную последовательность на окно. Будьте, однако, готовы к тому, что использование окон уменьшает разрешение по частоте. Кстати, при дополнении последовательности нулями мы должны умножать последовательность на окно до добавления нулей. Применение окна к дополненной нулями последовательности приведет к искажению окна и ухудшит утечку спектра. Хотя взвешивание окном и уменьшает утечку спектра, оно не устраняет проблему полностью. Даже при использовании окна мощные спектральные составляющие могут замаскировать слабые компоненты спектра.
Это особенно заметно, когда исходные данные содержат постоянную составляющую. При вычислении БПФ в этом случае постоянная составляющая высокого уровня на частоте 0 Гц закрывает соседние компоненты спектра. Мы можем устранить эту проблему, вычислив среднее значение исходных данных и вычтя его из исходной последовательности. (Усреднение и вычитание должны выполняться до взвешивания окном.) Этот 4.2. Советы по и актическом использованию БПФ 143 подход позволяет сделать постоянную составляющую равной нулю и удаляет со- ставляющую с частотой О Гц из результата БГ1Ф. 4.2.3.
Улучшение результатов БПФ Если мы используем БПФ для обнаружения энергии сигнала в присутствии шума, и у нас есть достаточно данных, мы можем улучшить чувствительность нашего обнаружителя, применяя усреднение результатов нескольких БПФ. Этот метод, рассматриваемый в разделе 11.3, может быть использован для обнаружения сигналов, мощность которых ниже среднего уровня шума. Другими словами, имея достаточно данных во временной области, мы можем обнаруживать компоненты сигнала при отрицательном отношении сигнал/шум.
Если данные во временной области имеют действительные значения, мы можем воспользоваться преимуществами метода 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 — комплексные величины вида Глава4. Быст оео воб азованиеФ ьв в результате преобразования, когда входные отсчеты действительны, оказываются хмноженными на ЛУ2.
клк гооб1нл лось н олзлеле 3 4 Если же нхолнме отсчеты ком- 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 отсчетов.
При М = 8 (4-20) и (4-20') реализуются так, как показано на рисунке 4.2. Х(0) х(0) Х(1) х(2) Х(2) х(4) Х(3) х(6) Х(4) х(1) Х(5) х(3) Х(6) х(5) Х(7) х(7) Рис. 4.2. Реализация БПФ для 8-точечного ДПФ с использованием двух 4-точеч- ных ДПФ Если мы запишем (4-20) н (4-20') в более простой форме (4-21) Х(т) =А(т) ч-(йт~)"В(т), Глава4.
Быст оеп еоб азоааниеф ье 148 Х(т+й»/2) = А(т) — (И"м) В(т), (4-21') мы можем пойти дальше и разбить два 4-точечных ДПФ на четыре 2-точечных ДПФ. Посмотрим, как можно разделить верхнее 4-точечное ДПФ на рисунке 4.2, четыре выхода которого равны А(т) в (4-21) и (4-21'). Мы можем разделить четные и нечетные входные отсчеты верхнего 4-точечного ДПФ: (М,'2) — 1 )и»и и=О (М,'4) — 1 (М/4)-1 =,» х(4п)(Иьу2) " +~, х(4п+ 2)(И)»у2)( " ) . (4-22) и-0 и-0 Поскольку (И~,О,2) " = (И',,~4)", мы можем выразить А(т) через два Л»/4-точечных ДПФ как (У/4)-1 (М/4)- 1 А(т) = Я х(4п)(И'~4)"~+(И~12)~,Я х(4п+2)(%~~4)'~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
