ГЛАВА 3. ВЫЧИСЛЕНИЕ ДВУМЕРНЫХ СВЕРТОК И ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

(Г. Дж. Нуссбаумер)

Главная цель главы—вывод быстрых алгоритмов вычисления двумерных сверток и дискретных преобразований Фурье (ДПФ). Эти алгоритмы базируются на преобразовании двумерных последовательностей в одномерные с использованием основных свойств колец полиномов. По сравнению с более традиционными методами, основанными на быстром преобразовании Фурье (БПФ), они значительно снижают число арифметических операций, требуемых для вычисления сверток и ДПФ.

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

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

3.1. Свертки и алгебра полиномов

Основой многих новейших методов быстрого вычисления сверток к ДПФ. таких, как алгоритм Винограда преобразования Фурье [3.1], алгоритм быстрой свертки Агарвала — Кули [3.2] и полиномиальные преобразования [3.3-3.5], является алгебра полиномов. Поскольку алгебра полиномов не нашла еще широкого применения в радиоэлектронике, за исключением теории кодирования, приведем здесь краткие сведения, касающиеся наиболее важных аспектов, связанных с вычислением сверток. Для более детального изучения читатель можег воспользоваться любым учебником по современной алгебре [3.6].

Рассмотрим сначала дискретную свертку

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

где — элементы некоторого поля обычно вещественных или комплексных чисел.

Очевидно, что полиномиальное представление свертки является более сложным, чем стандартное представление. Мы, однако, увидим, что использование полиномов обеспечивает эффективное снижение сложности вычисления сверток и полиномиальных произведений. Для этого необходимо сначала ввести понятия об остаточных полиномах и китайской теореме об остатках.

3.1.1. Остаточные полиномы

Рассматривая полиномы с коэффициентами, заданными на поле, определим что полином является делителем полинома если можно найти такой полином для которого выполняется соотношение . Полином называется неприводимым, если только его единственными делителя

ни являются полиномы степени которых равны 0. Если не является делителем , то при делении на образуется остаток

Легко показать, что это представление единственно. Все полиномы, которые при делении на дают один и тот же остаток называются конгруэнтными по модулю Соотношение конгруэнтности обозначается

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

В этом случае может быть однозначно выражен как функция полиномов полученных приведением по модулю различных полиномов Это выражение, являющееся обобщением на кольцах полиномов известной в теории чисел китайской теоремы об остатках [3.7], задается как:

где для каждого значения и индекса

Соотношения (3.8), (3.9) можно легко проверить приведением (3.8) по модулю различных полиномов Поскольку выражение (3.8) выполняется для каждого Точно так же приведение определенного в по модулю дает (3.9) при условии, что Выполнение последнего условия гарантируется тем. что полиномы являются взаимно-простыми. Полиномы можно легко построить, пользуясь полиномиальным вариантом алгоритма Евклида.