- •13. Связь между спектрами дискретного и аналогового сигналов. Явление наложения спектров. Приведенный спектр.
- •14. Передаточные функции рекурсивных цифровых фильтров
- •15. Прямая форма реализации нерекурсивных фильтров
- •16. Базовая структура анализатора спектра на основе дпф.
- •17. Алгоритм бпф с прореживанием по времени по основанию 2. Сигнальный граф алгоритма бпф с прореживанием по времени.
- •18. Организация процесса разработки решений
17. Алгоритм бпф с прореживанием по времени по основанию 2. Сигнальный граф алгоритма бпф с прореживанием по времени.
Алгоритмы быстрого преобразования Фурье (БПФ) - это способы быстрого вычисления ДПФ, устраняющие свойственную ДПФ вычислительную избыточность. Пусть задана последовательность x(n)N конечной длины N, n = 0, 1,.N – 1.Нужно найти ее ДПФ:
N-(номера бинов ДПФ) с минимальным объемом вычислений. Исходную последовательность x(n) длиной N разобьем на 2 подпоследовательности: длиной N/2 – четную (включающую отсчеты x(n) с четными индексами n: x1(n) = x(2n) и нечетную: x2(n) = x(2n + 1), n = 0,1,..(N/2) – 1. Это соответствует первому прореживанию сигнала по времени (рис. 8.1).
Обозначим их ДПФ как Выразим ДПФ исходной последовательности x(n)N через ДПФ подпоследовательностей x1(n)N/2 , x2(n)N/2:
Это первые N/2 частотных выборок ДПФ. Вторую половину частотных выборок X(jk) для k = (N/2), … (N – 1) найдем с учетом свойства периодичности:
В ходящий в (8.3) множитель Wк N , равный по модулю единице, называют поворачивающим. Вычисления в соответствии с (8.3) включают одно комплексное умножение и пару сложения–вычитания. Выражения (8.1), (8.2) определяют базовую операцию БПФ (операцию объединения) и изображают в виде графа:
- операцию сложения (верхний выход) и вычитания (нижний выход), а стрелка соответствует умножению на поворачивающий множитель
Сигнальный граф алгоритма БПФ получается в виде совокупности графов базовых операций. Для первого этапа прореживания он показан на рис. 8.3 для случая N = 8.
каждую из последовательностей x1(n) и x2(n) можно разбить еще на две под последовательности вдвое меньшей длины: x11(n), x12(n) и x21(n), x22(n) (четную и нечетную) и повторить вышеприведенные операции объединения их ДПФ с помощью базовых операций. Такое прореживание . выполняем L раз до получения N/2 двухточечных последовательностей xl(0), xl(1), ДПФ которых вычисляется тривиально:
В результате получаем полный граф БПФ, показанный на рис. 8.4 для N = 8.
Выигрыш БПФ относительно ДПФ по числу операций умножения: Выделенные на рис. 8.4 узловые точки графа соответствуют ячейкам оперативной сигнальной памяти.
Алгоритм БПФ с прореживанием по частоте по основанию 2. Сигнальный граф алгоритма БПФ с прореживанием по частоте.
Рассмотрим кратко, как осуществляют прореживание в данном алгоритме БПФ и определяют его базовую операцию. Для этого входную последовательность x(n) представляют в виде двух подпоследовательностей:
x1(n) = x(n) и x2(n) = x(n + (N/2)), n = 0, 1, …(N/2) – 1,
т. е. в виде ее первой x1(n) и второй x2(n) половин и выражают через них ДПФ исходной последовательности:
Далее выполняют прореживание ДПФ-последовательности X(jk) путем разбиения ее на две (N/2)-точечные ДПФ-подпоследовательности X(j2k), X[j(2k + 1)], соответствующие частотным выборкам с четными и нечетными номерами k:
= , (вместо g1(n) должно быть f1(n))
В результате ДПФ исходной последовательности выражается через ДПФ некоторых N/2-точечных последовательностей f1(n), g1(n)(базовые функции), определяемых следующим образом:
,
f1 и q1 разбиваются на две подпоследовательности, получаем 4 преобр.Фурье.
Отличие от метода прореживания по времени явл. необходимость в бит реверсной перестройке после преобразования.
Граф явл. зеркальным отображением предыдущего. (рисунок рисовать наоборот).