Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
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), достаточно
запомнить или вычислить только множители
и
.