二维离散余弦变换的一种新的快速算法

本文介绍了二维离散余弦变换(DCT)的一种新的快速算法。对于NN DCT(N=2m),只需用N个一维DCT和若干加法运算。与常规的行-列法相比,所需的乘法运算量减少了一半,也比其它的快速算法的乘法运算量要少,而加法运算量基本上是相同的。     

快速多项式变换(FPT)算法计算二维离散傅里叶变换(DFT)的一种新的改进方法

本文研究了利用快速多项式变换(FPT)来计算大小为N×N(N=2~t)的二维离散傅里叶变换。本文首先对多项式变换计算二维DFT的实现方案进行了讨论,提出了更利于具有专门乘法硬件处理器计算的FPf实现方案——用FFT法汁算FPT中奇DFT的算法。并在此基础上,通过对乘法和加法的综合考虑,对这种实现方案提出了一种改进方法。这种改进方法通过抽点,将一次N点奇DFT,分解为2次2点DFT,在乘法量基本保持不变下,加法量比原FPT减少5%左右。这种算法比常规的行——列法在乘法上减少约50%,在加法上减少约15%。     

二维离散W变换的多项式变换算法

本文利用多项式变换将二维离散Ｗ变换直接转移为一系列一维离散Ｗ变换，从而得到２ＤＤＷＴ的多项式变换法，算法不需复运算，结构简单，同上前使用的行列算法相比，该算法的乘法次数减少一倍，加法次数有所减少。     

离散傅里叶变换的算术傅里叶变换算法

离散傅里叶变换(DFT)在数字信号处理等许多领域中起着重要作用.本文采用一种新的傅里叶分析技术—算术傅里叶变换(AFT)来计算DFT.这种算法的乘法计算量仅为O(N);算法的计算过程简单,公式一致,克服了任意长度DFT传统快速算法(FFT)程序复杂、子进程多等缺点;算法易于并行,尤其适合VLSI设计;对于含较大素因子,特别是素数长度的DFT,其速度比传统的FFT方法快;算法为任意长度DFT的快速计算开辟了新的思路和途径.     

离散余弦变换的改进的算术傅立叶变换算法

离散余弦变换(DCT)是数字图像处理等许多领域的重要数学工具.本文通过一种新的傅立叶分析技术——算术傅立叶变换(AFT)来计算DCT.本文对偶函数的AFT进行了改进.改进的AFT算法不但把AFT所需样本点数减少了一半,从而使所需加法计算量减少了一半,更重要的是它建立起AFT和DCT的直接联系,因而提供了适合用于计算DCT的AFT算法.本文推导了用改进的AFT计算DCT的算法并对算法进行了简要的分析.这种算法的乘法量仅为O(N),并且具有公式一致,结构简单,易于并行,适合VLSI设计等特点,为DCT的快速计算开辟了新的途径.     

一种改进的二维离散极坐标Fourier变换快速算法

在雷达天线、图象配准、图象检索等领域内常常需要用极坐标表示二维数字信号的离散Fourier变换(DFT).与笛卡尔坐标系下的二维DFT不同,二维离散极坐标Fourier变换(DPFT)不具有行列可分性,直接计算非常耗时.本文提出一种改进的DPFT的快速算法.该算法针对二维阵列实信号,算法全部过程可用一维运算实现,大大降低了计算复杂度并且适用于实时处理.实验中与直接运算方法相比较,显示了该算法的良好性能.     

二维离散余弦变换的一种新的快速算法

本文介绍了二维离散余弦变换（ＤＣＴ）的一种新的快速算法，对于Ｎ×Ｎ ＤＣＴ（Ｎ＝２＾ｍ），只需用Ｎ个一维ＤＣＴ和若干加法运算。与常规的行－列法相比，所需的乘法运算量减少了一半，也比其它的快速算法的乘法运算量要少，而加法运算量基本上是相同的。     

计算2~m×2~m点二维离散Fourier变换的新算法

本文提出了一种计算2~m×2~m点二维离散Fourier变换的新算法。此法与一维FFT逐行逐列计算二维DFT的算法相比,优点是减少25～71％的复数乘法运算。文中还讨论了产生旋转因子和二维反序重排的快速算法。     

二维离散余弦变换的一种新的快速算法

介绍了二维离散余弦变换的一种新的快速算法，对于Ｎ×ＮＤＣＴ（Ｎ＝２ｍ），只需用Ｎ个一维ＤＣＴ和若干加法运算，与常规的行一列法相比，所需的乘法运算量减少了一半，也比其它快速算法的乘法运算量要少，而加法运算量基本上是相同的。     

二维离散傅里叶变换DFT（2^n;2）计算复杂性与张量乘积

本文从(?)单代数中的直和、张量乘积与离散傅里叶变换之间的关系出发,提出用直和、张量乘积表示的二维离散傅里叶变换DFT(2(?))各种算法的矩阵表示式。这种矩阵张量乘积表示式不仅揭示了各种DFT((?)2)算法之间内在联系和便于比较它们的计算复杂性,而且给出获得最小乘法次数的DFT(2(?)2)算法的途径,从而从理论上论证计算DFT(2(?)2)所需的最小实数乘法次数为2(?)-3n2(?)+3.2(?)+8。     

Multidimensional Polynomial Transform Algorithm For Multidimensional Discrete Hartley Transform

In this paper, we present an index permutation-based fast algorithm for the multidimensional discrete Hartley transform (MD-DHT). By reordering the MD-DHT input sequence, we first convert the MD-DHT into a multiple sum that contains a number of one-dimensional discrete W transforms (1D-DWTs). We then use a combination of the 1D-DWTs and the multidimensional polynomial transform to compute the multiple sum. It is shown that the number of multiplications and additions required for the proposed algorithm are approximately 1/m and 2m+1/3m times that of the commonly used row-column DHT method, respectively. The developed algorithm is also simple in structure and easy to realize in programming.     

改进的算术傅立叶变换（AFT）算法

算术傅立叶变换（AFT）是一种非常重要的傅立叶分析技术。AFT的乘法量少（仅为O（N））,算法结构简单,非常适合VLSI设计,具有广泛的应用。但AFT的加法量很大,为O（N∧2）,因此减少AFT的加法运算是很重要的工作。本文通过分析AFT的采样特点,给出了奇函数和偶函数的AFT的改进算法。然后在此基础上给出了一般函数的AFT的改进算法。改进算法比原算法的加法运算量降低了一半,因此计算速度快了一倍。本文改进的偶函数和奇函数的AFT算法还分别可以用来计算离散余弦变换（DCT）和离散正弦变换（DST）。     

New algorithm for r-dimensional DCT-II

The paper shows that the type-II r-dimensional discrete cosine transform (rD-DCT-II) of size q^l1×q^l2x...xq ^l1, where r>1 and q is an odd prime number, can be converted into a series of one-dimensional reduced DCT-IIs by using the polynomial transform. The number of multiplications for computing an rD-DCT-II is significantly reduced compared to that needed by the row-column method. The total number of arithmetic operations (additions plus multiplications) needed by the proposed algorithm is also reduced substantially. In addition to the capability of dealing with different dimensional sizes, the proposed algorithm also has a simple computational structure because it requires only the 1D-DCT-II and the polynomial transform     

New fast algorithm for two-dimensional discrete Fourier transform DFT (2/sup n/; 2)

Presents a new fast algorithm for computing the two-dimensional discrete Fourier transform DFT(2/sup n/; 2) using the fast discrete cosine transform algorithm. The algorithm has a lower number of multiplications and additions compared with other published algorithms for computing the two-dimensional DFT. Because it uses only real multiplications, the algorithm is more suitable for real input data.<>     

An efficient algorithm for cyclic convolution based on fast-polynomial and fast-W transforms

This paper first presents a fastW-transform (FWT) algorithm for computing one-dimensional cyclic and skew-cyclic convolutions. By using this FWT in conjunction with the fast polynomial transform (FPT), an efficient algorithm is then proposed for calculating the two-dimensional cyclic convolution (2D CC). Compared to the conventional row-column 2D discrete Fourier transform algorithm or the FPT Fast Fourier transform algorithm for 2D CC, the proposed algorithm achieves 65% or 40% savings in the number of multiplications, respectively. The number of additions required is also reduced considerably.     

Simple FFT and DCT algorithms with reduced number of operations

A simple algorithm for the evaluation of discrete Fourier transforms (DFT) and discrete cosine transforms (DCT) is presented. This approach, based on the divide and conquer technique, achieves a substantial decrease in the number of additions when compared to currently used FFT algorithms (30% for a DFT on real data, 15% for a DFT on complex data and 25% for a DCT) and keeps the same number of multiplications as the best known FFT algorithms. The simple structure of the algorithm and the fact that it is best suited for real data (one does not have to take a transform of two real sequences simultaneously anymore) should lead to efficient implementations and to a wide range of applications.     

Multidimensional polynomial transform algorithm formultidimensional discrete W transform

The multidimensional (MD) polynomial transform is used to convert the MD W transform (MDDWT) into a series of one-dimensional (1-D) W transforms (DWTs). Thus, a new polynomial transform algorithm for the MDDWT is obtained. The algorithm needs no operations on complex data. The number of multiplications for computing an r-dimensional DWT is only 1 times that of the commonly used row-column method. The number of additions is also reduced considerably     

Conjugate pair fast Fourier transform

A new algorithm for the fast computation of the discrete Fourier transform is introduced. The algorithm, called the conjugate pair FFT (CPFFT), is used to compute a length-2/sup n/ DFT. The number of multiplications and additions required by the CPFFT is less than that required by the SRFFT algorithm.<>