Г. Приложения к вычислению ДПФ и сверток.

Раньше в § 6 говорилось об использовании ДПФ для вычисления свертки. На основе исследований, связанных с применением в рассматриваемой нами области теоретико-числовых и полиномиальных преобразований, сделан вывод о возможности также эффективного использования сверток как метода выполнения ДПФ. Характеризуя сложившуюся в этой части ситуацию, переводчики книги [80] пишут следующее: "Гармонический анализ и свертка представляют собой два разных, но очень тесно связанных между собой раздела цифровой обработки сигналов. Хорошо известно, что свертку можно вычислять с помощью спектральных методов, но о том, что гармонический анализ можно проводить, вычисляя систему сверток, стало известно лишь недавно".

Считается перспективным применение числового преобразования Ферма (ЧПФ), так как при его выполнении используются эффективные алгоритмы типа БПФ. Уделяется внимание и числовому преобразованию Мерсенна (ЧПМ), не обладающему, правда, структурой БПФ, но более просто выполняемому. Теоретико-числовые преобразования с использованием чисел Ферма и Мерсенна основаны на выводах, следующих из китайской теоремы об остатках. Имеет различные применения в рассматриваемой нами области и китайская теорема об остатках для многочленов. Она используется при замене выполнения длинной свертки выполнением ряда коротких сверток. Она применена и при приближенной оценке числа умножений, выполняемых при вычислении свертки ([80], с. 29 и 30). При применении полиномиальных преобразований для вычисления периодической свертки вводится в рассмотрение и функция Эйлера, упоминавшаяся нами в п. Б (см. [80], с. 32).

Об основных результатах, полученных на основе использования теоретико-числовых и полиномиальных преобразований, упоминалось уже в п. 3 § 5. Не повторяя ранее сказанного об этом, приведем краткие сведения о рассмотренных в книге [76] 13 оригинальных работах, опубликование которых имело большое значение для формирования нового направления в теории и технике вычисления ДПФ и сверток. Из числа указанных статей шесть связаны с разработкой АВПФ.

В статье [56] описаны алгоритмы вычислений для больших объемов данных, основанные на сведении ДПФ к свертке и вычислении коротких сверток с минимальным количеством умножений. Использована китайская теорема об остатках для целых чисел. Рассмотрены два алгоритма вычисления ДПФ: АВПФ и алгоритм БПФ для простых множителей, основанный на идеях, предложенных Гудом, и на указанном Виноградом алгоритме ДПФ для коротких сверток. В ходе выводов используется понятие первообразного корня, о котором было сказано в п. Б. Характеризуя разработанные методы выполнения преобразований, авторы статьи отметили то, что здесь нашли применение понятия модульной арифметики, и то, что в данном

случае "теорема Винограда о минимальном числе умножений объясняется на языке умножения полиномов".

В работе [105] показано, что для последовательностей, длина которых является простым числом, -точечное ДПФ содержит -точечную периодическую свертку. Предложен метод быстрого вычисления такой свертки и на основе этого получен эффективный алгоритм вычисления ДПФ. Выводы тоже связаны с использованием упоминавшегося ранее понятия первообразного корня.

Авторы работы [3], применив китайскую теорему об остатках, показали, что возможно эффективное преобразование одномерной периодической свертки в многомерную. Говоря о том, что ими описывается вычисление периодической свертки, а не ДПФ, они делают следующую оговорку: "как, наверное, теперь очевидно, эти две операции в своей основе эквивалентны". Рассмотрено числовое преобразование Ферма. Рекомендовано к использованию при вычислении периодических сверток число

В статье [26] дано описание алгоритма Винограда преобразования Фурье. Рассмотрено полиномиальное представление данных. Выводы основаны на применении полиномиального варианта китайской теоремы об остатках. Характеризуя АВПФ, автор статьи отмечает, что "заключительный этап создания АВПФ состоит в отображении индексов по китайской теореме об остатках для преобразования длинного одномерного ДПФ в многомерное ДПФ, числа точек которого по каждой размерности взаимно просты".

Автор работы [38] рассмотрел два метода выполнения ДПФ. Указано, что простой вывод АВПФ получается при представлении алгоритмов БПФ и алогоритма для простых множителей в выражениях прямого произведения разреженных матриц. Даны определения числового преобразования Фурье и более общего преобразования фурье — Галуа.

В статье [90] показано, что преобразования, аналогичные ДПФ, могут быть определены в поле Галуа содержащем элементов, когда — простое число. Указано на возможность выполнения этих преобразований с помощью алгоритма быстрого преобразования фурье. Рекомендовано использовать их для вычисления сверток длинных последовательностей целых чисел.

Работа [2] содержит описание примененного для вычисления свертки числового преобразования Ферма (ЧПФ), для реализации которого требуется относительно небольшое количество сложений, вычитаний, поразрядных сдвигов и отпадает необходимость в выполнении операций умножения. Отмечено, что свертка вычисляется точно, так как отсутствует ошибка округления. Сообщено о разработке многомерных методов обработки данных предназначенных для снятия ограничения на длину последовательности входных данных, возникающего в связи с ограниченной длиной кодового слова.

Статья [2] посвящена методам быстрого вычисления одномерной свертки заданных сигналов путем вычисления многомерной свертки.

Рассмотрено вычисление сверток на основе применения ЧПФ. В статье имеется указание на наличие многих возможностей "комбинирования преобразований Фурье и Ферма различных длины и размерности с алгоритмами короткой свертки и со специальными аппаратурными средствами".

Работа [75] освещает вопросы аппаратной реализации ЧПФ. В работе [71] тоже рассмотрены вопросы выполнения преобразований с числами Ферма.

Статья [106] представляет интерес в связи с общей трактовкой вопроса. Вместе с тем оценены перспективы использования преобразований Мерсенна. Приведем аннотацию этой статьи: "Построено преобразование в поле Галуа из элементов т.е. в конечном поле, аналогичном полю комплексных чисел, если не является квадратичным вычетом по модулю простого числа Показано, что действие этого преобразования над эквивалентно ДПФ для последовательности комплексных чисел с ограниченным динамическим диапазоном. Если является простым числом Мерсенна, то можно использовать алгоритм БПФ, который позволит быстро вычислять свертку без ошибок округления, возникающих при использовании обычного БПФ". (Последний из поднятых здесь вопросов, касающийся ошибок округления при использовании обычного БПФ, будет рассмотрен нами в гл. IV.)

Цифровой фильтрации с помощью выполняемых без умножений комплексных преобразований Мерсенна посвящена статья [82]. Сравнивая применения преобразований Ферма и преобразований Мерсенна и отмечая перспективность того и другого из них, автор статьи констатирует, что "для преобразований Ферма можно применять алгоритмы быстрого преобразования, а для преобразований Мерсенна их не существует, и в то же время операции по модулю чисел Мерсенна выполняются проще, чем в арифметике по модулю чисел Ферма". (Когда здесь говорится о том, что для преобразований Мерсенна не существует алгоритмов быстрого преобразования, имеются в виду алгоритмы типа БПФ. Однако, сравнивая скорость выполнения операций при выполнении обычного ДПФ и преобразования Мерсенна, можно применить термин "быстрое преобразование" и по отношению к последним. Эта оговорка нужна во избежание возникновения недоразумений из-за того, что было сказано о быстрых преобразованиях в п. А § 5.)

В статье [25] показано, что минимальное число умножений при выполнении операции равно , где степень — число различных неприводимых многочленов в разложении отмечено, что минимальный алгоритм должен основываться на китайской теореме об остатках для многочленов.

Цриведенные выше сведения, а также сказанное ранее в п. 3 § 5, дают представление о том, как используется аппарат теории чисел и полиномиальных преобразований при создании новых методов вычисления ДПФ и сверток. Это представляет интерес и в связи с проводимой в последние годы интенсивной разработкой обобщенных методов выполнения различных ортогональных преобразований. К данному вопросу вернемся в § 4 и 5 гл. IV.