3.2.1. Полиномиальные преобразования

Пусть — двумерная - точечная циклическая свертка

Чтобы сделать основные упрощения при вычислении этой свертки, необходимо представить ее в терминах полиномиальной алгебры. Такое представление выполнено с учетом того, что (3.15) можно рассматривать как одномерную полиномиальную свертку:

где получено из полиномов путем выбора коэффициентов при

Предположим сперва, что А — нечетное простое число, . В этом случае, как показано в разд. 3.1, является произведением двух циклотомических полиномов:

Поскольку определен по модулю он может быть вычислен посредством приведения по модулю множителей вычисления полиномиальных сверток и над приведенными полиномами и последующего восстановления в соответствии с китайской теоремой об остатках:

где

Задача вычисления следовательно, сводится к более простой задаче вычисления Вычисление является чрезвычайно простым, так как определено по модулю Таким образом, есть сверточное произведение скаляров полученных подстановкой 1 вместо Z в

Наиболее трудной частью вычисления является определение Для его упрощения введем преобразование определенное по модулю

где . Будем называть это преобразование (которое имеет ту же структуру, что и ДПФ, но с заменой комплексных экспонент на Z) полиномиальным. Аналогично определим обратное преобразование

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

сложений, без каких-либо ограничений на арифметику, поскольку поле Р коэффициентов может быть выбрано проиавольным.

Покажем теперь, что полиномиальные преобразования, наряду с ДПФ и ТЧП, обладают свойством циклической свертки, и, следовательно, могут быть использованы для упрощения вычисления свертки. Это можно сделать, найдя преобразования от с помощью (3.28), умножив на по модулю и вычислив обратное преобразование от

где Пусть При последовательность экспонент от представляет собой простую перестановку целых чисел Следовательно, . Для

Поэтому единственный ненулевой случай соответствует или приводится к циклической полиномиальной свертке

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

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

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

4 полиномиальных произведений по модулю Это означает, что если свертка и полиномиальные произведения вычисляются по алгоритму с минимальным числом умножений, определенным согласно теоремам 3.2 и 3.3, то -точечная сзертка, — простое, вычисляется только за умножений.

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

Можно в действительности показать, что это является теоретически минимальным числом умножений для -точечной свертки при простом