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

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

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

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

Полиномиальное произведение определенное по модулю P(Z), задается тогда выражением которое со ответствует простому приведению Поскольку то это приведение достигается простым вычитанием из причем

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

Таким образом, одномерные свертки и полиномиальные произведения могут быть вычислены с помощью ДПФ или Трудности, связанные с использованием

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

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

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

и одного умножения вместо полиномиальных произведений по модулю и одной -точечной свертки. Схема вычислений по этому методу приведена на рис. 3.5.

В дальнейшем будем предполагать, что все двумерные свертки вычисляются аналогично, так что займемся только алгоритмами полиномиального произведения. Кроме того, увидим, что в большинстве случаев свертки можно найти с помощью ограниченного набора алгоритмов полиномиальных произведений, главным образом тех, которые определены по модулю: . Поскольку эти полиномы неприводимы, их всегда можно найти с помощью интерполяции в соответствии С теоремой 3.2 за умножений, где степень . Как показано в подразд. 3.5.1, 3.5.2, использование этого метода для умножений по модулю и модулю порождает алгоритмы с тремя умножениями и тремя сложениями.

Для полиномиальных произведений большей размерности этот метод, обеспечивающий минимальное число умножений, приводит к чрезмерному увеличению числа сложений. Это происходит потому, что в этом случае требуется различных полиномов Четыре наиболее простых интерполяционных полинома имеют вид: Таким образом, когда степень полинома больше двух, необходимо использовать целые отличные от 0 или ±1, а соответствующие приведения по модулю и восстановление по китайской теореме об остатках будут включать умножения на степени

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

Первый подход к снижению числа сложений за счет небольшого увеличения числа умножений состоит в применении комплексных интерполяционных полиномов. Если используем, например, нам нужно 3 действительных умножения вместо двух для полинома, имеющего действительные целые корни. Однако приведения и восстановление по китайской теореме об остатках остаются простыми, так как требуют только простых сложений и умножений на ±1 или . Другой подход состоит в преобразовании одномерных полиномиальных произведений в многомерные. Например, умножение по модулю можно заменить на умножение по модулю так как подстановка дает . В соответствии с этим методом входные полиномы сначала приводятся по модулю посредством подстановки Таким образом,

и аналогичные соотношения выполняются для Теперь полиномиальное произведение по модулю можно вычислить по методу интерполяции за

5 умножений по модулю . Поскольку, как показано в подразд. 3.5.2, каждое из этих полиномиальных умножений требует трех скалярных умножений, полиномиальное произведение по модулю выполняется за 15 умножений. Подробный алгоритм приведен в подразд. 3.5.5.

Аналогичный метод можно использовать для полиномиальных произведений по модулю Полиномиальное умножение по модулю выполняется, например, по модулю за 9 умножений и 15 сложений (см. подразд. 3.5.3), в то время как традиционный интерполяционный метод потребовал бы 7 умножений и 41 сложение.

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

где и х — вектор-столбцы входных последовательностей и — входные матрицы (знак X означает поэлементное произведение); - выходная матрица — вектор-столбец выходной последовательности

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

где — элементы матрицы Для алгоритма по модулю соответствующему циклической свертке, находим обычное условие, определяющее циклическую свертку:

Аналогично алгоритмы полиномиального произведения по модулю удовлетворяют условиям:

Теперь заменим матрицы Е и матрицами таким образом, чтобы их элементами были При этих условиях переходит в из (3.56), очевидно, вытекает

Следовательно, как указано в [3.14], свойство свертки по-прежнему сохраняется, если матрицы Е и меняются местами с помощью простого транспонирования и перегруппировки столбцов и строк. Такой же общий подход можно применить для полиномиальных произведений по модулю или Однако в этих случаях условия для или в (3.57) заменяются на или 1—0. Таким образом, элементами матриц должны быть: . Этот подход применен для описанного в алгоритма полиномиального произведения по модулю

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

(кликните для просмотра скана)

в соответствии с этими алгоритмами, дано в табл. 3.4. Следовало бы заметить, что мы оптимизировали алгоритмы с точки зрения снижения числа умножений. Если вычисления осуществляются на ЭВМ, у которой время выполнения умножения сравнимо с временем сложения, предпочтительно использовать Другие алгоритмы полиномиальных произведений, в которых еще больше уменьшается число сложений за счет некоторого увеличения числа умножений.