Обозначим. Графическое представление вычислительных операций приведено на рисунке

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

где

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru .

Учтем, что,

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Поэтому

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Графическое представление вычислительных операций приведено на рисунке.

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Стрелочками представлены множители

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru .

Отсчеты S0 , S1 , S2, S3 получаются с использованием операции сложения, поэтому около них стоит знак “ + “, отсчеты S4 , S5 , S6 , S7 находятся после выполнения операции вычитания и около них поставлен знак “ - “.

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

При N=2

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Последовательности на входах четырех двухточечных блоков Индекс исходного сигнала Индекс сигнала после перестановки разрядов
Десятичная СС   Двоичная СС Двоичная СС   Десятичная СС
X110 = X10 = X0
X111 = X12 = X4
X120 = X11= X2
X121 = X13 =X6
X210 = X20 = X1
X211 = X22 = X5
X220 = X21 = X3
X221 = X23 =X7

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

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

На каждом шаге разбиения выполняется N / 2 умножений, количество шагов равно M = log 2 N.

Следовательно, количество умножений равно (N / 2) log2 N вместо N2 при ДПФ.

Величина выигрыша при переходе от ДПФ к БПФ увеличивается с увеличением количества отсчетов N.

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

Пусть имеется исходная N - точечная последовательность xn , где N = 2M. Разобьем члены этой последовательности на две группы. В первую включим первую половину членов исходной последовательности, а во вторую группу - вторую половину. Из первой группы образуем последовательность x1m , а из второй - последовательность x2m.

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Индексы последовательностей xn и x1m связаны соотношением n = m, а индексы последовательностей xn и x2m - соотношением n = N/ 2 + m.

Тогда

Обозначим. Графическое представление вычислительных операций приведено на рисунке - student2.ru

Наши рекомендации