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

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

Введение

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

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

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



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

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

Дискретное преобразование Фурье (ДПФ) периодического дискретного сигнала x(n) с периодом N определяется как

(1.1),

где - основная частота преобразования (бин ДПФ).

Выражение (1.1) можно переписать в виде

(1.2),

где

(1.3).

Коэффициент W_N называется поворачивающим множителем. Легко показать, что является периодической функцией с периодом N

(1.4).

Поэтому ДПФ X(k) также является периодической функцией по аргументу k с периодом N.

Дискретное преобразование Фурье может быть использовано и для представления сигнала x(n) конечной длины N, определенного при n=0,1,…,N-1 и равного нулю вне интервала [0,N-1]. Действительно, такой сигнал можно рассматривать как один период соответствующего периодического сигнала и использовать преобразования (12.2). Следует только считать, что вне интервала [0,N-1] X(k) и x(n) равны нулю.

Если сравнить ДПФ конечного дискретного сигнала со спектром этого же сигнала, определяемым выражением

(1.5),

то очевидно, что ДПФ представляет собой N отсчетов спектра, взятых на периоде с интервалом дискретизации по частоте, равным .

В случае, когда x(n) является комплексным, при прямом вычислении N-точечного ДПФ нужно выполнить для каждого значения k (N-1) умножений и (N-1) сложений комплексных чисел или 4(N-1) умножений и 2(N-1) сложений действительных чисел. Для всех N значений k=0,1,…,N-1 требуется (N-1)² умножений и N(N-1) сложений комплексных чисел. Для больших значений N (порядка нескольких сотен или тысяч) прямое вычисление ДПФ по выражению (12.2) требует выполнения весьма большого числа арифметических операций умножения и сложения, что затрудняет реализацию вычислений в реальном масштабе времени.

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

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

Так, если исходный N-отсчетный сигнал разбить на два N/2-отсчетных сигнала, то для вычисления ДПФ каждого из них потребуется около (N/2)² комплексных умножений. Тогда для вычисления искомого N-отсчетного ДПФ потребуется порядка 2(N/2)²=N²/2 комплексных умножений , т.е. вдвое меньше по сравнению с прямым вычислением. Операцию разбиения можно повторить, вычисляя вместо (N/2)-отсчетного ДПФ два (N/4)-отсчетных ДПФ и сокращая тем самым объем вычислений еще в два раза. Выигрыш в два раза является приблизительным, поскольку не учитывается, каким образом из ДПФ меньшего размера образуется искомое N-отсчетное ДПФ.

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

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

Первый алгоритм называется алгоритмом БПФ с прореживанием по времени.

Пусть задан N-отсчетный дискретный сигнал x(n). Примем, что N равно степени двойки. Если это не так, то всегда можно легко дополнить заданный сигнал нулевыми отсчетами до количества отсчетов, равного ближайшей степени двойки.

Разобьём исходный сигнал x(n) на два N/2-отсчетных сигнала x₁(n) и x₂(n), составленных соответственно из четных и нечетных отсчетов исходного сигнала x(n)

(1.6).

N-точечное ДПФ сигнала x(n) можно записать как

(1.7).

С учетом того, что

(1.8)

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

(1.9)

или

(1.10),

где X₁(k) и X₂(k) - N/2-отсчетные ДПФ сигналов x₁(n) и x₂(n) соответственно.

Таким образом N-точечное ДПФ X(k) может быть разложено на два N/2-точечных ДПФ, результаты которых объединяются согласно (1.10).

Если бы N/2-точечные ДПФ вычислялись прямым способом, то для вычисления N-точечного ДПФ потребовалось бы (N²/2+N) комплексных умножений. При больших N (когда N²/2>>N) это позволяет сократить время вычислений на 50%.

Поскольку X(k) определено при , а X₁(k) и X₂(k) определены при , необходимо доопределить формулу (12.10) для . Учитывая, что X₁(k) и X₂(k) - периодические функции с периодомN/2, можно записать

(1.11),

поскольку .

Поэтому окончательно для N-точечного ДПФ можно записать

(1.12).

На рис.11.2 представлена последовательность операций при выполнении восьмиточечного ДПФ с использованием двух четырехточечных ДПФ.

Сначала входной сигнал x(n) разбивается на два сигнала x₁(n) и x₂(n), составленных соответственно из четных и нечетных отсчетов x(n). После этого рассчитывается ДПФ X₁(k) и X₂(k). Затем в соответствии с (1.12) получается X(k).

Рассмотренная схема вычислений может быть использована и для расчета N/2-точечных ДПФ. В соответствии с этим каждый из сигналов x₁(n) и x₂(n) разбиваются на последовательности, состоящие из четных и нечетных отсчетов родительских сигналов. Аналогично N/2-точечные ДПФ могут быть записаны как комбинации двух N/4-точечных ДПФ

(1.13).

С учетом того, что можно записать

(1.14).

На рис.11.2 представлена последовательность операций при выполнении восьмиточечного ДПФ с использованием двух четырехточечных ДПФ и четырех двухточечных ДПФ.

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

(1.15).



Поскольку , то окончательно получим

(1.16).

На рис.11.3 представлена порядок операций при последовательном вычислении восьмиточечного ДПФ в соответствии с описанным алгоритмом. Анализ рис.11.3 показывает, что на каждом этапе БПФ необходимо выполнить N/2 комплексных умножений. Поскольку общее количество этапов равно , то число комплексных умножений, необходимое для нахождения N-точечного ДПФ, приблизительно равно .

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

Процедура объединения. Граф «Бабочка»

Базовая операция алгоритма с прореживанием по времени (так называемая «бабочка») состоит в том, что два входных числа A и B объединяются для получения двух выходных чисел X и Y по правилу

(1.17).

На рис.11.4 изображен направленный граф базовой операции.

Каждый из этапов ДПФ содержит N/2 базовых операций. В случае когда - нетривиальный множитель, для каждой базовой операции необходимо выполнить только одно умножение, поскольку величину можно вычислить и запомнить. Таким образом, структура базовых операций такова, что для выполнения БПФ N-отсчетного сигнала, отсчеты которого размещены в памяти, достаточно иметь лишь одну дополнительную ячейку памяти. Результаты всех промежуточных этапов БПФ можно размещать в те же ячейки памяти, где находились исходные данные. Алгоритм БПФ, в котором для размещения входной и выходной последовательности используется один и тот же массив памяти, называется алгоритмом с замещением.

Алгоритм с замещением

При реализации алгоритма необходима перестановка отсчетов входного сигнала, чтобы выходная последовательность имела естественный порядок расположения отсчетов, т.е. k=0,1,…,N-1. В приведенном примере для 8-точечного БПФ для этого требовался следующий порядок размещения отсчетов входного сигнала: x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7). Закономерность перестановки заключается в том, что отсчеты входного сигнала должны быть размещены в памяти в двоично-инверсном порядке. Это означает, что требуемый номер ячейки памяти для размещения очередного отсчета входного сигнала определяется обратной перестановкой двоичных разрядов в двоичном представлении номера отсчета. Для случая N=8 соответствие номеров отсчетов входного сигнала и их номеров ячеек памяти представлено в таблице 1.1.

Таблица 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

На рис.11.5 показан алгоритм определения двоично-инверсного номера, предложенный Рейдером. Начиная с первого числа с прямым номером 0, этот алгоритм позволяет формировать последовательно все остальные двоично-инверсные номера.

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

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

Второй способ заключается в непосредственном вычислении коэффициентов как

(1.18)

с использованием процедур вычисления синуса и косинуса. Этот способ связан с большими временными затратами.

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

(1.19)

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



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

Рассмотрим еще один алгоритм БПФ, который называется алгоритм с прореживанием по частоте. Пусть снова имеем входной дискретный сигнал x(n), состоящий из N отсчетов, причем N равно степени двойки. Разобьём это сигнал на два N/2-отсчетных сигнала x₁(n) и x₂(n) так, что x₁(n) состоит из первых N/2 отсчетов x(n), а x₂(n) - из остальных N/2 отсчетов x(n), т.е.

(1.20).

При таком разбиении N-точечное ДПФ сигнала x(n) можно записать как

(1.21).

Поскольку , то получим

(1.22).

Запишем выражения отдельно для четных и нечетных отсчетов ДПФ.



(1.23).

Из выражения (1.23) видно, что N-точечное ДПФ можно получить как сумму двух N/2-точечных ДПФ N/2-отсчетных сигналов: сигнала и сигнала .

Аналогично предыдущему алгоритму, описанную процедуру можно применить повторно и представить каждое из N/2-точечных ДПФ в виде комбинации двух N/4-точечных ДПФ и т.д. На рис.11.6 представлен пример 8-точечного БПФ, реализованного по этому алгоритму.

Базовая операция этого алгоритма описывается выражением

(1.24).

Сравнение двух описанных алгоритмов позволяет выявить два очевидных различия между ними. Во-первых, при прореживании по времени порядок следования входных отсчетов двоично-инверсный, а выходных - прямой. При прореживании по частоте - наоборот. Однако это отличие кажущееся, поскольку в обоих алгоритмах порядок следования входных отсчетов можно сделать прямым. Тогда порядок следования выходных отсчетов будет двоично-инверсным. И наоборот.

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

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

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

Обратное ДПФ N-точечной последовательности X(k), k=0,1,…,N-1 определяется как

(1.25).

Взяв выражение, комплексно-сопряженное с (1.25) и умножив его на N получим

(1.26).

Однако, правая часть (1.26) представляет собой прямое ДПФ последовательности X^*(k) и может быть вычислена с использованием одного из вышеописанных алгоритмов БПФ. Искомую последовательность x(n) можно получить, взяв комплексно-сопряженное с (12.26) выражение и разделив его на N

(1.27).

Таким образом, алгоритмы БПФ обеспечивают вычисление и прямого и обратного ДПФ.

Алгоритмы БПФ могут быть использованы для вычисления реакции цифрового фильтра.

Если на вход фильтра N-го порядка с импульсной характеристикой h(n) подан входной сигнал x(n), то реакция фильтра может быть вычислена по правилу свертки

(1.28).

Применение алгоритмов БПФ позволяет выполнить эффективное вычисление выходного сигнала y(n) цифрового фильтра. С этой целью следует определить ДПФ H(k) и X(k) в N+M-1 точках для последовательностей h(n) и x(n), затем определить ДПФ Y(k)=X(k)H(k) выходного сигнала y(n). Вычисление y(n) по правилу обратного ДПФ выполняется также с помощью алгоритмов БПФ. Однако, если длина M последовательности x(n) велика, то реализация такого алгоритма вычисления y(n) связана со значительной временной задержкой, необходимой для накопления всех M выборок x(n). С целью уменьшения этой задержки можно входной сигнал x(n) разбить на отрезки x_i(n) каждый длиной L и обрабатывать каждый из них независимо от других. Представим

(1.29).

Тогда можно (12.28) записать в виде

(1.30),

где частная свертка y_i(n) определяется как

(1.31).

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

Применение в радиофизике

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

* количество точек для БПФ должно быть пропорционально, а для большинства случаев равно 2N, где N - целое число;

* разрешение по частоте F, получаемое при спектральном анализе с помощью БПФ, вычисляется по формуле (1): F = Fs/M, где М - количество временных отсчетов сигнала, используемых для БПФ, Fs - частота дискретизации ЦЗО (цифровых запоминающих осциллографов). Частота дискретизации должна удовлетворять условиям теоремы Котельникова, то есть быть как минимум в 2 раза больше максимально необходимого для спектрального анализа частотного компонента входного сигнала.

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

Рис. 1.7 Схема измерений для определения параметров БПФ ЦЗО



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

Вид функции окна определяет получаемые характеристики эквивалентного фильтра: ширину полосы пропускания, неравномерность амплитуды в полосе пропускания и уровень подавления помех относительно полезного сигнала. Поскольку идеальных фильтров не бывает, в БПФ используются различные виды окон. Рассмотрим две основные функции окна: прямоугольного (не вносит никаких изменений в сигнал) и плоского окна. Прямоугольное окно обеспечивает самую узкую полосу пропускания, равную разрешению по частоте (1), но характеризуется уровнем подавления помех относительно несущей около 13 дБ и может привести к ошибке в измерении амплитуды сигнала из-за применения окна до 4 дБ. Плоское окно имеет следующие характеристики: полоса пропускания ±4B?F (таким образом, для получения такого же эффективного разрешения по частоте, как у прямоугольного окна, для БПФ требуется в 8 раз больше точек), уровень подавления помех относительно несущей более 70 дБ и погрешность измерения амплитуды из-за применения окна не более 0,1 дБ. Соответственно, первое окно можно применять для частотных измерений, а второе - для амплитудных.

Динамический диапазон БПФ ЦЗО, кроме применяемых функций окна, ограничен разрешением аналогово-цифрового преобразователя (АЦП) и вносимыми им искажениями, внутренними шумами прибора, а также неравномерностью амплитудо-частотной характеристики осциллографа. Обычно динамический диапазон для БПФ ЦЗО с 8-разрядными АЦП составляет не менее 50 дБ и может быть увеличен еще на 20 дБ при помощи усреднения сигнала во временной области.

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



Вывод

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

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

1. Простота программной реализации алгоритмов и в тоже время высокая эффективность.

2. Выигрыши получаемые альтернативными алгоритмами БПФ незначительные по сравнению с алгоритмами по основанию два и нивелируются экспоненциально растущими вычислительными мощностями процессоров.

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

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

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

...