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

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

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))点     

离散余弦变换的一种推广

离散余弦变换(DCT)在数字信号、图像处理、频谱分析、数据压缩和信息隐藏等领域有着广泛的应用.推广离散余弦变换,给出一个包含三个参数的统一表达式,并证明在许多情形新变换是正交变换.最后给出一种新型离散余弦变换,并证明它是正交变换.     

离散积分小波变换的快速算法

本文讨论了积分小波变换的快速算法,通过尺度函数与小波间的二尺度关系,导出了一个实现积分小波变换的快速计算方法及相应滤波器的构造方法。     

离散Ter变换的快速算法

本文研究了第 ( 2 ,0 )类离散 Walsh-Haar类变换即离散 Ter变换的快速算法 .     

用多项式变换计算多维离散W变换

1．引言多维离散W变换作为多维离散Hartley变换的推广［1－3］，是处理多维问题的一种工具．在计算机视觉、高清晰度电视（HDTV）以及可视电话等领域，经常要对运动图象进行分析和处理，通常称为多帧检测（Multi－WameDetection，简称MFD）［4－5］，这时三维离散w变换是一种可行的方法．由于不需要进行复数运算，比三维离散傅立叶交换（DFT）有优越性．而对运动的三维图象进行处理时，可采用四维离散w变换．对维数更高的多维信号进行处理时，可采用多维离散w变换．对三维以上的w变换，需要的运算量非常大，设计好的快速算法极为重要…     

任意长度DCT—Ⅱ的MIMD并行算法

1 引 言 Ⅱ型离散余弦变换(DCT—Ⅱ)有超于统计最佳变换Karhunen—Loeve变换(KLT)的渐近性质,因而在通信和信号处理中得到了广泛应用,尤其是在图像处理中它是最有用的变换。设x(k)(k=0,1,…,N—1)为实数序例,其DCT—Ⅱ的定义为 X(n)=sum from k=0 to N-1 x(k)cos(π(2k+1)n)/2N,n=0,1,…,N-1。 (1)     

计算一类数字变换的收缩阵列

本文以DFT的收缩（Systolic）阵列结构为基础，给出了一类数字变换的收缩阵列，这些变换包括离散富里叶变换，离散余弦变换，离散正弦变换，离散Hartley变换，数论变换和多项式变换．     

任意长一维DFT的MIMD并行算法

本文提出了共享与分布储计算机上任意长一维ＤＦＴ的ＭＩＭＤ并行算法，若Ｎ＝Ｏ（ｐ，ｑ），则算法需要Ｏ（「ｑ／ｐ」（３／２ｐｌｏｇｐ＋ｐ）ｐ＋３／２ｑｌｏｇｑ＋ｑ）次算术运算。其中，ｐ与Ｎ可为任意自然数，分别表示处理机台数与ＤＦＴ长度。本算法具有很高的并行效率。     

任意长—维DFT的MIMD并行算法

本文提出了共享与分布式存储计算机上任意长—维ＤＦＴ的ＭＩＭＤ并行算法，若Ｎ＝Ｏ（ｐ，ｑ），则算法需要次算术运算。其中，Ｐ与Ｎ可为任意自然数，分别表示处理机台数与ＤＦＴ长度．本文算法具有很高的并行效率．     

斜变换ST的演化生成与快速算法

１．引言 含有“斜”基向量的正交变换（斜变换 ＳＴ）概念是由 Ｅｎｏｍｏｔｏ ＆ Ｓｈｉｂａｔａ（１９７１）提出的［１］．斜向量是一个在其范围内呈均匀阶梯下降的离散锯齿波形．对于亮度逐渐改变的图象,用斜向量来表示是适合的． Ｅｎｏｍｏｔｏ 　＆ 　Ｓｈｉｂａｔａ仅考虑了斜向量长度为 ４和 ８的情况．Ｐｒａｔｔ等人利用递推性将 ＳＴ推广到 Ｎ＝ ２ｍ阶的情形,给出了 ＳＴ的一般定义［２］,并与其它变换进行了比较［３］．ＳＴ已成功地用在图象编码上,而且在非正弦类交换编码的应用中,斜变换的效果最好［２,３］． Ａｈ…     

斜Haar类变换的演化生成与快速算法

1.引 言 Haar函数和Walsh函数是两类密切相关且十分重要的完备正交函数系,它们不仅在(离散)正交变换及其快速算法设计中起着重要的作用,而且在小波分析中占有重要地位:它们分别对应于Haar小波和Haar小波包.另外,它们还是遗传算法和密码学等涉及布尔函数或离散函数的学科之重要的理论分析工具.     

Vandermonde行列式的快速并行算法

n阶Vandermonder行列式的求值通常需要O(n~2)次算术运算．本文从计算复杂性的角度出发，给出一种求Vandermonde行列式、合流型Vandermonde行列式、广义Vandermonde行列式的快速算法．该算法仅需O(nlog~2n)次算术运算．若在n台处理机上并行计算，该算法需并行步数O(nlog_(2~2)n)．速度倍数为s_p=O(n)．并行效率为O(1)．     

对称Toeplitz系统的快速W变换基预条件子

１．引言考虑下列Ｎ阶线性方程组其中T_N=(t_i,j)　是Ｎ×Ｎ阶实对称正定（ＳＰＤ）Ｔｏｅｐｌｉｔｚ矩阵,即０,１,…,Ｎ－１）且Ｔ_Ｎ的所有特征值为正数．Ｔｏｅｐｌｉｔｚ系统已广泛应用于数字信号处理,时间序列分析（参见［１］）以及微分方程的数值解（参见［２１］等领域．八十年代以前,考虑到Ｔｏｅｐｌｉｔｚ矩阵的特殊性,人们主要用Ｌｅｖｉｎｓｏｎ递推技术及其变形或者分而治之思想直接求解方程组（１．１）,计算复杂性为Ｏ（Ｎ~（２））或Ｏ（ＮｌｏｇＮ~（２））（参见［３］）;比Ｇａｕｓｓ法运算量级Ｏ（Ｎ~（３）…     

分块K—循环Toeplitz矩阵求逆的快速付氏变换法

1算法描述及推导 Toeplitz矩阵及Toeplitz系统的求解在谱分析、线性预测、误差控制码、自回归滤波器设计等领域内起着重要的作用~[1-3]，而分块Toeplitz矩阵在计算机的时序分析、自回归时序模型滤波中也经常出现~[4]。对一般Toeplitz矩阵求逆，其算术复杂性为O(n~2)~[5]-[6]，其中n为Toepleitz矩阵的阶，而K-循环Toeplitz矩阵的求逆，其算术复杂性可降为O(nlog_2n)，本文提供了mn附分块K-循环Toeplitz矩阵求逆的一种快速付氏变换算法，其算术复杂性为O（mnlog_2mn）.     

正交小波变换中边界延拓的精确重构算法

本文研究了小波应用中的边界延拓问题.通过边界补偿的方法导出了零延拓滤波器矩阵的逆矩阵,分析了零延拓的滤波器矩阵与无穷滤波器矩阵之间的差异.     

求置换因子循环矩阵的逆阵及广义逆阵的快速算法

1 引 言 循环矩阵由于其应用非常广泛而成为一类重要的特殊矩阵,如在图象处理、编码理论、自回归滤波器设计等领域中经常会遇到以这类矩阵为系数的线性系统的求解问题.而对称循环组合系统也具有广泛的实际背景,例如造纸机的横向控制系统,具有平行结     

A FAST SINE TRANSFORM ALGORITHM FOR TOEPLITZ MATRICES AND ITS APPLICATIONS

In this paper, a fast algorithm for the discrete sine transform(DST) of a Toeplitz matrix of order N is derived. Only O(N log N) O(M) time is needed for the computation of M elements. The auxiliary storage requirement is O(N). An application of the new fast algorithm is also discussed.