离散余弦变换(DCT)及离散富里叶变换(DFT)的快速算法

离散余弦变换(DCT)是在信号处理中有广泛应用的正交变换。Z.Wang利用DCT的变换矩阵[C_N~Ⅳ]([2]中称为DCT-Ⅳ)的稀疏分解得到各类DCT和DST的快速算法。与[1]比较,运算量有所减少,但与[3]利用FFT计算DCT的方法比较,乘法量有所增加。最近[4]对[2]的方法进行了修改,得到了DCT-Ⅳ的更好的算法,从而使各类DCT与DST的运算量有所减少,Z.Wang本人在[7]中导出了用DCT-Ⅲ来计算DCT-Ⅳ的方法,与[2]中方法结合也可得到各类DCT及DST的快速算法。但是[2],[3],[7]均是利用DCT—Ⅳ来计算各类DCT和DST的,每一步运算均需不断地把一种形式变换为另一种形式,计算     

N=2^t点DFT的快速卷积算法

从所周知,循环卷积和离散富里叶变换(DFT)可以互相计算,只要得到其中一个的快速算法就可导出另一个的快速算法。循环卷积目前已有乘法量为O(N)的最佳算法(特别是当N较小时),为此关键是如何将DFT转化为循环卷积,当DFT的长度N=p(p为素数),Rader利用有限域GF(p)的乘法群是循环群就成功地将p点DFT转化为Q(p)(F(p)为户的Euler函数)点循环卷积;当N=p~e时,由于商环Z/(p~e)存在F(p~c)阶元素,人们也成功地将p~c点DFT转化为P(p~(c-1))一系列循环卷积,即一个y(p~c)点循环卷积,二个P(p~(c-1))点     

超大型二维循环卷积的FPT和FNT混合算法

本文将FPT和FNT相结合提出了一种计算超大型二维循环卷积的迭代算法,它的基础是应用了FPT.与二维循环卷积的FPT算法相比,乘法量减少了一个数量级,同时实际取消了FNT算法中卷积规模所受到的字长的限制.     

用快速多项式变换(FPT)计算二维离散富里叶变换(DFT)

一 引言 H.J.Nussbaumer和P.Quandalle在[1]中引入了多项式变换並用它计算数字卷积和离散富里叶变换[2],[3]。我们在[4]中详细的研究了模M(z)是可约多项式时变换存在的条件,並用它来计算两个多项式的乘积[5]。本文研究用FPT计算二维DFT的方法。结果表明,当N=2~(m-r+1),M=2~m(1≤r≤m)时,所用的加法次数与通常以2为基     

关于一种循环类预条件方程组的快速求解

１引言考虑下列Ｎ阶线性方程组其中Ｃ１＝,Ｃ２＝０≤ｉ,ｊ≤Ｎ－１,是Ｎ阶循环矩阵,Ｊ１＝（Ｊ）是Ｎ阶置换矩阵,其元素分别满足１９９３年,Ｔ,Ｋ．Ｋｕ,Ｃ．Ｃ．Ｊ．Ｋｕｏ在［１］中取Ｃ１,Ｃ２为实对称循环矩阵,而Ｃ１＋Ｊ１Ｃ２作为预条件矩阵来求解在数字信号处理中有一定应用的Ｔｏｅｐｌｉｔｚ加Ｈａｎｋｅｌ线性方程组［２］,得到了一种高效的预处理其轭梯度算法．当Ｔｏｅｅｌｉｔｚ与Ｈａｎｋｅｌ矩阵之和为正定矩阵且条件数适中时,所需运算量可达到０（Ｎｌｏｇ２Ｎ）,比原有算法［２,３,４］的运算量０（Ｎ２）…     

多项式变换及其在卷积计算中的应用

其中_q表示整数k模q的最小非负剩余.这种卷积的计算,在通用计算机及专门结构的数字处理装置中有广泛的应用,特别可用于图象处理方面.直接计算(1),需要p~2q~2次     

任意长度W变换的统一算法及其实现

任意长度Ｗ变换的统一算法及其实现曾泳泓，蒋增荣（国防科技大学）ＡＵＮＩＦＩＥＤＭＳＴＡＬＧＯＲＩＴＨＭＦＯＲＴＨＥＤＩＳＣＲＥＴＥＷＴＲＡＮＳＦＯＲＭＷＩＴＨＡＲＢＩＴＲＡＲＶＬＥＮＧＴＨ￥ＺｅｎｇＹｏｎｇ－ｈｏｎｇ；ＪｉａｎｇＺｅｎｇ－ｒｏｎｇ（７...     

二维数字卷积的FPT算法及其在计算机上的实现

其中〈k〉_N表示整数k模N的最小非负剩余。这种卷积的计算在通用计算机及专门结构的数字处理结构中有广泛的应用,特别可用于滤波及图象处理方面。直接计算(1.1),需N~2M~2次乘法及NM(NM-1)次加法,当N,M较大时,运算量是很大的,必需寻求快速算法以节省计算时间。