9.7. Обратное дискретное преобразование Фурье

По аналогии с периодическими сигналами можно представить заданную периодическую последовательность отсчетов комплексным рядом Фурье. Заменив в (9.15) t = k∆t, ω_И = 2π/(N∆t) и, учитывая, что суммируется конечное число членов ряда, запишем

(9.18)

Данное соотношение отражает алгоритм обратного преобразования Фурье (ОДПФ) . Формулы (9.17) и (9.18) являются аналогами прямого (1.17) и обратного (1.18) преобразований Фурье для непрерывных сигналов.

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

ПРИМЕР. 9.5. Вычислить обратное дискретное преобразование Фурье последовательности четырех отсчетов сигнала С₀ = 1, С₁ = 0, С₂ = 0; С₃ = 0.

Р е ш е н и е . Используя основную формулу (9.18) для ОДПФ, вычислим значения отчетов

.

Отсюда имеем: u₀ = 1; u₁ =1; u₂ = 1; u₃ = 1.

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

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

Пусть требуется вычислить ДПФ входной последовательности (массива отcчетов) дискретного сигнала {u(kΔt)} = {u_k}, имеющей четное число отсчетов (рис. 9.11, а), причем N = 2 ^r, где r –целое число (если это условие не выполняется, то последовательность искусственно дополняют нулями до требуемого значения N). Представим входную последовательность в виде двух последовательностей с четными и нечетными номерами и половинным числом членов в каждой (рис. 9.11, а, б, в)

··

u_чт = u_2k; u_нч = u_{2k + 1}; k = 0, 1, 2, ..., N/2 – 1.

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

Коэффициенты С_n результирующего ДПФ входной последовательности можно выразить через параметры С_nЧТ и С_nНЧ двух вновь введенных подпоследовательностей. Из последней формулы нетрудно заметить, что в диапазоне номеров отсчетов от 0 до N/2-1 ДПФ входной последовательности определяется соотношением

n = 0, 1, 2 ..., N/2-1. (9.19)

Так как ДПФ четной и нечетной последовательностей являются периодическими, имеющими период следования N/2, то:

Входящий в формулу (9.19) экспоненциальный множитель при n ≥ N/2 можно записать в виде

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

, n = 0, 1, 2, ....N/2-1. (9.20) .

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

Cоотношения (9.19) и (9.20) представляют собой алгоритмы БПФ. Следует отметить, что экспоненциальные фазовые множители в этих алгоритмах учитывают влияние сдвига нечетной подпоследовательности относительно четной.

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