一种更有效的素数长度DFT快速算法

A more Efficient Algorithm for Computing DFT of Primary Length

离散傅立叶变换（ＤＦＴ） 在数字信号处理、数字图象处理等许多领域起着重要作用．素数长度ＤＦＴ的快速计算是任意长度ＤＦＴ快速算法的基础及重要组成部分．传统的素数长度ＤＦＴ快速算法效率较低，且具有程序过于复杂，子进程调度较多等许多不利因素，很难在实际问题中得到应用．本文采用了一种新的傅里叶分析技术———算术傅立叶变换（ＡＦＴ） 来计算ＤＦＴ．该方法乘法计算量仅为Ｏ（ Ｎ） ，当用于计算素数长度ＤＦＴ 时，其效率比传统的方法高，且算法程序简单，并行性好．从而解决了传统方法计算素数长度ＤＦＴ 的困难，同时为任意长度ＤＦＴ 的快速计算开辟了一条新的思路和途径．

The discrete Fourier transform (DFT) plays an important role in digital signal processing, digital image processing and many other fields. The fast computing of DFTs of prime length is the basic and an important part of the fast computing of DFTs of any length. Traditional fast methods for computing DFTs of prime length show low efficiency. They also have many other disadvantages such as too complex programs, too many child proceedings, etc, which makes them difficult for using in practice. In this paper, we adopt a new technique for Fourier analysis called the arithmetic Fourier transform (AFT) for computing DFT. This method needs only O(N ) multiplications, when used for computing DFTs of prime length, this method shows much higher efficiency than the traditional methods. It has a very simple program and it can be easily performed in parrallel, which overcomes the difficulties of the traditional methods. Moreover, it gives a new idea and road for computing DFTs of any length.