3.4. Заключительные замечания

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

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

По-видимому, наиболее интересны те полиномиальные преобразования, размерность которых равна степени 2. Эти преобразования имеют структуру,

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