Двоичная инверсия входной последовательности для

Номер	Двоичное представление	Двоичная инверсия	Двоично-инверсный десятичный номер
0 1 2 3 4 5 6 7	0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1	0 4 2 6 1 5 3 7

Для осуществления двоичной инверсии входной последовательности, очевидно, необходим соответствующий алгоритм и программа.

5. Еще одна особенность алгоритма БПФ заключается в том, что на всех этапах преобразования используются коэффициенты Существует несколько способов получения этих коэффициентов. Простейший из них – составление таблицы, к которой можно обращаться в процессе счета. Недостатком этого метода является то, что для хранения этих коэффициентов необходима дополнительная память примерно из ячеек, так что при больших значениях имеющийся объем памяти может оказаться недостаточным. Второй способ состоит в непосредственном вычислении коэффициентов с использованием стандартных подпрограмм расчета синуса и косинуса. Однако это связано с большими затратами времени, так как вычисление синуса и косинуса – достаточно продолжительная процедура.

Вычисление коэффициентов по мере необходимости экономит память, но менее эффективно с точки зрения быстродействия. Более высокой эффективности можно достичь при применении рекуррентной формулы. Поскольку необходимые коэффициенты имеют вид некоторой степени W_N, т. е. , где q зависит от самого алгоритма, так и от конкретного этапа, то в том случае, когда коэффициенты требуются в естественном порядке, можно использовать формулу

(1.164)

для получения l-го коэффициента по (l – 1)-ому.

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

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

В символике 0 порядок вычислительной сложности БПФ оцениваются как 0 в то время как при прямом вычислении ДПФ он равен 0(N²).

Наглядное представление о получаемом выигрыше в объеме вычислений можно получить из таблицы 1.8.

Таблица 1.8

Оценка выигрыша в количестве операций

N	Оценка вычислительной сложности		Оценка выигрыша
	Прямое вычисление ДПФ –	Вычисление с помощью БПФ
8 16 32 64 128 256 512 1024 2048	64 256 1024 4096 16 384 65 536 262 144 1 048 576 4 194 304	24 64 160 384 896 2048 4096 10 240 22 528	2,7 4,0 6,4 10,7 18,3 32,0 56,9 102,4 186,2

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

Как видно из таблицы, алгоритмы БПФ позволяют уменьшить число операций в раз, где m – степень 2