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

摘要

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

关键词

离散傅立叶变换(DFT) / 快速傅立叶变换(FFT) / 算术傅立叶变换(AFT)

基金资助

国家教育部博士点基金!（9703825）