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

С другой стороны, запишем преобразование Фурье для каждого из данных векторов:

В почленном произведении последних двух сумм мысленно приведем подобные члены, т. е. найдем коэффициенты при хтуп. В полученной сумме будет всего N2 слагаемых. Докажем, что при т ≠ п коэффициент при хтуп равен 0.

Зафиксируем т = т0 и п = п0, причем т0 ≠ п0. Тогда коэффициент при xm0 yn0 будет равен

Так как сумма в скобках не зависит от l, то эта сумма повторяется N раз, и мы получаем после сокращения на N:

16

Таким образом, А совпадает с (2.4), и первое утверждение доказано.

2.4. Выражение линейной свертки через круговую

Покажем на примере как линейную свертку можно выразить через круговую, а затем приведем соответствующие формулы. Пусть даны две конкретные последовательности: (a) (2, 7, 1, 4) длины 4 (т = 4), (b) = (3, 5, 6) длины 3 (п = 3). Найдем вектор w (длины т + п – 1= 6), координаты ко-

торого равны координатам линейной свертки w = a b= = {w0, w1, w2, w3, w4, w5}. Тогда по определению свертки эти координаты таковы:

w0 = 2 · 3 = 6,

w1 = 2 · 5 + 7 · 3 = 31,

w2 = 2 · 6 +7·5 +1 · 3 = 50,

w3 = 2 · 0 + 7 · 6 + 1 · 5 + 4 · 3 = 59, w4 = 1 · 6 + 4·5 = 26,

w5 = 4 · 3 = 12.

Теперь проделаем следующую операцию: присоединим к первой последовательности п – 1 = 2 новых члена, равные 0, а ко второй т – 1 = 3 новых члена, равные 0. Тогда длины обеих последовательностей станут одинаковыми и равными т + п – 1 = 6. Иными словами, рассмотрим две новые последовательности

( a ) = (2, 7, 1, 4, 0, 0); ( b ) = (3, 5, 6, 0, 0, 0).

Тогда круговая свертка этих последовательностей есть новый вектор w a b . Координаты этого вектора таковы:

w0 a0b0 a1b5 a2b4 a3b3 a4b2 a5b1 .

2-е, 3-е, 4-е слагаемые здесь равны 0,так как b3 = b4 = b5 = 0, а 5-е и 6-е равны 0, так как а5 = а6 = 0, поэтому w0 a0b0 6 w0 .

w1 a0b1 a1b0 a2b5 a3b4 a4b3 a5b2 .

Здесь остаются только 2 первых слагаемых, 3-е, 4-е, 5-е слагаемые здесь равны 0,так как b3 = b4 = b5 = 0, а 6-е равно 0, так как а5 = 0, поэтому w1 a0b1 a1b0 31 w0 .

w2 a0b21 a1b1 a2b0 a3b5 a4b4 a5b3 .

17

Последние 3 слагаемых равны 0, и w2 w2 50 . Продолжая эти вычисления, убедимся, что для всех k выполняются равенства wk wk , и линей-

ная свертка совпадает с круговой.

Теперь проведем формальные рассуждения. Пусть даны две последовательности: (a) длины т и (b) длины п. Присоединим к первой последовательности п – 1 нулей, а ко второй т – 1 нулей. Тогда длины обеих последовательностей сравняются и будут равны N = m + n – 1.

Таким образом, мы ввели 2 новых вектора длины N = m + n – 1:

Можно доказать, что круговая свертка этих новых векторов равна линейной свертке данных последовательностей, так как все «наддиагональные» элементы формул для круговой свертки равны нулю.

3. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ (БПФ)

Этим термином обозначается нахождение дискретного спектра данного временного сигнала (т. е. прямого дискретного преобразования Фурье) с помощью формул, уменьшающих число умножений. Если преобразование Фурье производится непосредственно по формуле w = Fz, то для получения

результата требуется n2 умножений комплексных чисел, где п – порядок матрицы F. Заметим, что на каждое такое умножение компьютер тратит примерно в 140 раз больше времени, чем на сложение. Было выяснено, что если п – простое число, то число умножений уменьшить нельзя.

Если же п – составное число, то число умножений можно существенно уменьшить. Кроме того, было доказано, что наиболее существенно число

умножений можно уменьшить при n = N = 2s, поэтому обычно БПФ осуществляется при таком N. В этом случае БПФ называют еще «прореживанием», которое можно проводить либо по времени, либо по частоте.

Здесь мы сделаем только один шаг для «прореживания» по частоте и приведем формулы для БПФ и комментарии к ним.

Итак, пустьN = 2s ипустьсигнал(временнаяпоследовательность) имеет

значения Обозначим 2 2 2 i . На- f0 , f1, f2 , , fN 1 . w wN cos N i sin N e N

помним, что wN = 1 и что последовательность 1, w, w2 , , wN 1 – это все-

возможные корни степени N из единицы (всего их N) и сумма всех этих корней равна 0.

18

Коэффициенты прямого дискретного преобразования Фурье будем обозначать сп, п = 0, 1, 2, …, N – 1:

в каждой сумме мы проделаем подобную операцию, то у нас получатся формулы (правда, пока не окончательные) для 4 коэффициентов: с4l, c4l + 1,

c4l + 2 и c4l + 3. Число умножений здесь также равно N N4 4. Таким обра-

зом, для окончательных формул всего понадобится s log2 N шагов, и на каждом шаге будет произведено N умножений. Это значит, что общее чис-

19

ло умножений не будет превосходить N log2 N (при условии, что числа wk

вычислены заранее).

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

Итак, пусть N = 2s, L меняется от 1 до s, при каждом фиксированном L

в программах это совершается автоматически) и повторяем процедуру. При L = s мы получаем ответ, т. е. ДПФ, но он записан в двоично-инверсионном виде (что в технической литературе обычно изображается так называемой «бабочкой»). Именно, индекс у f j , j 0, 1, 2, ..., N 1, переводят в двоич-

ную систему, затем эту запись читают справа налево и получают уже нужный индекс k у коэффициента Фурье ck. Например, при s = 4 (N = 16)

дексов читаются одинаково слева направо и справа налево. Далее, f14 c7 , так как 14 в двоичной системе записывается в виде 1110, а 7 – в виде 0111.

Замечание 1. При использовании БПФ для обратного ДПФ используются «почти» те же формулы (заменяется только w на комплексно сопряженное число и в ответе все координаты делятся на N).

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

Замечание 3. Еще проще производится БПФ при «прореживании по времени». Оно основывается на отделении слагаемых ДПФ с четными и нечетными индексами:

т. е.

20