In this paper a new fast convolution algorithm is introduced. The concept of this new algorithm is fully algebraic. Therefore, no roundoff errors occur. The signal length N is a prime power N=p/sup n/, p/spl ges/2. Hence the paper generalizes the results of a previous paper (Minkwitz and Creutzburg, 1992) for power of 2 lengths. The cyclic convolution of signals of length N is interpreted as a multiplication of polynomials of degree N-1 modulo the polynomial X/sup N/-1. The calculation in our new method is done in a finite field extension of the field Q of rational numbers. To minimize the number of operations, an extension field Q[/spl omega/] is chosen, with /spl omega/ as a symbolic root of unity and deg[Q[/spl omega/]:Q]=(p-1/p[/spl radic/N]*). Here, [ ]* and [ ]* denote the well-known CEILING and FLOOR functions, respectively, but rather a mapping to the next larger power of p. The method achieves an arithmetic cost of O (N log N/spl middot/log log N) operations over Q, which is the same as that of the well-known algorithm by SCHONHAGE-STRASSEN. However, our algorithm avoids the much more complicated FERMAT arithmetic over integers and works for primes p/spl ne/2 as well, although it performs best with small p, preferably p=2 or 3.
展开▼
机译：本文介绍了一种新的快速卷积算法。这种新算法的概念是完全代数的。因此，不会发生舍入错误。信号长度N是素数功率N ＝ p / sup n /，p / spl ges / 2。因此，本文归纳了前一篇论文（Minkwitz和Creutzburg，1992）关于2个长度的幂的结果。长度为N的信号的循环卷积被解释为度N-1的多项式乘以多项式X / sup N / -1的乘积。我们新方法中的计算是在有理数字段Q的有限字段扩展中完成的。为了最大程度地减少操作次数，选择了扩展字段Q [/ spl omega /]，其中/ spl omega /是统一的符号根，deg [Q [/ spl omega /]：Q] =（p-1 / p [/ spl radic / N] *）。在这里，[] *和[] *分别表示众所周知的CEILING和FLOOR函数，而是映射到p的下一个较大幂。该方法在Q上实现了O（N log N / spl middot / log log N）次运算的算术成本，这与SCHONHAGE-STRASSEN的著名算法的算术成本相同。但是，我们的算法避免了整数上复杂得多的FERMAT算法，并且也适用于质数p / spl ne / 2，尽管它在较小的p（最好是p = 2或3）下表现最佳。
展开▼
