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

Представление сигналов с помощью гармонических функций В качестве примера рассмотрим представление сигнала типа «меандр» с помощью набора гармонических функций:

Представление сигналов с помощью гармонических функций Программа в среде MathLab, реализующая данную функцию:

Представление сигналов с помощью гармонических функций Результат синтеза:

Виды преобразования Фурье Если сигнал является непрерывным во времени и непериодическим – для его анализа в частотной области используется преобразование Фурье (FT). Для непрерывных во времени и периодических сигналов применяется последовательность Фурье (FS). Если сигнал дискретный во времени и непериодический – для его анализа применяется дискретное во времени преобразование Фурье (DTFT). Дискретные во времени и периодические сигналы анализируются с помощью дискретного преобразования Фурье (DFT). Только дискретное преобразование Фурье является физически реализуемым аппаратными средствами.

Прямое преобразование Фурье Прямое дискретное преобразование Фурье позволяет получить для цифрового сигнала x(n), период которого задан N точками, N значений спектральной характеристики, расположенных равномерно в полосе от 0 до f S с шагом 2π/N или f S /N. Математическая запись преобразования Фурье: Сигнал x(n) определен только в диапазоне от 0 до N-1.

Прямое преобразование Фурье Для двух крайних точек в спектре сигнала X(0) и X(N/2) легко определить их значения: и В обобщенном виде формула для прямого ДПФ записывается:

Прямое преобразование Фурье Базовая комплексная функция или коэффициент преобразования Фурье записывается следующим образом:

Прямое преобразование Фурье Если n=N, то значение коэффициента преобразования Фурье будет равно: Если n=N/2, то значение коэффициента преобразования Фурье будет равно: Коэффициенты преобразования Фурье обладают свойством симметрии и периодичности.

Прямое преобразование Фурье Свойство симметрии: Свойство периодичности:

Обратное преобразование Фурье Обратное преобразование Фурье позволяет восстановить сигнал x(n) во временной области по его спектру X(k). Математическая запись обратного преобразования Фурье следующая:

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

Свойства преобразования Фурье Свойство линейности: для двух сигналов во временной области x(n) и y(n), имеющих одинаковую длину n, истинным является где a и b – любые постоянные коэффициенты Любой сложный входной сигнал можно разложить на простые составляющие и определить их спектр. Результирующий спектр определяется как сумма всех простых составляющих.

Свойства преобразования Фурье Свойство комплексной сопряженности: для сигнала во временной области {x(n), 0 < n < N-1}, представленного действительными отсчетами, истинным является X(-k) = X * (k) = X(N-k), 0 < k < N-1 или в другом виде X(M+k) = X * (M-k), 0 < k < M, где X * (k) – комплексно-сопряженное значение X(k); M = N/2, если N – четное число; M = (N-1)/2 – если N – нечетное число. Данное свойство говорит о том, что для определения всех спектральных составляющих сигнала достаточно определить только (M+1) его компонентов

Свойства преобразования Фурье Свойство комплексной сопряженности означает, что действительные и мнимые части числа связаны между собой следующей зависимостью: Re[X(k)] = Re[X(N-k)] и Im[X(k)] = -Im[X(N-k)] где k = 1, 2, …, M-1 Эта же зависимость, представленная в полярной системе координат:

Свойства преобразования Фурье Графически это выглядит следующим образом:

Свойства преобразования Фурье Свойство периодичности: результатом прямого и обратного преобразования Фурье является периодический сигнал с периодом повторения, равным N: X(k) = X(k + N) для всех k, и x(n) = x(n + N) для всех n. Таким образом, сигналы x(n) и X(k) описывают только один период последовательности.

Быстрое преобразование Фурье (БПФ) Применение алгоритма БПФ позволяет существенно снизить количество выполняемых операций при вычислении спектра сигнала. Если для сигнала, состоящего из N отсчетов, вычисление ДПФ требует выполнения N 2 операций умножения, то для этого же сигнала, при использовании БПФ, понадобиться только Nlog 2 N операций. Алгоритм БПФ основан на свойствах симметричности коэффициентов преобразования Фурье (некоторые коэффициенты равны 0 или 1):

Быстрое преобразование Фурье (БПФ) Шаг 1. Прореживание (децимация) входного сигнала. - исходный сигнал, состоящий из N отсчетов, разбивается на две последовательности, состоящие из N/2 отсчетов (четные и нечетные) x 1 (m) = x(2m) и x 2 (m) = x(2m + 1) для m = 0, 1,…, (N/2-1) Спектр исходного сигнала определяется как сумма спектров этих двух последовательностей:

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

Быстрое преобразование Фурье (БПФ) Учитывая свойства периодичности и симметрии можно записать уравнение спектра в несколько ином виде: ={ где X 1 (k)=DFT[x 1 (m)] и X 2 (k)=DFT[x 2 (m)] по N/2 - точкам

Быстрое преобразование Фурье (БПФ) Графическое представление такого разложения для сигнала, содержащего 8 отсчетов, показано на рисунке: для такой структуры нужно выполнить только (N 2 +N)/2 операций умножения.

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

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

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

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

Быстрое преобразование Фурье (БПФ) Пример программы, анализирующей спектр сигналов с помощью БПФ

Быстрое преобразование Фурье (БПФ) Результат работы программы: