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

вторяя эту процедуру для каждого из получившихся 2-х векторов, получим

версальную формулу, удобную для создания вычислительного цикла: на

21

где wp e 2 p i1 . Так как для шага с номером р – 1 вычисляется всего 2р– 1 координат, то в формуле (3.2) считаем, что при j > 2p – 1 – 1 координата

который и является ДПФ исходного вектора.

Итак, на каждом из s = log2N шагов производится N умножений, так

что всего для ДПФ производится Nlog2N умножений (вместо N2 при использовании стандартных формул ДПФ).

Применение БПФ выгодно и при вычислении свертки двух последовательностей, если они достаточно длинны. Например, при N = 2n = 256 (n = 8)

стандартная круговая свертка требует ≈N2⁄2 ≈ 128·256 умножений, а переход к БПФ, почленное умножение результатов и обратное БПФ требуют ≈2

· 4 · Nlog2N + N = 8 · 256 · 8 + 256 = 65 · 256 умножений, что гораздо меньше, чем предыдущее число (появление множителя 4 объясняется тем, что при перемножении 2 комплексных чисел требуется перемножить 4 пары вещественных чисел). При увеличении числа N выгода будет только нарастать.

4.ДВА ПРИМЕРА ИСПОЛЬЗОВАНИЯ ДПФ

ИИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ К ЭТИМ ПРИМЕРАМ

Mы начнем этот раздел с примера, который очень полезен для понимания того, что происходит при применении ДПФ. Заметим, что аналогичные рассуждения и выкладки приходится неоднократно повторять для разработок конкретных устройств при нахождении их переходных характеристик (разумеется, при гораздо большем числе параметров, например, при N = 1024, и при разных длинах рассматриваемых последовательностей).

Пример 1. Какова должна быть переходная характеристика линейного устройства, которое переводит последовательность (0, 1, 2, 3) в последова-

тельность (0, 1, 1, 0)?

Замечание. На самом деле этот вопрос можно поставить и так: даны две последовательности чисел одинаковой длины; найти третью последовательность той же длины так, чтобы круговая свертка первой и третьей последовательностей равнялась второй последовательности. Непосредственно эту задачу можно решить, как систему 4 линейных уравнений с 4 неизвест-

22

ными. Эта система не всегда имеет решение, а иногда ее решение не единственно. Мы предлагаем решить эту задачу при помощи ДПФ (или БПФ), что особенно актуально при больших длинах данных последовательностей (в этом примере мы не касаемся вопросов «уравнивания» длин 1-й и 2-й последовательностей, хотя часто, и мы это отмечали, 2-я последовательность длиннее 1-й).

Итак, схема решения нашего примера:

1)Вычисляем ДПФ 1-й и 2-й последовательностей. Заметим, что если данная задача не имеет решения (или решение не единственно), то в ДПФ 1-й последовательности одна из координат равна 0 (что означает, что определитель соответствующей системы уравнений равен 0). В наших примерах ДПФ 1-й последовательности не содержит нулей.

2)В теории мы отмечали, что покоординатное произведение ДПФ временного сигнала и переходной характеристики устройства дает координаты ДПФ круговой свертки этих последовательностей. Так как оно нами найдено, то мы можем получить ДПФ искомой переходной характеристики покоординатным делением ДПФ 2-й последовательности на ДПФ 1-й.

3)СпомощьюобратногоДПФнаходимискомуюпоследовательность.

4)Делаем проверку полученного результата (т. е. непосредственно на-

ходим круговую свертку 1-й и полученной последовательностей и убеждаемся, что получили 2-ю данную последовательность).

Теперь приведем решение по указанной схеме нашего конкретного примера. Нам даны последовательности у = (0, 1, 2, 3) и z = (0, 1, 1, 0). Надо

найти такую последовательность х = (х0, х1, х2, х3), что y x z . 1) Находим ДПФ для у:

Видно, что yˆ не содержит нулевых координат и содержит 2 комплексно сопряженных элемента. Теперь найдем

(в ДПФ zˆ имеется нулевая координата, но это не играет роли).

23

2) Далее находим вектор xˆ , равный вектору, полученному почленным делением координат zˆ на координаты yˆ . Таким образом,

3) Теперь находим саму последовательность при помощи обратного ДПФ

последовательностью z = (0, 1, 1, 0):

z0 = y0 x0 + y1x3 + y2x2 + y3x1 = 0 12 121 2 13 0 ; z1 = y0 x1 + y1x0 + y2x3 + y3x2 = 0 121 23 14 1; z2 = y0 x2 + y1x1 + y2x0 + y3x3 = 0 16 122 1 1;

z3 = y0 x3 + y1x2 + y2x1 + y3x0 = 0 121 62 123 0 ;

таким образом, пример решен верно.

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

Индивидуальные задания 1–20

24

Даны две последовательности чисел y и z длины 4. Требуется найти при помощи ДПФ переходную характеристику линейного устройства, переводящего последовательность y в последовательность z (т. е. найти последовательность х, для которой круговая свертка с y равна z).

Перейдем теперь ко второму рассматриваемому примеру.

Пусть дана функция y = f(t) на интервале [a, b]. Считаем, что [a, b] – временной интервал, а y = f(t) – аналоговый временной сигнал. Для примене-

ния ДПФ эту функцию обычно представляют в виде вектора {y0, y1, y2, …,

Таким образом, y0 = f(a), yN – 1= f(b – h) (если продолжить вектор еще на один шаг, то yN было бы равно f(b)). Эта операция называется дискрети-

зацией временного сигнала. Заметим, что обычно здесь считают, что N = 2s (для того, чтобы можно было применить ДПФ), и мы тоже будем так считать. После этого, применяя ДПФ (или, что тоже, БПФ), мы получим дискретный спектр (или прямое преобразование Фурье) по формуле

Можно доказать (используя теорию рядов Фурье), что если f(t) – непрерывная функция и f(a) = f(b), то wj Cj2 , (С – некоторая константа) при

j < N2 . Поэтому если «малые» коэффициенты заменить нулями и выпол-

нить обратное преобразование Фурье, то получится (приближенно) исходный вектор. Если же функция не является непрерывной (или f (a) f (b) ),

то wj Cj при j N2 . Заметим также, что если f(t) была симметричной от-

носительно середины интервала, т. е. точки a 2 b , то прямое преобразова-

25