ГЛАВА 4. АЛГОРИТМ ВИНОГРАДА ДЛЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

(Ш. Зохар)

Здесь детально рассматривается новый алгоритм ДПФ, предложенный Виноградом. Этот алгоритм требует примерно в пять раз меньше умножений, чем алгоритм Кули — Тьюки, и применим к любым порядкам, которые являются произведением взаимно-простых множителей из следующего списка: 2, 3, 4, 5, 7, 8, 9, 16. Алгоритм описан с помощью схем специальной формы по одной для каждого члена списка. Такие схемы являются удобным, компактным графическим представлением последовательностей арифметических операций в соответствующих частях алгоритма. Использование этих схем вместе с табл. 4.5, 4.6 позволяет относительно легко реализовать алгоритм и оценить его эффективность.

Материал изложен так, что при первом чтении можно опускать значительные части текста.

4.1. Обзор

Со времен открытия алгоритма БПФ [4.1] многих мучил вопрос: «Является ли алгоритм БПФ единственным способом быстрого вычисления ДПФ или все-таки существует более быстрый алгоритм, который еще предстоит найти?» В 1968 г. один ответ на этот вопрос дал Явн [4.2], показав, что число умножений можно уменьшить в два раза при неизменном числе сложений. В 1969 г. значительный шаг на этом пути сделал Виноград [4.3], который разработал алгоритм, снижающий число умножений в алгоритме БПФ по основанию 2 [4.1] примерно в 5 раз. Такое уменьшение числа умножений сопровождается небольшим увеличением или уменьшением числа сложений. В большинстве случаев рост не превышает 20%.

В качестве основы для сравнения алгоритмов здесь и далее будем использовать «номинальную» эффективность алгоритма Кули — Тьюки (БПФ), а именно, число умножений и сложений вещественных чисел при вычислении ДПФ порядка с комплексными данными:

Итак, выбираем (4.1) в качестве основы сравнения при всех

Алгоритм Винограда решает упомянутую задачу, используя умножений вещественных чисел. Рассмотрим возможности и ограничения алгоритма с тем, чтобы читатель, прежде чем приступить к более глубокому изучению, смог оценить пригодное и его для своих нужд.

На нынешней стадии разработки алгоритм применим для любых удовлетворяющих соотношению

в котором — взаимно-простые множители, взятые из списка

Следовательно, максимальное значение равно Все значения удовлетворяющие указанному условию, перечислены в сводной табл. 4.6. В графе для каждого значения .V приводится фактическое значение выигрыша в числе умножений. В среднем для всех равно примерно 5,5. При таком значительном снижении числа умножений есть основания ожидать, что в большинстве случаев алгоритм будет работать быстрее, чем алгоритм Кули—Тьюки. Чтобы быть более уверенными в этом, надо знать основной системный параметр который является отношением времени выполнения одного вещественного умножения к времени выполнения одного вещественного сложения. (Термин «вещественный» используется как противоположность термина «комплексный», а не «целое», если иметь в виду Фортран). Для очень больших (например, в микропроцессорах, программных умножителях) выигрыш в скорости приближается к асимптотически. Для меньших значений выигрыш будет меньше. Обозначая выигрыш в скорости через можно показать, что

где — параметр, указанный в табл. 4.6 в одной колонке с Очевидно, теперь легко вычислить выигрыш в скорости для любой системы и любого допустимого Будет показано, что (4.4) основывается только на времени выполнения арифметических операций и что структурная сложность алгоритма Винограда обусловливает замедление его программной реализации.

Основным недостатком нового алгоритма является необходимость в большом объеме памяти. В табл. 4.6 это отражено параметром Для обработки комплексных данных надо иметь в памяти массив длиной вещественных слов. изменяется примерно от в начальных строках таблицы до в последних ее строках. Так, для больших значений требуется массив что на больше, чем минимально необходимые для запоминания входного вектора. Из полного объема памяти в вещественных

слов 0,5 необходимы для запоминания предварительно вычисленных констант. Поскольку не все константы отличаются друг от друга, вероятно, есть возможность снизить эту часть затрат памяти за счет использования более сложных схем адресации.

Другим возможным недостатком нового алгоритма является то, что он может потребовать больше бит на одно слово для сохранения заданной точности по сравнению с алгоритмом Кули — Тьюки. Это обстоятельство более детально рассматривается в разд. 4.9, но в целом проблема заслуживает дальнейшего изучения.

Вывод алгоритма разбит на две части. В первой рассматриваются быстрые алгоритмы ДПФ для малых порядков, значения которых перечислены в (4.3). Алгоритмы образуют набор конструктивных блоков, которые во второй части объединяются в искомые полные алгоритмы ДПФ для порядков описываемых выражением (4.2).

Алгоритмы малых порядков из (4.3) являются производными от алгоритмов порядков 2, 4, 6 преобразований другого типа. Эти преобразования называются лево-циркулянтными (ЛЦП) (чаще называются циклической корреляцией; см. разд. 4.2). Итак, излагаемый материал имеет следующую структуру. Раздел 4.2 посвящен взаимосвязи ДПФ - ЛЦП. Далее следует описание трех алгоритмов ЛЦП (разд. 4.3) и построенных на их основе семи алгоритмов ДПФ (разд. 4.4.-4.6). В разд. 4.7 рассматривается Объединение этих алгоритмов малого порядка в искомый алгоритм порядка удовлетворяющий (4.2). Раздел 4.8 посвящен рценке эффективности. В разд. 4.9 подводятся итоги и даются комментарии по поводу преобразования, выполняемого с оставлением на месте.

Мы постарались сделать рассмотрение достаточно детальным и полным, желая создать необходимую базу для дальнейшей разработки проблемы. Однако следует указать, что приемлемый уровень понимания основных идей и их приложений может быть достигнут без детального вывода алгоритмов малых порядков. При этом достаточно изучить разд. 4.2, первую часть разд. 4.3 (вплоть до рассмотрения лево-циркулянтного преобразования порядка 4), введение вектора обобщение схемы в разд. 4.6 [см. фрагмент между (4.126) и (4.127)], разд. 4.7, последнюю часть разд. 4.8 [следующую за (4.181) ] и разд. 4.9.