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

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

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

(12.1)

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

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

(12.2)

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

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

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

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

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

u_nT (t + T _и) = u_T (t), n = 0 ± 1, ±2,....

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

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

(12.3)

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

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

(12.4)

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

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

(12.5)

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

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

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

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

3. Число различных коэффициентов С_n равно числу отсчетов N за длительность сигнала T _и; при n = N коэффициент С_n = С ₀.

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

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

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

(12.6)

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

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

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

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

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

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

а – входная; б – с четными номерами; в – с нечетными номерами

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

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

(12.7)

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

C_n = С_{n чт} + exp(- j 2 π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:

C_{N /2+ n} = С_{n чт} - exp(- j 2 πn / N) ∙ С_{n нч}, n = N /2, N /2 + 1,,..., N - 1. (12.9)

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

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

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

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

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

Дата добавления: 2015-10-28