用多项式变换及W变换计算二维卷积

摘要

本文先给出了一种用Ｗ变换计算模（ｚ＾Ｎ＋１）多项式积的新算法。然后将它与多项式变换结合用于计算Ｎ×Ｎ（Ｎ＝２＾ｔ）二维复值圆卷积。这种结合法完成上述卷积仅需２Ｎ＾２·（ｌｏｇ２Ｎ＋３／２）次实乘及１０·Ｎ＾２·ｌｏｇ２Ｎ＋Ｎ＾２次实加。该乘法量仅为常规多项式变换法的一半。