Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 6.5. ОБЩИЕ ОСОБЕННОСТИ АЛГОРИТМОВ БПФВыше были обсуждены основные принципы эффективного вычисления дискретного преобразования Фурье. При этом были использованы представления с помощью сигнальных направленных графов, а не выписывались детально уравнения, соответствующие таким графам. По необходимости были приведены эти графы для частных значений Из рассмотрения направленных графов предыдущих параграфов ясно, что имеется два важных аспекта в любом алгоритме БПФ. Первым являются доступ к данным и их запоминание в промежуточных массивах. Второй — конкретное осуществление вычислений типа «бабочки». Хотя направленные графы предыдущего параграфа передают самую сущность изображаемых ими алгоритмов, имеется масса деталей, связанных с этими основными аспектами, которые необходимо рассмотреть при осуществлении заданного алгоритма. В этом параграфе будут, обсуждены некоторые детали, которые имеют отношение к осуществлению алгоритмов БПФ. Как и прежде, мы будем рассматривать в основном алгоритмы для 6.5.1. ИНДЕКСАЦИЯРассмотрим в качестве примера алгоритм, изображенный на рис. 6. 10. В этом случае входные выборки должны иметь двоично-инверсный порядок для того, чтобы вычисления можно было бы выполнить с замещением. Тогда результат появится в обычном порядке. Как правило, последовательность представлена не в двоично-инверсном порядке, и поэтому первым шагом в осуществлении алгоритма на рис. 6.10 должен быть процесс перестановки выборок входной последовательности. Этот процесс для
Рис. 6.30. Сортировка с двоичной инверсией для Из рисунка видно, что перестановка Таким образом, простым алгоритмом двоично-инверсного упорядочивания является следующий алгоритм: пронумеровать последовательность Получив входные выборки в двоично-инверсном порядке, можно перейти к первой ступени вычислений. В этом случае все множители равны В общем случае, если рассмотреть все направленные графы § 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. КОЭФФИЦИЕНТЫКак было показано, коэффициенты Вычисление коэффициентов по мере надобности дает экономию памяти, но менее эффективно с точки зрения быстродействия. Более высокая эффективность получается при применении рекуррентной формулы. Отметим, что в общем случае на каждой ступени вычислений все требуемые коэффициенты являются некоторыми степенями
для получения
|
1 |
Оглавление
|