Ж. Употребительные процедуры БПФ.

В некоторых случаях оказывается более удобным БПФ с прореживанием по времени, в других — БПФ с прореживанием по частоте. То и другое БПФ может выполняться с описываемым далее замещением или без замещения. Преимуществами БПФ с замещением являются сокращение общего числа комплексных умножений и возможность упрощения запоминания сигналов. Рассмотрим сначала БПФ с замещением при прореживании по времени.

При реализации алгоритмов с замещением данные, получаемые на каждой ступени выполнения БПФ, засылаются в те же регистры, из которых берутся исходные данные. Количество используемых регистров сокращается в два раза. Однако при выполнении БПФ с замещением порядок расположения выходных данных должен быть переставлен с упорядочением их по правилам двоичной инверсии по отношению к порядку входных данных. Если ввести обозначения для согласованных входной и выходной последовательностей, имея в виду ступень БПФ, и обозначения для всей входной последовательности при то, например, применительно к данным рис. 3.7, б будем иметь

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

Сравнивая двоичные числа в левой и правой частях каждого равенства, обнаруживаем, что они двоично-инверсны.

При двоичной инверсии данных граф каждой из основных элементарных операций представляется так, как показано на рис. 3.8, г или с учетом того, что как показано на рис. 3.8, д. При этом граф, изображенный на рис. 3.7, в, может быть преобразован к такому виду, когда на каждой ступени производится комплексных умножений и общее их количество становится равным Для запоминания отсчетов, отвечающих каждой из горизонтальных линий представленного на рис. 3.8, д элементарного графа, отводится одна и та же ячейка памяти. Изображенный на рис. 3.8, д граф основной элементарной операции отражает выполнение следующих действий: причем изменяются в функции от т.е. изменяются от ступени к ступени.

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

Употребительны алгоритмы БПФ по основанию 2, но используются также БПФ по основанию 4, а иногда - по основанию 8. Возможно применение БПФ и по другим основаниям, в общем случае — по смешанным основаниям.

БПФ по основанию 2 в принципе может использоваться не только при условии, что, как было указано, где k — целое число, но и тогда, когда для исходных данных это соотношение не имеет места: всегда можно к исходной последовательности добавить несколько точек с нулевыми отсчетами гак, чтобы для полученного нового значения N выполнялось условие

То, что применяются БПФ по основанию 4 и по основанию 8, связано с преимуществами в отношении объема вычислений, которое в некоторых случаях дает для больших N использование БПФ этого вида. Укажем, как выполняется БПФ по основанию 4, когда N является степенью 4. В этом случае N представляется как . Затем таким же образом представляется каждое из значений как и т.д. Элементарной операцией при этом является четырехточечное ДПФ. Рассмотрим в качестве примера, как получается четвертично-инверсный порядок на выходе при выполнении -точечного БПФ по основанию 4 с прореживанием по частоте. При прямом порядке расположения входных точек графа преобразования на выходе получается следующая четвертично-инверсная нумерация выходных отсчетов: 0, 4, 8, 12; 1,5,9, 13; 2, 6, 10,14; 3, 7, 11, 15. В случае реализации аналогичным способом БПФ-точечных последовательностей с большими N по основанию 8 элементарной операцией является -точечное ДПФ; при БПФ с прореживанием по частоте получается восьмерично-инверсный порядок на выходе.

В разных источниках даются различные оценки алгоритмов БПФ по основанию 2 и по другим основаниям, причем учитываются особенности аппаратурной или программной реализации БПФ. В работе [101] рекомендуется для выяснения того, какой из указанных выше алгоритмов более выгоден при той или иной реализации БПФ, в каждом конкретном случае проводить сравнительный анализ всех трех указанных алгоритмов БПФ, выясняя, какой из них обеспечивает минимальный объем вычислений.

БПФ допускает распараллеливание вычислительных операций (см., например, рис. 3.7, в и 3.8, а), что позволяет ускорить выполнение преобразования. Для параллельной обработки данных иногда бывает целесообразным использование специализированных ЭВМ. Применяются различные методы параллельного выполнения БПФ [101]. Производятся одновременно арифметические действия, обращение к запоминающему устройству и операции над командами; для обеспечения возможности

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

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

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

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

На графах, которые были нами до сих пор не показаны, отражены последовательно выполняемые на каждой ступени операции "бабочка". Однако при изменении системы упорядочения узлов уже не все ступени преобразования представляются на графе таким образом. Иллюстрацией служит показанный на рис. 3.9, а граф, являющийся перестроенным графом БПФ, ранее показанным на рис. 3.7, в; перегруппировка произведена здесь так, чтобы как входы, так и выходы имели обычный порядок [85]. Заметим также, что ранее указанные графы отражали процедуру БПФ в случае, когда N является степенью 2 (когда где целое число). При выполнении БПФ для последовательностей с не являющимся степенью 2, основной тоже остается операция "бабочка", но форма соединений между узлами графа оказывается на некоторых ступенях преобразования уже иной. В качестве примера сошлемся на приведенный в упомянутой выше книге граф вычисления -точечного БПФ при Рассмотрим только вторую ступень этого преобразования. На этой ступени производятся по одному и тому же алгоритму три шеститочечных преобразования. Граф одного из них показан на рис. 3.9, б.