计算二维FFT的MIMD并行算法

1.引言 Mueller提出一种计算信号阵列S(N,N)(设N=2~M)二维FFT的并行算法,它要用N~2/2个处理单元和2N个M立方体网,资源开销巨大,结构复杂,难以实现。而本文提出的两种计算信号阵列S(N,N)二维FFT的并行算法,一种叫宏流水线MIMD并     

节省乘法次数的FFT程序

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

大规模集群上多维FFT算法的实现与优化研究

快速傅里叶变换(fast Fourier transform,FFT)是用于计算离散傅里叶变换(discrete Fourier transform,DFT)或其逆运算的快速算法,在工程、科学和数学领域的应用非常广泛,例如信号分解、数字滤波、图像处理等。因此,在实际应用中对FFT算法进行细粒度优化是非常重要的。研究了FFT算法常用的分解策略以及FFT算法在大规模集群系统上的并行实现,并提出了相关的优化策略。在此基础上,对多种FFT算法在不同平台上进行了性能评估,并分析了各算法的实现、优缺点及其在大规模计算时的可扩展性。实验结果表明,相关研究有助于对现有的FFT算法进行进一步的优化,以及指导如何在大规模CPU+GPU的异构系统上根据不同需求选择实现性能更优的FFT算法。     

龙芯3A处理器上FFT的高效实现

FFT(Fast Fourier transform,快速傅立叶变换)是工程应用中的一个基本算法,优化其性能对于推广龙芯系列处理器的应用具有重要意义.本文充分挖掘龙芯3A处理器的硬件特性,对运算量和调整位序的过程作了优化并使用128位访存来减少访存指令的比例,从而实现了高效的FFT算法.实验结果表明,在825M龙芯3A处理器上经过优化后的一维FFT的速度是FF-TW库的2.5倍左右,而二维FFT的速度则是FFTW的3倍左右.     

多维快速循环褶积的计算

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

高分辨图像二维FFT正/反变换实时处理方法及硬件实现*

高精度密集型数值计算和大规模数据缓存,是高分辨率图像二维FFT(快速傅里叶变换)实时实现中的主要难点。利用实信号傅里叶变换的周期对称性和频域数据的共轭对称性,提出了一种高效且易于硬件实现的二维FFT正/反变换的实时处理方法,将实值图像二维FFT中的一维FFT计算和存储需求缩减了近一半。在以4片TS201为计算核心的DSP处理平台上,使用该方法实现了二维FFT正/反变换和图像频域滤波。实验表明,无须片外存储,单片TS201可处理最大512×512像素的图像;该尺寸图像的正/反变换总处理时间为49.6 ms,     

计算q~(l_1)×q~(l_2)二维DCT的快速算法

离散余弦变换 (DCT)广泛应用于信号处理的许多领域 ,多维 DCT(MD- DCT)是图像处理和视频信号处理的重要工具 .通常 ,多维 DCT采用行列法用一维算法实现 ,实现效率较低 .近年来虽然出现了一些多维 DCT直接实现算法 ,但大多要求变换为 2 n× 2 n,限制了适用范围 .该文研究较一般的二维 DCT快速算法 ,将 ql1 × ql2 (q为奇素数 ;l1 ,l2 分别为两个不同的整数 )二维 DCT转化为多项式变换和一维简化余弦变换 ,通过特别设计的快速多项式变换算法和 1D- RDCT递归分解算法 ,提出了一种计算复杂性较低且具有规则运算结构的 ql1 × ql2 二维 DCT算法 .本算法的设计方法可以方便地推广到多维 (>2 )的情况 .     

位片FFT专用计算机(BSFS系统)

本文论述一台用位片器件(Am2900系列)构成的专用计算机系统,此专用计算机用于信号处理,能对N=1024个采样数据进行FFT变换,由于位片式处理机是以微程序级面向用户的,所以本系统由微程序来实现FFT算法,本专用计算机通过模拟系统的模拟,证实了其方案是可行的。     

在多处理机中实现图像处理的并行化算法研究

单处理机系统难于满足大型数字图像的实时处理要求,多处理机并行工作系统可以提高数字图像处理的效率和效果.本文分析多处理机系统在数字图像处理中的并行化机会,运用数字图像处理中傅里叶变换的特点,在多处理机中实现流水线算法、FFT算法的并行化(二元交换算法)、快速傅里叶变换、基本的主从实现等算法,解决了傅里叶变换和快速傅里叶变换中N取较大值时所产生的顺序复杂性,进而使多处理机系统中能够使多个处理机之间能够更加协调工作,更加有效地利用CPU.     

基于DSP的实数FFT算法研究与实现

介绍了一种实数快速傅里叶变换(FFT)的设计原理及实现方法,利用输入序列的对称性,将2N点的实数FFT计算转化为N点复数FFT计算,然后将FFT的N点复数输出序列进行适当的运算组合,获得原实数输入的2N点FFT复数输出序列,使FFT的运算量减少了近一半,很大程度上减少了系统的运算时间,解决了信号处理系统要求实时处理与傅里叶变换运算量大之间的矛盾．同时,给出了在TMS320VC5402 DSP上实现实数FFT的软件设计,并比较了执行16,32,64,128,256,512,1024点实数FFT程序代码与相同点数复数FFT的程序代码运行时间．经过实验验证,各项指标均达到了设计要求．     

An approach for refocusing of ground fast-moving target and high-order motion parameter estimation using Radon-high-order time-chirp rate transform

Long synthetic aperture time can improve the imaging quality of a ground moving target, whereas a moving target may be severely smeared in the cross-range image due to the range migration and the Doppler frequency migration. In this paper, the effects of the third-order Doppler broadening and Doppler ambiguity of a fast-moving target are considered. To address these issues, a novel motion parameter estimation method named high-order time-chirp rate transform (HTRT) is proposed, and then a new synthetic aperture radar (SAR) imaging method based on Radon-HTRT (RHTRT) for a ground moving target is developed. The major contributions are as follows: 1) The proposed SAR imaging method can eliminate the Doppler ambiguity effect. 2) The proposed method can realize longer time coherent integration than Radon–Fourier transform (RFT) and Radon–fractional Fourier transform (RFRFT) methods. 3) The proposed method is computationally efficient since HTRT can obtain the motion parameters of a moving target via performing the 2-dimensional (2-D) fast Fourier transform (FFT). Both the simulated and real data processing results show that the proposed method can finely image a ground moving target in a high signal-to-clutter and noise ratio (SCNR) environment.     

Fast implementation of ground maneuvering target focusing

Ground maneuvering target detection is a hot topic in the applications of synthetic aperture radar (SAR), whereas its focusing performance is severely deteriorated by range migration and Doppler frequency migration during a long integration time. This paper proposes a novel method to image the target and estimate its parameters via performing two independent 2-dimensional (2-D) searches after a parameter separation operation. In order to improve the search speed, we set the limited search ranges and propose local mapping sparse Fourier transform (LMSFT) to replace fast Fourier transform (FFT). Compared with the traditional algorithms, the proposed method can realize fast coherent integration of multiple maneuvering targets via compensating the high-order range migration and Doppler frequency migration. In addition, the proposed method is stable under noise. Several simulation results have validated the effectiveness of the proposed method.     

基于DMFT的高动态载波捕获算法的改进

基于FFT的载波捕获方法对高动态信号不能适用,离散匹配傅里叶变换(DMFT)虽可用于高动态信号,但是其运算量大、精确度差。基于以上分析本文提出了将延迟自相关、FFT与DMFT三者相结合的二维载波捕获算法。首先将中频采样信号与其延迟做自相关,通过信号的延迟自相关的FFT得到频率变化率的粗略估计值,进而得到起始频偏的粗略估计值,然后在所得值附近利用DMFT进行搜索,从而获得高精度的参数估计值。此方法缩小了搜索的范围,在运算量减少的同时,也提高了参数的估计精度。仿真结果证明本文提出的方法有效可行。     

Performance Analysis of FFT Algorithms on Multiprocessor Systems

A decimation-in-time radix-2 fast Fourier transform (FFT) algorithm is considered here for implementation in multiprocessors with shared bus, multistage interconnection network (MIN), and in mesh connected computers. Results are derived for data allocation, interprocessor communication, approximate computation time, and speedup of an N point FFT on any P available processing elements (PE's). Further generalization is obtained for a radix-r FFT algorithm. An N X N point two-dimensional discrete Fourier transform (DFT) implementation is also considered when one or more rows of the input data matrix are allocated to each PE.     

可扩展的旋转因子表及FFT算法

该文提出了一个用于快速Fourier变换计算的反写码序的旋转因了表，这种旋转因子表具有可扩展性：本质上，这种旋转因子表的分量与变换的点数无关，当点数改变时，这种旋转因子表无须重新计算或者容易扩展；根据这种旋转因子表，该文设计了一个结构规整的基本基4计算2^n点FFT的算法及软件程序，该程序与FFTW软件包进行了对比实验，文中还以蛋白质序列相似性计算为例，对作者的算法与FFTW软件包中的相庆算法进行了对比实验，结果表明，采用该文的算法可节省计算时间约31．7％。     

可逆的DCT整型变换与无失真图像压缩

使用提升的方法,利用FFT(fast Fourier transform)的蝶型构造,完成了FFT与DCT(discrete cosine transform)的从整数到整数的变换.变换本身是可逆的,因此非常适合于无失真图像压缩.     

Fast Fourier Transform for Hexagonal Aggregates

Hexagonal aggregates are hierarchical arrangements of hexagonal cells. These hexagonal cells may be efficiently addressed using a scheme known as generalized balanced ternary for dimension 2, or GBT₂. The objects of interest in this paper are digital images whose domains are hexagonal aggregates. We define a discrete Fourier transform (DFT) for such images. The main result of this paper is a radix-7, decimation-in-space fast Fourier transform (FFT) for images defined on hexagonal aggregates. The algorithm has complexity N log₇ N. It is expressed in terms of the p-product, a generalization of matrix multiplication. Data reordering (also known as shuffle permutations) is generally associated with FFT algorithms. However, use of the p-product makes data reordering unnecessary.     

Constraining error—A sliding discrete Fourier transform investigation

The sliding discrete Fourier transform provides an alternative to the FFT, permitting a custom choice of frequency decomposition which outputs an update after each input sample. The technique relies on the application of the Fourier shift property, and is recursive by nature. This work investigates the error performance of alternative techniques (SDFT; gSDFT; mSDFT, rSDFT; and Douglas and Soh algorithms) under both floating point and fixed point arithmetic constraints. The results highlight that the sliding discrete Fourier transform with error correction provides consistent error performance over a range of test cases, and indicates the limitations applicable to all techniques.     

Computing the Fourier transform of real data on a hypercube

There are two ways, other than the standard fast Fourier transform (FFT) algorithm, of computing Fourier transforms of real data, namely, (1)the real fast Fourier transform (RFFT) algorithm, and (2) the fast Hartley transform (FHT) algorithm. On a sequential computer, it has been shown that both the RFFT and the FHT algorithms are faster than the FFT algorithm. However, it is not obvious that the same is true on a parallel machine. The communication requirements of the RFFT and the FHT algorithms, which are critical to the cost of any parallel implementation, are different from those of the FFT algorithm. In this paper we present efficient implementations of the RFFT and the FHT algorithms on a hypercube machine. Experimental results are given for the implementation of the RFFT and the FHT algorithms on the NCUBE machine.     

Toeplitz矩阵相乘的快速卷积算法

本文利用Ｔｏｅｐｌｉｔｚ矩阵可分解为循环阵与斜循环阵之和的特点２，借助于卷积的ＦＦＴ算法，推导出计算两个Ｔｏｅｐｌｉｔｚ矩阵之积的一种新的快速算法，其乘法复杂性为２ｎ＾２＋Ｏ（ｎｌｏｇ２ｎ）。