51. Теорема отсчётов в частотной области


АЛГОРИТМЫ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ. АНАЛИЗ ЭФФЕКТИВНОСТИ БПФ



Скачать 484,47 Kb.
страница14/52
Дата08.04.2021
Размер484,47 Kb.
1   ...   10   11   12   13   14   15   16   17   ...   52
    Навигация по данной странице:
  • N log
63. АЛГОРИТМЫ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ. АНАЛИЗ ЭФФЕКТИВНОСТИ БПФ.

Недостатком ДПФ является большое количество математических операций для формул Error: Reference source not found или Error: Reference source not found. Если число степеней свободы сигнала N, то для ДПФ потребуется N2 умножений и N2 сложений комплексных чисел, т.е. всего 2 N2 арифметических операций. Для больших N такая обработка становится слишком продолжительной, даже на быстродействующих моделях ЭВМ.

Для ускорения вычисления ДПФ применяют специальные алгоритмы, которые позволяют во много раз сократить объем вычислений. Такие алгоритмы называют Быстрым Преобразованием Фурье.

Существуют различные алгоритмы БПФ, например Кули-Тьюки, Винограда, теоретико-числовые преобразования, прореживания по частоте или по времени. Наиболее простыми алгоритмы получаются, если N являются целой степенью числа 2. Рассмотрим один из таких алгоритмов, основанный на т.н. прореживании по времени. Пусть требуется вычислить ДПФ числовой последовательности fk:

Поскольку число отсчетов сигнала N- четное, исходную последовательность fk можно разбить на две подпоследовательности: gi, куда войдут все fk с четными номерами, и подпоследовательность hi, куда войдут все fk с нечетными номерами, так что gi=f2i; hi=f2i+1 (i=0,1,2,...,N/2-1)

Применим ДПФ к подпоследовательностям gi и hi, содержащим по N/2 членов:



Для сокращения записи обозначим: тогда:



Нашей целью является вычисление значений Fn.

Учитывая, что все члены последовательности fk принадлежат gk или hk, можно записать:

(4.12)

Т.о., значение Fn можно вычислить по известным Gn и Hn.

Однако, Error: Reference source not found справедлива только для nN/2-1, т.к. Gn и Hn не определены для больших n. Поэтому для nN/2 значение Fn вычисляются с использованием периодичности ДПФ:



Учитывая, что



,

получим окончательную формулу для Fn при nN/2:

(4.13)

Для вычисления значений Gn и Fn нужно выполнить два ДПФ половинной длины. При этом для вычисления Gn и Fn необходимы по 2(N/2)2=N2/2 арифметических операций: по две операции для Error: Reference source not found и по одной операции для Error: Reference source not found. Таким образом, общее число арифметических операций равно N2+3/2N, что для больших N дает существенный выигрыш в количестве операций.

Каждую из частных подпоследовательностей gi и hi можно опять-таки разбить на две подпоследовательности половинной длины, для которых справедливы указанные выше формулы.

Процесс упрощения алгоритма расчета можно продолжать до тех пор, пока не останутся только простейшие двухточечные ДПФ. В результате, при применении данного алгоритма для вычисления ДПФ последовательности из N точек, требуется выполнить N log2N сложений и, самое большее, N log2N умножений. Использование БПФ для случая N=210=1024 отсчетов обеспечивает сокращение объема вычислений более чем в 100 раз!



Алгоритм вычисления ДПФ схематично изображают в виде направленного графа, граф двухточечного ДПФ из-за внешнего сходства получил название "бабочка".



Поделитесь с Вашими друзьями:
1   ...   10   11   12   13   14   15   16   17   ...   52


База данных защищена авторским правом ©psihdocs.ru 2019
обратиться к администрации

    Главная страница