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

Отличный от рассмотренного ранее мегод вычисления быстрого преобразования Фурье дается БПФ-алгоритмом Винограда. Этот алгоритм основывается на четырех отдельных идеях: алгоритме Рейдера, описанном в § 11.2 алгоритме Винограда вычисления коротких сверток, схеме индексации алгоритма Гуда-Томаса для простых множителей, гнездовом алгоритме Винограда (см.

ниже). БПФ-алгоритм Винограда лучше БПФ-алгоритмов Кули— Тьюки и Гуда-Томаса по числу умножений, но сложнее по структуре. За уменьшение числа умножений приходится платить усложнением индексации и использованием операций отображения.

БПФ-алгоритм Винограда подразделяется на малый БПФ-алгоритм Винограда и большой БПФ-алгоритм Винограда. К малому алгоритму относятся преобразования, длина которых равна малому простому числу или степени малого простого числа. Большой БПФ-алгоритм Винограда объединяет малые БПФ-алгоритмы Винограда, чтобы получить преобразование на большой длине

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

Построим алгоритм Винограда вычисления пятиточечного БПФ в поле находящий величины

Воспользуемся рассмотренным ранее (см. § 9.8) алгоритмом Рейдера, сводящим пятиточечное преобразование Фурье к свертке

где

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

Малый иятиточечпый алгоритм Винограда вычисления БПФ получится, если для вычисления произведения воспользоваться алгоритмом Винограда вычисления короткой свертки. Обращаясь к таблице на рис. 11.2, находим алгоритм Винограда вычисления четырехточечной циклической свертки, содержащий девять умножений. Воспользуемся этим алгоритмом для построения алгоритма преобразования Фурье. Соединим операции переиндексации алгоритма Рейдера с матричными операциями алгоритма свертки, выполняя соответствующие перестановки строк и столбцов. Далее, так как коэффициенты многочлена являются фиксированными константами поля то произведение на соответствующую матрицу можно вычислить заранее. Внеся все эти изменения в алгоритм чешрехточечной свертки и присоединяя к нему компоненты и получаем малый пятиточечный алгоритм Винограда БПФ. На рис. 11.6 приведена запись этого алгоритма в матричном виде:

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

Рис. 11.6. Чалый питмточечпыи алгоритм Винограда вычисление БПФ.

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

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

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

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

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

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

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

Элементы матриц одни и те же, но упорядочены по-разному. Очевидно также, что кронекеровское произведение дистрибутивно относительно обычного сложения матриц.

Следующая теорема утверждает, что кронекеровское произведение двух произведений матриц равно матричному произведению кронекеровских произведений соответствующих матриц.

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

Доказательство. Пусть матрицы имеют соответственно размеры Так как матрица содержит столбцов, а матрица содержит строк, то матричное произведение определено. Оно содержит строк, которые мы занумеруем парами и столбцов, которые мы занумеруем парами Элемент, стоящий на пересечении строки и столбца равен Так как матрица содержит I строк и столбцов, а матрица содержит строк и столбцов, то матрица также является -матри-цей. Стоящий на пересечении -строкн и -столбца элемент этой матрицы равен

что и завершает доказательство.

Кронекеровское произведение матриц применяется в теории преобразования Фурье. Пусть матрицы преобразования Фурье соответственно длин Тогда

являются соответственно матричными записями преобразований Фурье

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

Если предполагать, что одномерные -точечные векторы упорядочены описанным выше способом, то

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

Для алгоритма Винограда преобразований длин имеет место матричное разложение

где - матрицы целых чисел рассматриваемого поля, диагональные матрицы над Умножения на описывают все умножения, которые приходится выполнять в алгоритме Винограда. Положим и дважды применим теорему 11.7.2:

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

Из приведенного описания матрицы видно, что такое преобразование предполагает предварительную запись (с помощью алгоритма Гуда-Томаса для взаимно простых множителей) -точечного одномерного преобразования в виде двумерного преобразования с последующим считыванием преобразуемого двумерного вектора по строкам в виде одномерного -точечного вектора Следовательно, описанный способ вычисления -точечного преобразования предполагает предварительную перестановку компонент вектора и вычисление компонент вектора V также в переставленном порядке. Но поскольку вид матриц известен, то тривиальная перестановка столбцов матрицы А и строк матрицы В позполяет выписывать компоненты векторов и V в их естественном порядке.

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

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