3.2.3. Вычисление полиномиальных преобразований и приведений полиномов

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

Когда — простое, входные последовательности должны быть приведены по модулю 1—1 и по модулю Каждая операция

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

Восстановление по китайской теореме об остатках выполняется за сложений с использованием (3.33). Поскольку представляет собой Полиной «з членов, может быть определен как

Таким образом, (3.33) переходит в

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

Для — простое, полиномиальное преобразование определенное с помощью (3.28), вычисляется следующим образом:

Таблица 3.2

Число сложений для вычисления приведений, операций восстановления по китайской теореме об остатках и полиномиальных преобразований — нечетные простые)

где полиномы из членов. Пусть . Так как , то вычисляется за сложений. При представляет собой сумму полиномов, каждый из которых умножен на степень сначала вычисляется по модулю Поскольку каждый полином Чтосле умножения на степень Z становится полиномом из членов, где один член равен нулю, т. е. вычисление требует сложений. Затем приводится по модулю с помощью сложений. Таким образом, вычисление каждого при требует сложений. Поскольку для

вычисляется за сложений при помощи соотношения:

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

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

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