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

Чувашский государственный университет имени И.Н. Ульянова

Факультет информатики и вычислительной техники

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Курсовая  работа

по дискретной математике на тему:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнила: студентка группы 42-09

                                                                                                             Зайкина Юлия

Проверил  преподаватель :

                                                                                                             Андреева А.А..

 

 

 

 

 

 

                             

 

 

Чебоксары 2011

Содержание:

 

Содержание: 2

Введение 3

Задание 3

1. Математическое описание  задачи 4

1.1 Определение и свойства  дискретного преобразования Фурье 4

1.2 Математическое описание  БПФ с прореживанием по времени 8

2. Разработка  алгоритмов  и программы для решения практической  задачи 12

2.1 Представление данных 12

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

3. Анализ результатов  моделирования алгоритма БПФ  с прореживанием по времени 14

3.1 Обращение к программе 14

3.2 Входные и выходные  параметры 14

3.3 Примеры работы программы 14

Выводы 17

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

Приложение 19

 

 

Введение

Целью курсовой работы является изучение и освоение методов цифровой обработки сигналов и изображений.

В настоящее  время во многих отраслях науки и  техники, таких как радиолокация, сейсмография, связь, радиоастрономия, медицинская электроника, цифровая обработка сигналов (ЦОС) приобретает все более широкое применение.

Важный момент применения ЦОС - это выбор разумно построенного алгоритма среди огромного разнообразия алгоритмов дискретного преобразования: быстрых алгоритмов свертки или быстрого преобразования Фурье. Общий подход к построению быстрых преобразований основан на факторизации матриц преобразования.

В наше время существуют три основные области применения дискретных спектральных преобразований:

●  использование преобразований для выделения характерных признаков сигнала при спектральном анализе;

            ●  кодирование (сжатие изображений);

●  косвенное вычисление линейной свертки, позволяющее проводить ЦОС более эффективно.

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

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

Задание

Реализовать программу для выполнения спектрального анализа с помощью  алгоритма дискретного быстрого преобразования Фурье с прореживанием  по времени.

 

1. Математическое описание задачи

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

Сигнал - это физический процесс, отображающий некоторую информацию. Сигнал может  быть математически описан некоторой функцией определенного типа.

Например:

1. одномерные сигналы описываются вещественной или комплексной функцией x_a(t), которая определена на интервале вещественной оси t'<=t<=t";

2. аналоговые сигналы - непрерывной или кусочно-непрерывной функцией x_a(t);

3. дискретные сигналы - решетчатыми функциями, или последовательностями х(nТ),

где T=const - интервал дискретизации, n =0,1,2,3,...;

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

Определение 1. Прямое преобразование Фурье - это спектр X_a(jω) аналогового сигнала x_a(t), т.е.

                                                                               (1.1)

Согласно обратному преобразованию Фурье:

                                                                       (1.2)

Определение 2. Дискретное преобразование Фурье - это пара взаимнооднозначных преобразований:

                                                           (1.3)

 

                                                        (1.4)

где Ω=2π/(NT) – основная частота преобразования.

Т.к. e^{j2π N} =W_n - поворачивающий множитель, то отсюда ДПФ и ОДПФ:

                                           (1.5)

                                         (1.6)

где x(n) - периодическая последовательность с периодом N (период – N отсчетов), т.е. x(n)=x(n+mN), m - целое число.

Определение 3. Величина называется поворачивающим множителем.

Основным свойством этих преобразований является тот факт, что из последовательности {x} получается (при прямом преобразовании) последовательность {X}, а если потом к {X} применить обратное преобразование, то снова получится исходная последовательность {x}.

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

                                      Рис.1

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

                                                

X_k в общем случае величина комплексная. Разложим ее на действительную и мнимую составляющую: X_k = Re_k + i Im_k, разложим экспоненту по формуле Эйлера на синус и косинус действительного аргумента, внесем 1/N под знак суммы и перегруппируем элемент на две суммы:

Так как все x_n – действительные числа, вторая сумма равна нулю. Отсюда:

                                                   (1.7)

Поскольку при дискретизации было взято t_n=nT/N, то можно выполнить замену n=t_nN/T. В результате формула принимает следующий вид:

                                               (1.8)

Рассмотрим теперь формулу колебаний:

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

                                                    (1.9)

Если в этой формуле выделить компоненты, не зависящие от t и заменить  их: и , то формула запишется следующим образом:

                                                                           (1.10)

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

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

                                                         (1.11)

Функция называется k-гармоникой.

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

Дискретное  преобразование Фурье имеет следующие  основные свойства:

1. Линейность

Если X(k) и Y(k) есть ДПФ последовательностей x(nT) и y(nT) соответственно, то ДПФ последовательности ax(nT)+by(nT), где a и b – произвольные константы, равно aX(k)+bY(k).

2. Сдвиг

Пусть X(k) – ДПФ последовательности x(nT), а последовательность y(nT) получается из последовательности x(nT) путем сдвига (в случае конечной последовательности – кругового сдвига) на n₀ отсчетов: y(nT)=x(nT+n₀T). Тогда ДПФ последовательности y(nT) равно .

Аналогичный результат справедлив для сдвига коэффициентов ДПФ. Если X(k) и Y(k) есть ДПФ последовательностей x(nT) и y(nT) соответственно и Y(k)=X(k-k₀), то .

 

                                                         Рис.2

При анализе  последовательностей конечной длины  необходимо учитывать специфический  характер временного сдвига последовательности. Так, на рис.2 а изображена конечная последовательность х (n) длиной в N отсчетов. Там же крестиками изображены отсчеты эквивалентной периодической последовательности х_p(n), имеющей то же ДПФ, что и х(n). Чтобы найти ДПФ сдвинутой последовательности х(n – n₀), причем n₀ < N, следует рассмотреть сдвинутую периодическую последовательность Хр(n — n0) и в качестве эквивалентной сдвинутой конечной последовательности (имеющей ДПФ ) принять отрезок последовательности х_p(n – n₀) в интервале 0 ≤ n ≤ N — 1. Таким образом, с точки зрения ДПФ последовательность х(n – n₀) получается путем кругового сдвига элементов последовательности х(n) на n₀ отсчетов.

         3.Свойства симметрии

Если последовательность x(nT) является действительной, то ее ДПФ удовлетворяет следующим условиям симметрии:

1.2 Математическое описание БПФ с прореживанием по времени

Пусть задана последовательность x(n) , n = 0, 1, 2, … , N - 1.

                                                                  N = 2 ^t.                                                    (1.12)

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

                                          {x(2*n)} = {x(0),  x(2), ... , x(N–2)} и

                                 {x(2*n+1)} = {x(1),  x(3), ... , x(N–1)}.

Выражение для дискретного преобразования Фурье:

Т.к. x(n) имела длину N,  X(k) имеет период N.

                                                                                                      _(1.13)

При  можно записать

                                 ;                  (1.14)

                                                                              (1.15)

Обозначим

                                ,                                     (1.16)

                              ,                                     (1.17)

тогда

                                                             _(1.18)

                             ,                (1.19)

т.е. N-точечное ДПФ вычисляется через -точечное.

Пример.     N=8.

                                                         Рис.3

Операция  “бабочки” для ДПФ с прореживанием  по времени:

         Рис.4

 

A = a + W*b

B = a – W*b.

 

4-точечное  преобразование Фурье можно вычислить  через два 2-точечных:

                                                                       Рис.5

В результате многократного прореживания входные отсчеты располагаются  в двоично-инверсном порядке. Поэтому  двоичное реверсирование является первым шагом для ДПФ с прореживанием  по времени:                                                         Таблица 1.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