Сергиенко А.Б. Цифровая обработка сигналов (2002) (1095939), страница 47
Текст из файла (страница 47)
Условное обозначение .бабочки» БПФ с прореживаннем по частоте (слева) и ее структурная схема (справа] ЗАМЕЧАНИЕ Для получения алгоритма обратного БПФ достаточно поменять в приведенных формулах знак в показателях комплексных экспонент и добавить на выходе (или на входе) деление на два (в более общем случае — на используемый коэффициент прореживания). ЗАМЕЧАНИЕ Возможен также обобщенный подход к рассмотрению алгоритмов БПФ с прореживанием по времени и по частоте. Его описание можно найти в [7, 81 В названиях алгоритмов БПФ можно встретить слово «РкА()1Х» («основание»вЂ” в математическом смысле).
Следующее после него число обозначает число фраг- Рис. 6.4. Вычисление 6-точечного ДПф с помощью двух 4-точечных ДПф путем прорежиэания по частоте х(т) )(т) .(- т) Основание алгоритма БПФ Х(0) .Ц1) Х(2) х(з) 44) Х(5) 46) 217) 2В1 Алгоритм быстрого преобразования Фурье ментов, на которое разбивается сигнал на каждом этапе прореживания (а также минимальный размер «кусочков» входного вектора, который достигается в результате его последовательных разбиений).
В алгоритмах «ВА1)1Х-2» размер анализируемой последовательности должен быть равен степени двойки, а ее половинное деление производится вплоть до получения двухэлементных последовательностей. Вычисление их ДПФ не требует операций умножения — два спектральных отсчета представляют собой сумму и разность отсчетов временных: Х(0) = х(0) + х(1), Х(1) = х(0) — х(1). В алгоритмах «КАР1Х-4» количество отсчетов сигнала должно быть равно степени четверки, при каждом прореживании сигнал делится на четыре фрагмента, а последней стадией деления являются четырехзлементные последовательности.
При вычислении их ДПФ умножение производится только на 1у', а такое умножение сводится к взаимной перестановке вещественной и мнимой частей комплексного числа с изменением знака у одной из них: Х(0) = х(0)+ х(1)+ х(2)+ х(3), Х(1) = х(0) — у х(1) — х(2)+ 1'х(3), Х(г)= (0)- (1)+х(г)- (3), Х(З) =х(0)+ гх(1)-х(2)- тх(3). В 18] показано, что использование основания 4 позволяет ощутимо уменьшить число выполняемых умножений. в д Наибольшее ускорение вычислений благодаря алгоритму БПФ достигается при длине анализируемого вектора, равной степени двойки. При разложении длины вектора на иные множители ускорение также возможно, хотя и не столь значительное. Если длина вектора — простое число, вычисление спектра может быть выполнено только по прямой формуле ДПФ.
Пример, демонстрирующий зависимость числа вычислительных операций от размерности БПФ, будет приведен далее, при описании функции тгг в разделе «Функции спектрального анализа в МАТЮКАВ». Завершая краткое рассмотрение идеи БПФ, необходимо отметить следующее: З БПФ не является приближенным алгоритмом; при отсутствии вычислительных погрешностей он даст точно такой же результат, что и исходная формула ДПФ (5.3).
Ускорение достигается исключительно за счет оптимальной организации вычислений; (2 применение БПФ имеет смысл, если число элементов в анализируемой последовательности является степенью числа 2. Как уже отмечалось, некоторое ускорение вычислений возможно и при разложении Ж на другие множители, однако зто ускорение не столь велико, как при У- 2"; Глава 5. Спектральный анализ С1 алгоритм БПФ предназначен для одновременного расчета всех спектральных отсчетов Х(п). Если же необходимо получить эти отсчеты лишь для некоторых и, может оказаться предпочтительнее прямая формула ДПФ или рассматриваемый далее алгоритм Герцеля. Взаимосвязь ДПФ и фильтрации К данному моменту мы уже познакомились с понятиями дискретной фильтрации и дискретного преобразования Фурье, однако пока что эти понятия обсуждались по отдельности.
В данном разделе рассматривается, как они связаны друг с другом, причем связь эта оказывается двусторонней — ДПФ можно представить как обработку сигнала набором фильтров, а дискретную фильтрацию можно организовать с помощью ДПФ, что позволяет значительно уменьшить число вычислительных операций за счет использования алгоритмов БПФ. ДПФ как дискретная фильтрация Рассмотрев принципы дискретной фильтрации и познакомившись с дискретным преобразованием Фурье, можно заметить, что формулы, описывающие эти два процесса, весьма схожи — в обоих случаях онн представляют собой линейную комбинацию отсчетов входного сигнала.
Это говорит о том, что ДПФ можно трактовать как обработку сигнала фильтром с соответствующей импульсной характеристикой. Эту импульсную характеристику можно получить, если заметить, что ед'" - 1 при целочисленном л, и с учетом этого записать формулу прямого ДПФ (5.3) в виде л-~ хн~-~*р~ р и — ~к-а). в-а йГ л ()т) = ехр() 2к — lг ~, lг - О, 1, ..., Ж вЂ” 1. л Разумеется, импульсная характеристика для каждого частотного отсчета ДПФ своя; чтобы подчеркнуть это, в ее обозначении использован индекс и. Определим частотную характеристику такого фильтра.
Для этого, как было по- казано в разделе «Способы описания дискретных систем» главы 4, сначала необ- ходимо получить функцию передачи: Н„(-) = 1+ ехр )2к — р + ехрр2к — р +...+ ехрр2к и'), Г, 2п'1 з (. (Х-1)л'~ -лн йтп'1 -и ехр 12к — ~в — 1 м) 1-з п1 (, П "1 ехр т'2к — ~з — 1 1 — ехрр2к — ~ й/ ж,) (5.16) Преобразованная таким способом формула ДПФ представляет собой дискрет- ную свертку (4.3), то есть У-й отсчет результата обработки входного сигнала х(1т) фильтром, импульсная характеристика которого равна 263 Взаимосвязь ДПФ и фильтрации ЗАМЕЧАНИЕ Для расчета функции передачи использована формула суммы конечной геометрической прогрессии: к,7к+1 ч~"„6,0' = Ь, ь-о т) — 1 Для расчета частотной характеристики используем подстановку; " е'"т 1-е ть'~ К„(а) = Н„(ест ) = )з' т л 1-е ье '"т АЧХ такого фильтра после несложных тригонометрических преобразований мож- но записать следующим образом: а)тТ з(ив з(п кХ вЂ”" (5.17) 51П Л— и где а = — а .
л тт л' Результат показывает, что АЧХ фильтра описывается рассмотренной в разделе «Функции генерации периодических сигналов» главы 3 функцией Дирихле; К(а) - Йг(сн (а — а„). На рис. 5.6 показан график АЧХ одного из каналов ДПФ при У- 8 (градуировка частотной оси выполнена в номерах каналов). Пунктирной линией на этом рисунке изображена АЧХ соседнего частотного канала: »М 8: » н - 0:0.1;М: » р1о1(и, аЬз(Ь)г1с((ь-3)/М*2*р). М))) » Ьо1Ь ап » р1о1(и.
аоз(о1г)с((и-4)т'М*2*р1. М)), '--') » Ьо10 отт Как видно из графиков, АЧХ фильтра, реализуемого при вычислении ДПФ, имеет большой уровень боковых лепестков — примерно 1/(А(з(п(Зл/(2Ат))). При Ы» 1 это выражение стремится к 2/(Зн) = 0,2 и -13,5 дБ. Для уменьшения уровня боковых лепестков используют весовые функции, или окна (см. в этой главе далее).
264 Глава б. Спектральный анализ 0.9 0.6 ОД 0.6 О.б 0.4 О.З 0.2 ОЛ 0 1 2 3 4 б 6 7 6 Рис. 6.6. АЧХ частотных каналов ДПФ Алгоритм Герцеля Функция передачи отдельного канала ДПФ, записанная в форме (5.16), соответствует рекурсивному фильтру Ю-го порядка. Поэтому вычисление отдельного спектрального отсчета можно реализовать с помощью такого фильтра. Если необходимо вычислить лишь некоторые отсчеты ДПФ, данный алгоритм может оказаться предпочтительнее, чем использование БПФ, принципиально ориентированного на получение всех спектральных отсчетов. Однако для удобства практического использования формулу (5.16) можно модифицировать. Прежде всего заметим, что слагаемое -- в числителе выполняет -М лишь роль «ограничителя», заставляя импульсную характеристику закончиться, достигнув длины Н отсчетов.
Такой фильтр вычисляет отсчет мгновенного спектра сигнала, все время используя последние У отсчетов входного сигнала. Если же мы будем обрабатывать сигнал порциями по М отсчетов, перед каждой порцией обнуляя состояние фильтра, то конечность длины импульсной характеристики не будет иметь значения. В этом случае можно удалить слагаемое -- из числителя -н функции передачи, получив таким образом рекурсивный фильтр первого порядка; 1 Н„(-) = 1 — ехр(/2х л//т') с ' Следующее изменение связано с тем, что коэффициент обратной связи в единственной рекурсивной ветви данного фильтра является комплексным. Поэтому при обработке каждого входного отсчета необходимо выполнить четыре вещественных умножения и столько же вещественных сложений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
