Материал: конспект-лекций

аргумента n с сохранением того же шага по частоте, как это показано на рис. 8.1.3 для огибающей значений спектра.

На рис. 8.1.4. показано обратное преобразование Фурье для дискретного спектра, выполненное по фор-

муле s'(k) = (1/100) n S(n) exp(j2 kn/100), которое

показывает периодизацию исходной функции s(k), но главный период k={0,99} этой функции полностью совпадает с исходным сигналом s(k).

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

стотном представлении, как, например, фильтрации сигналов непосредственно в частотной форме)

будет соответствовать свертка периодизированных функций во временном представлении (и

наоборот). Такая свертка называется циклической (см. раздел 8.4) и ее результаты на концевых участках информационных интервалов могут существенно отличаться от свертки финитных дис-

кретных функций (линейной свертки).

Из выражений ДПФ можно видеть, что для вычисления каждой гармоники нужно N опера-

ций комплексного умножения и сложения и соответственно N2 операций на полное выполнение ДПФ. При больших объемах массивов данных это может приводить к существенным временным затратам. Ускорение вычислений достигается при использовании быстрого преобразования Фурье.

163

Быстрое преобразование Фурье (БПФ, fast Fourier transform - FFT). Он базируется на том,

что при вычислениях среди множителей (синусов и косинусов) есть много периодически повто-

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

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

водит к меньшим ошибкам округления.

Допустим, что массив чисел sk содержит N = 2r отсчетов (r - целое). Разделим исходный массив на два первых промежуточных массива с четными и нечетными отсчетами:

sk' = s2k, sk" = s2k+1, 0 k N/2-1.

Выполним ДПФ каждого массива с учетом того, что шаг функций равен 2 (при t=1), а пе-

риод промежуточных спектров будет соответственно равен N/2: sk' Sn', sk" Sn", 0 n N/2-1.

Для получения одной половины искомого спектра Sn сложим полученные спектры с учетом теоремы запаздывания, т.к. отсчеты функции sk" сдвинуты относительно sk' на один шаг дискрети-

Нетрудно видеть, что для вычисления полного спектра в данном случае потребуется N2/4

операций для вычисления промежуточных спектров плюс еще N операций комплексного умноже-

ния и сложения, что создает ощутимый эффект по сравнению с ДПФ.

Но деление массивов на две части может быть применено и к первым промежуточным мас-

сивам, и ко вторым, и т.д. до тех пор, пока в массивах не останется по одному отсчету, фурье -

преобразование которых равно самому отсчету. Тем самым, алгоритм преобразования превраща-

ется в пирамидальный алгоритм перестановок со сложением/вычитанием и с единичным умноже-

нием на значение exp(-j2 n/N) соответствующего уровня пирамиды. Первый алгоритм БПФ на данном принципе (из множества модификаций, существующих в настоящее время) был разрабо-

тан Кули-Тьюки в 1965 г. и позволил повысить скорость вычислений в N/r раз по сравнению с ДПФ. Чем больше N, тем больше эффект БПФ. Так, при N = 1024 имеем r = 10 и соответственно

N/r 100. Что касается условия по количеству точек N = 2r, то оно рассматривается в варианте Nk

2r, где r - минимальное целое. Массивы с Nk < 2r дополняется до 2r нулями, что не изменяет форму спектра. Изменяется только шаг по представлению спектра (= 2 /2r < 2 /N), ко-

торый несколько избыточен по адекватному представлению сигнала в частотной области. В насто-

164

ящее время существуют и алгоритмы БПФ с другими основаниями и их комбинациями, при кото-

рых не требуется дополнения сигналов нулями до 2r.

Заметим, что в соответствии с (8.1.7) отсчеты, сопряженные с правой половиной главного частотного диапазона (0, ), относятся не к диапазону (- ,0), а к диапазону ( ,2 ), что, учитывая периодичность спектра дискретных данных, значения не имеет. Т.е. выходной частотный диапазон БПФ равен (0, 2 ). Общее количество отсчетов комплексного спектра в этом условно главном диапазоне равно количеству точек исходного сигнала (с учетом нулевых точек при дополнении сигнала до N=2r). Алгоритм быстрого обратного преобразования (ОБПФ) тождественен алгоритму прямого БПФ.

Алгоритмы прямого и обратного БПФ широко используются в современном программном обеспечении для анализа и обработки цифровых данных. Пример выполнения БПФ приведен на рис. 8.1.5.

Рис. 8.1.5. Пример БПФ.

Применение ДПФ. Основная область использования ДПФ – спектральный анализ физиче-

ских данных. При этом интерес обычно представляют только амплитуды отдельных гармоник, а

не их фазы, и спектр отображается в виде графика зависимости амплитуды (модуля спектра) от частоты. Часто шкала амплитуд градуируется в децибелах. Децибелы - логарифмы отношения ам-

плитудных значений. Например, разница на 20 дБ означает различие амплитуд в 10 раз, разница на

40 дБ - 100 раз. Различию амплитуд в 2 раза отвечает разница примерно в 6 дБ. Шкала частот так-