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

       ВВЕДЕНИЕ 
 

       Верно, что господин Фурье  был того мнения, что конечной целью  математики является общественная польза и объяснение явлений  природы;…

       Якоби К. 

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

       Историческая  справка: Жозеф Фурье(1768 - 1830) родился в период, когда французская революция и наполеоновская эпоха создали исключительно благоприятные условия для дальнейшего развития математики. На континенте Европы был открыт путь для промышленной революции. Она побуждала к занятиям физическими науками, создала новые общественные классы с новыми взглядами на жизнь,  заинтересованные в науке и в техническом образовании. В академическую жизнь ворвались демократические идеи, устаревшие формы мышления вызывали критику, школы и университеты были преобразованы и обновлены.

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

       И в этот период Ж. Фурье остается приверженцем утилитарного подхода и в своих  исследованиях склоняется к практическому  применению математических теорий. Фурье  был одним выдающихся математиков, связанных с Политехнической школой в ее раннем периоде. Он, как и О. Коши, С. Пуассон, глубоко интересовался применением математики к механике и к физике и благодаря таким интересам пришел к открытиям в чистой математике. О Фурье мы прежде всего вспоминаем как об авторе «Аналитической теории теплоты»(1822г.). Это – математическая теория теплопроводности и, стало быть, в основном исследовании уравнения . В силу общности метода эта книга стала источником всех современных методов математической физики, относящихся к интегрированию уравнений в частных производных при заданных граничных условиях. Методом Фурье было применение тригонометрических рядов, что уже было предметом дискуссий между Эйлером, Даламбером и Даниилом Бернулли. Фурье полностью разъяснил положение вещей. Он установил тот факт, что «произвольную» функцию (функцию, которую можно изобразить дугой непрерывной кривой или сочетанием таких дуг) можно представить тригонометрическим рядом вида .  Несмотря на все то, что было указано Эйлером и Бернулли, эта идея была настолько нова и ошеломляюща во времени Фурье, что, когда он впервые в 1807г. высказывал свои соображения, он встретил энергичную оппозицию со стороны Лагранжа. Ряды Фурье теперь стали хорошо разработанным средством в теории уравнений в частных производных при решении граничных задач. Они и сами по себе привлекают внимание благодаря присущим им свойствам. Исследование этих рядов, проведенное Фурье, отчетливо поставило вопрос о том, что следует понимать под функцией. Это было одной из причин того, что математики XIX столетия сочли необходимым более тщательно рассмотреть вопросы о строгости математических доказательств и об общих основах математических понятий.

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

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

       Целью данной работы является объективная характеристика ДПФ.

       Для ее достижения были поставлены следующие  задачи:

1. Изучение основных понятий ДПФ
2. Исследование недостатков ДПФ
3. Поиск путей их разрешения
4. Исследование практической значимости ДПФ
5. Оформление работы в форме, пригодной для использования в качестве методической разработки для предметов «Статистический анализ» и «Анализ временных рядов».

 
 
 
 
 
 

       1 ОСНОВНЫЕ ПОНЯТИЯ ДИСКРЕТНОГО  ПРЕОБРАЗОВАНИЯ ФУРЬЕ. НЕДОСТАТКИ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, ПРИ ПРИМЕНЕНИИ ЕГО НА ПРАКТИКЕ, И ПУТИ ИХ РАЗРЕШЕНИЯ 

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

       Определение 1. Дана конечная последовательность чисел (в общем случае комплексных). Прямое дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности элементы которой вычисляются по формуле:

       

                     (1.1)

где -мнимая единица, - постоянная, - количество элементов в последовательностях и , n – индекс текущего элемента в последовательности , k – индекс текущего элемента в последовательности [15].

       В терминологии анализа временных  рядов под прямым ДПФ понимают способ представления временных зависимостей (сигналов) в виде набора гармоник. Гармоника – это гармоническая составляющая сигнала, представленного в виде тригонометрического ряда Фурье , или другими словами одна из слагаемых этого ряда [13].

       Определение 2. Дана конечная последовательность чисел (в общем случае комплексных). [15] Обратное дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности элементы которой вычисляются по формуле:

       

                   (1.2)

       В терминологии анализа временных  рядов под обратным ДПФ понимают преобразование спектра во временную зависимость [13].

         ДПФ стало особенно эффективным  методом решения прикладных задач  после создания быстрого преобразования Фурье (БПФ). 

       Алгоритм  БПФ [15] - это оптимизированный по скорости способ вычисления ДПФ. Основная идея заключается в двух пунктах.

1. Необходимо разделить сумму (1.1) из N слагаемых на две суммы по слагаемых, и вычислить их по отдельности. Для вычисления каждой из подсумм, надо их тоже разделить на две и т.д.
2. Необходимо повторно использовать уже вычисленные слагаемые.

       Применяют либо "прореживание по времени" (когда  в первую сумму попадают слагаемые  с четными номерами, а во вторую - с нечетными), либо "прореживание по частоте" (когда в первую сумму попадают первые слагаемых, а во вторую - остальные). Оба варианта равноценны. В силу специфики алгоритма приходится применять только N, являющиеся степенями 2. В данной работе рассмотрен случай прореживания по времени.

       1.1 Физический смысл ДПФ 

       Для чего нужно ДПФ? Как работает БПФ? Давайте попробуем разобраться.

       Пусть у нас есть функция синуса .

       

       Рисунок  1. 1 - График

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

       Период  колебания функций и равен 2π. Если мы хотим увеличить период до T, то надо умножить переменную t на коэффициент . Это вызовет растяжение графика по горизонтали: .

       Частота колебания обратна периоду: . Также говорят о круговой частоте, которая вычисляется по формуле: . Откуда: .

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

       

       Рисунок 1.2 - График

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

       

       Рисунок 1.3 - График

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

       

                                             (1.3)                   

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

       Преобразуем (1.3) по формуле косинуса суммы:

       

                 (1.4) 

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

       

                    (1.5)

        ,

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

       

 и        (1.6)

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

       

                   (1.7)

       Выполним  над этой формулой следующие действия: разложим каждое комплексное X_k на мнимую и действительную составляющие ; разложим экспоненту по формуле Эйлера на синус и косинус действительного аргумента; перемножим; внесем под знак суммы и перегруппируем элементы в две суммы:

       

     (1.8)

       Оставим эту формулу пока в стороне  и рассмотрим очень распространенную ситуацию. Пусть у нас есть звуковое или какое-то иное колебание в  виде функции x = f(t). Пусть это колебание было записано в виде графика для отрезка времени [0, T]. Для обработки компьютером нужно выполнить дискретизацию. Отрезок делится на N-1 частей и сохраняются значения функции x₀, x₁, x₂,..., x_N для N точек на границах отрезков t₀ = 0, t₁ = T/N, t₂ = 2T/N,..., t_n =nT/N,..., t_N = T.     

        

       Рисунок 1.4 - Дискретизация колебания, представленного в виде функции

       В результате прямого дискретного  преобразования Фурье были получены N значений для X_k:

       

                    (1.9)

       Теперь, если применить обратное ДПФ, то получится исходная последовательность . Исходная последовательность состояла из действительных чисел, а последовательность в общем случае комплексная. Теперь вернемся к формуле (1.8). Слева стоит действительное число x_n, а справа - две суммы, одна из которых помножена на мнимую единицу j. Сами же суммы состоят из действительных слагаемых. Отсюда следует, что вторая сумма равна нулю, если исходная последовательность была действительной. Отбросим ее и получим:

                                                                 (1.10)

       Поскольку при дискретизации мы брали  и , то можем выполнить замену: . Следовательно, в синусе и косинусе вместо можно написать . В результате получим:

                     (1.11)

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