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

Дискретные сигналы (как и аналоговые) могут быть представлены во временной и частотной областях. В настоящее время обработка дискретных сигналов чаще всего проводится в частотной области, так как при этом значительно сокращается время и сложность аппаратуры.

Подвергнем дискретной обработке аналоговый импульсный сигнал u(t) длительностью Tи, имеющий спектральную плотность S(ω) (рис. 12.1, а, б). Воспользуемся теоретическим представлением дискретизации сигнала периодической последовательностью дельта-функций

(12.1)

где N = Tи/∆t – требуемое число отсчетов, отвечающих теореме Котельникова.

Следовательно выражение для дискретного сигнала (рис. 12.1, е) с учетом пределов суммирования (от 0 до N – 1) имеет вид

(12.2)

где uk = u(k∆t).

На основании формулы (12.2) можно сделать вывод, что спектр данного дискретного сигнала имеет Алгоритмы дискретного и быстрого преобразований Фурье периодическую структуру с периодом по оси частот ω1 = 2π/∆t (рис. 12.1, г). Мысленно продолжим дискретный сигнал периодически с интервалом Tи (рис. 12.1, д) |Сn|

Рис. 12.1. Графики к выводу ДПФ:

а,б – аналоговый сигнал и его спектр; в,г – дискретный сигнал и его спектр;

д – периодическая последовательность дискретного сигнала; е – ДПФ сигнала

unT(t + Tи) = uT(t), n = 0 ± 1, ±2,... .

По аналогии с представлением периодических непрерывных сигналов

где – комплексная амплитуда n-й гармоники. Дискретную функцию unT(t) можно разложить в комплексный ряд Фурье:

(12.3)

где ωн = 2π/Tи = 2π/(N∙∆t) – частота дискретизации сигнала.

Коэффициенты этого ряда

(12.4)

Для определения коэффициентов проделаем следующее. Подставим формулу (12.2) в (12.4) и заменим параметр Tи = N Алгоритмы дискретного и быстрого преобразований Фурье∙∆t. Введем безразмерную переменную y = t/∆t и запишем

Используя фильтрующее свойство дельта – функции, находим

(12.5)

Это соотношение называется дискретным преобразованием Фурье (ДПФ). Дискретное преобразование Фурье по существу представляет собой алгоритм вычисления гармонических составляющих спектра Сn по заданным дискретным отсчетам uk аналогового сигнала u(t), что значительно сокращает время обработки. Характерный вид модулей коэффициентов Сn показан на рис. 12.1,е.

Следует отметить ряд свойств ДПФ, которые вытекают из определения (12.5).

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

2. Коэффициент С0 представляет собой среднее значение (постоянную составляющую) всех дискретных отсчетов сигнала

3. Число различных коэффициентов Сn равно числу Алгоритмы дискретного и быстрого преобразований Фурье отсчетов N за длительность сигнала Tи; при n = N коэффициент Сn = С0.

Пример. Определить коэффициенты ДПФ дискретизированного прямоугольного импульса единичной амплитуды, заданного четырьмя отсчетами (N = 4).

Решение. Используя основную формулу (12.5), вычислим пять первых коэффициентов ДПФ: С0 = 4/4 = 1;

При изучении теории ДПФ возникает очевидный вопрос: можно ли по известным коэффициентам ДПФ вычислить отсчетные значения uk непрерывного сигнала? По аналогии с периодическими сигналами представим заданную периодическую последовательность отсчетов комплексным рядом Фурье, заменив t = k∆t, ωн = 2π/(N×∆t) и, учитывая, что суммируется конечное число членов ряда, запишем



(12.6)

Данное соотношение определяет алгоритм обратного дискретного преобразования Фурье (ОДПФ). Формулы (12.5) и (12.6) являются аналогами прямого и обратного преобразований Фурье для непрерывных Алгоритмы дискретного и быстрого преобразований Фурье сигналов.

Выражение (12.5) показывает, что для определения одного коэффициента ДПФ сигнальной последовательности из N отсчетов, необходимо выполнить около N операций умножения на комплексное число и столько же сложений, а для нахождения всех коэффициентов объем вычислений составит N2. В частности, при N = 210 = 1024 надо осуществить более миллиона (10242) умножений и сложений. Если длины обрабатываемых массивов превышают тысячу единиц, то дискретная спектральная обработка сигналов в реальном масштабе времени требует высокопроизводительных вычислительных комплексов.

Многократно сократить число операций позволяет быстрое преобразование Фурье (БПФ), обеспечивающее вычисление коэффициентов ДПФ за меньшее число операций. В основу БПФ положен принцип разбиения заданной последовательности отсчетов дискретного сигнала на несколько промежуточных последовательностей Алгоритмы дискретного и быстрого преобразований Фурье. Для этого число отсчетов N разделяется на множители (например, N = 8 = 2 × 2 × 2, N = 60 = 3 × 4 × 5). Затем определяются спектры этих промежуточных последовательностей и через них находится спектр всего сигнала.

В зависимости от состава, числа и порядка следования указанных множеств можно создать различные алгоритмы БПФ. В цифровой технике удобно обрабатывать сигнальные последовательности со значениями N, являющимся степенью числа два (4, 8, 16 и так далее). Это позволяет многократно делить входную последовательность отсчетов на подпоследовательности.

Пусть требуется вычислить ДПФ дискретного сигнала {u(k∆t)} = {uk}, имеющего четное число отсчетов (рис. 12.2, а), причем N = 2r; r – целое число.

Рис. 12.2. Разбиение последовательности uk на две подпоследовательности:

а – входная; б Алгоритмы дискретного и быстрого преобразований Фурье – с четными номерами; в – с нечетными номерами

Представим входную последовательность в виде двух подпоследовательностей с четными и нечетными номерами и половинным числом членов в каждой (рис. 12.2, б,в): uчт = u2k; uнч = u2k+1; k = 0, 1, 2,..., N/2 – 1.

Коэффициенты ДПФ для последовательностей с четными и нечетными номерами запишем отдельно:

(12.7)

Коэффициенты Сn результирующего ДПФ входной последовательности можно выразить через параметры Сnчт и Сnнч двух вновь введенных подпоследовательностей. Анализ (12.7) показывает, что в диапазоне номеров отсчетов от 0 до N/2 - 1, ДПФ входной последовательности определяется соотношением:

Cn = Сnчт + exp(-j2πn/N) ∙ Сnнч, n = 0, 12 ,..., N/2 – 1. (12.8)

Так как ДПФ четной и нечетной последовательностей являются периодическими, с периодом N/2, то Алгоритмы дискретного и быстрого преобразований Фурье Сnчт = С(n+N/2)чт; Сnнч = С(n+N/2)нч.

Запишем экспоненциальный множитель в формуле (12.8) при n ≥ N/2, т.е. для ДПФ С(N/2+n)нч, в виде:

С учетом двух последних выражений находим коэффициенты ДПФ входной последовательности для отсчетов с номерами от N/2 до N - 1:

CN/2+n = Сnчт - exp(-j2πn/N) ∙ Сnнч, n = N/2, N/2 + 1, ,..., N - 1. (12.9)

Соотношения (12.8) и (12.9) полностью определяют алгоритмы вычисления коэффициентов с помощью БПФ. Отметим, что экспоненциальные фазовые множители exp(-j2πn/N) в этих алгоритмах учитывают влияние сдвига нечетной подпоследовательности относительно четной.

Чтобы еще уменьшить число вычислений, четную и нечетную подпоследовательности также разбивают каждую на Алгоритмы дискретного и быстрого преобразований Фурье две промежуточные части. Разбиение продолжают вплоть до получения простейших двухэлементных последовательностей. Определив ДПФ данных простейших пар отсчетов, можно вычислить ДПФ четырехэлементных, восьмиэлементных и так далее подпоследовательностей. При объединении ДПФ четной и нечетной подпоследовательностей используют алгоритмы (12.8) и (12.9), подставляя в них соответствующие значения номеров N и n.

Нетрудно заметить, что вычисления по формулам (12.7) не потребуют операций умножения, в (12.7) имеются только сложение и вычитание комплексных чисел. Учитываться же должны лишь операции умножения в алгоритмах (12.8) и (12.9) для различных n при разбиениях массива отчетов на мелкие подпоследовательности. Число этих операций при первом разбиении составляло N/2. Такое же число N/2 операций требуется выполнить Алгоритмы дискретного и быстрого преобразований Фурье при каждом следующем разбиении. Таким образом, вдвое увеличивается число подпоследовательностей и вдвое сокращается наибольшее число n в формулах вычисления спектральной плотности дискретного сигнала.

Вычисление коэффициентов ДПФ последовательности из N отсчетов по алгоритмам БПФ требует примерно N∙log2N операций умножения. Алгоритмы БПФ сокращают число операций по сравнению с алгоритмами ДПФ в N:log2N раз. Например, при количестве отсчетов N = 210, имеем log2N = 10 и сокращение числа операций составляет N : log2N ≈ 100. При очень больших массивах отсчетов входного сигнала выигрыш в скорости обработки может достигать нескольких тысяч.

Таким образом, в алгоритмах БПФ выполняются операции сложения и вычитания с умножением одного из компонентов Алгоритмы дискретного и быстрого преобразований Фурье на экспоненциальный множитель exp(-j2πn/N). Эту базовую для БПФ операцию очень удобно представлять сигнальным графом, называемым в цифровой технике «бабочкой». БПФ по рассмотренному методу называют методом прореживания отсчетов во времени.


documentarwrzrd.html
documentarwshbl.html
documentarwsolt.html
documentarwsvwb.html
documentarwtdgj.html
Документ Алгоритмы дискретного и быстрого преобразований Фурье