З. Другие модификации БПФ.

Рассмотрим некоторые алгоритмы быстрых преобразовавдй, отличающиеся от традиционных алгоритмов БПФ (алгоритм Винограда преобразований Фурье — АВПФ и другие). К числу модифицированных алгоритмов БПФ относится алгоритм Рейдера - Бреннера, предусматривающий замену умножения комплексных чисел умножением комплексного числа на вещественное или мнимое число [170, 80]. При применении БПФ Рейдера-Бреннера уменьшается по сравнению с традиционными БПФ, описанными нами в разделах количество выполняемых умножений, хотя и производится несколько большее количество сложений. В целом этот метод выполнения БПФ, если оценивать его по количеству производимых арифметических действий, более эффективен, чем традиционные методы БПФ. То же самое относится и к алгоритму выполнения БПФ, предложенному Бруном [149, 80], в тех случаях, когда находятся ДПФ вещественных последовательностей: при вычислении

Рис. 3.9 (см. скан)

для них ДПФ этим методом в основном выполняются лишь вещественные операции, что упрощает процедуру вычисления.

Среди перспективных методов быстрых преобразований, служащих для нахождения ДПФ многоточечных последовательностей, отметим метод, в основе которого сочетание алгоритмов вычисления, предложенных Рейдером и Гудом [169, 157, 80].

Считается перспективным алгоритм Винограда преобразования Фурье (АВПФ), применение которого может быть эффективным при вычислении ДПФ как коротких последовательностей, так и последовательностей большой длины. В основе АВПФ представление матрицы -точечного ДПФ в виде произведения матриц -точечных ДПФ, где N есть произведение всех Для вычисления этих ДПФ используется круговая свертка

соответствующих последовательностей [181, 182, 183, 35, 80]. Структуру такого алгоритма выполнения ДПФ называют гнездовой. По некоторым оценкам АВПФ требует на 80% меньше операций умножения, чем традиционные БПФ [35]. Эффективным оказьюается, если иметь в виду уменьшение количества операций умножения, сочетание алгоритма АВПФ с упоминавшимся выше алгоритмом Рейдера [80]. Особенно эффективен АВПФ для вычисления ДПФ последовательностей вещественных величин.

В разделе А было отмечено, что количество выполняемых арифметических операций не является единственным критерием для оценки эффективности того или иного метода вычисления ДПФ. Согласно касающимся АВПФ суждениям, приведенным в книге [80], использование АВПФ позволяет экономить память при обработке вещественных данных. Это преобразование оказьюается целесообразным при обработке информации в реальном масштабе времени в условиях, когда недопустима задержка в ходе одновременной обработки двух последовательных блоков вещественных данных.

Чтобы имело существенные преимущества применение АВПФ, программа АВПФ должна быть эффективнее обычных программ выполнения БПФ. Разработаны программы реализации АВПФ [76]. Но при сравнении их с программами традиционных БПФ выясняется следующее. При выполнении БПФ по одному основанию, например по основанию 2 или 4, используются одни и те же подпрограммы, какой ни была бы длительность N последовательности, для которой производится преобразование. При выполнении же АВПФ последовательностей различной длительности в каждом случае используется особая вычислительная процедура. В связи с указанным по оценке, которая дана в книге [80], при сравнимых размерах дискретных преобразований Фурье программы АВПФ содержат большее число команд, чем программы БПФ. Кроме того, они содержат подпрограммы, осуществляющие выбор вычислительных процедур в зависимости от размера БПФ. С учетом этой особенности АВПФ в указанной книге описан способ организации структуры АВПФ, при котором суммарные затраты памяти для хранения данных и коэффициентов оказываются такими же, как и при применении БПФ обычного вида, а размеры программы лишь незначительно превышают размеры программ выполнения БПФ.

В том же источнике как важный вопрос указан и вопрос о шумах квантования при реализации АВПФ, возникающий из-за конечной разрядной сетки. Отмечено, что этот вопрос пока мало изучен, но предварительные результаты показывают, что соответствующее масштабирование на каждом этапе алгоритма более сложно, чем для БПФ. Это объясняется тем, что блоки алгоритма отличаются друг от друга. К тому же не все масштабирующие коэффициенты равны степени 2. При выполнении операций с фиксированной запятой указанное выше существенно влияет на отношение сигнал — шум АВПФ. Поэтому, если исходить из того, что допускаются такие же ошибки, как и при выполнении БПФ, то для представления данных в АВПФ требуется примерно на один-два бита больше.

Из сказанного следует, что имеются различные подходы к сравнительной оценке АВПФ и применяемых сейчас БПФ. Несмотря на указанные недостатки АВПФ, этот алгоритм представляет большой интерес. Широко ведутся работы, направленные на то, чтобы обеспечить возможность рационального его использования для быстрого выполнения ДПФ. Специалисты считают АВПФ эффективным алгоритмом вычисления ДПФ [35, 76, 80].

Упомянутые выше нетрадиционные методы быстрого выполнения ДПФ и сверток в большей своей части были разработаны на основе использования методов теории чисел и теории полиномиальных преобразований, отличающихся от других методов математического представления и обработки информации, ранее описанных в нашей книге. Теоретико-числовые и полиномиальные преобразования будут рассмотрены особо в § 9 этой главы. Будет показано, как они "используются при разработке новых способов выполнения быстрых преобразований Фурье и новых алгоритмов вычисления сверток.

Здесь были указаны лишь некоторые из перспективных методов вычисления ДПФ. Опубликованы статьи и книги, в которых описаны и другие методы. Названием некоторых из них подчеркнута связь их с методами построения определенных видов ЭВМ. Таким является, например, описанный в книге [35] метод, получивший название КОРДИК (CORDIC - Coordinate Rotation Digital Computer). В указанной книге описан также специальный вид ДПФ, названный нечетно-временным нечетно-частотным ДПФ, и описано выполняемое с использованием ДПФ дискретное косинусное преобразование (ДКП), рассматриваемое нами в гл. V. Все эти методы быстрых преобразований представляют интерес для области управления и связи.