Введение

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

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

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

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

Рассмотрим формулу ДПФ.

Пусть последовательность отчетов {x(k)} является периодической с периодом N:

для любого k.

Такая последовательность полностью описывается конечным набором чисел, в качестве которого можно взять произвольный фрагмент длиной N, например {x(k), k=0,1, …, N-1}. Поставленный в соответствии этой последовательности сигнал из смещенных по времени дельта-функций:

Также, разумеется, будет периодическим с минимальным периодом NT.

Так как сигнал s(t) является дискретным, его спектр должен быть периодическим с периодом 2П/Т. Так как этот сигнал является также и периодическим, его спектр должен быть дискретным с расстоянием между гармониками, равным 2П/(NT).

Периодический дискретный сигнал имеет периодический дискретный спектр, который также описывается конечным набором из N чисел (один период спектра содержит =N гармоник).

Процедура вычисления спектра периодического дискретного сигнала. Так как сигнал периодический, будем раскладывать его в ряд Фурье. Коэффициенты этого ряда, согласно общей формуле, равны

(3)

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

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

(4)

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

(5)

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

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

2. БПФ с прореживание по времени

Рассмотрим идею БПФ с прореживанием по времени на примере деления набора отсчетов пополам.

Итак, пусть N-четное число. Выделим в формуле (4) два слагаемых, соответствующих элементам исходной последовательности с четными и нечетными номерами:

(6)

Две суммы в (4) представляют собой ДПФ последовательностей {y(m)} (отсчеты с четными номерами) и {z(m)} (отсчеты с нечетными номерами). Каждой из этих ДПФ имеет размерность N/2. Таким образом,

, (7)

где и -ДПФ, соответственно, последовательностей отсчетов с четными и нечетными номерами:

(8)

(9)

Так как ДПФ размерности N/2 дает лишь N/2 спектральных коэффициентов, непосредственно использовать формулу (7) можно только при 0<=n<N/2. Для остальных n (N/2<=n<N) следует воспользоваться периодичностью спектра дискретного сигнала (и, соответственно, периодичностью результатов ДПФ):

(10)

(11)

С учетом этого при n>=N/2 формула(7) представляется в виде

(12)

Процесс вычисления 8 точечного ДПФ путем разбиения его на два 4 - точечных ДПФ иллюстрируется на рисунке 1.

Размещено на http://www.allbest.ru/

Рисунок 1 - Вычисление 8-точечного ДПФ с помощью двух 4-точечных ДПФ

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

(13)

Блоки, выполняющие на рис 1 объединение результатов двух ДПФ. Каждый такой блок имеет два входных и два выходных сигнала. Один из входных сигналов умножается на комплексную экспоненту , после чего суммируется со вторым входным сигналом и вычитается от него, формируя таким образом два выходных сигнала. Это соответствует реализации формул (7) и (12). Данная операция получила название «бабочки». Расшифровка структуры представлена на рисунке 2.

Размещено на http://www.allbest.ru/

Рисунок 2 - Условное обозначение «бабочки» БПФ с прореживанием по времени

Оценим количество операций, необходимое для вычисления ДПФ указанным способом. Каждое из двух ДПФ половинной размерности требует операций. Кроме того, при вычислений окончательных результатов каждый спектральный коэффициент умножается на экспоненциальный комплексный множитель. Это добавляет еще N/2 операций. Итого получается

(14)

что почти в двое меньше, чем при вычислении ДПФ прямым способом.

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

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

3. БПФ с прореживанием по частоте

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

Разделим исходную последовательность {x(k)} на две следующие друг за другом половины:

(15)

Из второй суммы можно выделить множитель . Этот множитель равен 1 или - 1 в зависимости от четности номера вычисляемого спектрального отчета n, поэтому дальше рассматриваем четные и нечетные n по отдельности. После выделения множителя ±1 комплексные экспоненты в обеих суммах становятся одинаковыми, поэтому выносим их за скопки, объединяя две суммы:

(16)

. (17)

Фигурирующие здесь суммы представляют собой ДПФ суммы и разности половин исходной последовательности, при этом разность перед вычислением ДПФ умножается на комплексные экспоненты exp (-j2рm/N). Каждое из двух используемых здесь ДПФ имеет размерность N/2.

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

1. Из исходной последовательности {x(k)} длинной N получают две последовательности {y(m)} и {z(m)} длиной N/2 согласно следующим формулам:

, (18)

. (19)

2. ДПФ последовательности {y(m)} дает спектральные отсчеты счетными номерами, ДПФ последовательности {z(m)} - с нечетными:

, (20)

(21)

Процесс вычисления 8-точечного ДПФ путем разбиения его на два 4-точечных ДПФ с прореживанием по частоте показан на рис. 3.

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

Размещено на http://www.allbest.ru/

Рисунок 3 - Вычисление 8-точечного ДПФ с помощью двух 4-точечных ДПФ путем прореживания по частоте

Размещено на http://www.allbest.ru/

Рисунок 4 - Условное обозначение «бабочки» БПФ с прореживанием по частоте

спектральный фурье преобразование алгоритм

4. Основание алгоритма БПФ

В названиях алгоритма БПФ можно встретить слово «RADIX» («основание» - в математическом смысле). Следующее после него число обозначает число фрагментов, на которое разбивается сигнал на каждом этапе прореживания (а так же минимальный размер «кусочков» входного вектора, который достигается в результате его последовательных разбиений).

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

, (22)

.

В алгоритмах «RADIX-4» количество отсчетов сигнала должно быть равно степени 4, при каждом прореживании сигнала делится на четыре фрагмента, а последней стадией деления являются четырехэлементные последовательности. При вычислении их ДПФ умножение производиться только на ±j, а такое умножение сводится к взаимной перестановке вещественной и мнимой частей комплексного числа с изменением знака у одной из них:

(23)

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

5. Выводы по алгоритму БПФ

1. БПФ не является приближенным алгоритмом; при отсутствии вычислительных погрешностей он даст в точности тот же результат, что и исходная форма ДПФ (4). Ускорение достигается исключительно за счет оптимальной организации вычислений.

2. Применение БПФ имеет смысл, если число элементов в анализируемой последовательности является степенью числа 2. Как уже отмечалось, некоторое ускорение вычислений возможно и при разложении N на другие множители, однако это ускорение не столь велико, как при N=.

3. Алгоритм БПФ предназначен для одновременного расчета всех спектральных отсчетов . Если же необходимо получить эти отсчеты лишь для некоторых n, может оказаться предпочтительнее прямая формула ДПФ.

6. Недостатки БПФ

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

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

1. Голд Б., Рэйдер Ч. Цифровая обработка сигналов / Пер. с англ. под ред. А.М. Трахтмана. - М: Советское радио, 1973. - 368 с.

2. Куприянов М.С., Матюшкин Б.Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. - СПб.: Политехника, 1998. - 592 с.

3. Лебедев Е.К. Быстрые алгоритмы цифровой обработки сигналов. - Красноярск, Красноярский университет, 1989. - 192 с.

4. Сергиенко А.Б. Цифровая обработка сигналов 2-е издание. Учебник для вузов. - СПб.: Питер, 2007. - 751 с.

Размещено на Allbest.ru