【多维离散傅里叶变换算法计算复杂性与快速新算法的研究】杨德坤.pdf

【多维离散傅里叶变换算法计算复杂性与快速新算法的研究】杨德坤.pdf

摘要 本文从DFT的变换矩阵分解成矩阵Kronecker积形式出发,提 出一种二维傅里叶变换DFT(2.2)算法的统一矩阵表示形式,由此 导出现有各种DFT(2.2)算法的矩阵Kronecker积表示式,根据这 数.本文提出两种DFT(2.2)快速新算法:这两种DFT(2.2)快速 新算法都仅使用实数乘法,具有现有各种DFT(2.2)算法无法比拟 的优点:在实数据输入情况下有很好的的适应性,能在不改变算 法实现结构条件下减少一半乘法次数,此外,DFT(2.2)快速新算 法所需要的乘法次数和加法次数是现有各种DFT(2.2)算法中最 工 少的,本文首次提出一种k维离散傅里叶变换DFT(p.目 第一章 绪论 第二章 二维离散傅里叶变换DFT(2.2)的乘法复杂性 2-1 矩阵Kronecker积及其性质 2-2 DFT(2;2)算法统一矩阵形式 DFT(2;2)算法的最小乘法次数 2-2 第三章 二维离散傅里叶变换DFT(2;2)的两种快速新算法 53-1 引言 53-2 3-3 各种DFT(2;2)快速算法比较 3-4 3-5 第四章 4-1 引言 4-2 循环卷积与DFT 4-3 k维离散傅里叶变换DFT(p.k)快速算法 K 4-4 DFT(p.多维DFT(DFT(p.k)算法计算复杂性与快速新算法进行较为全面的 探讨.这项工作的最初动机在于对如何使多维DFT广泛应用到现代信 号处理之中这个目标的浓厚兴趣.到目前为止,2的幂长度的一维DFT(DFT(2)和奇素数P的幂长 度的一维DFT(DFT(p)算法研究沿着各自的方向发展,已经形成各 自比较完整的体系.在DFT(2)快速算法研究方面,从不同的角度得到具有相同的 目前最少计算量的几种算法年,J.B.Martens利用多项式域 的DFT定义,用递归割园分解方法,推导出一种递归割园分解算法(RCFA)[23].与RCFA出现同时,P.Duhamel和H.