# Вторая пачка часть 95

Вызывающая в общем слу¬чае большие за¬тра¬ты времени двоичная инверсия мо¬жет быть при N = 2n эффективно осуществлена с по¬мощью метода пе¬ре¬ста¬нов¬ки данных, использующего толь¬ко десятичную ариф¬метику в соответствии с ал¬го¬рит¬мом, пред-ло¬жен¬ным Н.Ахмедом и К.Р.Рао [1980], суть которого за¬клю¬ча¬ется в следующем. 1. Число N выражается в терминах n множителей: ns= N/2s , s=1,2,......, n=log2 N. (9.17) 2. Формируется таблица T следующего вида: 0 n1 n2 (n1 + n2 ) n3 (n1 + n3 ) (n2 + n3 ) (n1 + n2 + n3 ) n4 (n1 + n4 ) (n2 + n4 ) (n1 + n2 + n4 ) ... . . . nn , элементы которой представляют собой двоичную ин¬вер¬¬сию {k} = {0, n1 , n2 , (n1 + n2 ), n3 , (n1 + n3 ), ..., (n1 + n2 + ... + nn ) } исходной "естественной" последовательности {m}. На¬при¬¬мер, для N=8 имеем: n1 =4, n2 =2, n3 =1 и вместо ис¬ход¬ной последовательности {m}={0,1,2,3,4,5,6,7} по¬лу¬чим инвертированную: {k}={0,4,2,6,1,5,3,7}. Принимая во внимание изложенное, процедуру, ре¬а¬ли¬зующую алгоритм Кули - Тьюки вычисления БПФ, мож¬¬но сформулировать следующим образом [Бе¬ла¬шо-ва, Белашов, 1990]. 1. Получение методом перестановки инвертирован¬ной последовательности {k} из ряда {m}, пред¬став¬лен¬но¬¬го в естественном порядке, в соотвествии с формулой (9.17). 2. Получение последовательности степеней W (см. фор¬¬мулы (9.14)) с показателями, представляющими со¬бой последовательность {k}: 3. Выполнение n = log2 N итераций согласно графу, при¬мер которого для N = 8 показан на рис. 9.1. При этом каждой группе i-й итерации соответствует свой множитель из последовательности {W(k)}. По¬лу¬чен¬¬ные после i-й итерации промежуточные значения за-писываются на место исходного массива {X(m)}, что, как видно из рис. 9.1, вполне осуществимо при ите¬рационном методе реализации алгоритма БПФ и да¬ет значительную экономию оперативной памяти. 4. Вычисление коэффициентов Cx(k) по формуле (9.14а). Замечание. Рассмотренный алгоритм БПФ не за¬ви¬сит от того, являются ли исходные величины X(m) дей¬ст¬ви¬тельными или комплексными

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа