一种更有效的素数长度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.