Принцип построения алгоритмов БПФ

Поскольку сложность алгоритма растет квадратично относительно размера входного сигнала, можно достичь существенного ускорения вычисления если нам удастся свести расчет N точечного ДПФ к двум N\2 точечным ДПФ

Основная идея алгоритма БПФ с прореживанием по времени заключается в

поэтапном вычислении N-точечного ДПФ (N = 2 v) на v этапах, на каждом из которых текущее ДПФ определяется как комбинация ДПФ вдвое меньшей размерности правило начальной расстановки отсчетов N-точечной последовательности Начальные условия алгоритма БПФ формируются в результате однократного разбиения исходной N-точечной последовательноcти на две N/2-точечныс, выделив отдельно четные и нечетные отсчеты Начальные условия формируются в результате v-кратного разбиения N-точечной последовательности, а сформированная последовательность называется прореженной по времени., отсчеты которого следуют в естественном порядке

Алгоритм БПФ с прореживанием по времени в общем виде можно представить: - задание начальных условий: -отсчеты N-точечной последовательности расставляются по определенному правилу; - на первом этапе определяется 2-точечное ДПФ каждой пары отсчетов последовательности;- на вторам этапе определяются 4-точечные ДПФ как комбинация 2-точечных

ДПФ;- на 3i-ом этапе определяются 2i-точечные ДПФ как комбинация 2i-1 -точечных

ДПФ;-на (v-1)-ом этапе определяются N/2-точечные ДПФ как комбинация N/4- точечных ДПФ; -на v -ом (последнем) этапе определяется искомое N-точечное ДПФ как комбинация N/2-точсчных ДПФ, отсчеты ДПФ следуют в естественном порядке k = 0,1,...,(N -1).

Алгоритм БПФ с прореживанием по частоте

Основная идея алгоритма БПФ с прореживанием по частоте заключается в поэтапном вычислении N -точечного ДПФ па v этапах, на каждом из которых ДПФ пределяется через ДПФ вдвое большей размерности

Алгоритм БПФ с прореживанием по частоте в общем случае описывается следующим образом: - задание начальных условий - естественный порядок следования отсчетов входных отсчетов; -на первом этапе определяются N/2 -точечные ДПФ N/2 -точечных последовательностей (двух половин исходной последовательности);- па втором этапе определяются N/4 -точечныс ДПФ как комбинация N/2- точечпых ДПФ;- на i-ом этапе определяются 2i-1 -точечные ДНФ как комбинация 2i-точечных

ДПФ;- на v-ом (последнем) этапе определяются 2-точечные ДПФ как комбинация4-точечных ДПФ. Выходные отсчеты ДПФ следуют в бит-реверсивном порядке двоичных номеров.

где i –– номер этапа т — номер ДПФ; k — номер отсчета ДПФ M — количество ДПФ L — размерное ДПФ

Передаточная функция ЦФ

Передаточной функцией H (z) ЦФ называется отношение Z –преобразования выходной последовательности к Z -преобразованию входной последовательности при нулевых начальных условиях.

Таким образом, передаточная функция ЦФ может быть получена путем применения Z -преобразования к разностным уравнения. Для РЦФ передаточная

функция имеет вид:

 

Пример Функция Рекурсивный ЦФ

11. Преобразование Уолша-Адамара и его свойства

Пара дискретного преобразования Уолша-Адамара в показательной форме представляется в виде

 

прямое преобразование и дает спектр сигнала в базисе Уолша

 

обратное (Наверно!) где s,b векторы-столбцы отсчетов сигнала и спектральных коэффициентов соответственно

Основными свойствами преобразования являются:

1. Линейность. спектры {b_x(k)}

2. Инвариантность к диадному сдвигу. Сущность диадного сдвига заключается в перестановке отсчетов исходной функции. В

частности, на место отсчета с номером n ставится отсчет с номером (n ⊕τ)

3.Теорема о свертке и корреляции.. диадная свертка совпадает с диадной корреляцией и определяется выражением

где n = 0, 1, …, (N-1).

Теорема о свертке утверждает, что спектр свертки равен произведению спектров сворачиваемых последовательностей: