10.3. Нумерация при БПФ. Двоичная инверсия и разрядная инверсия для алгоритмов БПФ с постоянным основанием

Начнем с очень простого примера, иллюстрирующего, каким образом выходные гармоники БПФ с замещением оказываются переставленными, в результате чего  размещается, вообще говоря, не в -м регистре, хотя отсчет  находился в нем. Пусть задана четырехточечная последовательность . Ее ДПФ равно

,

Выполним эти вычисления с помощью четырехточечного БПФ по схеме, изображенной на фиг. 10.9. Заметим, что  и  поменялись местами, т.е. гармоники оказались переставленными.

Фиг. 10.9. Алгоритм четырехточечного БПФ по основанию 2 с прореживанием по частоте и с замещением.

Фиг. 10.10. Иллюстрация двоичной инверсии для 16-точечного БПФ с помощью последовательности матричных перестановок.

Такую перестановку, характерную для БПФ, можно объяснить, используя описанную в гл. 6 возможность выполнения одномерного ДПФ по схеме двумерного ДПФ. Существенно, что результат преобразования имеет матричную перестановку. Если рассматривать алгоритм БПФ как последовательность прореживаний (путем представления одномерных массивов двумерными), то перестановку гармоник можно рассматривать как результат выполнения последовательности матричных перестановок в массивах уменьшающихся размеров, как показано на фиг. 10.10 для 16-точечного БПФ.

Оказывается, что в алгоритмах БПФ с постоянным основанием порядок следования гармоник достаточно просто определяется порядком следования входных отсчетов. Правило определения порядка на выходе, которое будет сначала просто сформулировано, а затем и доказано, известно под названием двоичной инверсии для БПФ с основанием 2 или (в общем случае) разрядной инверсии для основания , причем номера отсчетов в последнем случае записываются в -ичной системе счисления. Так, если при БПФ с основанием 2 отсчет  находится в -м регистре, причем  представляется двоичным числом вида  (т. е. 6-разрядным адресом, в котором  равны нулю или единице), то выходная гармоника  окажется в регистре с адресом , для которого расположение двоичных разрядов оказывается инверсным. Все сказанное справедливо и для БПФ с основанием 4, когда  представляют собой четверичные цифры, принимающие значения 0, 1, 2 или 3; для алгоритмов с основанием 8  будут восьмеричными цифрами.

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

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

Заметим далее, что если, то умножение двоичного числа на 2 по модулю эквивалентно круговому сдвигу разрядов по часовой стрелке на одну позицию. Аналогично умножение на 4 по модулю  эквивалентно круговому сдвигу по часовой стрелке на две позиции или на один четверичный разряд. В общем случае умножение на  по модулю  соответствует круговому сдвигу по часовой стрелке на один -ичный разряд.

Рассмотрим, что произойдет при выполнении в r-ичном числе определенной последовательности таких круговых сдвигов на r-ичный разряд. Пусть исходное число имеет вид

1. Сдвинем по кругу все шесть разрядов:

2. Сдвинем по кругу пять старших разрядов:

3. Сдвинем по кругу четыре старших разряда:

4. Сдвинем по кругу три старших разряда:

5. Сдвинем по кругу два старших разряда:

Теперь остается доказать, что при БПФ с основанием r перестановку гармоник можно описать инверсией разрядов. Начнем с представления исходного массива в виде матрицы размером . Этапу 1 соответствует матричная перестановка всего массива. После нее каждый из  столбцов (размером по ) также следует представить матрицей размером. Преобразование каждой из этих матриц связано с круговым сдвигом всех разрядов, за исключением младшего. Аналогично при переходе от этапа к этапу будет сдвигаться все меньшее число старших разрядов. Поясним сказанное на примерах. Рассмотрим 16-точечное ДПФ по основанию 2 с прямым порядком следования исходных отсчетов. Выберем алгоритм с прореживанием по частоте и будем выполнять по строкам двухточечные ДПФ. Порядок размещения результатов будет описываться круговым смещением разрядов на этапе 1 и соответствовать матричной перестановке исходного массива. Подчеркнем, что адрес каждого регистра заменяется на новый, получаемый на этапе 1 описанного выше процесса разрядной инверсии. Но каждый из столбцов, используемых на этапе 1 разрядной инверсии, представляется матрицей из элементов, так что их адреса изменяются в соответствии с этапом 2 процесса разрядной инверсии. Рассматривая, наконец, каждый столбец этапа 2 инверсии как матрицу из элементов, получаем перестановку выходных результатов, действительно являющуюся двоичной инверсией. Важно не забывать, что адреса регистров соответствуют геометрическому положению чисел и считаются в процессе преобразования неизменными. Так, например, после выполнения всего алгоритма в регистре 14 находится седьмая гармоника, в регистре 5 — десятая и т. д.

Алгоритм с основанием 4

Если число N является степенью 4, то его можно записать как ; аналогично  и т. д. В результате элементы исходного одномерного массива можно расположить таким образом, чтобы элементарные операции представляли собой четырехточечные  ДПФ. Простой пример для  показан на фиг. 10.11.

Фиг. 10.11. 16-точечное БПФ с основанием 4.

Фиг. 10.12. 16-точечное БПФ по основанию 4 с прореживанием по частоте, прямым порядком на входе и четверично-инверсным на выходе.

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

Фиг. 10.13. 16-точечное БПФ по основанию 4 с прореживанием по времени и с замещением, нормальным порядком на входе и четверично-инверсным на выходе.

Таким образом, на фиг. 10.12 эти кружки представляют четырехточечные ДПФ, а умножения на поворачивающие множители изображены, как и на схемах БПФ с основанием 2, стрелками. Ячейки памяти также представлены точками и пронумерованы сверху вниз, причем номера регистров не приводятся.

По аналогии с БПФ по основанию 2 возможны варианты БПФ по основанию 4 с прореживанием по частоте и по времени. Первый вариант представлен на фиг. 10.12, а второй — на фиг. 10.13.

Интересно сравнить количество арифметических операций, выполняемых в схемах фиг. 10.12 и 10.13 и в любой из 16-точечных структур с основанием 2, приведенных на фиг. 10.1—10.8. Во втором случае используются 10 нетривиальных комплексных умножений (тривиальными являются умножения на  или на ). Аналогичный подсчет для БПФ с основанием 4 дает восемь таких умножений. Таким образом, уже отсюда видно, что эффективность различных структур БПФ с одинаковыми конечными результатами неодинакова. Но решение вопроса о том, выгодно ли применение алгоритма БПФ с основанием 4, зависит в каждом конкретном случае от большого числа факторов и здесь не рассматривается.

На фиг. 10.14 изображена схема алгоритма БПФ с основанием 4 для массива из 64 отсчетов. Чтобы понять, каким образом в этом алгоритме осуществляется прореживание, будем считать, что первые 16 отсчетов образуют первую строку матрицы из 16 столбцов И 4 строк, следующие 16 отсчетов составляют вторую строку и т. д. На первом этапе алгоритма фиг. 10.14  выполняется  16 четырехточечных ДПФ от  элементов каждого столбца. Затем производятся повороты, причем показатели экспонент поворачивающих множителей указаны перед обозначением ячеек памяти второго этапа. Затем все четыре строки прореживаются путем формирования из них матриц размером (4х4) и преобразуются по схеме 16-точечного БПФ с основанием 4, но с другими поворачивающими множителями.

Фиг. 10.14. 64-точечное БПФ по основанию 4 с прореживанием по частоте, нормальным порядком на входе и четверично-инверсным на выходе.

На первом этапе алгоритма фиг. 10.14 выполняется 16 четырехточечных ДПФ от элементов каждого столбца. Затем производятся повороты, причем показатели экспонент поворачивающих множителей указаны перед обозначением ячеек памяти второго этапа. Затем все четыре строки прореживаются путем формирования из них матриц размером  и преобразуются по схеме 16-точечного БПФ с основанием 4, но с другими поворачивающими множителями.

Алгоритм фиг. 10.14 можно рассматривать как вариант БПФ с прореживанием по частоте, так как повороты производятся после ДПФ. Можно построить и алгоритм с прореживанием по времени, но для этого придется переходить от матриц меньшего размера к более крупным матрицам. Читателю, вероятно, интересно самому найти значения поворачивающих множителей для варианта алгоритма фиг. 10.14 с прореживанием по времени. Как получить нужный результат, исходя из повторяющейся процедуры сведения матрицы к четырехточечным ДПФ?