6.2. АЛГОРИТМЫ БПФ С ПРОРЕЖИВАНИЕМ ПО ВРЕМЕНИ

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

Разделяя на четные и нечетные точки, получим

или, заменяя индексы суммирования на при четном при нечетном получим

так как Следовательно, (6.10) можно записать в виде

Каждая из сумм в (6.11) является -точечным ДПФ. Первая сумма -точечное ДПФ четных точек исходных

последовательностей, а вторая — -точечное ДПФ нечетных точек исходных последовательностей. Хотя индекс простирается на значений, каждая из сумм требует вычислений только для к от 0 до так как периодичны по с периодом После того как ДПФ, соответствующие двум суммам в (6.11), вычислены, они объединяются и дают -точечное

Рисунок 6.3 иллюстрирует вычисление в соответствии с (6.11) для восьмиточечной последовательности, т. е. для На этом рисунке использованы направленные сигнальные графы, которые были введены в гл. 4 для представления разностных уравнений [5, 7].

Рис. 6.3. Направленный граф, иллюстрирующий разложение -точечного ДПФ на два -точечных ДПФ в алгоритмах с прореживанием по времени

Рис. 6.4. Направленный граф, иллюстрирующий разложение -то-чечного ДПФ на два -точечных ДПФ в алгоритмах с прореживанием по времени

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

Перестроив вычисления согласно (6.11), можно сравнить требуемое число умножений и сложений с числом умножений и сложений, Необходимым при прямом вычислении ДПФ. Раньше мы видели, что при прямом вычислении без использования симметрии требуется комплексных умножений и сложений.

Выражение (6.11) требует вычисления двух N/2-точечных ДПФ, что, в свою очередь, требует комплексных умножений и приблизительно комплексных сложений. Затем два -точечных ДПФ должны быть объединены, потребует комплексных умножений, соответствующих умножению второй суммы на и затем комплексных сложений, соответствующих сложению произведения с первой суммой. Следовательно, вычисления по (6.11) для всех значений требуют или комплексных умножений и комплексных сложений. Легко проверить, что при будет меньше, чем

Выражение (6.11) соответствует разбиению исходного -точеч-ного вычисления на два -точечных вычислений. Если — четное число, что имеет место всегда, когда равно степени 2, то можно вычислять каждое -точечное ДПФ в (6.11) путем разбиения сумм на два -точечных ДПФ, которые затем объединяются, давая -точечное ДПФ. Таким образом, в (6.11) могут быть вычислены как

или

Аналогично

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

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

В более общем случае, когда является более высокой степенью 2, мы бы продолжили разложение -точечных преобразований в (6.12) и (6.13) в -точечные преобразования и продолжали бы до тех пор, пока не остались бы только двухточечные преобразования. Это потребует ступеней вычисления, где

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

Рис. 6.5. Результат подстановки направленного графа рис. 6.4 в граф рис. 6.3

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

Рис. 6.6. Направленный граф двухточечного ДПФ

Рис. 6.7. Направленный граф для полного разложения восьмиточечного ДПФ в алгоритме с прореживанием по времени

Граф на рис. 6.7 показывает явно эти операции. Подсчитав ветви с передачами вида замечаем, что на каждой ступени необходимо комплексных умножений и комплексных сложений. Так как число ступеней равно получаем, как и прежде, общее число комплексных умножений и сложений, равное

Это существенная экономия вычислений. Мы увидим, то использование симметрии и периодичности коэффициентов даст дальнейшее уменьшение количества вычислений.