| N=2^t点DFT的快速卷积算法 |
| |
| 引用本文： | 蒋增荣 成礼智. N=2^t点DFT的快速卷积算法[J]. 高等学校计算数学学报, 1997, 19(2): 163-172 |
| |
| 作者姓名： | 蒋增荣 成礼智 |
| |
| 作者单位： | 国防科技大学系统工程与数学系 长沙410073 |
| |
| 摘 要： | 从所周知,循环卷积和离散富里叶变换(DFT)可以互相计算,只要得到其中一个的快速算法就可导出另一个的快速算法。循环卷积目前已有乘法量为O(N)的最佳算法(特别是当N较小时),为此关键是如何将DFT转化为循环卷积,当DFT的长度N=p(p为素数),Rader利用有限域GF(p)的乘法群是循环群就成功地将p点DFT转化为Q(p)(F(p)为户的Euler函数)点循环卷积;当N=p~e时,由于商环Z/(p~e)存在F(p~c)阶元素,人们也成功地将p~c点DFT转化为P(p~(c-1))一系列循环卷积,即一个y(p~c)点循环卷积,二个P(p~(c-1))点
|
| 关 键 词： | 傅里叶变换 快速卷积算法 离散傅里叶变换 |
FAST CONVOLUTION ALGORITHMS FOR DFT OF SIZE N=2~t |
| |
| Jiang Zengrong Cheng Lizhi. FAST CONVOLUTION ALGORITHMS FOR DFT OF SIZE N=2~t[J]. Numerical Mathematics A Journal of Chinese Universities, 1997, 19(2): 163-172 |
| |
| Authors: | Jiang Zengrong Cheng Lizhi |
| |
| Affiliation: | National University of Defense Technology |
| |
| Abstract: | In this paper, a recursive algorithm for DFT of size N=2t by using isomorphism of number system and Chinese Remainder theorem is developed, that is reduce a DFT of size N to a DFT of size N/2 and a DFT of size N/4, a skew-cyclic convolution of size N/8. Then by the optimal convolution algoritm, we obtain a fast convolution algorithms for DFT of size N=2t, the number of read multiplication is M(N) = 7N+O(1), where O(1) is infinitesimal about N with order one. As compared with Cooley-Tukey radix-2 FFT algorithm, the number of multiplication was reduced by about one order of magnitude. |
| |
| Keywords: | DPT cyclic convolution isomorphism chinese Remainder theorem. |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
