Материал: Фарфоровская Ю. Б. Математика. Дискретное и быстрое преобразование Фурье

ным спектром вектора z = (z0, z1, …, zn). На практике очень удобно и часто применяется обозначение дискретного спектра w = zˆ .

Далее, из (3) получаем: z = F–1w = F*w. Так как F* отличается от F множителем 1n и знаков «минус» у экспонент нет, то верны формулы

Это и есть формулы обратного дискретного преобразования Фурье (обратного ДПФ).

Приведем, для примера, конкретные матрицы F4, F4*, F8.

Замечание. Пусть заданная на всей оси функция f(x) такова, что для всех х вне отрезка [0, 1] все ее значения равны 0: для x [0, 1] f (x) 0 .

Тогда ее обычное преобразование Фурье задается равенством

Интегральная сумма для последнего интеграла при разбиении отрезка [0, 1] на п равных частей (или, что то же, приближенное значение этого ин-

11

ким образом, ДПФ можно рассматривать как приближенное преобразование Фурье. Конечно, реальный сигнал не обязательно сосредоточен на отрезке [0, 1], но любой отрезок может быть преобразован в этот отрезок за счет линейного преобразования временной оси. Заметим также, что так как ДПФ вектора с одинаковыми координатами а равно вектору, у которого только первая координата равна па, а остальные координаты равны нулю, то «сдвиг» по оси y меняет у ДПФ только нулевую координату. «Сдвиг» сигнала по временной оси (с соответствующим изменением интервала) вообще ничего не меняет.

2. ЛИНЕЙНЫЕ И КРУГОВЫЕ СВЕРТКИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ.

СВЯЗЬ ИХ С ДПФ 2.1. Линейная свертка

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

Здесь у – входной сигнал, а z = Ly – выходной. Линейность этой системы означает, что преобразование входного сигнала является линейным, т. е.

L(y1 + y2) = Ly1 + Ly2 и L(cy) = cLy.

Иными словами, линейным комбинациям входных сигналов соответствуют линейные комбинации с теми же коэффициентами выходных сигналов. Естественно, мы считаем, что любой входной сигнал – это элемент линейного пространства, т. е. вектор или функция. Например, линейными устройствами являются линейные электрические цепи или разного рода

12

фильтры (т. е. устройства, умеющие распознать и разделить разного рода входные сигналы, в частности, устранять определенного рода помехи).

Предположим, что на вход такой линейной системы подается единичный по величине достаточно короткий импульс. На выходе на этот сигнал последует определенная реакция (которая считается всегда одинаковой). Часто эта реакция оказывается гораздо длиннее по времени поданного импульса. Приближенно эту реакцию представляют в виде конечной последовательности

чисел (коэффициентов) zk, k = 0, 1, 2, …, n – 1, причем каждое число рассматривается как реакция системы за единичный по времени такт, который имеет некоторый номер k. Эта последовательность называется переходной характеристикой данного устройства. Если же на вход подается конечная последовательность (единичных по времени) сигналов с коэффициентами

{yk}, k = 0, 1, 2,…, m – 1, то на выходе должна получиться линейная свертка

последовательностей {yk} и {zk}. Действительно, обозначим начало реакции нашего устройства нулевым тактом (единичным по продолжительно-

сти), а ее величину в k-ом такте символом {wk}. Тогда очевидно, что

w0 = y0z0,

w1 = y0z1 + y1z0,

w2 = y0z2 + y1z1 + y2z0,

…………………………

wn–1 = y0zn-1 + y1zn-2 + …+yn-1z0,

wn = y1zn-1 + y2zn–2 +y3zn-3 +… + ynz0.

…………………………………………

wm + n-2 = ym – 1zn–1.

Предполагается, что последовательность {yk} продолжена нулями, когда т < п. Таким образом, реакция на сигнал из т тактов содержит ровно т + п – 1 такт.

Последовательность {wk} и называется линейной сверткой последова-

тельностей {yk} и {zk}. Заметим, что если обе последовательности продолжить нулями, то координату свертки с номером r можно записать в виде

s 0

Таким образом, линейная свертка двух последовательностей {yk} и {zk} – это новая последовательность {wk}, обозначаемая символом

w = y z = {wr}.

13

Отметим также, что число ненулевых элементов при свертке двух конечных последовательностей тоже содержит конечное число ненулевых членов. Однако линейную свертку можно определить и для бесконечных последовательностей по формуле (2.1). Нетрудно доказать, что операция свертки перестановочна, т. е. что y z = z y и обладает линейными свойствами по каждому из множителей (как для конечных, так и для бесконечных последовательностей).

Перейдем теперь к определению круговой свертки. Эта свертка важна тем, что именно для круговой свертки преобразование Фурье обладает важными свойствами. Позже будет показано, как линейную свертку выразить через круговую.

2.2. Круговая свертка

Пусть имеются две комплексные последовательности одинаковой длины N: yk kN 01 и zk kN 01 . Их круговой сверткой называется новая последовательность длины N, координаты которой определяются формулой

продолжена по периодичности с периодом N, т. е. zs = zs + N , например, z–2 = zN–2. Собственно, чтобы воспользоваться формулой (2.2), достаточно продолжить последовательность zk kN 01 на один период влево, т. е. рас-

смотреть последовательность z–N+1, z–N+2,…, z–1, z0, z1, …, zN–1, или, что то

же, z1, z2,…, zN-1, z0, z1, …, zN–1. Напишем круговую свертку для двух последовательностей длины 4 (т. е. N = 4: {y0, y1, y2, y3} и

{z0, z1, z2, z3}):

w0 = y0 z0 + y1z3 + y2z2 +y3z1; w1 = y0 z1 + y1z0 + y2z3 +y3z2; w2 = y0 z2 + y1z1 + y2z0 +y3z3; w3 = y0 z3 + y1z2 + y2z1 +y3z0.

Заметим, что если «отсечь» наддиагональные элементы в этих формулах, (то есть считать их равными нулю), то круговая свертка совпадет с линейной. Именно это и позволяет сравнительно легко выразить линейную свертку через круговую (с помощью добавления нулей и выравнивания длин данных последовательностей.

14

Очевидно, что круговая свертка также перестановочна и обладает линейными свойствами.

2.3.Четыре свойства ДПФ, связанные с круговой сверткой

1)Пусть даны две временные последовательности xk kN 01 и yk kN 01 .

Построим новый вектор z той же длины, координаты которого равны произведениям соответствующих координат данных векторов, т. е. образу-

ем новый вектор z = zk kN 01 = xk yk kN 01 . Тогда дискретный спектр (т. е. дис-

кретное преобразование Фурье) вектора z равен круговой свертке спектров векторов х и у, т. е. если дискретные спектры x и y равны соответственно

2) Обратное дискретное преобразование Фурье, примененное к круговой свертке дискретных спектров двух данных временных последовательностей, равно вектору, составленному из произведений их соответствующих координат.

3) Круговая свертка двух периодических временных последовательностей имеет дискретный спектр (т. е. прямое дискретное преобразование Фурье), равный вектору, координаты которого равны произведениям соответствующих координат дискретных спектров данных последовательностей.

Наконец, четвертое свойство, которое получается обращением третьего.

4) Обратное дискретное преобразование Фурье вектора, координаты которого равны произведениям соответствующих координат дискретных спектров двух данных векторов, равно круговой свертке этих данных временных последовательностей.

Ясно, что второе и четвертое свойства являются применением обратного преобразования Фурье для первого и третьего утверждений. Мы докажем здесь только первое утверждение (третье получается аналогично).

Доказательство первого утверждения.

Пусть даны две временные последовательности xk kN 01 и yk kN 01 .

Рассмотрим вектор z = zk kN 01 = xk yk kN 01 . Запишем s-ю координату его дискретного преобразования Фурье:

15