10.2. Обзор теоретических основ БПФ

Как уже отмечалось в гл. 6, БПФ можно выполнять по схемам с замещением и без замещения. В первом случае результаты всех ДПФ, которые используются при выполнении БПФ, засылаются в те же регистры, откуда были взяты исходные числа. Например, в 16-точечном БПФ (фиг. 10.1) при выполнении на первом этапе двухточечного ДПФ, обозначенного верхним незачерненным кружком, используется содержимое нулевого и восьмого регистров. Обозначим эти числа через  и . Результатами двухточечного ДПФ являются  и  причем  заносится в регистр на место , a замещает .

В алгоритме с замещением выходные гармоники всегда оказываются переставленными. Для БПФ с основанием 2 (фиг. 10.1) эта перестановка соответствует двоичной инверсии номеров гармоник. В разд. 10.3 будет рассмотрен характер перестановки гармоник при использовании более высоких оснований.

Как было показано в гл. 6, в алгоритмах БПФ могут использоваться прореживание по времени и прореживание по частоте. При прореживании по времени умножение на поворачивающие множители предшествует выполнению в вершинах графа двухточечных ДПФ, а при прореживании по частоте оно выполняется вслед за ДПФ. На фиг. 10.1 показаны два набора поворачивающих множителей, один из которых используется при прореживании по времени, а другой — по частоте. Стрелки с числами возле них соответствуют умножению на ,  где  - число, записанное около стрелки. Данная структура может быть использована также в случае, когда исходные отсчеты расположены в двоично-инверсном порядке. При этом выходные гармоники будут размещаться в нормальном порядке.

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

Фиг. 10.2. Алгоритм БПФ с замещением, двоично-инверсным порядком отсчетов на входе и прямым на выходе (для прореживания по времени множители расположены слева от вершин графа, для прореживания по частоте - справа).

На фиг. 10.2 изображена другая схема алгоритма с теми же свойствами. Здесь также показаны варианты прореживания по частоте и по времени.

Если не будет оговорено особо, то будем считать, что регистры на схемах нумеруются сверху вниз и их номера на схемах не приводятся. Числа, указанные на фиг. 10.1 и 10.2 на входах и выходах, представляют собой номера входных отсчетов и выходных гармоник.

Алгоритм 16-точечного БПФ с основанием 2 и постоянной структурой на всех этапах показан на фиг. 10.3. Здесь результаты базовой операции не возвращаются в те регистры, откуда были взяты исходные числа, поэтому этот алгоритм относится к алгоритмам без замещения. На всех этапах характер нумерации не меняется, что позволяет в некоторых случаях упростить программы или аппаратуру. Входные отсчеты располагаются в нормальном порядке, а выходные гармоники — в двоично-инверсном. Вообще справедливо следующее правило: при работе с замещением необходимо  комплексных регистров, при работе без замещения —  комплексных регистров. На фиг. 10.4 представлен алгоритм с постоянной структурой, в котором входные отсчеты располагаются в двоично-инверсном порядке, а выходные гармоники — в прямом. Поворачивающие множители для вариантов прореживания по времени и по частоте можно найти из схемы алгоритма фиг. 10.3, рассматривая ее от выхода к входу и поменяв направления всех стрелок. На фиг. 10.5 представлен алгоритм, в котором за счет работы без замещения удается избежать двоичной инверсии выходных гармоник. Здесь показан только вариант прореживания по времени. Вариант прореживания по частоте нетрудно получить, переместив стрелки за вершины графа.

Фиг. 10.3. Алгоритм 16-точечного БПФ по основанию 2 с постоянной структурой, без замещения, с нормальным порядком отсчетов на входе и двоично-инверсным на выходе (показаны множители для прореживания по времени и по частоте).

Фиг. 10.4. Алгоритм 16-точечного БПФ по основанию 2 с постоянной структурой, без замещения, с двоичной инверсией на входе и прямым порядком на выходе.

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

На фиг. 10.6 представлена разновидность алгоритма БПФ, позволяющая использовать преимущества сверхоперативного запоминающего устройства. Особенности аппаратурной реализации этой структуры будут рассмотрены позднее; отметим лишь, что вершины графа можно объединить в пары и выполнять сразу по две базовые операции над четырьмя отсчетами, так что для этих отсчетов будут проведены сразу два этапа БПФ, и только после этого будут аналогично обрабатываться следующие четыре отсчета. Допустим, например, что отсчеты 0 и 8 поступают в нулевую вершину нулевого этапа БПФ, а отсчеты 4 и 12 — в четвертую вершину того же этапа. После выполнения этих двух базовых операций перейдем к вершинам 0 и 4 первого этапа и убедимся, что для них все исходные числа снова размещаются в тех же четырех регистрах с номерами 0, 4, 8 и 12. Содержимое регистров 1, 5, 9 и 13 можно также пропустить сразу через два этапа БПФ. Таким образом, если арифметическое устройство способно обрабатывать не два, а сразу четыре отсчета, то необходимое число циклов обращения к памяти может быть сокращено в два раза. Данную структуру можно рассматривать как алгоритм с замещением, в котором выполняются сразу два этапа, поэтому порядок результатов будет двоично-инверсным.

Фиг. 10.6. Алгоритм 16-точечного БПФ по основанию 2 с совместным выполнением двух этапов над четырьмя отсчетами без промежуточных обращений к ЗУ. Входные отсчеты — в прямом порядке, выходные — переставлены (но не в двоично-инверсионном порядке).

Фиг. 10.7. Алгоритм БПФ с прореживанием по частоте и совместным выполнением двух этапов, устраняющий двоичную инверсию на выходе.

Фиг. 10.8. Алгоритм с совместным выполнением двух этапов, допускающий двукратное распараллеливание.

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

На фиг. 10.8 представлен еще один алгоритм с одновременным выполнением двух базовых операций, который отличается от алгоритма фиг. 10.7. Здесь регистры ЗУ организованы так, чтобы можно было считывать (или записывать) одновременно по два комплексных слова. Так, например, отсчеты 0 и 8 считываются для выполнения базовой операции параллельно, за счет чего удается сэкономить один цикл обращения к памяти. В расположенной справа таблице показана желательная группировка отсчетов на различных этапах БПФ. Чтобы осуществить ее и обеспечить параллельную работу, необходимо одновременно поменять местами четыре совместно обрабатываемых отсчета. Например, отсчеты 0, 8 и 4, 12 переставляются, а затем обрабатываются пары отсчетов 0, 4 и 8, 12. Снова напомним, что регистры на схеме пронумерованы. Конечные результаты (правая колонка чисел) показывают, что выходные гармоники переставлены, причем перестановка является результатом инверсии и матричной перестановки, получающейся при заполнении матрицы размером  по строкам с последующим чтением ее по столбцам.