4.9. Заключительные замечания

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

Стартовой точкой в применении алгоритма является табл. 4.6, поскольку она представляет список допустимых значений и соответствующих параметров, характеризующих производительность алгоритма. После выбора нужного следует обратиться к табл. 4.5 и отыскать конкретные схемы, требующиеся в соответствии с табл. 4.6. При реализации алгоритма сначала осуществляется перестановка элементов входного вектора, а затем применяется фаза 1 схем (в том порядке, который предписан табл. 4.6) к все меньшим и меньшим сегментам вектора данных, которые оказываются в различных частично преобразованных состояниях. Этот процесс завершается, когда, в конце концов, однокомпонентные «сегменты» умножаются на константы в фазе 2. С этого момента процесс развивается в обратном направлении на фазе 3. Скаляры, появившиеся как результат фазы 2, комбинируются в векторы все большей и большей размерности, превращаясь, наконец, в -мерный вектор, который отличается от результата преобразования лишь перестановкой своих элементов.

Эта глава содержит подробную информацию, достаточную для непосредственной аппаратурной или программной реализации упомянутой выше схемы. Хотя мы не рассмотрели конкретной реализации, стоит обратить внимание на некоторые особенности схем, специально внесенные в них для облегчения их реализации. Мы имеем в виду преобразование с оставлением на месте. Рассмотрим схему седьмого порядка (см. рис. 4.8). Заметим, что исходные компоненты используются только для вычисления Следовательно, нет необходимости выделять дополнительную память для Они могут храниться в массиве на месте Единственно, что требуется, — это временно сохранить, скажем, так чтобы, запомнив можно было бы использовать Для вычисления . Даже если является вектором, необходимо лишь одно слово памяти для временного хранения, так как вычисления выполняются покомпонентно.

Это свойство, которое мы проиллюстрировали здесь на примере преобразования является общим для всех переменных в схемах порядков 2, 3, 5, 7. Оно остается в силе и для остальных схем. если рассматривать как выходной вектор. Единственное отклонение заключается в том, что в некоторых случаях должны рассматриваться группы из трех, а не из двух компонент. В выбранной схеме таким случаем является вычисление Однако даже в этом случае достаточно иметь временную память на одно слово.

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

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

Обратимся теперь к краткому рассмотрению вопроса потери точности, упомянутому в разд. 4.1. В приложении (см. последний раздел) некоторые преобразования, применявшиеся при построении схем, отрицательно сказываются на точности. Подобная ситуация имеет место и при вычислении 61 в некоторых схемах. Анализ (4.84), (4.85) показывает, что выбранный вид выражения (4.85) включает в себя сложение и вычитание Следовательно, если мы непременно столкнемся с проблемой потери значащих битов в арифметике с плавающей запятой и возможностью переполнения в арифметике с фиксированной запятой. Подобные же манипуляции с операциями сложения — вычитания имеют место в том или ином виде при выводе всех схем.

Вследствие этих особенностей схем для гарантии определенной степени точности в алгоритме Винограда необходимо, вероятно, больше битов на слово, чем в алгоритме Кули—Тьюки. Мы не анализировали здесь эту проблему точности, но надо отметить, что структура алгоритма в том в котором она представлена на рис. 4.20, делает такой анализ относительно простым.

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

Признательность. Представленная здесь работа выполнена в Лаборатории реактивного движения (ЛРД) Калифорнийского технологического института, по контракту NASA № NAS7-100. Автор хотел бы также выразить благодарность д-ру Л. Д. Баумерту, бывшему сотруднику ЛРД, за полезные комментарии, относящиеся к некоторым теоретико-числовым аспектам этой работы.

Приложение. Конгруентность полиномов.

Выкладки в разд. 4.3 требуют численного решения уравнения

где

— монический полином степени 1 или 2, корни которого лежат на единичной окружности. Здесь мы получаем все необходимые для этого результаты.

должен иметь степень нуль

и в этом случае эквивалентно

где является полиномом степени Подставляя получаем

Заметим, что при является алгебраической суммой коэффициентов не содержащей умножений.

должен быть полиномом первой степени

эквивалентно

Отсюда

Заметим, что

Следовательно, вычитая из , получаем

где — полином Чебышева второго рода.

Для получения умножаем на на после чего находим их разность

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

Таблица П.1

Конкретное применение табл. заключается в следующем. Дано

Найти

может быть выражена с помощью следующим образом:

Отождествляя заключенный в скобки полином с в табл. П.1, получаем:

Начиная с каждая из этих формул требует 4 умножения. Однако при соответствующем переупорядочении членов можно заменить одно из этих умножений дополнительным сложением, тем самым ускорив вычисления. Завершается это добавлением и вычитанием из члена Этого достаточно для мы также модифицируем член добавляя и вычитая Результаты сведены в табл. и мы видим, что трех умножений теперь достаточно. Однако случай по-видимому, показывает, что затраты оказываются выше, чем утверждалось ранее, а именно, они составляют 3 дополнительных сложения. В общем случае это, несомненно, верно. Но мы намереваемся применять эти результаты в ситуации, когда арифметические операции, включающие только не принимаются в расчет. (Соответствующие константы

Таблица П.2

вычисляются заранее.) При этих условиях затраты составляют одно дополнительное сложение.

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