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

Еще одной особенностью алгоритма с прореживанием по времени (как, впрочем, и большинства других алгоритмов БПФ) яв­ляется необходимость такой перестановки элементов входной последовательности, чтобы выходная последовательность X(k) имела естественный (прямой) порядок расположения, т. е. k=0,1,…. В примере на фиг. 6.3 для этого требовался следующий порядок размещения входной последовательности: x(0), x(4), x(2), x(6), x(1), x(5), x(3) и x(7). Характер перестановки эле­ментов входной последовательности может быть описан сравнительно просто. Ниже будет показано, что в случае, когда N яв­ляется степенью 2, входная последовательность должна быть рас­положена в памяти в двоично-инверсном порядке для того, чтобы выходная последовательность получалась в прямом порядке. Двоично-инверсный порядок определяется следующим образом.

Если записать порядковые номера элементов входной последова­тельности в двоичном коде, используя L двоичных разрядов, при­чем N=2^L, а затем инвертировать порядок следования разрядов, то получаемые при этом числа и будут номерами элементов вход­ной последовательности после их перестановки. Так, для случая N=8=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

Если записать порядковые номера элементов входной последова­тельности в двоичном коде, используя L двоичных разрядов, при­чем N=2^L, а затем инвертировать порядок следования разрядов, то получаемые при этом числа и будут номерами элементов вход­ной последовательности после их перестановки. Так, для случая N=8=2³ прямой порядок номеров приведен в табл. 6.1 слева, а двоично-инверсный порядок — справа.

1 Соотношение (6.10) является прямым следствием периодичнорсти ДПФ. Заметим также, что , так что формулу (6.10) можно переписать в виде:

2 Незачерненные кружки в правлй части фиг.6.1. обозначают операцию сложения/вычитания, причем верхний выход соотвествует сумме, а нижний – разности. Стрелка  обозначает операцию умножения на значение множителя a, указанного над стрелкой. Заметим, что кружок можно интерпретировать как двухточечное ДПФ. Узля обозначают регистры, содержащие входные и выходные массивы отдельных ДПФ. Все эти обозначения согласуются с правилами изображения направленных графов в теории линейных систем.