Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 27
Текст из файла (страница 27)
А85 Р-26, Хо. 6, ПесегпЪег 1978. (Кстати, на странице 505 этой статьи фраза «такой, что ЪЪг(Г) ) 0|| 1» означает, что функция ЪЪг(Г) никогда не бывает отрицательной. Символ Ъ| значит «для всех».) 6. О'Роппе!Ц. «1ооЬ(пб ТЬгоц8Ь сЬе К!8Ьс ЪЪ'1пдочч 1шргочез брессга! Апа1уяз,» ЕТ)1ч', ХочешЪег 1984.
7. Ка(зег, !. К «О!ясса! Р!!сегз,» ш 5узгет Апа1уяз бу 1)18(га1 Сотригег. Е|1. Ъу Г. К Кпо апд !. К Касзег, 1оЬп ЪЪ|11еу апд бонз, Хе|и 'г'огас, 1966, рр. 218-277. 8. КаЪ|пег, 1.. К., апд Оо!д, В. Т7|е Т7|еогуапг7Арр(ссагюпо/018(га(518па1Ртосея(п8. Ргепгссе-На!1, Еп81еч оод СИ(з, Хе|ч )егзеу, 1975, р. 88 (есть русский перевод: Рабинер Л., Голд Б. «Теория и применение цифровой обработки сигналов», Мс Мир, 1978, доступен по адресу Ьсср://йео81п.пагод.гц/агЬ(ч/дзр/дэрЗ.Ьсш.
Кстати на этом сайте по адресу Ьсср://бео8!п.пагод.гп/геада11.Ьсш есть неплохая подборка книг по ЦОС в электронном виде.). 9. ЗсЬоеп|ча!д,). «ТЬе бпг1асе Асоцэс1с ЪЪ|аче Е11сег: ЪЪгшдо|ч Еппссюпз», ЕРЕ|еяйп, МагсЬ 1986. 10. Нагйз, Г. «Оп сЬе 1)зе о1%'шдо|чз 1ог Наппошс Апа!уэсз |чссЬ сЬе 1)!эсгесе ЕопПег Тгапз(огш,» Ргосеейпбз о/йе 1ЕЕЕ, Ъ'о1.
66, Хо. 1, !аппагу 1978. 140 Глава4. Быст оеп еоб азованиеф ье 4.1. Связь БПФ с ДПФ Существует ряд различных алгоритмов БПФ. В этом разделе мы увидим, почему алгоритм БПФ по основанию 2 так популярен, и узнаем, как он связан с классическим ДПФ. Алгоритм БПФ по основанию 2 — это очень эффективный алгоритм вычисления ДПФ„когда длина ДПФ равна целой степени двух. (То есть количество точек преобразования равно У = 2, где в — некоторое положитеь льное число.) Посмотрим, почему практикующие специалисты по 1[ОС предпочитают БПФ по основанию 2. Вспомните пример 1 главы 3, в котором мы отметили некоторое количество избыточных операций при выполнении 8-точечного ДПФ.
(Например, мы вычисляли произведение 1.0607 0.707 четыре раза.) БПФ по основанию 2 устраняет эту избыточность и существенно снижает количество необходимых арифметических операций. Чтобы оценить эффективность БПФ, рассмотрим количество комплексных умножений, необходимых для выполнения давно знакомого нам Ж-точечного ДПФ и-! Х(т) ~) х(п)е впт/ (4-1) в-а В случае 8-точечного ДПФ из (4-1) следует, что нам необходимо выполнить А1~, или 64, комплексных умножений. (Потому что для каждого из восьми отсчетов Х(т) мы должны просуммировать восемь комплексных произведений при изменении п от 0 до 7.) Как мы убедимся в последних разделах этой главы, количество комплексных умножений для в1-точечного БПФ равно примерно (У/2) ° 1~8 з У.
(4-2) (Мы говорим «примерно», потому что некоторые умножения выполняготся на +1 или — 1 и сводятся к простой перемене знака.) Величина (М/2) !о8 з Х указывает на значительное снижение количества комплексных умножений по сравнению с А! операций, необходимых для реализации (4-1), особенно при больших Х. Насколько значительно это снижение, показывает рисунок 4.1, на котором сравнивается количество комплексных умножений, необходимых для реализации ДПФ и БПФ по основанию 2 при разных значениях Ф.
При М = 512, например, ДПФ требует в 200 раз больше комплексных умножений, чем БПФ. При Х = 8 192 ДПФ требует 1000 комплексных умножений на каждое комплексное умножение в алгоритме БПФ! А вот мой любимый пример эффективности БПФ по основанию 2. Если мы выполняем БПФ длиной в два миллиона точек (У = 2 097 152) на нашем персональном компьютере, оно занимает 10 секунд.
С другой стороны, вычисление ДПФ такой последовательности на настольном компьютере займет более трех недель! Публикация и распространение алгоритма БПФ по основанию 2 были, наверное, самым важным событием в цифровой обработке сигналов. Здесь уместно подчеркнуть, что БПФ не является аппроксимацией ДПФ. Это в точности ДПФ.
Более того, все характеристики ДПФ, описанные в предыдущей главе; симметрия, линейность, утечки, гребешковые искажения и прочие,— присущи также и БПФ. 141 4.2. Советы по п актическом использованию БПФ 10' 108 ю' 10' 10' 104 03 10' 101 10' 10ж 10 104 10' И Рис. 4.1. Количество комплексных умножений, как функция М, при реализации ДПФ и БПФ по основанию 2 4.2. Советы по практическому использованию БПФ Учитывая ценность БПФ для практики, мы приводим здесь ряд практических указаний по накоплению данных и использованию БПФ по основанию 2 для анализа сигналов реального мира. 4.2.1.
Дискретизируйте достаточно часто и достаточно ДОЛГО Как мы знаем из главы 2, при преобразовании непрерывных сигналов в цифровую форму с помощью АЦП частота дискретизации должна быть не менее чем в два раза больше ширины спектра непрерывного сигнала, чтобы предотвратить наложения в частотной области. На практике в зависимости от приложения используют частоту дискретизации, которая в два с половиной — четыре раза превышает ширину спектра сигнала.
Если мы знаем, что ширина спектра преобразуемого сигнала не очень велика по сравнению с максимальной частотой преобразования нашего АЦП, от наложений легко избавиться. Если мы не знаем, какова ширина спектра непрерывного сигнала, как нам определить, имеются ли наложения или нет? В этом случае нам следует с недоверием относиться к результатам БПФ, если имеются спектральные компоненты значительного уровня на частотах вблизи половины частоты дискретизации. В идеале нам хотелось бы работать с сигналами, спектр которых убывает с ростом частоты.
Будьте очень осторожны, когда в спектре обнаруживаются компоненты, частоты которых зависят от частоты дискретизации. Если у нас есть подозрение, что возникает наложение или что непрерывный сигнал содержит широкополосный шум, необходимо перед АЦП включить аналоговый ФНЧ. Частота среза ФНЧ должна быть несколько выше максимальной интересую1цей нас частоты и ниже половины частоты дискретизации. Глааа4. Быст оеп еоб азоааниеФ ье 142 Хотя мы знаем, что БПФ по основанию 2 требует Ж = 2 входных отсчетов, ь сколько же именно отсчетов должны мы накопить для анализа? Ответ состоит в том, что интервал времени, на котором выполняется накопление, должен соответствовать требуемой разрешающей способности БПФ при заданной частоте дискретизации /г Длительность интервала накопления данных является величиной, обратной требуемой разрешающей способности, и чем больше мы берем отсчетов с фиксированной частотой дискретизации /„тем выше разрешение по частоте; т.
е. общий интервал накопления равен ХД, секунд, а разрешающая способность У-точечного БПФ равна / /Ж Гц. Следовательно, если нам необходима разрешающая способность 5 Гц, то/,/Ж = 5 Гц и У =~, /(требуемое разрешение) =~,/5 = 0.2/,. (4-3) В этом случае, если /, равна, скажем, 10 кГц, то 1У должно быть нс меньше 2000, и нам придется взять 1У = 2048, потому что это ближайшее число, равное целой степени 2. 4.2.2. Предварительная обработка данных Если при использовании БПФ по основанию 2 мы не можем повлиять на количество получаемых отсчетов, и длина последовательности не равна целой степени двойки, можно применить один из двух подходов.
Мы можем отбросить часть отсчетов данных так, чтобы длина оставшейся последовательности была равна целой степени двойки. Использование этого варианта не рекомендуется, т. к. игнорирование части отсчетов данных приведет к ухудшению разрешения по частоте. (Чем больше )у, тем лучше разрешение, не правда ли?) Лучше дополнить последовательность нулями так, чтобы получить необходимое общее количество отсчетов. Например, если у нас есть 1000 отсчетов, которые необходимо преобразовать, вместо того, чтобы анализировать 512 из этих отсчетов, нам следует добавить в конец последовательности 24 нулевых отсчета и использовать 1024-точечное БПФ.
(Метод дополнения нулями более подробно обсуждается в разделе 3.11.) БПФ подвержено тем же эффектам утечки спектра, которые мы обсуждали в раздеде 3.8 для ДПФ. Для уменьшения утечки мы можем умножить исходную последовательность на окно. Будьте, однако, готовы к тому, что использование окон уменьшает разрешение по частоте. Кстати, при дополнении последовательности нулями мы должны умножать последовательность на окно до добавления нулей. Применение окна к дополненной нулями последовательности приведет к искажению окна и ухудшит утечку спектра. Хотя взвешивание окном и уменьшает утечку спектра, оно не устраняет проблему полностью.
Даже при использовании окна мощные спектральные составляющие могут замаскировать слабые компоненты спектра. Это особенно заметно, когда исходные данные содержат постоянную составляющую. При вычислении БПФ в этом случае постоянная составляющая высокого уровня на частоте 0 Гц закрывает соседние компоненты спектра. Мы можем устранить эту проблему, вычислив среднее значение исходных данных и вычтя его из исходной последовательности.
(Усреднение и вычитание должны выполняться до взвешивания окном.) Этот 4.2. Советы по и актическом использованию БПФ 143 подход позволяет сделать постоянную составляющую равной нулю и удаляет со- ставляющую с частотой О Гц из результата БГ1Ф. 4.2.3. Улучшение результатов БПФ Если мы используем БПФ для обнаружения энергии сигнала в присутствии шума, и у нас есть достаточно данных, мы можем улучшить чувствительность нашего обнаружителя, применяя усреднение результатов нескольких БПФ. Этот метод, рассматриваемый в разделе 11.3, может быть использован для обнаружения сигналов, мощность которых ниже среднего уровня шума. Другими словами, имея достаточно данных во временной области, мы можем обнаруживать компоненты сигнала при отрицательном отношении сигнал/шум.