Быстрое преобразование Фурье и его применение

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ ГАГАРИНА Ю.А.»

Контрольная работа

по дисциплине «Вероятностные методы анализа систем»

на тему

«Быстрое преобразование Фурье и его применение»

Работу выполнил студент

ИнЭТМ, б2-ИВЧТипу21,заочно сокращенная форма обучения

Катков Дмитрий Евгеньевич

Руководитель работы

доцент каф. СТ Бокова Лариса Геннадьевна

Саратов - 2019



Введение

Фурье анализ на сегодняшний день, без сомнения самый распространенный инструмент анализа, который применяется во всех отраслях науки и техники. Однако до появления компьютеров дискретное преобразование Фурье (ДПФ) использовалось редко, поскольку вычисление ДПФ 32 отсчетов требует 1024 операции комплексного умножения и сложения, что в ручную считать довольно долго. Однако первое упоминание об алгоритме быстрого преобразования Фурье относится к работе Гаусса, в которой он использовал свойства периодичности тригонометрических функций для расчета ДПФ. Однако на эту работу долгое время никто не обращал внимания, до тех пор пока персональные компьютеры не получили широкое распространение.

Первая программная реализация алгоритма БПФ была осуществлена в начале 60-х годов XX века Джоном Кули в вычислительном центре IBM под руководством тески Джона Тьюки, а в 1965 году ими же была опубликована статья, посвященная алгоритму быстрого преобразования Фурье. С этого момента начинается настоящая БПФ-мания. Публикуются тысячи работ посвященных алгоритму БПФ, одна за одной выходят монографии, программисты соревнуются в эффективности реализации алгоритма. БПФ становится основным инструментом спектрального анализа сигналов.



Краткие теоретические сведения

У периодических функций отношение двух любых частот есть рациональное число. Если это отношение иррациональное, то имеем почти периодическую функцию. Пример.

Периодическую детерминированную функцию с периодом Т, удовлетворяющую условиям Дирихле, можно разложить в ряд Фурье

,(7.1)

где - комплексная амплитуда n-й гармоники ряда

.(7.2)

Модуль комплексной амплитуды , зависящий от , представляет собой линейчатый спектр периодической функции. Средняя мощность периодической функции определяется по формуле

(7.3)

и называется теоремой Парсеваля.

У периодической функции спектр линейчатый, но не всякая функция с линейчатым спектром - периодическая.

Пусть непериодическая функция абсолютно интегрируема на

. (7.4)

Заменим функцией такой, что . Тогда для существует ряд Фурье (1).

При , поэтому рассмотрим вместо величину

.

Таким образом, получаем прямое и обратное преобразование Фурье (ППФ и ОПФ)

, (7.5)

. (7.6)

ПФ оригинала называется спектральной характеристикой.

Теорема Котельникова. Непрерывный сигнал с финитным спектром, т.е. с конечной полосой частот при , однозначно восстанавливается по значениям в точках , если частота дискретизации , не менее . Непрерывный сигнал может быть получен из последовательности по формуле

. (7.7)

Связь между спектрами дискретизированного и непрерывного сигналов определится соотношением

где - частота дискретизации.

Отсюда видно, что спектр функции с дискретным временем представляет собой периодическое продолжение спектра функции с непрерывным временем. Если частота дискретизации меньше , то периодически продолженные спектры будут перекрываться соседними, что приводит к искажению спектра и носит название эффекта наложения или мимикрии частот.

Частота носит название частоты Найквиста. При дискретизации сигнала гармоники с частотой, большей частоты Найквиста, будут накладываться на гармоники меньшей частоты.

Пара дискретного преобразования Фурье (ДПФ)N-точечной последовательности определяется выражениями:

,(7.8)

,(7.9)

где .

Если же задана N-точечная последовательность с шагом T, то ДПФ будет иметь вид:

,(7.10)

,(7.11)

Эту пару называют парой дискретно-временных рядов Фурье (ДВРФ).

ДПФ можно рассматривать как некоторую аппроксимацию НВПФ, основанную на использовании конечного числа отсчетов данных

Дискретизация сигнала с шагом T приводит к ограничению ширины спектра частотами и периодичности спектра. Ограничение длины последовательности N-отсчетами приводит к взятию отсчетов по частоте с шагом , что в свою очередь приводит к периодическому продолжению исходной временной последовательности с периодом NT.

Возможен другой путь объяснения пары ДПФ, эквивалентный изложенному. В этом случае ограничиваем длину последовательности во временной и частотной областях и осуществляем дискретизацию во временной области с шагом T и в частотной области с шагом . Ограничение ширины спектра и дискретизация во временной области приводит к периодичности спектра, а дискретизация спектра приводит периодичности во временной области. Если шаг дискретности , то имеем пару ДПФ.

Минимальный шаг дискретности по частоте ДПФ равен обратной величине длины последовательности N. При малых N возникают неопределенности в спектре и невозможно обнаружить пиковые значения из-за попадания между отсчетами. Для этого используют процедуру дополнения N нулями исходной последовательности. Для этого N-точечную последовательность отсчетов дополняют N нулевыми значениями до размера 2N. Тогда ДПФ дополненной последовательности равен

.

Если здесь выделим значения с четными номерами, то получим

,

Здесь предел суммирования исходной последовательности, так как

.

Если из ДПФ дополненной последовательности выделить значения с четными номерами, то получим ДПФ исходной последовательности , а ДПФ с нечетными номерами будет соответствовать интерполированным значениям между отсчетами ДПФ этой же последовательности. В результате получаем преобразование более сглаженной формы.

Для вычисления каждой гармоники ДПФ необходимо N операций комплексного умножения и сложения и соответственно N2 операций на полное выполнение ДПФ. При больших объемах массивов данных это может приводить к существенным временным затратам. Ускорение вычислений достигается при использовании быстрого преобразования Фурье. Наиболее широко распространенным является вычисление БПФ по основанию 2 или алгоритм Кули-Тьюка, разработанный в 1965 г, который требует не более умножений.

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

Вычисление БПФ по основанию 2 значительно проще, чем вычисление ДПФ, так как необходимо вычислять только 2-точечные ДПФ. Однако вычисляемые поворачивающие множители будут различными на каждом этапе прореживания.

Пусть дана последовательность длины Nцелой степени 2. ДПФ последовательности равно:

.

Разобьем последовательность на две, состоящие из четных и нечетных номеров:

,

Но

.

Поэтому:

(7.12)

Здесь и два ДПФ -точечных последовательностей, состоящих из номеров четных и нечетных индексов.

Число умножений этих двух ДПФ равно:

то есть в 2 раза меньше, чем в исходной ДПФ.

Если , то продолжим дальнейшее разбиение последовательности и получим четыре -точечные ДПФ.

Деление будем продолжать до тех пор, пока не получим подпоследовательности, содержащие только по 2 элемента.

Для двухточечной последовательности ДПФ равно:

(7.13)

Последовательность ДПФ периодична с периодом N, т.е.

,

так как .

Направленный граф 8-точечного БПФ с прореживанием по времени приведен на рис 7.1.

Разобьем последовательность на две подпоследовательности, включив в первую первых отсчетов, а вторую - остальные. Тогда

(7.14)

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Рис. 7.1. Направленный граф БПФ с прореживанием по времени.

Но эти слагаемые не равны -точечным ДПФ. Преобразуем выражение (7.14) следующим образом, но

Поэтому

.(7.15)

Разобьем выражение (7.15) на два, выделив четные и нечетные номера. Тогда получим:



,(7.16)

но

Следовательно, имеем два -точечных ДПФ для последовательностей

(7.17)

Если продолжим деление дальше, то получим двухточечное ДПФ.

Направленный граф алгоритма с прореживанием по частоте для последовательности длины N приведен на рис. 7.2.

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Рис. 7.2. Направленный граф БПФ с прореживанием по частоте.

Для вычисления ОДПФ с помощью алгоритма БПФ:

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

.

2. В ходе БПФ используем вместо . Полученные результаты не забываем разделить на N.

Быстрое преобразование Фурье с прореживанием по времени

Дана последовательность из 8 чисел: {x[m]}= {1 2 4 1 8 2 4 3}. Необходимо вычислить ДПФ с помощью алгоритма БПФ с прореживанием по времени. Сначала последовательность {x[m]} разбиваем на две подпоследовательности:

{x1[m]}={1184}; {x2[m]}={2423},

каждую из которых в свою очередь разбиваем на две подпоследовательности:

{x11[m]}={1 8}, {x12[m]}={1 4}; {x21[m]}={2 2}, {x22[m]}={4 3}.

Таким образом, преобразуем исходную последовательность в нужный для алгоритма БПФ вид:

{x[m]}={1 8 1 4 2 2 4 3}.

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Рис. 1. Направленный граф БПФ с прореживанием по времени.

Определим число итераций алгоритма: . Дальнейшие вычисления просты и не требуют дополнительного пояснения.

1 итерация.

X1[0]=1+8=9

X1[1]=1 - 8 = -7

X1[2]=1+4=5

X1[3]=1 - 4 = -3

X1[4]= 2 + 2 =4

X1[5]= 2 - 2 = 0

X1[6]=4 + 3 = 7

X1[7]= 4 - 3 = 1

2 итерация.

Вычисляем множители:

.

Для начала вспомним формы представления комплексных чисел.

- показательная форма,

- тригонометрическая форма,

- алгебраическая форма.

Алгебраическая форма связана с предыдущими соотношениями:

преобразование фурье итерация алгоритм

.

Модуль комплексного числа (необходим для построения амплитудно-частотной характеристики):

.

Аргумент комплексного числа (необходим для построения фазово-частотной характеристики):

.

Вернемся к нашему примеру.

X2[0]= 9 + 5(1) = 14

X2[1]= -9+5 (-j) = -4

X2[2]= -7 + 3(-1) = -4

X2[3]= 7 + 3(j) = 11

X2[4]= 4 + 7(1) = 11

X2[5]= -4+7(j) = 3

X2[6]= 0 + 1(1) = 1

X2[7]= 0 + 1(j) = 1

З итерация.

Вычисляем множители:

.

Для нахождения коэффициентов ДПФ потребуются вычисления комплексных чисел, поэтому вспомним операции с ними:

.

X3[0]= 14 + 11(1) = 25

X3[1]= -4 + j(0,707 - 0,707j) = -3,293 + 0,707j

X3[2]= -4 + 1(-j) = -3

X3[3]= -4 - 3(-0,707 - 0,707j) = -1,707 + 0,707j

X3[4]= 14 +11(-1) = 1

По аналогии:

X3[5]= -3,707 - 0,707j

X3[6]= 3 + j

X3[7]= -3,293 - 0,707j

Примечание. Для действительных последовательностей необходимо вычислять только первые коэффициентов ДПФ, так как остальные являются комплексно-сопряженными относительно центрального значения.

Два комплексно-сопряженных числа представляют собой пару

В рассматриваемом примере:

X3[7]=X3*[1]



Список литературы

1. Власова, И. Н. Основы математической обработки информации [Электронный ресурс]: учебное пособие для организации самостоятельной деятельности студентов / Власова И. Н. - Пермь: Пермский государственный гуманитарно-педагогический университет, 2013. Режим доступа: http://www.iprbookshop.ru/32076.html

2. Гмурман, В. Е.Руководство к решению задач по теории вероятностей и математической статистике: учеб. пособие для вузов / В. Е. Гмурман. - 11-е изд., перераб. и доп. - М.: Юрайт: ИД Юрайт, 2011.

3. Карманов, Ф. И.Статистические методы обработки кспериментальных данных. Лабораторный практикум с использованием пакета MathCad: [Электронный ресурс]: учебное пособие / Карманов Ф.И.; Острейковский В.А. - Москва: Абрис, 2012.

4. Костин, В. Н. Теория эксперимента [Электронный ресурс]: учебное пособие /Костин В. Н. - Оренбург: Оренбургский государственный университет, ЭБС АСВ, 2013. - 209 с. Режим доступа:http://www.iprbookshop.ru/30132.html

5. Улитина, Е. В.Статистика [Электронный ресурс]: учебное пособие / Улитина Е. В. - Москва: Московский финансово-промышленный университет «Синергия», 2013. Режим доступа: http://www.iprbookshop.ru/17045.html

Размещено на Allbest.ru

...