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

Как видно, из формул (7.4) и (7.5), чтобы вычислить ДПФ или ОДПФ последовательности из N элементов, требуется выполнить операций с комплексными числами. Если длины обрабатываемых массивов имеют порядок тысячи или более, то использовать эти алгоритмы дискретного спектрального анализа в реальном масштабе времени затруднительно из-за ограниченного быстродействия вычислительных устройств.

Выходом из положения является алгоритм быстрого преобразования Фурье (БПФ) , предложенный в 60-х годах. Существенно сократить число операций удаётся за счёт того, что обработка входного массива сводится к нахождению ДПФ (или ОДПФ) массивов с меньшим числом членов.

Предположим, что число отсчётов , где Р - целое число. Разобьём входную последовательность на две части с чётными и нечётными номерами.

(7.6)

И представим n-й коэффициент ДПФ в виде:

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

n=0,1,2,…,(N/2)-1 (7.7)

Учтём, что последовательности коэффициентов, относящихся к чётной и нечётной частям входного массива, являются периодическими с периодом N/2:

Кроме того, входящий в формулу (7.7) множитель при можно преобразовать так:

Отсюда находим выражение для второй половины множества коэффициентов ДПФ

(7.8)

Формулы (7.7) и (7.8) лежат в основе алгоритма БПФ. Далее вычисления строят по итерационному принципу: последовательности отсчётов с чётными и нечётными номерами вновь разбивают на две части. Процесс продолжают до тех пор, пока не получается последовательность, состоящая из единственного элемента. ДПФ этого элемента совпадает с ним самим.

Число операций, необходимых для вычисления БПФ оценивается как .

Выигрыш в скорости вычислений по сравнению с традиционным ДПФ достигает сотен и даже тысяч при достаточных длинах входных массивов.

Z-преобразование

При анализе и синтезе дискретных и цифровых устройств Z-преобразование играет такую же роль, как интегральные преобразования Фурье по отношению к непрерывным сигналам.

Пусть – числовая последовательность, конечная или бесконечная, содержащая отсчётные значения некоторого сигнала. Поставим ей в однозначное соответствие сумму ряда по отрицательным степеням комплексной переменной Z:

(7.9)

Эта сумма называется Z-преобразованием последовательности . Свойства дискретных последовательностей чисел можно изучать, исследуя их Z-преобразования обычными методами математического анализа.

На основании формулы (7.9) можно непосредственно найти Z-преобразования сигналов с конечным числом отсчётов. Так простейшему дискретному сигналу с единственным отсчётом соответствует Если же, например, , то

Рассмотрим случай, когда в ряде (7.9) число слагаемых бесконечно велико.

Возьмём дискретный сигнал образованный одинаковыми единичными отсчётами и служащий моделью обычной функции включения. Бесконечный ряд является суммой геометрической прогрессии и сходится при любых Z, |Z|>1. Суммируя прогрессию, получаем

Аналогично получается Z-преобразование бесконечного дискретного сигнала , где а-некоторое вещественное число. Здесь

Данное выражение имеет смысл при |Z|>a

Пусть x(z) – функция комплексной переменной Z. Замечательное свойство Z-преобразование состоит в том, что функция x(z) определяет всю бесконечную совокупность отсчётов ( ).

Действительно, умножим обе части ряда (7.9) на множитель :

(7.10)

а затем вычислим интегралы от обеих частей полученного равенства, взяв в качестве контура интегрирования произвольную замкнутую кривую, При этом воспользуемся фундаментальным положением из теоремы Коши:

Интегралы от всех слагаемых правой части обратятся в нуль, за исключением слагаемого с номером m, поэтому:

(7.11)

Данное выражение носит название обратное Z-преобразование.

Важнейшие свойства Z-преобразования:

1. Линейность. Если и - некоторые дискретные сигналы, причём известны соответствующие Z-преобразования x(z) и y(z), то сигналу будет отвечать преобразование при любых постоянных и . Доказательство проводится путём подстановки суммы в формулу (7.9).

2. Z-преобразование смещённого сигнала. Рассмотрим дискретный сигнал , получающийся из дискретного сигнала путём сдвига на одну позицию в сторону запаздывания, т.е. когда . Непосредственно вычисляя Z-преобразование, получаем следующий результат:

(7.12)

Таким образом, символ служит оператором единичной задержки (на один интервал дискретизации) в Z-области.

3. Z-преобразование свёртки. Пусть x(z) и y(z) – непрерывные сигналы, для которых определена свёртка:

(7.13)

Применительно к дискретным сигналам по аналогии с (7.13) принято вводить дискретную свёртку – последовательность чисел общий член которой:

(7.14)

Подобную дискретную свёртку называют линейной

Вычислим Z-преобразование дискретной свёртки:

(7.15)

Итак свёртке двух дискретных сигналов отвечает произведение Z-преобразований.

Часть