Принцип построения алгоритмов БПФ
Поскольку сложность алгоритма растет квадратично относительно размера входного сигнала, можно достичь существенного ускорения вычисления если нам удастся свести расчет N точечного ДПФ к двум N\2 точечным ДПФ
Основная идея алгоритма БПФ с прореживанием по времени заключается в
поэтапном вычислении N-точечного ДПФ ( N = 2v ) на 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. Линейность. спектры {bx(k)}
2. Инвариантность к диадному сдвигу. Сущность диадного сдвига заключается в перестановке отсчетов исходной функции. В
частности, на место отсчета с номером n ставится отсчет с номером ( n ⊕τ )
3.Теорема о свертке и корреляции.. диадная свертка совпадает с диадной корреляцией и определяется выражением
где n = 0, 1, …, (N-1).
Теорема о свертке утверждает, что спектр свертки равен произведению спектров сворачиваемых последовательностей: