计算长度2~mDFT的新算法

本文提出一种计算长度为2~m的离散傅里叶变换(DFT)的新算法。算法所需的实数乘法和实数加法运算量均低于常规FFT算法,同时具有和常规FFT类似的蝶形运算结构,易于计算机软件和硬件实现。     

基于ARMv8处理器的实数FFT实现与性能优化研究

FFT(快速傅里叶变换)是离散傅里叶变换或其逆变换的一种常见快速算法,是高性能计算领域最重要的基础核心算法之一,在科学、工程和数学等领域的应用十分广泛.实数FFT算法,即输入或者输出为实数的FFT算法,其中包括R2C(Real-to-Complex)、C2R(Complex-to-Real)等变换类型.相比复数FFT算法,实数FFT算法在图形图像处理、数据压缩等领域有着不可替代的作用.传统实数FFT实现针对的是输入规模为偶数,一般转变为复数FFT进行运算.然而当前鲜有针对输入规模为奇数的实数FFT高效实现.对此,本文提出了一种实数FFT高效算法(DRFFT),并采用蝶形网络优化、蝶形计算优化、访存优化、SIMD优化以及数据转置等方法进行优化,大幅提升了实数FFT算法性能,最终构建了一种针对实数FFT的高性能算法库.实验结果表明,本文实现的DRFFT R2C变换在单双精度浮点数处理方面较FFTW库性能分别平均提升了37.6%和4.6%,较ARMPL库性能分别平均提升了67.6%和28.1%.DRFFT C2R变换在单双精度浮点数处理方面则较FFTW库性能分别平均提升了58.6%和10.8...     

Agarwal—Cooley短卷积嵌套算法（ACCNA）

离散富里叶变换(DFT)和卷积计算在图象、数字信号处理中起着重要的作用,因此对快速算法的研究早就引起人们足够的重视。自从1965年Cooley、Tukey提出基-2快速富里叶变换(FFT)算法以来,各种新算法、改进算法不断涌现,其中Winograd在1976年提出的短DFT嵌套算法(WFTA)是一种计算DFT的有效方法。1977年后,H.Silverman、J.H.McClellan、L.R.Morris等曾先后详细讨论过WFTA     

基于算术傅里叶变换的离散Hartley变换的快速算法

离散Hartley变换是一种有用的实值正交变换。文中对其快速算法进行研究,首先介绍利用算术傅里叶变换（AFT）计算离散傅里叶变换（DFT）可使其乘法计算量仅为O（N）,然后文章根据这一特点,分析离散Hartley变换（DHT）的结构特征,通过DFT将AFT和DHT建立了直接联系,提出了一种新的快速DHT算法。算法的计算复杂度能够达到线性O（N）,且算法结构简单,公式统一且易于实现,并与其他快速算法进行了比较,分析可知在数据长度不是2的幂次方时,文中提出的算法的计算时间明显比其他算法的计算时间要小。实验结果也验证了文中算法的有效性,从而为DHT的快速计算开辟了新的思路和途径。     

长为PL的快速递归付里叶变换算法

一、引言离散付里叶变换(DFT)的实际应用愈来愈广泛,但直接计算DFT需要正比于N~2的运算次数。显然当N很大时,直接计算DFT要花费大量的计算时间.一九六五年,Cooley和Tukey提出的快速付里叶变换(FFT)使计算DFT的运算次数正比于N logN,从而使运     

离散Hartley变换(DHT)及其快速算法

一、引言 离散Hartley变换(DHT)在图象处理、模识识别等领域都有一定的应用。1984年,R.N.Bracewell提出了一种快速Hartley变换(FHT)算法。最近,R.Ku-meresan提出了二维离散Hartley变换的概念,并研究了其特殊情形(N×N点)的     

多维快速Hadamard变换的计算

前 言 近年来,在数字信息的表示和分类、数字谱分析、数据压缩和数字图象处理等方面,快速Hadamard变换(FHT)已显示出很大的优越性.但是,大部分工作仅限于一维及二维FHT的应用.要对三维及三维以上的多维数据应用FHT却十分困难. 本文提出一个计算多维Hadamard变换的新的快速算法.它适用于点数为N=2~p     

基数为2的DFT的最快速算法

自从1965年Cooley-Tukey提出快速富氏变换(FFT)算法以后,离散富氏变换(DFT)在许多领域得到广泛的应用。但是,在处理大型数据时,FFT算法的计算量仍然很大。因此,人们对DFT不断提出一些新的快速算法,其中以R.D.Preuss在[5]中提出的算法的计算量较小,仅为其它新算法计算量的三分之二。但是,Preuss算法需要将     

节省乘法次数的FFT程序

计算离散Fourier变换(DFT)快速算法的种类各式各样,因此实现FFT程序也是名目繁多的.介绍了一种FFT程序(以下简称程序1),使用它计算一个长度N=2~m(m为大于1的整数)的复数序列需要2Nlog_2N次实数乘法,但这个程序在运算量的节省上还有很大潜力.在此,我们给出一种FFT程序(以下简称程序2),它以程序1为基础,不多占存贮单元,但计算N点复数序列仅需     

基于LS MPP的图像并行傅立叶分析技术(1)--算法的原理、分析与设计

基于LSMPP的K元2-立方体网络结构,设计了一种新颖快速的计算FFT的SIMD算法。系统地分析了时间提取的基-2一堆FFT算法及其原理,较详细地讨论了用二雏FFT算法并行计算二堆DFT的问题：主要从算法原理出发,分析并给出了在LSMPP SIMD计算机上用二雏FFT并行计算二堆DFT时各变换步的变换矩阵及其格式,设计了自动建立各变换步的变换矩阵的算法。     

多维快速循环褶积的计算

目前,在数字滤波、图象处理、数字信号处理等许多方面,循环褶积得到了广泛地应用。但是,常规作法都是多次使用一维FFT进行处理。例如,一维褶积要施行三次FFT;(N×N)序列的二维褶积要施行6N次FFT;(N×N×N)序列的三维褶积要施行9N~2次FFT。至于多维褶积则十分困难,甚至难以实现。 本文提出一个多维褶积的新的快速算法。我们利用多维广义正交变换矩阵定义多维     

FFT计算菲涅尔衍射相位的跳变与矫正研究

采用傅里叶变换算法计算菲涅尔衍射相位时,在相位未解包裹的情况下,接收面上提取的相位分布曲线会出现跳变,如果进行解包裹,必然会导致错误的结果。研究发现用傅里叶变换算法进行衍射计算导致接收面上相位跳变的原因,是因为快速傅里叶变换（FFT）对矩阵标注索引的方式与离散傅里叶变换（DFT）有所区别,从而导致计算结果的相位与真实相位有差异。本文提出在FFT运算前后分别进行一次倒谱的方法矫正这种相位跳变,并仿真利用单次FFT进行二维矩孔的菲涅尔衍射,用2次倒谱矫正接收面上的相位跳变,结果证明了该矫正方法的可行性。     

基4FFT算法

FFT(快速富里叶变换)算法与DFT(离散富里叶变换)算法比较,其运算量显著减少,用计算机实现时速度大为提高。但FFT过程所需的运算量仍较可观,常给数字信号的实时处理带来困难。理论和实践表明,若要加快FFT算法在计算机上的实现,关键是得设     

离散Hartley变换的一种快速递归算法

离散Hartley变换(DHT)在数字信号处理中逐渐得到广泛的应用。本文推导了计算DHT的一种快速递归算法,给出了一般信号流图,并与DHT的其他快速算法作了比较。     

高效FFT硬化方案

本文应用Cooley-TuKey经典算法,采用双加法器和“映像”存储器,获得100％的高效FFT流水蝶形运算,使1024个实数点达到1毫秒的速度,并导出其硬化的寻址、运算序列。 通常计算N点DFT,也即FFT可以用下式表示:     

二维Tchebichef 正交矩反变换的快速算法

提出了一种二维Tchebichef矩反变换的快速算法.借助Clenshaw递推公式,推导了一维Tchebichef矩反变换的快速算法,并将其推广至二维Tchebichef正交矩反变换的计算.与以迭代方式计算Tchebichef多项式进而计算二维Tchebichef矩反变换的方法相比,文中提出的算法有效地减少了算术运算的次数,大幅提高了计算速度.实验结果表明了该方法的有效性.     

基于FFT的正弦信号失真度测试方法

通过对正弦信号失真度计算公式的描述，提出了一种利用FFT来计算信号失真度的方法，并重点对DFT的定义、如何用DFT来计算模拟信号的傅立叶变换、FFT的有关原理，以及信号的倍频电路进行了论述，并给出FFT算法的源程序。     

频域抽取多维向量基快速傅里叶变换

给出了频域抽取(DIF)多维向量基快速傅里叶变换(FFT)算法。对多维频域信号的每一维,采用向量基2频域抽取法,导出了快速算法蝶形运算的一般形式。该FFT算法适合于维数为任意整数的情况,当维数为1时,算法退化为著名的频域抽取向量基2 FFT算法。为了便于编程实现,以频域抽取3维向量基FFT算法为例,给出了快速算法实现流程,该流程易于向任意整数维推广。计算量比较结果显示,频域抽取多维向量基FFT算法比多维分离式FFT算法计算量低。     

多维离散余弦变换的快速算法

本文提出多维离散余弦变换(DCT)的一个快速算法。我们将点数为2的整次幂的p维离散信号,按照编号偶数正序、奇数逆序进行重排。经过适当地变换,就将p维DCT导致p维DFT。再利用文献[1]或[2]中处理多维DFT的新方法,就可获得p维DCT的快速算法。本算法直观、简明、且易于在计算机上实现。     

利用对称性加速实序列FFT的方法及其FPGA实现*

针对工程实践中傅里叶变换的输入序列一般为实序列的情况,充分利用FFT（快速傅里叶变换）奇偶虚实的对称性质,提出了一种实序列FFT的加速算法。将2N点的实序列DFT转换为N点的复序列DFT,并行计算使运算量明显减少;并给出了基于FPGA的硬件实现方法。