Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 104
Текст из файла (страница 104)
В этом случае вместо выполнения полного БПФ мы можем выполнить только вычисления, показанные на графе жирными линиями. БПФ с уменьшенным объемом вычислений часто называют обрезанным БПФ [39 - 421 (Как и в главе 4, для простоты в бабочках на рисунке 13.39 показаны только множители аргументов поворачивающих множителей, а не полные аргументы.) Для реализации обрезанных БПФ мы должны знать аргументы поворачивающих множителей, связанных с вычислением всех необходимых бабочек, форма которых приведена на рисунке 13.40 (а). Здесь мы предлагаем вашему вниманию интересный алгоритм вычисления аргументов поворачивающих множителей 2лА 1/Л( и 2лА2/%для БПФ произвольного размера [43].
каскад 1 каскад 2 каскад 3 каскад 4 «(о) х(о) «(1) х(в) х(2) Х(4) х(з) Х(12) х(4) х(г) х(в) х((о) «(в) х(в) х(7) х(ы) «(в) х(О «(9) х(9) х(10) х(в) х(11) х((з) х(12) х(з) х(13) х(тй х(14) Х(7) «(15) Х(10) Рис. 13.39. Сигнальный граф 16-точечного БПФ по основанию 2 13. 16. Вычисление пово ачивающи«множителей БПФ Алгоритм основан на следующих особенностях БПФ с прореживанием по времени по основанию 2: а бабочка имеет вид, показанный на рисунке 13.40 (а); а множители аргумента А~ и А2 являются целыми числами, показанны- ми на рисунке 13.39; а М-точечное БПФ по основанию 2 имеет М каскадов (обозначенных в верхней части рисунка 13.39), причем М = 1ояз(А1); каждый каскад содержит Ж/2 бабочек.
Множитель аргумента произвольной бабочки вычисляется как (13-76) где 5 — индекс каскада преобразования, принимающий значения в диапазоне 1 < Я < М. Значение В представляет собой индекс одной из А1/2 бабочек в каждом каскаде, при этом 1 < В < Ж/2. Величина В - 1 соответствует верхней бабочке в каскаде. Операция ~д~ возвращает наибольшее целое, которое не превосходит гу. Выражение Вт„[г) представляет собой трехступенчатую операцию: преобразование десятичного целого г в двоичное число длиной М-1 бит, выполнение реверса битов двоичного представления числа (см.
раздел 4.5), и преобразование реверсированного двоичного числа обратно в десятичное целое, в результате которой получается коэффициент А е Множитель аргумента А2 на рисунке 13 40 (а) вычисляется затем как (13-76') Аз = А г + М/2 . «тн, « "«-1+7 т«<.1 У«-« 1ь> Рис. 13.40.
Две формы бабочек БПФ по основанию 2 Этот алгоритм можно также использовать для вычисления единственного поворачивающего множителя оптимизированной бабочки, показанной на рисунке 13.40 (Ь). Ниже приведен исходный текст программы для МАТЮКАВ, реализующей описанный алгоритм вычисления множителей аргумента поворачивающих множителей. с1еах И * 16; $равмер ВПЕ И = 1ос2(В); $Еоличество каскадов Яе$ах$ = 1; $Первый обрабатываемый каскад Вавор И; $Последлий обрабатываемый каскад Ве$ак$ = 1р $Первая вычисляемая бабочка Вектор В/2; $Последияя вычисляемая бабочка ройисет = 0; $ивициалиаация указателя результатов 62О Глава 13. Маленькие кит ости ци овей об аботки сигналов Ест 3 = Зетатс:Затор Ест В = Ветатт:Затор Е = 61оот((2"3*(3-1)) /М); %Вычислить целое т % Вычислить бит-реверсивное представление Е Еьт = О; Ест 1 ~ М-2:-1гО Ы Е>=2"1 ЕЬт = ЕЬт + 2" (М-1-2); Е в Е -2л1.
епс1 епб Вдовец вычислении бит-реверс. представлении А1 = ЕЬт; %Множитель архумента А1 А2 = ЕЬт + М/2р $ Множитель аргумента А2 Ро1птет = Ро1псет +1; Вееи1те(Ро1птет,:) = (З,В,А1,А2); епс1 епс1 Вееи1те, с11ер ( ' Зтаде В-Й1у, А1, А2 ' ), ЖеР ( ' ' ) Переменные в тексте программы, в имени которых содержатся строки в ватт и есор, позволяют вычислять подмножество поворачивающих множителей М-точечного БПФ. Например, для вычисления множителей аргумента пятой и шестой бабочки третьего каскада 32-точечного БПФ мы можем задать Ж = 32, 8е тахт 3, Затор = З,Ветатт ~ 5 и Вечор = 6 и выполнить эту программу.
1 3.17. Обнаружение отдельного тона В этом разделе мы рассмотрим структуру БИХ-фильтра, используемого для выполнения спектрального анализа при обнаружении и измерении параметров отдельных синусоидальных тонов. Стандартным методом вычисления спектра сигнала является дискретное преобразование Фурье (ДПФ), обычно реализуемое в форме быстрого преобразования Фурье (БПФ). Однако имеются приложения, в которых необходимо вычислять спектр на подмножестве Ж центральных частот бинов Ж-точечного.ДПФ. Популярным и эффективным методом вычисления прореженных отсчетов БПФ является алгоритм Герцеля, использующий некоторую реализацию БИХ-фильтра для вычисления одного отсчета ДПФ по М входным отсчетам сигнала. Самым распространенным применением этого алгоритмы является обнаружение присутствия отдельного непрерывного синусоидального тона.
Учитывая зто, давайте коротко рассмотрим задачу обнаружения тона. Конечно, для обнаружения присутствия отдельного синусоидального тона в последовательности х(п) можно использовать БПФ. Например, если бы мы хотели обнаружить тон частотой 30 кГц при частоте дискретизации ~, = 128 кГц, мы могли бы начать с выполнения 64-точечного БПФ, как показано на рисунке 13А1. Затем мы проанализировали бы модуль компле)ссного отсчета Х(15) и проверили бы, превышает ли он некоторый заданный пордг. Такое использование БПФ крайне неэффективно. В нашем примере нам пришлось бы выполнить 192, (64/2)()о6264), комплексных умножения для вычисления 64-х комплексных отсчетов Х(т), чтобы получить единственный интересующий 13. 17.
Обна ение отдельного тона 521 нас отсчет Х(15). Мы отбросили бы 98 % полученных результатов! Мы могли бы повысить эффективность нашего алгоритма, вычислив требуемый отсчет Х( 15) с помощью одноточечного ДПФ, что потребовало бы Н = 64 комплексных умноже- ния при реализации формулы 63 Х(т) = ~~> «(И)Š— 12ллтз/64 (13-77) л-0 Это, конечно, уже лучше, но существует более эффективный способ. Он называется алгоритмом Герцеля.
(26 КГц х(!) (6 ЗО КГц Х(2) 'Это единственный результат БПФ, Х(за) и — который нем нужен (гл = 16) х(л) х(63) Рис. 13.41. Обнаружение тона частотой 30 КГц с помощью ДПФ в виде БПФ 13.17.1. Алгоритм Герцеля Алгоритм Герцеля реализуется в форме БИХ-фильтра второго порядка с двумя действительными коэффициентами обратной связи и одним комплексным коэффициентом в цепи прямой связи, как показано на рисунке 13.42.
(Хотя мы не используем эту структуру как традиционный фильтр, принято называть ее фильтром.) Этот фильтр вычисляет значение единственного бина ДПФ (т-й бин )т(-точечного ДПФ), который определяется как и — т Х(т) = ~ х(п)е 12"лкл/)У. л 0 (13-78) Нс(г) = У(г)/Х(г) = (1 — е 12пт/и г ~)/11 — 2соз(2пт//Х)~ т + г-2) (13-79) Ее единственный ноль расположен в точке г = е 12"оз/)у на г-плоскости, а комплексно-сопряженные полюсы — в точках г = е+-12лез/~', как показано на рисунке 1ЗАЗ (а).
Ноль и полюс в точке г = е 12лоз/и взаимно уничтожаются. Вообще расположение полюса фильтра на единичной окружности рискованно с точки зрения Выходной сигнал фильтра у(п) равен отсчету ДПФ Х(т) в момент времени и = Н, если индекс первого отсчета сигнала и = О.
Мы подчеркиваем, что выходной сигнал фильтра у(п) не равен Х(т) в любой момент времени и и Ж. Чтобы результат был эквивалентен ДПФ, индекс в частотной области ш должен быть целым числом в диапазоне О < т < У вЂ” 1. Вы вполне можете рассматривать алгоритм Герцеля как однобиноеое ДНФ. Построение структуры этого фильтра (алгоритма) описывается в литературе [44 - 46]. Передаточная функция фильтра Герцеля имеет вид 522 Глава 13. Маленькие хит ости ци овей об ботки сигналов и) ачание т определяет резонансную частоту фильтра Рис. 13.42. Реализация БИХ-фильтра алгоритма Герцеля Алгоритм Герцеля реализуется с помощью комплексного резонатора, имеющего импульсную характеристику бесконечной длительности )т(л) = е12лптl)У, и этим объясняется такая малая ширина его АЧХ. Разностные уравнения фильтра Герцеля во временной области выглядят следующим образом ю(л) = 2соз(2лтл/А))ш(л — 1) — ш(л — 2) + х(л), у(л) = тл(л) — е РлтРет(л — 1).
(13-80) (13-81) Преимущество фильтра Герцеля при вычислении значения отсчета Ж-точечного ДПФ Х(т) состоит в том, что вычисление выражения (13-80) выполняется Фраз, в то время как выражение (13-81) — цепь прямой связи на рисунке 13А2— вычисляется только один раз при подаче на вход Ж-го входного отсчета. Таким образом, для действительной входной последовательности х(п) фильтр выполняет с целью вычисления Х(т) А1+2 действительных умножений и 2АГь1 действительных сложений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
