4.6. Перестановка данных

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

Шаг 1. Выразить N в терминах множителей

(4.6.1)

Шаг 2. Сформировать следующую таблицу :

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

(4.6.2)

В качестве примера рассмотрим случай . При этом формула (4.6.1) дает . Таблица имеет вид

и дает последовательность , которая представляет собой «переставленную» исходную последовательность, расположенную в естественном порядке .