Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095938), страница 28
Текст из файла (страница 28)
Кстати на этом сайте по адресу Ьсср://бео8!п.пагод.гп/геада11.Ьсш есть неплохая подборка книг по ЦОС в электронном виде.). 9. ЗсЬоеп|ча!д,). «ТЬе бпг1асе Асоцэс1с ЪЪ|аче Е11сег: ЪЪгшдо|ч Еппсс(опз», ЕРЕ|еяйп, МагсЬ 1986. 10. Нагйз, Г.
«Оп сЬе 1)зе о1%'шдо|чз 1ог Наппошс Апа!уэсз |чссЬ сЬе 1)!эсгесе ЕопПег Тгапз(огш,» Ргосеейпбз о/йе 1ЕЕЕ, Ъ'о1. 66, Хо. 1, !аппагу 1978. Глава 4 Быстрое преобразование Фурье Хотя ДПФ представляет собой наиболее простую математическую процедуру определения частотного состава временных последовательн<ютей, оно ужасно неэффективно. При увеличении количества точек ДПФ до сотен и тысяч количество выполняемых операций превышает все разумные пределы. В 1965 году бьша опубликована статья Кули и Тычки, описывающая очень эффективный алгоритм реализации ДПФ [11.
Этот алгоритм сегодня известен как быстрое преобразование Фурье (БПФ) '. До появления БПФ ДПФ длиной в несколько тысяч точек требовало так много времени, что его применение ограничивалось крупными исследовательскими и университетскими вычислительными центрами. Благодаря Кули и Тычки, а также полупроводниковой промьгпьленности сегодня 1024-точечное ДПФ может быть вычислено за несколько секунд на домашнем компьютере.
О БПФ написаны тома, и, как никакое другое изобретение, разработка этого алгоритма изменила цифровую обработку сигналов, сделав доступной всю мощь анализа Фурье. В этой главе мы покажем, почему наиболее популярные алгоритмы БПФ (которые называют БПФ по основанию 2) имеют преимущества над классическим алгоритмом ДПФ, дадим ряд рекомендаций, позволяющих получить больше практической пользы от БПФ, и приведем ссылки на листинги исходных текстов программ на разных языках программирования. Для читателей, желающих узнать некоторые детали, мы завершаем эту главу выводом алгоритма БПФ по основанию 2 и демонстрацией нескольких способов реализации БПФ.
В действительности БПФ имеет интересную историю. Исследуя рассеяние рентгеновских лучей, два физика в 1940-х годах воспользовались преимушествами симметрии синусов и косинусов, применив математический метод, основанный на опубликованном в начале 1900-х приеме. Прошло более 20 лет, прежде чем алгоритм БПФ был открыт заново Полную историю вы найдете в [2[ 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-точечное БПФ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
