6.4. Перестановка данных и двоичная инверсия

Еще одной особенностью алгоритма с прореживанием по времени (как, впрочем, и большинства других алгоритмов БПФ) является необходимость такой перестановки элементов входной последовательности, чтобы выходная последовательность  имела естественный (прямой) порядок расположения, т. е.  В примере на фиг. 6.3 для этого требовался следующий порядок размещения входной последовательности:  и . Характер перестановки элементов входной последовательности может быть описан сравнительно просто. Ниже будет показано, что в случае, когда  является степенью 2, входная последовательность должна быть расположена в памяти в двоично-инверсном порядке для того, чтобы выходная последовательность получалась в прямом порядке. Двоично-инверсный порядок определяется следующим образом. Если записать порядковые номера элементов входной последовательности в двоичном коде, используя  двоичных разрядов, причем , а затем инвертировать порядок следования разрядов, то получаемые при этом числа и будут номерами элементов входной последовательности после их перестановки. Так, для случая  прямой порядок номеров приведен в табл. 6.1 слева, а двоично-инверсный порядок - справа.

Табл. 6.1.

Номер	Двоичное представление	Двоичная инверсия	Двоично-инверсный номер
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

Фиг. 6.6. Блок-схема программы двоично-инверсного счётчика (предложенного Райдером).

Фиг. 6.7. Перестановка данных с замещением

Таким образом, для двоичной инверсии входной последовательности необходим соответствующий алгоритм. На фиг. 6.6 показан легко реализуемый двоично-инверсный счетчик, предложенный Рейдером. Начиная с первого двоично-инвертируемого числа  (с прямым номером 000 в табл. 6.1), алгоритм позволяет формировать последовательно все остальные двоично-инверсные номера. Половина из общего количества двоично-инверсных номеров формируется с использованием лишь двух операций, поскольку только в половине случаев старший значащий разряд  будет равен 1. Аналогично четверть всех двоично-инверсных номеров формируется с помощью трех операций и т. д. Таким образом, этот алгоритм является весьма аффективным.

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

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

                        (6.15)

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