1097

Преобразование Фурье

Лекция

Математика и математический анализ

Аналоговое преобразование Фурье. Дискретное преобразование Фурье. Алгоритм быстрого преобразования Фурье с прореживанием по времени. Алгоритм быстрого преобразования Фурье с прореживанием по частоте. Метод двоичной инверсии.

Русский

2013-01-06

225 KB

179 чел.

лекция

Преобразование Фурье

Рассматриваются следующие вопросы:

- аналоговое преобразование Фурье

- дискретное преобразование Фурье

- алгоритм быстрого преобразования Фурье с прореживанием по времени

- алгоритм быстрого преобразования Фурье с прореживанием по частоте

- метод двоичной инверсии

3.1. Аналоговое преобразование Фурье

При обработке акустических сигналов важную роль играет анализ их частотно-амплитудного представления (спектра). Наиболее распространенным методом выделения спектра сигнала является преобразование Фурье [5,6].

Аналоговый сигнал  переводится в спектральное представление с помощью прямого аналогового преобразования Фурье в виде (3.1).

(3.1)

Обратное аналоговое преобразование Фурье осуществляется      согласно (3.2)

(3.2)

Спектр аналогового сигнала (3.3) представляет собой совокупность гармонических колебаний (гармоник), характеризующихся амплитудой , начальной фазой  и угловой частотой w.

(3.3)

Поскольку современные ЭВМ представляют собой цифровые устройства, то вместо аналогового преобразования используется дискретное.

3.2. Дискретное преобразование Фурье

Прямое ДПФ конечной последовательности  {x(n)}, , позволяет получить спектр в виде  

,     (3.4)

Аналогично аналоговому сигналу, спектр дискретного сигнала представляет собой совокупность гармонических колебаний (гармоник), характеризующихся амплитудой (3.5), начальной фазой (3.6) и угловой частотой (3.7).

,  (3.5)

, (3.6)

,   (3.7)

где ,  - коэффициенты ряда Фурье, .

Графическое представление, наглядно интерпретирующее коэффициенты ряда Фурье принято называть спектральной диаграммой периодического сигнала. Различают амплитудные и фазовые диаграммы дискретного сигнала (рис.3.1).

               а)                                                 б)

Рис. 3.1. Спектральные диаграммы сигнала x(n):

а) - амплитудная; б) - фазовая

Обратное ДПФ выглядит следующим образом

,  (3.8)

Прямое ДПФ можно представить в более удобной форме в виде

, , (3.9)

где . Легко показать, что  является периодической последовательностью с периодом N, т.е.

 

Обратное ДПФ выглядит следующим образом:

,  (3.10)

Ниже будет показано, что периодичность  является одним из ключевых моментов БПФ. Часто периодичность  подчеркивают тем, что  вместо   записывают .

При непосредственных вычислениях  заменяется на . Используя формулу (3.4), можно записать

 (3.11)

,

Из формулы (3.8) следует, что непосредственное вычисление дискретного преобразования Фурье последовательности  x(n) требует  умножений (или сложений) комплексных чисел.

Таким образом, для достаточно больших N  (порядка 1024) прямое вычисление ДПФ требует выполнения чрезмерного количества вычислительных операций.

Для более эффективного вычисления ДПФ используются алгоритмы быстрого преобразования Фурье. Эти алгоритмы сравнимы по эффективности и образуют следующие классы -  алгоритмы БПФ с прореживанием по времени и алгоритмы БПФ с прореживанием по частоте.

3.3. Алгоритм быстрого преобразования Фурье с прореживанием по времени

Основная идея БПФ с прореживанием по времени состоит в том, чтобы разбить исходную N-точечную последовательность x(n) на две более короткие последовательности, ДПФ которых могут быть скомбинированы таким образом, чтобы получилось ДПФ исходной N-точечной последовательности. Так, например, если N  четное, а исходная N-точечная последовательность разбита на две N/2-точечные последовательности, то для вычисления искомого N-точечного ДПФ потребуется порядка  2(N/2)2=N2/2  комплексных умножений, т.е. вдвое меньше по сравнению с прямым вычислением. Здесь множитель (N/2)2 дает число умножений, необходимое для прямого вычисления N/2-точечного ДПФ, а множитель 2 соответствует двум ДПФ, которые должны быть вычислены. Эту операцию можно повторить, вычисляя вместо N/2-точечного ДПФ два N/4-точечных ДПФ (предполагая, что N/2 четное) и сокращая тем самым объем вычислений еще в два раза.

Проиллюстрируем описанную методику для N-точечной последовательности {x(n)}, считая, что N равно степени 2. Введем две N/2-точечные последовательности  { x1(n) } и { x2(n) }  из четных и нечетных членов x(n) соответственно, т.е.

x1(n) = x(2n),      ,

x2(n) = x(2n+1),  .

N-точечное ДПФ последовательности  {x(n)}  можно записать как

(3.12)

             четные              нечетные

,    

С учетом того, что

(3.13)

перепишем выражение (3.12) в виде

(3.14)

,   ,  (3.15)

где X1(k) и X2(k) равны N/2-точечным ДПФ последовательностей  x1(n) и x2(n).

Из формулы (3.15) следует, что N-точечное ДПФ X(k) может быть разложено на два N/2-точечных ДПФ, результаты которых объединяются согласно (3.15). Таким образом, БПФ обеспечивает рекуррентное вычисление всех 2-точечных, затем 4-точечных, …, N-точечных ДПФ.

Общее число комплексных умножений и сложений равно , что значительно меньше  (количество комплексных умножений и сложений без использования БПФ).

3.4. Алгоритм быстрого преобразования Фурье с прореживанием по частоте

В данном алгоритме исходная последовательность {x(n)} также разбивается на две последовательности {x1(n)} и {x2(n)}, содержащие по N/2 отсчетов, но в данном случае в последовательность {x1(n)} записываются не четные отсчеты, а все отсчеты, расположенные в интервале , а в последовательность {x2(n)} – не нечетные отсчеты, а все отсчеты, расположенные в интервале , т.е.

,   ;

,   .

В этом случае ДПФ последовательности {x(n)}  можно записать в виде

(3.16)

             четные                    нечетные

,    

Учитывая, что , получим

 (3.17)

Запишем выражения отдельно для четных и нечетных частотных отсчетов

, (3.18)

, (3.19)

Общее число комплексных умножений и сложений равно , что значительно меньше  (количество комплексных умножений и сложений без использования БПФ).

3.5. Метод двоичной инверсии

Особенностью алгоритмов БПФ является перестановка элементов входной последовательности. Перед вычислением (3.15) или (3.18)-(3.19) используется двоично-инверсный метод (рис.3.2). Как видно из алгоритма, исходный номер k преобразуется в двоично-инверсный номер m. Четность проверяется отсутствием единицы в самом младшем разряде. Для ускорения работы алгоритма операции  2*m  и  [k/2] заменяются сдвигами на единицу влево или вправо соответственно.

Преобразование линейной последовательности в двоично-инверсную для 8 элементов представлено в табл.3.1.

Таблица 3.1

Пример метода двоичной инверсии

Индекс в линейной последовательности

Двоичное представление

Двоичная инверсия

Номер в двоично-инверсной последовательности

0

000

000

0

1

001

100

4

2

010

010

2

3

011

110

6

4

100

001

1

5

101

101

5

6

110

011

3

7

111

111

7

3.6 Численное исследование звуков речи и оборудования посредством преобразования Фурье

В работах [1, 38] было проведено численное исследование. На рис.3.3 представлен звук «а» в амплитудно-временном представлении, а на рис.3.4 – в амплитудно-частотном. На рис.3.5 представлен звук «ш» в амплитудно-временном представлении, а на рис.3.6 – в амплитудно-частотном. Как видно из рис.3.4 и 3.6, звук «а» наиболее ярко выделяется в частотном диапазоне до 2000 Гц, а звук «ш» - в частотном диапазоне свыше 2000 Гц.

Рис. 3.2. Двоично-ннверсный метод

Рис. 3.3. Звук «а» в амплитудно-временном представлении

Рис. 3.4. Звук «а» в амплитудно-частотном представлении

Рис. 3.5. Звук «ш» в амплитудно-временном представлении

Рис. 3.6. Звук «ш» в амплитудно-частотном представлении

Другой областью применения преобразования Фурье является исследование дефектов оборудования. На рис.3.7-3.8 приведены: временное представление акустического сигнала, полученного от подшипника турбовентилятора (рис.3.7); амплитуда спектра сигнала (рис.3.8); преобразованная амплитуда спектра сигнала (выделены частоты, связанные с возможными дефектами, характерными для этого класса подшипника) (рис.3.9).

Согласно рис.3.9, амплитуда частоты 38 Гц (первая гармоника частоты вращения ротора) превышает допустимый порог.

Рис. 3.7. Временное представление акустического сигнала

Рис. 3.8. Амплитуда спектра сигнала

Рис. 3.9. Преобразованная амплитуда спектра сигнала


 

А также другие работы, которые могут Вас заинтересовать

51318. Системы массового обслуживания 59 KB
  Задание: На вход n – канальной СМО с отказами поступает поток заявок с интенсивностью 6 заявок в час. Среднее время обслуживания одной заявки 0.8 часа. Каждая обслуженная заявка приносит доход 4у.е. Содержание одного канала обходится 2 у.е./час. Определить экономически целесообразное количество каналов.
51319. Разработка нового позиционирования марки супа быстрого приготовления “Быстросуп” компании «Europe Food GB» на фоне усиливающейся кросс-категориальной конкуренции 1.24 MB
  Отрасль потребительских товаров (Fast Moving Consumer Goods / FMCG) является одной из самых динамично развивающихся в современном бизнесе. И в России за последнее десятилетие производство товаров, без которых человек не может обходиться каждый день, совершило большой рывок: модернизируются привычные продукты
51323. ПРИГРАНИЧНАЯ ИНФРАСТРУКТУРА ЧИТИНСКОЙ ОБЛАСТИ И ПРОБЛЕМЫ ЕЁ СОВЕРШЕНСТВОВАНИЯ 95.5 KB
  В условиях постоянного и динамичного роста товарооборота между Российской Федерацией и Китайской Народной Республикой слабым звеном являются пункты пропуска. С каждым пунктом пропуска увязан целый комплекс проектов торговоэкономического сотрудничества от которых зависит дальнейшее развитие приграничных районов Читинской области. Проект строительства целлюлозного завода предусматривает строительство автомобильного моста через реку Амур в районе пункта пропуска Покровка Логухэ. В Читинской области на российскокитайском участке...