Практика №4

Практика №4

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

Как и при анализе аналоговых сигналов, дискретные сигналы можно представить во временной и частотной областях. В настоящее время обработку дискретных сигналов чаще всего проводят в частотной области, что диктуется значительными сокращениями объема цифровой аппаратуры и времени обработки.
Пусть дискретной обработке подвергается аналоговый импульсный сигнал  длительностью  , имеющий спектральную плотность  (рис. 9.16, а, б). Теоретически можно предположить, что дискретизация сигнала производится периодической последовательностью дельта-функций

,

(9.35)

где  — требуемое число отсчетов, отвечающих теореме Котельникова.
Подставив в (9.32) пределы суммирования от 0 до  , и заменив здесь и далее для упрощения и уменьшения объема формул  , запишем выражение для дискретного сигнала (рис. 9.16, е)

.

(9.36)

На основании формулы (9.36) можно сделать вывод, что спектр данного дискретного сигнала имеет периодическую структуру с периодом по оси частот  (рис. . 9.16, г). Мысленно продолжим дискретный сигнал периодически с интервалом  (рис. . 9.16, д).

Рис. 9.16. Графики к выводу ДПФ:
а,б - аналоговый сигнал и его спектр; в,г - дискретный сигнал и его спектр; д - периодическая последовательность дискретного сигнала; е - ДПФ сигнала
,  .
По аналогии с представлением периодических непрерывных сигналов
, где  - комплексная амплитуда  -й гармоники. Дискретную функцию  можно разложить в комплексный ряд Фурье:

,

(9.37)

где  - частота дискретизации сигнала.
Коэффициенты этого ряда

.

(9.38)

Для определения коэффициентов проделаем следующее. Подставим формулу (9.36) в (9.38) и заменим параметр  . Введем безразмерную переменную  и запишем
.
Используя фильтрующее свойство дельта – функции, находим

.

(9.39)

Это называется дискретным преобразованием Фурье (ДПФ). Дискретное преобразование Фурье по существу представляет собой алгоритм вычисления гармонических составляющих спектра  по заданным дискретным отсчетам  аналогового сигнала  , что значительно сокращает время обработки. Характерный вид модулей коэффициентов  показан на рис. 9.16,е.
Следует отметить ряд свойств ДПФ, которые вытекают из определения (9.39).
1. Дискретное преобразование Фурье обладает свойством линейности: линейной комбинации дискретных сигналов соответствует линейная комбинация их ДПФ.
2. Коэффициент  представляет собой среднее значение (постоянную составляющую) всех дискретных отсчетов сигнала
.
3. Число различных коэффициентов  равно числу отсчетов  за длительность сигнала  ; при  коэффициент  .
Пример 9.2. Определить коэффициенты ДПФ дискретизированного прямоугольного импульса единичной амплитуды, заданного четырьмя отсчетами  .
Решение. Используя основную формулу (9.39), вычислим пять первых коэффициентов ДПФ:  ;
; 
;  .
При изучении теории ДПФ возникает очевидный вопрос: можно ли по известным коэффициентам ДПФ вычислить отсчетные значения  непрерывного сигнала? По аналогии с периодическими сигналами представим заданную периодическую последовательность отсчетов комплексным рядом Фурье. Заменив в (7.25)  ,  и, учитывая, что суммируется конечное число членов ряда, запишем

.

(9.40)

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

Рис.9.17. Разбиение последовательности  на две подпоследовательности: а - входная; б - с четными номерами; в - с нечетными номерами
Многократно сократить число операций позволяет быстрое преобразование Фурье (БПФ), обеспечивающее вычисление коэффициентов ДПФ за меньшее число операций. В основу БПФ положен принцип разбиения заданной последовательности отсчетов дискретного сигнала на несколько промежуточных последовательностей. Для этого число отсчетов N разделяется на множители (например,  ). Затем определяются спектры этих промежуточных последовательностей и через них находится спектр всего сигнала. В зависимости от состава, числа и порядка следования указанных множеств можно создать различные алгоритмы БПФ. В цифровой технике удобно обрабатывать сигнальные последовательности со значениями N, являющимся степенью числа два (4, 8, 16 и так далее). Это позволяет многократно делить входную последовательность отсчетов на подпоследовательности.
Пусть требуется вычислить ДПФ дискретного сигнала  , имеющего четное число отсчетов (рис. 9.17, а), причем  ;  - целое число.
Представим входную последовательность в виде двух подпоследовательностей с четными и нечетными номерами и половинным числом членов в каждой (рис. 9.17, б,в):  ;  ; .
Коэффициенты ДПФ для последовательностей с четными и нечетными номерами запишем отдельно:

.

(9.41)

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

,  .

(9.42)

Так как ДПФ четной и нечетной последовательностей являются периодическими, с периодом  , то  ; .
Запишем экспоненциальный множитель в формуле (9.42) при  , т.е. для ДПФ  , в виде:

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

,  .

(9.43)

Соотношения (9.42) и (9.43) полностью определяют алгоритмы вычисления коэффициентов с помощью БПФ. Отметим, что экспоненциальные фазовые множители  в этих алгоритмах учитывают влияние сдвига нечетной подпоследовательности относительно четной.Чтобы еще уменьшить число вычислений, четную и нечетную подпоследовательности также разбивают каждую на две промежуточные части. Разбиение продолжают вплоть до получения простейших двухэлементных последовательностей. Определив ДПФ данных простейших пар отсчетов, можно вычислить ДПФ четырехэлементных, восьмиэлементных и так далее подпоследовательностей. При объединении ДПФ четной и нечетной подпоследовательностей используют алгоритмы (9.42) и (9.43), подставляя в них соответствующие значения номеров  и  .
Нетрудно заметить, что вычисления по формулам (9.41) не потребуют операций умножения, в (9.41) имеются только сложение и вычитание комплексных чисел. Учитываться же должны лишь операции умножения в алгоритмах (9.42) и (9.43) для различных  при разбиениях массива отчетов на мелкие подпоследовательности. Число этих операций при первом разбиении составляло  . Такое же число  операций требуется выполнить при каждом следующем разбиении. Таким образом, вдвое увеличивается число подпоследовательностей и вдвое сокращается наибольшее число  в формулах (7.30), (7.31).
Вычисление коэффициентов ДПФ последовательности из N отсчетов по алгоритмам БПФ требует примерно  операций умножения. Алгоритмы БПФ сокращают число операций по сравнению с алгоритмами ДПФ в  раз. Например, при количестве отсчетов  , имеем  и сокращение числа операций составляет  . При очень больших массивах отсчетов входного сигнала выигрыш в скорости обработки может достигать нескольких тысяч.
Таким образом, в алгоритмах БПФ выполняются операции сложения и вычитания с умножением одного из компонентов на экспоненциальный множитель  . Эту базовую для БПФ операцию очень удобно представлять сигнальным графом, называемым в цифровой технике «бабочкой».
БПФ по рассмотренному методу (его называют методом прореживания отсчетов во времени) осуществляют, как правило, в следующем порядке. Сначала для получения желательного при обработке сигнала порядка следования отсчетов  , , выполняется двоично-инверсная перестановка элементов исходной последовательности  ,  . Для этого записывают порядковые номера элементов  в двоичном коде и инвертируют порядок следования разрядов. Новый порядок следования элементов  определяется номерами, полученными после инверсии разрядов.
Пример при N=4

u(l)			u(k)
0→	00→	00→	0→
1→	01→	10→	2→
2→	10→	01→	1→
3→	11→	11→	3→

Новый порядок следования элементов:  . После этого поступают так. На первом этапе вычислений определяют двух точечные ДПФ "новой" последовательности  , объединяя попарно элементы этой последовательности. На втором этапе из двух точечных ДПФ получают четырех точечные ДПФ, пользуясь основной базовой операцией данного метода (см. ниже). Затем четырех точечные ДПФ объединяют в восьми точечные и т.д.
Базовые операции  и  показывают, как два входных числа А и В объединяются для получения двух выходных чисел X и Y. Для метода прореживания во времени базовая операция изображается «бабочкой», представленной на рис. 9.18. Надпись  у стрелки, идущей вверх, означает умножение  на величину В.

Рис. 9.18. Операция «бабочка», используемая
при реализации алгоритма БПФ
При вычислении двух точечного ДПФ  и выходные числа X и Y определяются без операции умножения  ,  .
Пример 9.3. Построим граф вычисления БДНФ с прореживанием во времени для N=4 (рис. 9.19).

Рис. 9.19. Граф для вычисления БПФ при N=4
Учитывая, что ,  , получаем согласно приведенному графу




На рис. 9.20 показан граф вычисления БДПФ с прореживанием во времени для N=8.

Рис. 9.20. Граф для вычисления БПФ при N=8