一种快速计算循环卷积的新算法

A New Fast Algorithm to Compute Circular Convolution

本文提出一种阶数为d·2p的新的快速循环卷积算法，它的乘法计算量相对基2分裂基（split－Radix）FFT卷积算法减少25％，加法计算量减少10％；新算法可推广到GF（22t＋1）有限域，只需整数的循环移位和加法。

In this paper, A new fast algorithm of circular convolution with the d. 2p length is proposed, Thenumber of multiplicaions required is 25% less than the split-Radix FFT convolution algorithm, and its additionnumber is 10% less than the split-Radix FFT convolution algorithm, The new algorithm can applied to GF(22t+ 1)finite field, and only requires circular shifts and additions of integer.