Алгоритм бпф с прореживанием по частоте кратко

Обновлено: 05.07.2024

Алгоритмы БПФ с прореживанием по времени были основаны на разложении ДПФ путем формирования уменьшающихся подпоследовательностей входной последовательности . С другой стороны, можно рассмотреть такое же разложение выходной последовательности на уменьшающиеся подпоследовательности. Класс алгоритмов БПФ, основанный на этой процедуре, обычно называется классом алгоритмов с прореживанием по частоте. Чтобы вывести БПФ-алгоритм с прореживанием по частоте для являющегося степенью 2, сначала нужно разделить входную последовательность на две половины так, что

Важно отметить, что, хотя (6.18) содержит две суммы по точек, каждая из этих сумм не является -точечным ДПФ, так как каждой из сумм стоит а не Объединяя две суммы в (6.18) и используя соотношение получим

Рассмотрим теперь отдельно четные и нечетные обозначив через суммы соответственно четных и нечетных точек, так что

Нетрудно видеть, что (6.20) и (6.21) являются -точечными в случае (6.20) — от суммы первой и последней половины входной последовательности, а в случае (6.21) — от произведения на разность первой и второй половины входной последовательности. В отличие от (6.19), суммы в (6.20) и (6.21) соответствуют -точечным ДПФ потому, что

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

Рис. 6.15. Направленный граф, иллюстрирующий разложение -точечного ДПФ на два -точечных ДПФ в алгоритмах с прореживанием по частоте

Рис. 6.16. Направленный граф, иллюстрирующий разложение восьмиточечного ДПФ на четыре двухточечных для алгоритмов с прореживанием по частоте

Поступая так же, как и в случае вывода алгоритма с прореживанием по времени, замечаем, что так как является степенью четно, и, следовательно, -точечные ДПФ могут быть найдены путем вычисления по отдельности четных и нечетных выходных точек этих ДПФ. Как и в случае исходного разложения, приводящего к (6.20) и (6.21), это делается путем объединения первой и второй половины входных точек для каждого из -точечных ДПФ и затем вычисления -точечных ДПФ. Направленный граф, соответствующий этому шагу для восьмиточечного ДПФ, показан на рис. 6.16. Для восьмиточечного ДПФ вычисления теперь сводятся к вычислению двухточечных ДПФ, которые, как мы видели раньше, получаются путем сложения и вычитания входных точек. Таким образом, двухточечные ДПФ на рис. 6.16 могут быть замечены вычислениями, показанными на рис. 6.17 так, что в результате для восьмиточечного ДПФ получим граф, изображенный на рис. 6.18.

Рис. 6.17. Направленный граф двухточечного ДПФ на последней ступени разложения для алгоритмов с прореживанием по частоте

Рис. 6.18. Направленный граф при полном разложении восьмиточечного ДПФ для алгоритмов с прореживанием по частоте

Подсчитывая число арифметических операций на рис. 6.18 и обобщая на случай убеждаемся, что вычисления по рис. 6.18 требуют комплексных умножений и комплексных сложений. Таким образом, общее количество вычислений для алгоритмов с прореживанием по частоте и с прореживанием по времени одинаково.

На прошлой лекции мы изучили, что такое дискретное преобразование Фурье (ДПФ), изучили его свойства, подводные камни, способы улучшения результатов, а также частотно-временное преобразование Фурье.

Вспомним выражение для ДПФ:

$\begin (1) X[m] = \sum\limits_^x[n]\cdot e^ <-j2\pi n m/N>\end$

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

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

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

В рамках данной лекции рассмотрим два самых распространённых алгоритма БПФ — с прореживанием по времени и с прореживанием по частоте.

Итак, выше мы уже отметили, что для -точечного ДПФ требуется операций комплексного умножения и сложения. А что, если разделить исходный сигнал на два длиной отсчётов каждый? Тогда получается, что для вычисления ДПФ от одной из половин потребуется математических операций. Или для двух половин (если не считать процедуру разделения и объединения). Получается, эффективность вычислений возрастает в два раза! Но это ещё не предел. Мы можем делить наш сигнал до тех пор, пока не получим набор из сигналов, состоящих из двух отсчётов:

Разбиение сигнала до N=2

$W_N^<n m> Теперь давайте немного модифицируем выражение (1). Пусть = e^<-j2\pi n m/N>$
, тогда:

$\begin (2) X[m] = \sum\limits_^x[n]\cdot W_N^ \end$

$\begin W_8^0 &= e^ = 1\\ W_8^1 &= e^ <-j2\pi/8>= e^ <-j\pi/4>= \frac> = a\\ W_8^2 &= a^2 = \left( \frac> \right)^2 = \frac = -j\\ W_8^3 &= a^3 = a^2 \cdot a = -a^*\\ W_8^4 &= a^4 = (a^2)^2 = -1 \\ W_8^5 &= a^5 = a^4\cdot a = -a\\ W_8^6 &= a^6 = a^4\cdot a^2 = j\\ W_8^7 &= a^7 = a^4\cdot a^3 = a^*\\ W_8^8 &= a^8 = a^4 \cdot a^4 = 1 \end$

отличается от второй половины только знаком:

$\begin W_8^0 &= -W_8^4\\ W_8^1 &= -W_8^5\\ W_8^2 &= -W_8^6\\ W_8^3 &= -W_8^7 \end$

Если произведение выходит за диапазон от 0 до 7, мы также увидим повторяемость этих значений. Например, при , а :

$\begin W_8^ = a^ = (a^8)^5 \cdot a^2 = a^2 = -j \end$

Следовательно, в процессе ДПФ вычисление одних и тех же значений повторяется несколько раз. Наша задача — оптимизировать процесс так, чтобы избежать выполнение повторяющихся операций.

Давайте разделим сигнал на отсчёты с чётными и нечётными номерами, как показано на рисунке:

Прореживание сигнала по времени

Эта операция называется прореживание по времени. Математически это можно записать следующим образом:

$\begin (3) X[m] = \sum\limits_^x[2n]\cdot W_N^ + \sum\limits_^x[2n+1]\cdot W_N^ \end$

$\begin (4) W_N^ = e^ <-j2\pi 2n m/N>= e^<\frac<-j2\pi n m>> = W_>^ \end$

$\begin (5) W_N^ = W_N^ \cdot W_N^m = W_>^ \cdot W_N^m \end$

Тогда, выражение (3) принимает вид:

$\begin (6) X[m] = \sum\limits_^x[2n]\cdot W_>^ + W_N^m\sum\limits_^x[2n+1]\cdot W_>^ \end$

Это был расчёт ДПФ для первых отсчётов. Теперь запишем подобное выражение для второй половины отсчётов:

$\begin (7) \begin X\left[m+\frac\right] = \sum\limits_^x[2n]\cdot W_N^<2n(m+\frac)> +\\ +\sum\limits_^x[2n+1]\cdot W_N^<(2n+1)(m+\frac)> \end \end$

Давайте теперь по очереди разбираться со всеми множителями:

$\begin (8) \begin W_N^<2n(m+\frac)> = W_N^ \cdot W_N^> = W_>^ \cdot e^<\frac<-j2\pi 2n\frac>> = \\ = W_>^ \cdot e^ <-j2\pi n>\end \end$

$e^<-j2\pi n> Т.к. = 1$
, то выражение (8) принимает вид:

$\begin (9) W_N^<2n(m+\frac<N>)> = W_>^ \end$

Рассмотрим следующий множитель:

$\begin (10) W_N^<(2n+1)(m+\frac<N>)> = W_N^ \cdot W_N^ \cdot W_N^m \cdot W_N^ \end$

$\begin (11) W_N^ = e^<\frac<-j2\pi N>> = e^ <-j\pi>= -1, \end$

то выражение (10) можно упростить:

$\begin (12) W_N^<(2n+1)(m+\frac<N>)> = -W_>^ \cdot W_N^m \end$

Подставим результаты из (9) и (12) в уравнение (7) и получим:

$\begin (13) \begin X\left[m+\frac\right] = \sum\limits_^x[2n]\cdot W_<\frac>^ - \\ - W_N^m\sum\limits_^x[2n+1]\cdot W_<\frac>^ \end \end$

Для простоты восприятия сделаем две замены:

$\begin (14) G[m] = \sum\limits_^x[2n]\cdot W_>^ \end$

$\begin (15) H[m] = \sum\limits_^x[2n+1]\cdot W_>^ \end$

Тогда, с учётом (14) и (15), сгруппируем уравнения (6) и (13):

$\begin (16) \begin X[m] = G[m]+W_N^m \cdot H[m]\\ X\left[m+\frac\right] = G[m]-W_N^m \cdot H[m] \end \end$

Полученное выражение (16) называется графом “бабочка”. Почему? Это станет ясно, если посмотреть на его графическое представление:

Граф “бабочка” для БПФ с прореживанием по времени

Данное выражение лежит в основе БПФ с прореживанием по времени.

Таким образом, берём анализируемый сигнал и продолжаем разбивать его на сигналы, состоящие из чётных и нечётных индексов до тех пор, пока не получим набор сигналов из двух отсчётов. На рисунке ниже показан пример такого разбиения для сигнала из восьми отсчётов.

Алгоритм БПФ с прореживанием по времени для N=8

Для вычисления ДПФ такого сигнала требуется 3 стадии разбиения. На первом этапе получаем набор из четырёх ДПФ от сигналов из двух отсчётов:

$\begin X_[0] = x[0] + W_2^0 x[4]\\ X_[1] = x[0] - W_2^0 x[4]\\\\ X_[0] = x[2] + W_2^0 x[6]\\ X_[1] = x[2] - W_2^0 x[6]\\\\ X_[0] = x[1] + W_2^0 x[5]\\ X_[1] = x[1] - W_2^0 x[5]\\\\ X_[0] = x[3] + W_2^0 x[7]\\ X_[1] = x[3] - W_2^0 x[7] \end$

Далее, на основе полученных результатов формируется два ДПФ для сигналов, состоящих из четырёх отсчётов:

$\begin X_[0] = X_[0] + W_4^0 X_[0]\\ X_[1] = X_[1] + W_4^1 X_[1]\\ X_[2] = X_[0] - W_4^0 X_[0]\\ X_[3] = X_[1] - W_4^1 X_[1]\\\\ X_[0] = X_[0] + W_4^0 X_[0]\\ X_[1] = X_[1] + W_4^1 X_[1]\\ X_[2] = X_[0] - W_4^0 X_[0]\\ X_[3] = X_[1] - W_4^1 X_[1] \end$

И на последнем этапе формируются итоговые результаты восьмиточечного ДПФ:

$\begin X[0] = X_[0] + W_8^0 X_[0]\\ X[1] = X_[1] + W_8^1 X_[1]\\ X[2] = X_[2] + W_8^2 X_[2]\\ X[3] = X_[3] + W_8^3 X_[3]\\ X[4] = X_[0] - W_8^0 X_[0]\\ X[5] = X_[1] - W_8^1 X_[1]\\ X[6] = X_[2] - W_8^2 X_[2]\\ X[7] = X_[3] - W_8^3 X_[3] \end$

Если количество отсчётов исходного сигнала , где — целое положительное число, то его разбиение на сигналы, состоящие из чётных и нечётных индексов вплоть до последнего уровня можно сделать легко и за одну итерацию с помощью двоично-инверсной перестановки.

Для этого записываем индексы всех отсчётов в двоичной системе счисления, при этом должны быть записаны все бит индекса, включая ведущие нули. Затем зеркально отображаем код каждого из этих двоичных чисел и записываем полученные результаты обратно в десятичную систему счисления. Готово! Если расставить элементы исходного массива в соответствии с полученными индексами, мы получим подряд идущие пары отсчётов для двухточечного ДПФ. Пример, как это работает для сигнала из восьми отсчётов, представлен в таблице:

Номер до перестановки	Двоичное	Двоично-инверсная перестановка	Десятичное
0	000	000	0
1	001	100	4
2	010	010	2
3	011	110	6
4	100	001	1
5	101	101	5
6	110	011	3
7	111	111	7

Можете сравнить с рисунком выше, действительно совпадает. Именно поэтому, рассматриваемые нами алгоритмы также называются БПФ по основанию два. У них есть одно небольшое ограничение — количество отсчётов анализируемого сигнала должно быть равно степени двойки (например, 16, 32, 64, 128, 256 и т.д.). “Но как же быть, если, скажем, в моём сигнале всего 200 отсчётов?” — спросите вы. Ничего страшного, нужно просто дополнить сигнал нулевыми отсчётами, пока его длина не станет равна ближайшей степени двойки.

Как вы догадались из названия раздела, прореживать можно не только время, но ещё и частоту. Граф “бабочка” для БПФ с прореживанием по частоте показан на рисунке:

Граф “бабочка” для БПФ с прореживанием по частоте

Подробно рассматривать данный алгоритм не будем, просто примем его как данность. Пример БПФ с прореживанием по частоте для сигнала, состоящего из 8 отсчётов показан ниже:

Алгоритм БПФ с прореживанием по частоте для N=8

Прореживание (двоично-инверсная перестановка) в данном случае производится уже после вычисления ДПФ, т.е. по частотным отсчётам, отсюда и такое название.

По количеству операций умножения данный алгоритм схож с алгоритмом прореживания по времени, поэтому эффективность их схожая. Какой метод выбрать — решать вам.

В вышеупомянутых “бабочках” есть множитель . Он называется поворотным коэффициентом. На нижнем уровне БПФ, когда имеем дело с двумя отсчётами, требуется всего один поворотный коэффициент . Умножение на единицу считается тривиальной операцией, откуда следует, что на первом уровне не требуется ни одной операции умножения, только сложение и вычитание.

На втором уровне у нас получается два поворотных коэффициента и . Умножение на также делается просто: нужно поменять местами действительную и мнимую часть, а также инвертировать знак мнимой части. На этом уровне также не требуется операций умножения.

На следующем уровне требуется четыре поворотных коэффициента , , и , их значения мы рассчитывали в начале нашей статьи.

Давайте проиллюстрируем на графике все упомянутые выше поворотные коэффициенты (и даже немного больше):

Из графика видно, что на каждом следующем уровне количество поворотных коэффициентов увеличивается в два раза, при этом половина из них совпадает с поворотными коэффициентам предыдущего уровня.

Когда БПФ используется для решения каких-либо задач в устройствах цифровой обработки сигналов, количество отсчётов анализируемого сигнала как правило заранее известно и скорее всего не будет меняться в процессе работы устройства. Поэтому, чтобы не тратить время на вычисление , их заранее рассчитанные значения для заданного количества отсчётов и всех уровней разбиения записывают в памяти в виде таблицы констант, которые в дальнейшем будут использоваться для умножения в графах “бабочка”.

$\frac БПФ — это всего лишь алгоритм эффективного вычисления ДПФ, поэтому результаты вычисления БПФ и ДПФ получаются абсолютно идентичны. Для вычисления ДПФ сигнала, состоящего из отсчётов нам требуется вычислений с комплексными числами, в случае с БПФ — \log_2$
вычислений с комплексными числам.

Чтобы наглядно продемонстрировать эффективность алгоритма, давайте взглянем на таблицу:

Кол-во отсчётов, N	Количество вычислений с комплексными числами		Эффективность
Кол-во отсчётов, N	ДПФ	БПФ	Эффективность
256	65 536	1 024	64:1
512	262 144	2 304	114:1
1024	1 048 576	5 120	205:1
2048	4 194 304	11 264	373:1
4096	16 777 216	24 576	683:1

Особенно заметен прирост эффективности с увеличением количества отсчётов.

Алгоритмы быстрого преобразования Фурье (БПФ) − это способы быстрого вычисления ДПФ, устраняющие свойственную ДПФ вычислительную избыточность. Они были впервые предложены в 1965 году американцами Кули и Тьюки и относятся к базовым алгоритмам ЦОС в частотной области. Алгоритмы основываются на свойствах комплексной

и периодичности W kn

периодом, равным длине обрабатываемой реализации сигнала N (числу точек БПФ). С учетом последнего свойства экспоненте W N pkn = W N kn / p

соответствует период N/p , где p – целые числа, на которые делится N . Использование данных свойств в алгоритмах БПФ исключает большое число повторяющихся при вычислении ДПФ операций.

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

Разбиение означает прореживание последовательностей во временной или в частотной области. В связи с этим различают БПФ с прореживанием по времени и БПФ с прореживанием по частоте .

В отличие от ДПФ, БПФ может вычисляться только по определенному числу точек N , соответствующему целой степени его основания m : N = m L , где L – это число этапов прореживания : L = log m N . К наиболее используемым относятся БПФ по основаниям т = 2, 4, 8, но чаще всего применяют БПФ по основанию 2 .

Как показано в [40], главе 5, с помощью БПФ вычисляется также и обратное ДПФ (ОДПФ).

8.2. АЛГОРИТМ БПФ С ПРОРЕЖИВАНИЕМ ПО ВРЕМЕНИ ПО ОСНОВАНИЮ 2

Пусть задана последовательность x(n) N конечной длины N, n = 0, 1,.N – 1.

Нужно найти ее ДПФ: X ( jk ) = ∑ x( n )W N kn для k = 0, 1. N – 1 (номера n = 0

бинов ДПФ) с минимальным объемом вычислений.

Решение этой задачи в данном алгоритме БПФ находится следующим образом.

Исходную последовательность x(n) длиной N разобьем на 2 подпоследовательности длиной N/2 – четную (включающую отсчеты x(n) с

четными индексами n : x 1 (n) = x(2n) и нечетную : x 2 (n) = x(2n + 1), n = 0,

1. (N/2) – 1. Это соответствует первому прореживанию сигнала по времени

0 1 2 3 4 5 6 7 8 9 10 N – 1

Рис. 8.1. Иллюстрация прореживания сигнала по времени

Обозначим их ДПФ как X 1 (jk) N/2 и X 2 (jk) N/2 . Выразим ДПФ исходной последовательности x(n) N через ДПФ подпоследовательностей x 1 (n) N/2 , x 2 (n) N/2 :

N k = X 1 ( jk + ) W N K X 2 ( jk ) , (8.1)

Это первые N/2 частотных выборок ДПФ.

Вторую половину частотных выборок X(jk) для k = (N/2), … (N – 1) найдем с учетом свойства периодичности:

Выражения (8.1), (8.2) определяет базовую операцию БПФ (операцию

множитель W N k , равный по модулю единице, называют

поворачивающим . Вычисления в соответствии с (8.3) включают одно комплексное умножение и пару сложения–вычитания.

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

Рис. 8.2. Сигнальный граф базовой операции БПФ

сложения (верхний выход) и

соответствует умножению на

поворачивающий множитель W N k .

Сигнальный граф алгоритма БПФ получается в виде совокупности графов базовых операций. Для первого этапа прореживания он показан на рис. 8.3 для случая N = 8.

Рис. 8.3. Сигнальный граф БПФ для первого этапа прореживания

Оценим требуемый объем вычислений в соответствии с данным графом по числу операций умножения:

для ДПФ K умн.ДПФ = N 2 ; для БПФ K умн.БПФ = 2( N /2) 2 + N /2 = N 2 /2 + N /2.

Как видим, в результате однократного прореживания объем вычислений уменьшился примерно в 2 раза.

Дальше каждую из последовательностей x 1 (n) и x 2 (n) можно разбить еще на две подпоследовательности вдвое меньшей длины: x 11 (n), x 12 (n) и x 21 (n), x 22 (n) (четную и нечетную) и повторить вышеприведенные операции объединения их ДПФ с помощью базовых операций. Такое прореживание

выполняем L раз до получения N/2 двухточечных последовательностей x l (0), x l (1) , ДПФ которых вычисляется тривиально: X l (j0) = x l (0) + W 2 0 x l (1), X l (j1) = x l (0) − W 2 0 x l (1). В результате получаем полный граф БПФ , показанный на рис. 8.4 для N = 8.

x p (1) = x(4) x p (2) = x(2)

x p (4) = x(1) x p (5) = x(5) x p (6) = x(3) x p (7) = x(7)

Рис. 8.4. Полный граф БПФ для N = 8

В соответствии с графом на каждом из L этапов вычисления–объединения ДПФ выполняются N/2 базовых операций, а общий объем вычислений для комплексных операций умножения и сложения − вычитания составляет:

log 2 N , K слож.БПФ = NL = N log 2 N .

Число операций с вещественными числами в 4 раза больше для умножения и в 2 раза больше для сложения–вычитания. Выигрыш БПФ относительно ДПФ по числу операций умножения K умн.ДПФ /K умн.БПФ = 2N/log 2 N. Так, при

N = 2 10 = 1024 K умнБПФ = 5120, K умнДПФ ≈ 10 6 , выигрыш равен 204,8.

Выделенные на рис. 8.4 узловые точки графа соответствуют ячейкам оперативной сигнальной памяти . Так как вычисления выполняются поэтапно, то возможно замещение ячеек памяти, определяющее общую требуемую сигнальную память в объеме , равном 2N ячеек для N

комплексных чисел (их реальной и мнимой части). При этом используемые ячейки памяти на входе графа с N отсчетами входного сигнала x(n) (в общем случае комплексного) замещаются в конечном итоге N комплексными частотными выборками БПФ X(jk) .

Особенностью алгоритма БПФ с прореживанием по времени является требуемый им неестественный порядок отсчетов входного сигнала ,

обусловленный его многократными разбиениями на четные и нечетные подпо-следовательности ( n = 0, 4, 2, 6, 1, 5, 3, 7 для N = 8). Такой порядок следования называют двоично-инверсным . Это приводит к необходимости предварительной перестановки отсчетов исходной последовательности до начала вычислений. Для этого естественные номера отсчетов последовательности x(n) представляются в L -разрядном двоичном коде, коды эти прочитываются в обратном порядке, т. е. справа налево и преобразуются

затем снова в десятичную форму, соответствующую номеру отсчета переставленной последовательности x(p) .

Например, для графа рис. 8.4 отсчету n (10) = 4 исходной последовательности x(n) в десятичной системе соответствуют двоичный код

n (2) = 100, двоично-инверсный (перевернутый) код n дв.инв. = 001 и десятичный номер p = 1 отсчета переставленной последовательности x(p) .

8.3. ГРАФ-СХЕМА АЛГОРИТМА ПРОГРАММНОЙ РЕАЛИЗАЦИИ БПФ

С ПРОРЕЖИВАНИЕМ ПО ВРЕМЕНИ ПО ОСНОВАНИЮ 2

Этапы вычисления–объединения ДПФ в соответствии с сигнальным графом рис. 8.4 следуют в порядке, обратном этапам прореживания сигнала, выполняемым при выводе алгоритма БПФ. На первом этапе вычисляются N /2 двухточечных ДПФ, каждому из которых соответствует одна базовая операция БПФ, на втором путем их попарного объединения с помощью двух

базовых операций вычисляются N /4

четырехточечных ДПФ и т. д., на L -м

этапе два ( N /2)-точечных ДПФ

с помощью N /2 базовых операций

объединяются в N -точечное ДПФ исходной последовательности. С учетом указанной закономерности процесс программного вычисления БПФ можно разбить на три вложенных цикла (в порядке их вложения):

по номеру этапа вычисления – объединения ДПФ i = 1, 2,…L (внешний);

по номеру вычисляемого ДПФ на i- м этапе l = 1, 2, …2 L – i ;

по номеру базовой операции вычисляемого ДПФ m = 1, 2, …2 i – 1 . Значения поворачивающих множителей для базовой операции на i -ом этапе

определяются обобщенным выражением

L − i , k = 0, 1, . ( N /(2 L – i + 1 ) ) –

В результате получается граф-схема алгоритма программной реализации БПФ, представленная на рис. 8.5. Она включает описание (объявление) используемых переменных, ввод N отсчетов обрабатываемой последовательности (вектора) x(n) (программная переменная X(n)), перестановку отсчетов в соответствии с правилом двоичной инверсии и формирование переставленной последовательности x(p) .

Поскольку сложность алгоритма растет квадратично относительно размера входного сигнала, можно достичь существенного ускорения вычисления если нам удастся свести расчет 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. Линейность. спектры x(k)>

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

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

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

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

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