6.5. ОБЩИЕ ОСОБЕННОСТИ АЛГОРИТМОВ БПФ

Выше были обсуждены основные принципы эффективного вычисления дискретного преобразования Фурье. При этом были использованы представления с помощью сигнальных

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

Из рассмотрения направленных графов предыдущих параграфов ясно, что имеется два важных аспекта в любом алгоритме БПФ. Первым являются доступ к данным и их запоминание в промежуточных массивах. Второй — конкретное осуществление вычислений типа «бабочки». Хотя направленные графы предыдущего параграфа передают самую сущность изображаемых ими алгоритмов, имеется масса деталей, связанных с этими основными аспектами, которые необходимо рассмотреть при осуществлении заданного алгоритма. В этом параграфе будут, обсуждены некоторые детали, которые имеют отношение к осуществлению алгоритмов БПФ. Как и прежде, мы будем рассматривать в основном алгоритмы для хотя большая часть материала применима также к общему случаю.

6.5.1. ИНДЕКСАЦИЯ

Рассмотрим в качестве примера алгоритм, изображенный на рис. 6. 10. В этом случае входные выборки должны иметь двоично-инверсный порядок для того, чтобы вычисления можно было бы выполнить с замещением. Тогда результат появится в обычном порядке. Как правило, последовательность представлена не в двоично-инверсном порядке, и поэтому первым шагом в осуществлении алгоритма на рис. 6.10 должен быть процесс перестановки выборок входной последовательности. Этот процесс для изображен на рис. 6.30.

Рис. 6.30. Сортировка с двоичной инверсией для

Из рисунка видно, что перестановка может быть сделана «с замещением». Это удобно сделать, используя индекс, который «считает» в двоично-инверсном порядке. (Граф такого двоичноинверсного счетчика дан в [7].) Предположим, что — обычный индекс, двоично-инверсный индекс. Тогда исходным массивом является Из рис. 6.30 замечаем, что при нет необходимости в перестановке, но при необходимо переставить Однако нужно быть уверенными, что эта перестановка будет сделана только 1 раз. Это можно обеспечить путем сравнения и I, осуществляя перестановку только при

Таким образом, простым алгоритмом двоично-инверсного упорядочивания является следующий алгоритм: пронумеровать последовательность изменяя от 0 до в обычном порядке, в то время как I изменяется от 0 до в двоично-инверсном порядке. При произвести перестановку

Получив входные выборки в двоично-инверсном порядке, можно перейти к первой ступени вычислений. В этом случае все множители равны и входами «бабочек» являются соседние элементы массива На второй ступени вычислений множителями являются либо либо степени а входы «бабочек» разнесены на две ячейки. На ступени множителями являются степени а входы «бабочек» разнесены на ячеек. Отметим, что если вычисления в «бабочках» начинаются с верхнего края направленного графа рис. 6.10, то степени должны появляться в обычном порядке. Вышеизложенное определяет способ доступа к данным на каждой стадии вычислений, который, конечно, зависит от графа алгоритма. Например, на ступени вычислений по рис. 6.12 узлы «бабочки» разнесены на коэффициенты являются степенями и в этом случае эти степени должны поступать в двоично-инверсном порядке. Входные выборки имеют обычный порядок, а выходные — двоично-инверсный порядок, так что может понадобиться их перестановка по указанному выше алгоритму.

В общем случае, если рассмотреть все направленные графы § 6.2 и 6.3, то увидим, что каждому алгоритму присущи свои проблемы индексации. Выбор конкретного алгоритма зависит от нескольких факторов. Преимуществом алгоритмов вычисления с замещением является эффективное использование памяти, хотя и требуется память с произвольным, а не последовательным доступом. Дополнительным недостатком этих алгоритмов является то, что либо входные, либо выходные выборки имеют двоично-инверсный порядок. К тому же, в зависимости от того, какой из алгоритмов выбран (с прореживанием по времени или по частоте), а также от необходимости упорядочения входных и выходных выборок, доступ к коэффициентам может быть либо в обычном, либо в двопчно-ннверсном порядке. Были рассмотрены алгоритмы быстрого преобразования Фурье, использующие память с последовательным, а не произвольным доступом, но опять же. либо входные, либо выходные выборки должны иметь двоично-инверсный порядок. Граф алгоритма может быть преобразован так, что входы, выходы и коэффициенты будут иметь обычный порядок, но тогда структура индексов такого алгоритма будет сложной и потребуется вдвое больше объем памяти с произвольным доступом. Следовательно, использование таких алгоритмов не представляется выгодным.

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

быть преобразованы только один раз, то, очевидно, двоично-инверсную перестановку можно сделать как на входе, так и на выходе. Однако в некоторых случаях данные сначала подвергаются прямому преобразованию, результат этого преобразования изменяется некоторым образом, а затем подвергается обратному преобразованию. Например, при реализации КИХ-цифровых фильтров при помощи дискретного преобразования Фурье отрезок входных данных преобразуется, умножается на ДПФ импульсной характеристики фильтра, и результат подвергается обратному преобразованию. В другом примере при вычислении авто- или взаимокорре-ляционной функции с помощью дискретного преобразования Фурье данные будут преобразовываться, умножаться на ДПФ и результирующее произведение будет подвергаться обратному преобразованию.

В тех случаях, когда два преобразования выполняются таким же образом, имеется возможность путем выбора подходящего алгоритма БПФ избежать двоичной инверсии. Например, при реализации КИХ-цифрового фильтра посредством ДПФ можно выбрать алгоритм прямого преобразования, использующий входные данные в обычном порядке, а ДПФ в двоично-инверсном порядке. При этом можно использовать как направленный граф рис. 6.12, основанный на прореживании по времени, так и граф рис. 6.18, основанный на прореживании по частоте. Разница между этими двумя формами графов состоит в том, что граф с прореживанием по времени использует коэффициенты в двоично-инверсном порядке, тогда как прореживание по частоте требует, чтобы коэффициенты поступали в обычном порядке.

При использовании любого из этих алгоритмов преобразованные данные появляются в двоично-инверсном порядке, и, следовательно, нужно будет запоминать ДПФ, соответствующее частотной характеристике фильтра в двоично-инверсном порядке. Тогда для обратного ДПФ можно выбрать алгоритм, который использует входные данные в двоично-инверсном порядке, а результаты выдает в обычном порядке. Здесь могут быть использованы как направленный граф рис. 6.10, основанный на прореживании по времени, так и граф рис. 6.21, основанный на прореживании по частоте. Однако граф рис. 6.10 использует коэффициенты в обычном порядке, тогда как для графа рис. 6.21 требуются коэффициенты в двоичноинверсном порядке. Для использования коэффициентов только в обычном (что предпочтительнее) или только в двоично-инверсном порядке необходимо, чтобы при использовании алгоритма с прореживанием по времени в случае прямого преобразования для обратного преобразования был выбран алгоритм с прореживанием по частоте; при этом коэффициенты должны быть в двоично-инверсном порядке. Если для прямого преобразования выбирается алгоритм с прореживанием по частоте, то для обратного преобразования должен быть выбран алгоритм с прореживанием по времени; при этом коэффициенты должны иметь обычный порядок.

6.5.2. КОЭФФИЦИЕНТЫ

Как было показано, коэффициенты могут понадобиться как в двоично-инверсном, так и в обычном порядке. В любом случае нужно либо запоминать таблицу, достаточную для нахождения всех необходимых значений, либо вычислять эти значения по мере необходимости. Первый способ имеет преимущество в скорости вычислений, но требует дополнительной памяти. Нам требуются при Таким образом, для полной таблицы значений необходимо комплексных запоминающих ячеек. В том случае, когда применяются алгоритмы с двоичноинверсным порядком коэффициентов, эту таблицу необходимо записать в память в двоично-инверсном порядке.

Вычисление коэффициентов по мере надобности дает экономию памяти, но менее эффективно с точки зрения быстродействия. Более высокая эффективность получается при применении рекуррентной формулы. Отметим, что в общем случае на каждой ступени вычислений все требуемые коэффициенты являются некоторыми степенями где зависит от алгоритма и ступени вычислений. Поэтому, если коэффициенты требуются в обычном порядке, то мы можем использовать рекуррентную формулу

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