| 引用本文: | 蒋增荣.用快速多项式变换（FPT）计算二维离散富里叶变换（DFT）.[J].国防科技大学学报,1982,(4):71-88.[点击复制] |
| Jiang Zengrong.Computation of Two Dimensional Discrete Fourier Transforms (DFT) Using Fast Polynomial Transforms (FPT)[J].Journal of National University of Defense Technology,1982,(4):71-88[点击复制] |
|
| |
|
|
| 本文已被：浏览 5405次 下载 5291次 |
| 用快速多项式变换（FPT）计算二维离散富里叶变换（DFT） |
| 蒋增荣 |
|
()
|
| 摘要: |
| 本文利用快速多项式变化（FPT）计算N×M型二维DFT(M=2m,N=2m-r+1,1≤r≤m),所需的乘法及加法次数（复乘及复加）分别为Mu=1/2NMlog2M-3/2NM+N2+N(1+log2M-log2N)
Ad=NMlog2NM，与通常的以2为基的二维FFT比较，加法次数相同，乘法次数减少约30-40%，从而提高了计算精度。本算法还适用于并行算法。 |
| 关键词: |
| DOI： |
| 投稿日期：1981-12-20 |
| 基金项目: |
|
| Computation of Two Dimensional Discrete Fourier Transforms (DFT) Using Fast Polynomial Transforms (FPT) |
| Jiang Zengrong |
| Abstract: |
| In this paper，a fast algorithm is developed to compute two-dimensional Discrete Fourier Transform (DFT) of an array of NxM complex number points using FPT，where M=2m,N=2m-r+1,1≤r≤m.As compared with the conventional radix-2 two-dimensional Fast Fourier Transforms,this new algorithm requires less number of multiplications (decrease by 30-40%) and same number of additions, so that elevates the computing accuracy. The number of multiplications and additions are respectively
Mu=1/2NMlog2M-3/2NM+N2+N(1+log2M-log2N)
Ad= NMlog2MN.
This algorithm also has the advantage to adopt the parallel algorithm. |
| Keywords: |
|
|
