3.2.2. Составные полиномиальные преобразования

Для простоты мы до сих пор ограничивались -точечными свертками, -простое. На практике метод полиномиального преобразования не ограничен случаем простого Из (3.28) — (3.31) ясно, что любое полиномиальное преобразование, имеющее корень и определенное по модулю полинома будет обладать свойством циклической свертки при условии

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

где степень каждого полинома есть -функция Эйлера Покажем сначала, что всегда существует полиномиальное -точечное преобразование с корнем обладающее свойством циклической свертки, если оно определено по модулю являющемуся наибольшим циклотомическим полиномом, множителем Это можно увидеть, если учесть, что, поскольку и является множителем то

Отсюда вытекает (3.34). В условии так как

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

Тогда Наибольший полиномиальный множитель есть полином степени Наибольший полиномиальный множитель является цнклотомическнм полиномом степени отличается от поскольку , и он не может быть множителем для так как — неприводимый полином. Таким образом, Тем самым соотношение (3.35) доказано.

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

Необходимо также заметить, что когда -точечное полиномиальное преобразование (корень — нечетное) обладает свойством свертки, всегда можно увеличить длину преобразуемой последовательности до где . В этом случае корнем нового преобразования будет где Это свойство является прямым следствием того, что — корень из единицы порядка — корень из единицы порядка где — взаимно-простые. Оно чрезвычайно полезно для вычисления и -точечных сверток, так как в этих случаях или и полиномиальные преобразования по-прежнему вычисляются без умножений.

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

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

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

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

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

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