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

       ВВЕДЕНИЕ 
 

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

       Якоби К. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

       В терминологии анализа временных  рядов под обратным ДПФ понимают преобразование спектра во временную зависимость [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.4) элементы, независимые от t, и обозначим их как Re и Im:

        ,

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

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

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

       Оставим эту формулу пока в стороне  и рассмотрим очень распространенную ситуацию. Пусть у нас есть звуковое или какое-то иное колебание в  виде функции 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.8). Слева стоит действительное число x_n, а справа - две суммы, одна из которых помножена на мнимую единицу j. Сами же суммы состоят из действительных слагаемых. Отсюда следует, что вторая сумма равна нулю, если исходная последовательность была действительной. Отбросим ее и получим:

                                                                 (1.10)

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

                     (1.11)

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

       Мы  видим, что сумма (1.11) представляет собой сумму из N гармонических колебаний разной частоты, фазы и амплитуды:

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

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

       Амплитуда, фаза, частота и период каждой из гармоник связаны с коэффициентами X_k формулами:

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

       1.2 Зеркальный эффект 

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

       Эта задача имеет практический интерес. Пусть нам дан некий сигнал, который физически получился  как сумма гармонических колебаний (или близких к ним). Простейший пример: кто-то сыграл аккорд, аккорд записан  как звуковое колебание в виде mp3 или wav-файла; и надо восстановить, из каких нот аккорд состоял. Или другой случай. Во время испытаний самолета возник флаттер (разрушительные нарастающие колебания), самолет разбился, но самописцы в черном ящике записали изменение перегрузки (суммарное механическое колебание). Надо посмотреть, из каких гармоник состояло это колебание. Каждой гармонике соответствует некоторая часть конструкции. В результате можно понять, какие части самолета колебались сильнее всего и вызвали флаттер.

       Вернемся  к предыдущей ситуации.

       Дана  функция  отрезке .

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

       Пусть выполнено прямое ДПФ и функция разложена на сумму из N гармоник:

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

       

.

       Получится ли в результате ее преобразования последовательность {X}, в которой все элементы равны нулю, кроме элемента , который дает как раз эту гармонику?

       Как указывалось ранее – нет. Вместо этой одной гармоники мы получим две:

       Как видно из формул у них половинные амплитуды, противоположные фазы и частоты, зеркально симметрично расположенными на отрезке [0, N]. Это и есть тот самый зеркальный эффект.

       1.2.1 Неоднозначность представления суммой гармоник

       Преобразуем сумму этих гармоник по формуле суммы  косинусов:

       Итого:

       А нам требовалось:

       Однако, формулы (1.15) и (1.16) дают один и тот же результат в точках . В самом деле, подставим сначала в (1.15):

       Учитывая, что для целого n выполняется и , получаем:

       Теперь  подставим в (1.16):

       Формулы (1.17) и (1.18) совпадают, что и требовалось доказать.

       Из  этого примера следует важный вывод. Заданная дискретная последовательность {x_n} может быть разложена в общем случае на разные суммы гармоник . Даже в элементарном случае, когда исходная функция представляла собой одну гармонику, в результате можно получить две. То есть, разложение дискретной последовательности на гармоники неоднозначно.

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

       Рисунок 1.5 - Зеркальный эффект ДПФ функции для и

       На  рисунке 1.5 в точках дискретизации, отмеченных вертикальными штрихами, сумма гармоник и совпадает с гармоникой .

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

       Итак, мы имеем правило:

       Разложение  на гармоники, когда исходные данные представлены дискретным набором точек {x_n} является принципиально неоднозначным. Функции

         дают после дискретизации одни и те же исходные данные и те же результаты ДПФ.

             На основе доказательства зеркального эффекта (Приложение А) получим формулу для X_k (k – того элемента последовательности ):

       Для и для :

       Для :

       Для :

       Для остальных k:

       Вывод:

       Зеркальный  эффект всегда проявляется  так, что гармонические  колебания:

       в процессе дискретного  преобразования Фурье  представляются как  сумма колебаний 

       При этом все коэффициенты ДПФ равны нулю за исключением 

       и

       кроме частных случаев  и , в которых единственный ненулевой коэффициент:

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

       1.2.2 Исправление зеркального эффекта

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

       Рисунок 1.6 - Зеркальный эффект

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

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

       Частота восстанавливается проще всего: ν = m/T, где m - индекс найденного ненулевого элемента X_m. Амплитуда и фаза восстанавливаются по формуле (1.14):

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

       Поэтому, не теряя полезной информации, мы можем  вычесть из ДПФ коэффициенты, соответствующие  найденной гармонике: и   . Для этого мы обнуляем X_m, а над коэффициентом X_{N - m} выполняем действия:

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

       1.3 Эффект размазывания 

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

        Подставим в  эту формулу  вместо m и выполним упрощения, воспользовавшись формулой (А.1) и введя обозначение .  

       Итого:

        Теперь построим график функции, чтобы понять, как она себя ведет. На рисунке 1.7 показана трехмерная поверхность. По горизонтальной оси отложено k, по вертикальной |X_k| и по оси, уходящей вглубь плоскости, отложено q от 0.01 до 0.99.

       Рисунок 1.7 – Эффект размазывания    

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