6.8. Единый подход к алгоритмам БПФ

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

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

Пусть, например, N = 60. Это число можно представить как произведение меньших чисел различным образом: и т. д. В зависимости от порядка следования сомножителей и их общего количества могут быть получены различные формы алгоритма БПФ. Для характеристики разложения обычно используется понятие «основание». Понятие «смешанное основание» означает, что не все сомножители N одинаковы. Для N = 60 все формы алгоритма БПФ имеют смешанные основания. Если N можно представить в виде произведения одинаковых сомножителей , то соответствующий алгоритм называют алгоритмом БПФ с основанием . Например, если то получаются рассмотренные в предыдущих разделах главы алгоритмы БПФ с основанием 2. Если же N записать как 64 = 8x8, то получится алгоритм БПФ с основанием 8.

Очень важно отметить, что разложение числа на множители можно выполнить различйыми способами. Так, N = 60 можно представить как 12 х 5, а затем 12 — как 4 х 3. С другой стороны, можно было бы записать , далее . Таким образом, для выявления общих закономерностей следует провести тщательный анализ свойств разложения очередного числа на два сомножителя. Возьмем в качестве примера снова N 60 и запишем одно из возможных разложений обрабатывавмого массива в виде матрицы из (5x12) номеров отсчетов сигнала:

Далее, поскольку столбцы содержат по 5 (т. е. простое число) отсчетов, они больше не могут быть разложены. Однако строки, состоящие из 12 отсчетов, можно представить в виде матриц размером (3x4). Например, первая строка будет иметь вид

Остальные строки можно представить аналогично. Итак, теперь нужно установить, каким образом, оперируя с двумерным массивом, можно получить ДПФ исходного одномерного массива.

Для получения основного результата будем считать, что входные отсчеты пронумерованы по строкам и по столбцам, поэтому их номера могут быть представлены следующими парами чисел:

Далее, пусть текущий номер столбца равен — текущий номер строки. Если исходный номер отсчета обозначить через , то

где М—число столбцов. L-число строк (в данном примере М = 12, L = 5).

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

Теперь коэффициенты одномерного ДПФ можно выразить через преобразование массива , используя простую подстановку формул (6.28) и (6.29) в выражение для ДПФ (6.2), что дает

Разлагая с учетом того, что и располагая соответствующие переменные под знаками суммирования, преобразуем формулу (6.30) к следующему виду:

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

1. Вычислить -точечные ДПФ всех столбцов. Результат является функцией s и , причем меняется от 0 до .

Обозначим его через и перепишем формулу (6.31):

Отсюда следует, что второй шаг вычисления сводится к следующему:

2. Найти новый массив , умножая каждый элемент на поворачивающий множитель .

Теперьформула (6.32) принимает вид

Она представляет М-точечные ДПФ каждой из строк с номерами s. Поэтому последний шаг алгоритма заключается в следующем:

3. Вычислить М-точечные ДПФ всех строк матрицы с ядром преобразования .

Описанная методика напоминает вычисление двумерного ДПФ, когда сначала вычисляются ДПФ строк, а затем столбцов, но шаг 2 отсутствует. Разделимость ядра преобразования с более высокой размерностью и является причиной того, что при расчете ДПФ с более высокой размерностью требуется меньше операций, чем при расчете одномерного ДПФ при одинаковом общем числе отсчетов.

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

Следует отметить, что изменение порядка суммирования в формуле (6.30) на обратный дает

так что порядок вычисления становится следующим:

1. Умножить отсчеты сигнала на поворачивающие множители .

2. Вычислить М-точечные ДПФ всех строк.

3. Вычислить L-точечные ДПФ всех столбцов.

В целом методика вычисления преобразования идентична рассмотренной ранее, но отдельные операции выполняются в другом порядке: умножения на поворачивающие множители здесь предшествуют вычислению ДПФ строк, тогда как раньше они выполнялись после вычисления ДПФ столбцов. Эти отличия не только напоминают, но и действительно связаны с обсуждавшимся выше различием между алгоритмами БПФ с основанием 2 при прореживании по времени и по частоте.

Отметим еще одно важное свойство методики преобразования, вытекающее из формулы (6.30), в которой переменные являются номерами столбцов, а — номерами строк. При увеличении на единицу номер отсчета исходного массива также возрастает на 1, тогда как при увеличении на 1 номера столбца преобразованного массива аргумент возрастает на L. Это означает, что в результате преобразования номера строк и столбцов меняются местами. Последнее обстоятельство настолько важно, что для его иллюстрации приведем пример вычисления 15-точечного ДПФ с использованием разложения (3x5). Исходную матрицу сигнала можно записать следующим образом:

Результирующая матрица гармоник ДПФ будет иметь вид

Таблица 6.1

Если N = 30 = 5x6 = 5x2x3, то основную теорему разложения можно использовать дважды, начав с разложения (5x6), а затем выполнить шеститочечные ДПФ, используя для этого разложение (2x3). Этот случай целесообразно рассмотреть на конкретном примере. Другие N читатель может проанализировать самостоятельно. Начнем с нумерации 30 отсчетов исходной матрицы сигнала:

Матрица

Теперь рассчитаем шесть пятиточечных ДПФ всех столбцов; умножив элементы полученной матрицы на поворачивающие множители, получим новую матрицу :

Далее, вместо того чтобы непосредственно вычислять пять шеститочечных ДПФ, представим каждую строку, содержащую шесть элементов, в виде матрицы размером Так, первые две строки матрицы переписываются следующим образом: Строка 1

Строка 2

Таким образом, искомые шеститочечные ДПФ можно найти, вычисляя ДПФ столбцов, содержащих по два элемента, умножая результаты ДПФ на поворачивающие множители и затем рассчитывая ДПФ строк, содержащих по три элемента. Вычисление заканчивается, когда таким образом будут преобразованы все пять матриц размера (2x3).

Перечислим все операции, требуемые для выполнения 30-точечного ДПФ с использованием разложения (5x2x3):

1) 6 пятиточечных преобразований;

2) 30 умножений на поворачивающие множители;

3) 15 двухточечных преобразований;

4) 30 умножений на поворачивающие множители;

5) 10 трехточечных преобразований.

Используя этот пример, можно рассчитать, сколько операций необходимо для общего случая :

1) LM -точечных преобразований;

2) LMP умножений на поворачивающие множители;

3) MP L-точечных преобразований;

4) LMP умножений на поворачивающие множители;

5) LP М-точечных преобразований.

Чтобы оценить уменьшение объема вычислений за счет использования алгоритма БПФ, рассмотрим несколько частных случаев. Прежде всего положим где L и М — простые числа, большие 2. Из формулы (6.2) следует, что М-точечное ДПФ требует «операций», состоящих из умножения и сложения в комплексной форме. Учитывая это, получим следующее общее число операций для разложения вида :

Член LM учитывает количество умножений на поворачивающие множители, выполняемых между преобразованиями строк и столбцов (строго говоря, эти LM действий состоят только из комплексного умножения и поэтому требуют несколько меньше времени, чем вся «операция»). Ясно, что при выполнении -точечного ДПФ самым громоздким прямым методом потребовалось бы операций. Таким образом, с помощью формулы (6.34) можно оценить выигрыш во времени вычислений, характерный для преобразования с использованием разложения. Если, например, то относится к числу операций при прямом расчете ДПФ как 17:55. Очевидно, что с ростом N выигрыш увеличивается. Например, если N = 15, L = 5, М = 3, то будет относиться к числу операций при прямом расчете ДПФ как 9:15.

Рассмотрим теперь случай, когда N можно разложить на три простых целых сомножителя, т. е. . Нетрудно показать, что в этом случае число операций равно

Например, при относится к числу операций при прямом расчете ДПФ как , т. е. достигнуто уменьшение числа операций почти на порядок. Чтобы оценить выигрыш в общем случае, изменим обозначения и положим . Тогда

С помощью полученных формул можно достаточно точно определить величину выигрыша при условии, что все числа простые (и не равные 2), так как только в этом случае общее число операций при -точечном преобразовании равно N. Если же числа не являются простыми или необходимо быть очень осторожными в оценках. Например, как было показано выше, при двухточечном ДПФ (т. е. ) умножения вообще не используются. Это же справедливо и для . При число умножений существенно меньше 64. В связи с этим при разложении N на такие сомножители, как 2, 4 или 8, полученные выше формулы непригодны. Рассмотрим, например, N, равное степени 2, скажем . Тогда член формулы (6.36), учитывающий двухточечные ДПФ, включает только комплексные сложения и вычитания, тогда как член учитывает умножения на поворачивающие множители. В зтом случае формула (6.36) становится весьма неудобной для оценок, поскольку приходится сопоставлять затраты времени на умножение и на сложение.

Чтобы получить направленный граф (подобный графам на фиг. 6.3 и 6.11) для самого общего случая разложения, необходимо расширить круг обозначений, введенных на фиг. 6.3 и 6.11. Это сделано на фиг. 6.13, где 30-точечный массив представлен в виде двумерного массива, содержащего 5 строк и 6 столбцов, со следующими элементами (числа обозначают номера элементов исходного массива):

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

Фиг. 6.13. Направленный граф 30-точечного БПФ, основанного на последовательных прореживаниях за счет представления одномерных массивов двумерными.

Узлы направленного графа обозначают регистры, содержащие входные и выходные отсчеты ДПФ. Все выходные отсчеты ДПФ умножаются на поворачивающие множители; для обозначения этой операции введено 30 стрелок, около которых записаны значения коэффициентов W. Следующий зтап состоит в вычислении ДПФ всех строк. Поскольку строки содержат по 6 элементов, каждая из них может быть представлена в виде матрицы с 2 строками и 3 столбцами.

В примере, приведенном на фиг. 6.13, каждая шеститочечная строка преобразуется с помощью: 1) трех двухточечных ДПФ; 2) умножений на поворачивающие множители; 3) двух трехточечных ДПФ.

Отметим также следующую особенность обозначения. Строго говоря, каждая линия, выходящая из незачерненного кружка, должна иметь свою стрелку с коэффициентом W. Если, однако, учесть, что , то такой поворачивающий множитель можно опустить. Во всех приводимых направленных графах (в том числе и на фиг. 6.3 и 6.11) авторы по своему усмотрению решали, ввести или опустить . При нахождении поворачивающих множителей для второго этапа графа на фиг. 6.13 необходимо помнить, что для него коэффициент W равен TF, поэтому матрица поворачивающих множителей для каждой из прореживаемых строк исходной матрицы, содержащей 5 строк и 6 столбцов, имеет вид

В заключение осталось рассмотреть характер перестановки данных на фиг. 6.13. Если бы весь массив из 30 отсчетов был преобразован в матрицу размером (5x6) (и никак иначе), то строки и столбцы матрицы результатов оказались бы просто переставленными относительно исходной матрицы. Так как в действительности каждая строка также прореживалась, то это привело к дополнительной перестановке результатов. Окончательный порядок следования результатов ДПФ показан на фиг. 6.13.