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

Обновлено: 08.07.2024

На рисунке проиллюстрирован второй этап вычисления ДПФ. Линиями сверху вниз показано использование элементов для вычисления значений новых элментов. Очень удобно то, что два элемента на определенных позициях в массиве дают два элемента на тех же местах. Только принадлежать они будут уже другим, более длинным массивам, размещенным на месте прежних, более коротких. Это позволяет обойтись одним… Читать ещё >

Быстрое преобразование Фурье (БПФ) ( реферат , курсовая , диплом , контрольная )

Содержание

Введение
Преобразование Фурье Быстрое преобразование Фурье Применение преобразования Фурье Практическая часть
Список литературы

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

Пусть у нас есть функция синуса x = sin (t).

Максимальная амплитуда этого колебания равна 1. Если умножить его на некоторый коэффициент A, то получим тот же график, растянутый по вертикали в A раз: x = Asin (t).

Период колебания равен 2π. Если мы хотим увеличить период до T, то надо умножить переменную t на коэффициент. Это вызовет растяжение графика по горизонтали: x = A sin (2πt/T). Частота колебания обратна периоду: ν = 1/T. Также говорят о круговой частоте, которая вычисляется по формуле: ω= 2πν = 2πT. Откуда: x = A sin (ωt).

И, наконец, есть фаза, обозначаемая как φ. Она определяет сдвиг графика колебания влево. В результате сочетания всех этих параметров получается гармоническое колебание или просто гармоника:

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

Большой разницы нет. Достаточно изменить фазу на π/2, чтобы перейти от синуса к косинусу и обратно. Далее будем подразумевать под гармоникой функцию косинуса:

x = A cos (2πt/T + φ) = A cos (2πνt + φ) = A cos (ωt + φ) (18)

В природе и технике колебания, описываемые подобной функцией чрезвычайно распространены. Например, маятник, струна, водные и звуковые волны и прочее, и прочее. Преобразуем (18) по формуле косинуса суммы:

x = A cos φ cos (2πt/T) — A sin φ sin (2πt/T) (19)

Выделим в (19) элементы, независимые от t, и обозначим их как Re и Im:

x = Re cos (2πt/T) — Im sin (2πt / T) (20)

Re = A cos φ, Im = A sin φ

По величинам Re и Im можно однозначно восстановить амплитуду и фазу исходной гармоники:

и (21) Рассмотрим очень распространенную практическую ситуацию. Пусть у нас есть звуковое или какое-то иное колебание в виде функции x = f (t). Пусть это колебание было записано в виде графика для отрезка времени [0, T]. Для обработки компьютером нужно выполнить дискретизацию. Отрезок делится на N-1 равных частей, границы частей обозначим tn = nT/N. Сохраняются N значений функции на границах частей: xn = f (tn) = < x0, x1, x2,…, xN >. В результате прямого дискретного преобразования Фурье были получены N значений для Xk:

Теперь возьмем обратное преобразование Фурье:

Выполним над этой формулой следующие действия: разложим каждое комплексное Xk на мнимую и действительную составляющие Xk = Rek + i Imk; разложим экспоненту по формуле Эйлера на синус и косинус действительного аргумента; перемножим; внесем 1/N под знак суммы и перегруппируем элементы в две суммы:

Это была цепочка равенств, которая начиналась с действительного числа xn. В конце получилось две суммы, одна из которых помножена на мнимую единицу j. Сами же суммы состоят из действительных слагаемых. Отсюда следует, что вторая сумма должна быть равна нулю. Отбросим ее и получим:

Поскольку при дискретизации мы брали tn = nT/N то можем выполнить замену: n = tnN/T. Следовательно, в синусе и косинусе вместо 2πkn/N можно написать 2πktn/T. В результате получим:

Сопоставим эту формулу с формулой (20) для гармоники:

x = Re cos (2πt/T) — Im sin (2πt / T) (20)

Слагаемые суммы (26) аналогичны формуле (20), а формула (20) описывает гармоническое колебание. Значит сумма (26) представляет собой сумму из N гармонических колебаний разной частоты, фазы и амплитуды. Выше объяснялось, каким образом формула вида (20) может быть преобразована в формулу вида (18):

x = A cos (2πt/T + φ) (18)

Выполним такое же преобразование для слагаемых суммы (26), преобразуем их из вида (20) в вид (18). Получим:

Далее будем функцию

Gk (t) = Ak cos (2πtk/T + φk) (28)

называть k-й гармоникой.

Для вычисления Ak и φk надо использовать формулу (21). Теперь выпишем в одном месте все формулы, которые связывают амплитуду, фазу, частоту и период каждой из гармоник с коэффициентами Xk:

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

Практическая часть Рассмотрим реализацию быстрого преобразования Фурье на примере 8 точек:

x 1+i 1 1+2i -1+2i i -2+i -2+2i 1−2i Разделим множество на четные и не четные:

x_even₁ x_odd₁ 1+i 1 1+2i -1+2i i -2+i -2+2i 1−2i Затем снова, каждое из множеств разобьем на четное и не четное:

x_even₂ x_odd₂ x_even₃ x_odd₃ 1+i 1+2i 1 -1+2i i -2+2i -2+i 1−2i Теперь можно вычислить преобразованные коэффициенты.

X_even₃ X_odd₃ X_even₂ X_odd₂ -1+i 0 1+2i -1+4i 3-i -2+4i 1 3 Для дальнейших расчетов необходимо знать значения функции Продолжая вычисления, получим:

X_even₁ X_odd₁ 6i -1+4i 2,1+2,9 999 999 999 9999i -0,99 999 999 999 999+4i 2−2i -1+4i -2,1−0,9 999 999 999 9999i -3,1

Эти значения рассчитываем по формуле:

Результат будет иметь вид:

X -1+10i 4,12 132 034 355 966+6,5 355 339 059 3272i 6−1,01i 0,12 132 034 355 963+1,1 213 203 435 5967i 1+2i -0,12 132 034 355 964−0,5 355 339 059 3274i -2−2,9 999 999 999 9999i -4,12 132 034 355 965−3,1 213 203 435 5965i

Для реализации комплексной арифметики в среде MS Excel использовались следующие средства:

=КОМПЛЕКС (a;b) — задание комплексного числа a+bi.

=МНИМ.ПРОИЗВЕД (a;b) — произведение двух комплексных чисел.

=МНИМ.РАЗН (a;b) — вычисление разности двух комплексных чисел a-b

=МНИМ.СУММ (a;b) — вычисление суммы комплексных чисел a+b

=МНИМ.EXP (a) — возведение экспоненты в комплексную степень a.

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

А. П. Господариков , Г. А. Колтон , С. А. Хачатрян . Ряды Фурье. Интеграл Фурье. Операционное исчисление. Учебно-методическое пособие. САНКТ-ПЕТЕРБУРГ, 2005.

Введение

в теорию интегралов Фурье: — Санкт-Петербург, Ком

Книга, 2007 г.- 480 с.

А. Е. Полищук: Абелевы многообразия, тэта-функции и преобразование Фурье: — Москва, МЦНМО, 2010 г.- 312 с.

Г. Нуссбаумер. Быстрое преобразование Фурье и алгоритмы вычисления сверток. Перевод с английского Ю. Ф. Касимова и И. П. Пчелинцева под редакцией чл.-кор. АН Каз

ССР В. М. Амербаева и Т. Э. Кренкеля/ МОСКВА:

РАДИО И СВЯЗЬ — 1985

И. Снеддон. Преобразование Фурье. Издательство: ИНОСТРАННОЙ ИТЕРАТУРЫ — 1955

Залманзон Л. А. Преобразование Фурье, Уолша, Хаара и их применение в управлении, связи и других областях Наука: 1989

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

Рубрика	Математика
Вид	курсовая работа
Язык	русский
Дата добавления	21.06.2019
Размер файла	267,3 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дана последовательность из 8 чисел: = . Необходимо вычислить ДПФ с помощью алгоритма БПФ с прореживанием по времени. Сначала последовательность разбиваем на две подпоследовательности:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подобные документы

Нахождение спектральных составляющих дискретного комплексного сигнала. Быстрое преобразование Фурье с прореживанием по времени. Методы сокращения числа комплексных умножений. Вычислительные процедуры, уменьшающие количество умножений и сложений.

презентация [133,3 K], добавлен 19.08.2013

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

курсовая работа [231,5 K], добавлен 27.08.2012

Дискретный периодический сигнал, представленный рядом Фурье. Прямое и обратное дискретное преобразование. Его свойства: линейность и симметрия. Алгоритм вычисления круговой свертки сигналов. Равенство Парсеваля для них. Связь ДПФ с Z-преобразованием.

презентация [72,0 K], добавлен 19.08.2013

Свойства дискретного преобразования Фурье, представленные в виде математических формул, которые наиболее адекватно соответствуют цифровой технике обработки информации. Алгоритм быстрого преобразования Фурье (БПФ), его значение для программирования.

учебное пособие [223,6 K], добавлен 11.02.2014

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

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

1. Быстрое преобразование Фурье.. …. ……………………….….…. 5

3. Применения преобразования Фурье .……………………..….…..…. 9

4. Преобразование Фурье ……………………………….…. … 10

6. Простыми словами о преобразовании Фурье………………….…. 14

7. Фурье и техника связи………………………………………. …… 18

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

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

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

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

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

Существует большое количество алгоритмов БПФ. Однако все они являются частными случаями единого алгоритма, базирующегося на задаче разбиения одного массива чисел на два. Тот факт, что это можно сделать более чем одним способом, определяет многообразие алгоритмов БПФ. Рассмотрим два из них.

В настоящее время алгоритмы быстрого преобразования Фурье хорошо известны и широко используются в спектральном анализе. Хотя в современной литературе излагается целый ряд различных подходов к разработке алгоритмов БПФ, мы ограничимся одним из них, а именно, так называемым алгоритмом Кули–Тьюки, впервые описанным в статье J . W . Cooley and J . W . Tukey , " An algorithm for the machine calculation of complex Fourier series ," Math . Comput. 19, 297–301 (1965).

Необходимость введения быстрых алгоритмов суммирования рядов Фурье связана со значительными вычислительными затратами, требующимися при выполнении преобразований Фурье над массивами большой размерности. В самом деле, для вычисления одной Фурье - гармоники по N отсчетам (см. формулу (3.3)), нужно выполнить порядка N операций каждая из которых включает вычисление W –kj , умножение u( j) W −kj и сложение. Для нахождения всего спектра, состоящего из N гармоник, требуется порядка S₀ = N 2 операций. То же самое касается и обратного преобразования Фурье. Алгоритм БПФ позволяет значительно уменьшить число операций, причем одним из ключевых моментов является периодичность ядра преобразования W kj с периодом N.

Для удобства и компактности изложения временно откажемся от принятых ранее пределов нумерации узлов сетки и фурье – гармоник от −N / 2 до N / 2 −1 , и будем использовать для оригинала и спектра пределы суммирования от 0 до N – 1 При этом прямое и обратное преобразования выразятся формулами

На рис. 1 изображены дискретный оригинал и дискретный спектр при такой нумерации узлов сетки и фурье - гармоник.

Рисунок 1 – Альтернативная нумерация узлов сетки j и фурье - гармоник k

Алгоритм быстрого суммирования рядов Фурье принципиально основывается на возможности разбиения числа N на сомножители. Отметим сразу, что если N – простое число, то построить указанный алгоритм не удается. Рассмотрим для определенности прямое преобразование Фурье

(2)

Предположим, что N – составное, т.е.

(3)

где N₁ и N₂ – целые числа. Тогда, разбив число N на N₂ групп по N₁ отсчетов, можно представить текущий номер узла сетки в виде j = j₁ + j₂N₁, где j₁ = 0,1,L, N1 −1 , j₂ = 0,1 ,L, N₂ −1 (рис. 2).

Рисунок 2 – Представление номеров узлов сетки j в виде N ₂ групп по N ₁ , узлов в каждой группе

Аналогично представим номер фурье - гармоники как k = k₂ + k₁N₂, где

Рисунок 3 – Представление номера фурье – гармоники k в виде N ₁ групп по N ₂ гармоник в каждой группе

Введем обозначение u( j) = u( j₁ + j₂N₁) = u( j₁, j₂) . Тем самым мы сведем одномерный массив u( j) к двумерному массиву u( j₁, j₂) , состоящему из N₂ строк и N₁ столбцов. Тогда прямое преобразование Фурье (2) выразится в виде:

Вынесем за знак внутренней суммы не зависящий от j₂ множитель W −kj1 , а в оставшемся сомножителе представим k = k₂ + k₁N₂. После этого имеем:

Учтем, что W - k 1 N 2 N 1 = W - k 1 j 2 N . Используя явный вид W_N = exp (2π i / N ), получим, что W - k 1 j 2 N 2 N 1 =е -2π k 1 j 2 =1. Введем обозначение для внутренней суммы в (5), а именно:

Выражение (6) называют спектром разреженных отсчетов, где j₁ – параметр, принимающий значения j₁ = 0,1,…, N₁ −1 . Разреженные отсчеты u( j₁*, j₂) образуются из отсчетов с номерами j1*, взятыми во всех группах с j₂ = 0,1 . N₂ −1 (рис. 4).

Рисунок 4 – Разреженные отсчеты

Используя (6), прямое преобразование Фурье можно записать следующим образом:

3. Применения преобразования Фурье

Преобразование Фурье используется во многих областях науки — в физике, теории чисел, комбинаторике, обработке сигналов, теории вероятностей, статистике, криптографии, акустике, океанологии, оптике, геометрии, и многих других. В обработке сигналов и связанных областях преобразование Фурье обычно рассматривается как декомпозиция сигнала на частоты и амплитуды, то есть, обратимый переход от временно́го пространства (time domain) в частотное пространство (frequency domain). Богатые возможности применения основываются на нескольких полезных свойствах преобразования:

– Преобразования являются линейными операторами и, с соответствующей нормализацией, также являются унитарными (свойство, известное как теорема Парсеваля или, в более общем случае как теорема Планшереля, или в наиболее общем как дуализм Понтрягина).

– Преобразования обратимы, причём обратное преобразование имеет практически такую же форму, как и прямое преобразование.

– Синусоидальные базисные функции (вернее, комплексные экспоненты) являются собственными функциями дифференцирования, что означает, что данное представление превращает линейные дифференциальные уравнения с постоянными коэффициентами в обычные алгебраические. (Например, в линейной стационарной системе частота — консервативная величина, поэтому поведение на каждой частоте может решаться независимо.)

– По теореме о свёртке, преобразование Фурье превращает сложную операцию свёртки в простое умножение, что означает, что они обеспечивают эффективный способ вычисления основанных на свёртке операций, таких как умножение многочленов и умножение больших чисел.

– Дискретная версия преобразования Фурье может быстро рассчитываться на компьютерах, используя алгоритм быстрого преобразования Фурье (БПФ, англ. FFT).

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

Анализ Фурье закладывает основы многих методов, применяющихся в области цифровой обработки сигналов (ЦОС). По сути дела, преобразование Фурье (фактически существует несколько вариантов таких преобразований) позволяет сопоставить сигналу, заданному во временной области, его эквивалентное представление в частотной области. Наоборот, если известна частотная характеристика сигнала, то обратное преобразование Фурье позволяет определить соответствующий сигнал во временной области.

Семейство преобразований Фурье (преобразование Фурье, ряды Фурье, дискретные ряды Фурье и дискретное преобразование Фурье) представлено на рисунке 5. С течением времени принятые определения получили развитие в зависимости от того, является ли сигнал непрерывно-апериодическим, непрерывно-периодическим, дискретно-апериодическим или дискретно-периодическим

Рисунок 5 – Семейство преобразований фурье

Единственный член этого семейства, который имеет отношение к цифровой обработке сигналов, – это дискретное преобразование Фурье, которое оперирует дискретной по времени выборкой периодического сигнала во временной области. Для того чтобы быть представленным в виде суммы синусоид, сигнал должен быть периодическим. Но в качестве набора входных данных для ДПФ доступно только конечное число отсчетов (N). Эту дилемму можно разрешить, если мысленно поместить бесконечное число одинаковых групп отсчетов до и после обрабатываемой группы, образуя, таким образом, математическую (но не реальную) периодичность, как показано на рисунке 6.

Рисунок 6 – БПФ периодического сигнала

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

Рисунок 7 – БПФ не периодического сигнала

Рисунок 8 – Применение функции окна на входной сигнал

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

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

Важной особенностью алгоритма БПФ является необходимость такой перестановки элементов входной последовательности u(j), чтобы выходная последовательность U(k) имела естественный (прямой) порядок расположения, т. е. k = 0,1,L, N −1 . Характер такой перестановки элементов входной последовательности может быть описан сравнительно просто. В случае, когда N является степенью числа 2, входная последовательность должна быть расположена в памяти в двоично-инверсном порядке, который определяется следующим образом. Если записать порядковые номера элементов входной последовательности в двоичном коде, используя m двоичных разрядов, причем m N = 2 , а затем инвертировать порядок следования разрядов, то получаемые при этом числа и будут номерами элементов входной последовательности после их перестановки. Более подробно с практической реализацией двоичной инверсии, в частности. Для случая N = 8 23= прямой порядок номеров приведен в таблице 1 слева, а двоично-инверсный порядок – справа.

Таблица 1 – Двоичная инверсия

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

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

В таблице помещены исходные номера последовательности в десятичном представлении (первая колонка), в двоичном представлении (вторая колонка), двоично-инверсном представлении (третья колонка) и в десятичном представлении после двоичной инверсии (четвертая (колонка).

6. Простыми словами о преобразовании Фурье

Без использования сложных формул и матлаба я постараюсь ответить на следующие вопросы:

– FT, DTF, DTFT — в чем отличия и как совершенно разные казалось бы формулы дают столь концептуально похожие результаты?;

– Как правильно интерпретировать результаты быстрого преобразования Фурье (FFT);

– Что делать если дан сигнал из 179 сэмплов а БПФ требует на вход последовательность по длине равную степени двойки;

– Почему при попытке получить с помощью Фурье спектр синусоиды вместо ожидаемой одиночной “палки” на графике вылезает странная загогулина и что с этим можно сделать;

– Зачем перед АЦП и после ЦАП ставят аналоговые фильтры;

– Можно ли оцифровать АЦП сигнал с частотой выше половины частоты дискретизации (школьный ответ неверен, правильный ответ — можно);

– Как по цифровой последовательности восстанавливают исходный сигнал.

Начать надо, наверное, с того что обычное преобразование Фурье — это некая такая штука которая, как можно догадаться из названия, преобразует одни функции в другие, то есть ставит в соответствие каждой функции действительного переменного x(t) её спектр или фурье - образ y(w):

Если приводить аналогии, то примером аналогичного по смыслу преобразования может послужить например дифференцирование, превращающее функцию в её производную. То есть преобразование Фурье — такая же, по сути, операция как и взятие производной, и её часто обозначают схожим образом, рисуя треугольную “шапочку” над функцией. Только в отличие от дифференцирования которое можно определить и для действительных чисел, преобразование Фурье всегда “работает” с более общими комплексными числами. Из-за этого постоянно возникают проблемы с отображением результатов этого преобразования, поскольку комплексные числа определяются не одной, а двумя координатами на оперирующем действительными числами графике. Удобнее всего, как правило, оказывается представить комплексные числа в виде модуля и аргумента и нарисовать их по раздельности как два отдельных графика.

График аргумента комплексного значения часто называют в данном случае “фазовым спектром”, а график модуля — “амплитудным спектром”. Амплитудный спектр как правило представляет намного больший интерес, а потому “фазовую” часть спектра нередко пропускают. В этой статье мы тоже сосредоточимся на “амплитудных” вещах, но забывать про существование пропущенной фазовой части графика не следует. Кроме того, вместо обычного модуля комплексного значения часто рисуют его десятичный логарифм умноженный на 10. В результате получается логарифмический график, значения на котором отображаются в децибелах (дБ).

Если взять функцию, состоящую из суммы множества синусоид с разными частотами, то согласно свойству линейности, фурье - образ этой функции будет состоять из соответствующего набора дельта - функций. Это позволяет дать наивную, но наглядную интерпретацию спектра по принципу “если в спектре функции частоте f соответствует амплитуда a, то исходную функцию можно представить как сумму синусоид, одной из которых будет синусоида с частотой f и амплитудой 2a”. Строго говоря, эта интерпретация неверна, поскольку дельта-функция и точка на графике — это совершенно разные вещи, но как мы увидим дальше, для дискретных преобразований Фурье она будет не так уж и далека от истины.

Второе свойство преобразования Фурье — это независимость амплитудного спектра от сдвига сигнала по времени. Если мы подвинем функцию влево или вправо по оси x, то поменяется лишь её фазовый спектр.

Третье свойство — растяжение (сжатие) исходной функции по оси времени (x) пропорционально сжимает (растягивает) её фурье - образ по шкале частот (w). В частности, спектр сигнала конечной длительности всегда бесконечно широк и наоборот, спектр конечной ширины всегда соответствует сигналу неограниченной длительности.

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

Шестое свойство говорит о симметрии фурье - образов. В частности, из этого свойства следует что в фурье - образе действительно значной функции (т.е. любого “реального” сигнала) амплитудный спектр всегда является четной функцией, а фазовый спектр (если его привести к диапазону -pi. pi) — нечетной. Именно по этой причине на графиках спектров практически никогда не рисуют отрицательную часть спектра — для действительно значных сигналов она не дает никакой новой информации (но, повторюсь, и нулевой при этом не является).

Наконец последнее, седьмое свойство, говорит о том, что преобразование Фурье сохраняет “энергию” сигнала. Оно осмысленно только для сигналов конечной продолжительности, энергия которых конечна, и говорит о том, что спектр подобных сигналов на бесконечности быстро приближается к нулю. Именно в силу этого свойства на графиках спектров как правило изображают только “основную” часть сигнала, несущую в себе львиную долю энергии — остальная часть графика просто стремится к нулю (но, опять же, нулем не является).

Документ предоставляется как есть, мы не несем ответственности, за правильность представленной в нём информации. Используя информацию для подготовки своей работы необходимо помнить, что текст работы может быть устаревшим, работа может не пройти проверку на заимствования.

Можно ли скачать документ с работой

Да, скачать документ можно бесплатно, без регистрации перейдя по ссылке:

РЕФЕРАТ

Данная курсовая работа содержит (без учета разделов в приложениях) 32 страницы, 10 рисунков, 1 таблица, 2 приложения. Использовано 8 источников.

Ключевые слова: дискретное преобразование Фурье, быстрое преобразование Фурье, программирование, спектральный анализ, частотно-временной анализ звукового сигнала, цифровая обработка сигналов, микроконтроллеры.

Задачи работы: аналитический обзор алгоритмов спектрального анализа, изучение программных функций обработки звукового сигнала, рассмотреть основные этапы дискретизации звука, настройку и работу аналого-цифрового преобразователя, практический обзор широтно-импульсной модуляции, с последующим применением на микроконтроллере Atmel с учётом его всех архитектурных особенностей.

В результате исследования получены результаты, подтверждающие возможность и целесообразность применения микроконтроллеров в задачах выполнения алгоритмов спектрального анализа

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

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

БПФ – быстрое преобразование Фурье;

ДПФ – дискретное преобразование Фурье;

ШИМ – широтно-импульсная модуляция;

АЦП – аналого-цифровой преобразователь;

ЦОС – цифровая обработка сигналов;

Содержание

Введение

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

1 Аналитический раздел

Спектральный анализ

Спектральный анализ – это один из методов обработки сигналов, который позволяет охарактеризовать частотный состав измеряемого сигнала. Преобразование Фурье является математической основой, которая связывает временной или пространственный сигнал (или же некоторую модель этого сигнала) с его представлением в частотной области. Методы статистики играют важную роль в спектральном анализе, поскольку сигналы, как правило, имеют шумовой или случайный характер. Если бы основные статистические характеристики сигнала были известны точно или же их можно было бы без ошибки определить на конечном интервале этого сигнала, то спектральный анализ представлял бы собой отрасль точной науки. Однако в действительности по одному отрезку сигнала можно получить только некоторую оценку его спектра.

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

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

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

Семейство преобразований Фурье (преобразование Фурье, ряды Фурье, дискретные ряды Фурье и дискретное преобразование Фурье) представлено на рисунке 1. С течением времени принятые определения получили развитие в зависимости от того, является ли сигнал непрерывно-апериодическим, непрерывно-периодическим, дискретно-апериодическим или дискретно-периодическим

Рисунок 1– Семейство преобразований Фурье

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

Рисунок 2 – Уравнение N -точечного ДПФ

По отношению к этому уравнению следует сделать некоторые терминологические разъяснения. X(k) (прописная буква X) представляет собой частотный выход ДПФ в k-ой точке спектра, где k находится в диапазоне от 0 до N-1. N представляет собой число отсчетов при вычислении ДПФ. Значение x(n) (строчная буква x) представляет собой n-ый отсчет во временной области, где n также находится в диапазоне от 0 до N-1. В общем уравнении x(n) может быть вещественным или комплексным.

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

Рисунок 3–БПФ периодичного сигнала

Рисунок 4 – БПФ не периодичного сигнала

Рисунок 5 – Применение функции окна на входной сигнал

Быстрое Преобразование Фурье. Функции

В данной работе была использована математическая библиотека FastFouriertransform с размером N выборки в 128 точек. Программная библиотека быстрого преобразования Фурье имеет встроенные функции, соответствующие поэтапному преобразованию Фурье. С точки зрения программного кода (Приложение Б), все данные помещаются в один глобальный массив f h t_input[] ,и все последующее преобразование разделяется на 4 основные функции в порядке использования:

f h t_window() – Применение окна Ханна (Хеннинга). Эта функция умножает входные данные на функцию окна, чтобы увеличить частотное разрешение данных.

f h t_reorder()–Функция переупорядочивания частотных данных. После её применения, все частотные данные распределяются в массиве f h t_input[] в порядке увеличения частоты.

f h t_run()–Это основной вызов функции БПФ. Он не принимает переменных и не возвращает переменных. Данные хранятся в массиве с именем f h t_input [], который содержит 16-битное число для каждой точки данных БПФ.

f h t_mag_lin()–Представление данные в линейном виде. Данная функция последняя и она определяет, в каком виде будут выходные частотные данные. Для этого, суммируются квадраты мнимой и вещественной части, а затем берется квадратный корень. Данные берутся из f h t_input []и возвращаются в новый массив f h t_lin_out []. Все значения находятся в последовательном порядке.

2 Конструкторский раздел

Выбор языка программирования

Для реализации данного курсового проекта был выбран язык программирования C++. Это компилируемый, статически типизированный язык программирования общего назначения. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником — языком C, — наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования.

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

Стоит также отметить, что в языке С++ все низкоуровневые операции, выполняемые компьютерами, представлены в виде абстрактных конструкций, позволяющих разработчикам сосредоточиться на программировании одной лишь логики, не заботясь о машинном коде. Таким образом, изучив язык С++, можно легко переходить от одного семейства микроконтроллеров к другому, тратя гораздо меньше времени на разработку.

Микроконтроллер ATMEGA 328 P

Микроконтроллер – однокристальный компьютер на одной микросхеме. Предназначен для управления различными электронными устройствами и осуществления взаимодействия между ними в соответствии с заложенной в микроконтроллер программой. В отличие от микропроцессоров, используемых в персональных компьютерах, микроконтроллеры содержат встроенные дополнительные устройства. Эти устройства выполняют свои задачи под управлением микропроцессорного ядра микроконтроллера.

Устройства памяти включают оперативную память (RAM), постоянные запоминающие устройства (ROM), перепрограммируемую ROM (EPROM), электрически перепрограммируемую ROM (EEPROM). Таймеры включают, и часы реального времени, и таймеры прерываний. Средства I/O включают последовательные порты связи, параллельные порты (I/O линии), аналого-цифровые преобразователи (A/D), цифроаналоговые преобразователи (D/A), драйверы жидкокристаллического дисплея (LCD) или драйверы вакуумного флуоресцентного дисплея (VFD). Встроенные устройства обладают повышенной надежностью, поскольку они не требуют никаких внешних электрических цепей.

Микроконтроллеры можно встретить в огромном количестве современных промышленных и бытовых приборов: станках, автомобилях, телефонах, телевизорах, холодильниках, стиральных машинах и даже кофеварках. Среди производителей микроконтроллеров можно назвать Intel, Motorola, Hitachi, Microchip, Atmel, Philips, TexasInstruments и многих других.

Тактовая частота, или, более точно, скорость шины, определяет, сколько вычислений может быть выполнено за единицу времени. В основном производительность микроконтроллера и потребляемая им мощность увеличиваются с повышением тактовой частоты. Производительность микроконтроллера измеряют в MIPS (MillionInstruсtionsperSecond - миллион инструкций в секунду).

В основе преобразования Фурье (ПФ) лежит чрезвычайно простая, но исключительно плодотворная идея – почти любую периодическую функцию можно представить суммой отдельных гармонических составляющих (синусоид и косинусоид с различными амплитудами A, периодами Т и, следовательно, частотами ω). Пример одной из таких функций S(t), состоящей из гармоник С_i(t), приведен на рис.1.

Рис. 1. Представление прямоугольного импульса суммой гармонических составляющих

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

Рис. 2. Дискретное представление непрерывной функции

ПФ часто применяется при решении задач, возникающих в теории автоматического регулирования и управления, в теории фильтрации и т.д. Разберем один из примеров. Имеется некий линейный фильтр – изготовленный то ли в виде набора спаянных между собой резисторов, конденсаторов и катушек индуктивности, то ли в виде модульной конструкции интегральных микросхем. Известен также входной сигнал (на рис.3 в качестве входного сигнала изображена дельта-функция, то есть импульс исчезающе короткой длительности и бесконечно большой амплитуды). Необходимо определить, какой сигнал появится на выходе нашего фильтра.

Рис. 3. Исследование линейного фильтра

Рис. 4. Быстрое преобразование Фурье

Итак, два пути – какой из них избрать? По-видимому, тот, который проще. Во всяком случае, в большинстве практических задач предпочтение отдается частотному направлению.

Лаврус В.С. Практика измерений в телевизионной технике. – К.: НиТ, 1996.

Карташкин А. Уйти, чтобы вернуться.

Раздел: Математика
Количество знаков с пробелами: 3723
Количество таблиц: 0
Количество изображений: 4

Читайте также: