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

UDC 621.317

Vydrin D. F.

student

4course, faculty «Avionics, energy and communications» Ufa state aviation technical University

Russia, Ufa

Abzalilova Y. R.

student

4course, faculty «Avionics, energy and communications» Ufa state aviation technical University

Vdovin A. K.

student

4course, faculty «Avionics, energy and communications» Ufa state aviation technical University

FAST FOURIER TRANSFORMATION AT DIGITAL SIGNAL PROCESSING

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

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

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

■Vik) ^ ;;-_{|; л}л,,Ш' .'\ 0 (1)

где X(k) – k -я комплексная амплитуда (составляющая) спектра; x(n) – отсчеты дискретного сигнала (периодического с периодом N или конечной длины N); W ^^k - поворачивающий множитель (или ядро преобразования), равный

2Я

W? = e " ⁷^^nk . (2)

Прямое вычисление ДПФ по формуле (1) для больших N (при обработке звуковых сигналов длина звукового сигнала может достигать 2¹⁰ = 1024) неэффективно, большое количество операций не дает возможным обеспечение реального времени. Действительно, для вычисления N -точечного преобразования требуется произвести ( N -1)² комплексных умножений и N ( N -1) комплексных сложений, т. е. объем вычислений имеет порядок N ² операций сложения и умножения комплексных чисел.

Для уменьшения вычислительных затрат разработаны алгоритмы БПФ, основанные на периодичности ядра преобразования W^k. Идея БПФ состоит в том, чтобы разделить N-точечную последовательность на две, из ДПФ которых можно получить ДПФ исходной последовательности, и продолжать такое деление каждой новой последовательности до тех пор, пока не останутся последовательности, состоящие только из двух элементов. [1]

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

В алгоритме БПФ с прореживанием по времени N-точечная последовательность делится на две N/2-точечных последовательности, одна из которых X1 содержит отсчеты с нечетными номерами, а другая X2 - с четными номерами. Тогда N-точечное ДПФ исходной последовательности преобразуется в два N/2-точечных ДПФ:

_№M) ⁺ ^2^(k );   0 — к — N — 1.

( X i (k) + W^ (k),

Далее аналогичным образом N/2-точечные ДПФ заменяются двумя N/4-точечными каждое, и т.д. Такая сортировка продолжается до тех пор, пока не образуется N/2-последовательностей по два элемента в каждой. В результате N-точечное ДПФ сводится к m = log2N этапам, на каждом из которых требуется вычислить N коэффициентов. Выражения (3) показывают, что на каждом этапе требуется N комплексных сложений и N/2 комплексных умножений. В результате снижается количество требуемых для вычисления N-точечного ДПФ комплексных сложений с N2 3Nlog2N, что является существенной временных ресурсов. [1]

В алгоритмах БПФ

последовательность делится

экономией вычислительных, а потому и с прореживанием по частоте входная пополам на N/2 первых и N/2 последних отсчетов до тех пор, пока не сформируются N/2 двухэлементных последовательностей, что приводит к подобному сокращению вычислительных операций, и рассчитывается по формуле (4).

^1(k)+^2(k);

⁽⁾   ((^(к)-^))^,    - -    '

Благодаря своим преимуществам, алгоритмы БПФ получили большое распространение в современных системах, в которых необходимо работать со спектром, анализировать или преобразовывать его. Его широко используют и в учебных ПО, таких как MATLAB или Arduino [2]. Наличие библиотек упрощают работу с данным алгоритмом и позволяют использовать его в системах без необходимости подробного изучения принципа работы.