第32卷第3期电子与信息学报Vol.32No.32010年3月JournalofElectronicsInformationTechnologyMar.2010一种任意窗函数的复数调制重叠变换的快速算法葛云章东(南京大学电子科学与工程系南京210093摘要:该文提出了一种任意窗函数的复数调制重叠变换(MCLT的快速计算方法。针对输入信号长度为2M的MCLT,该算法将其转化为长度为2M的II型离散Hartley变换,然后对后者运用快速算法。与现有算法相比,该方法能够达到最少的算术运算量。关键词:音频处理;重叠转换;快速算法;离散Hartley转换:TP391.42文献标识码:A:1009-5896(201003-0747-03DOI:10.3724/SP.J.1146.2009.00204NewFastAlgorithmforModulatedComplexLappedTransformwithArbitraryWindowingFunctionGeYunZhangDong(DepartmentofElectronicScienceandEngineering,NanjingUniversity,Nanjing210093,ChinaAbstract:AnewalgorithmforefficientcomputationoftheModulatedComplexLappedTransform(MCLTwitharbitrarywindowingfunctionispresented.FortheMCLToflength-2Minputdatasequence,theproposedmethodisbasedoncomputingalength-2Mtype-IIgeneralizeddiscreteHartleytransform.Comparisonwithexistingalgorithmsshowsthattheproposedmethodachievestheminimalnumberofarithmeticoperations.Keywords:Audioprocessing;Lappedtransform;Fastalgorithm;DiscreteHartleytransform1引言复数调制重叠变换(MCLT是一种把实值信号转化为复数域的变换[1],MCLT的实数部分与同一信号的MLT相同,而虚数部分携带着相位的信息。因此,MCLT可被用于需要相位信息的信号处理问题,如声学水印和识别[2]。MCLT较之离散傅立叶变换(DFT的优势在于它的重建公式不是唯一的,因此,它能够更加灵活地应用于音频增强和译码系统。由于MCLT涉及较多的运算,有关其快速算法近年来吸引了学者的关注。Malvar[1]进一步提出了一种经由长为2M的DFT来计算长度为2M的MLCT快速算法。Dai和Chen[3]发展了一种以DCT为基础的高效计算MCLT的方法,他们的算法对任何对称窗函数均适用。对于一个正弦窗,Dai的算法相比文献[1]提出的算法需要稍多的算术运算量。此后,他们又对该算法提出了改进[4],值得指出的是,文献[4]中的方法适用于任意窗函数。Britanak[5]提出了基于正弦窗函数的快速算法,Dai[6]在此基础上发展,在M为二次幂的条件下,提出新的算法,其算术运算量,基本和文献[4]相似。本文针对任意窗函数的MCLT,提出一种新的快速算法。该方法将MCLT转换为GDHT-II型[7,8],然后对后者运用快速算法。较之已有方法,本文方2009-02-20收到,2009-07-21改回江苏省教育厅(JHB06-01资助课题通信作者:葛云geyun@nju.edu法能够达到最少的算术运算量。2新型的快速算法一个长度为2M的实输入数据序列{x(n},n=0,1,",2M–1,其MLCT变换[1]定义为21(((,,=0,1,,1MnXkxnpnkkM−==−∑"(1其中(,(,(,cspnkpnkjpnk=−(2(((,(cos21214cpnknnMkMπ=+++⎡⎤⎢⎥⎢⎥⎣⎦(3(((,(sin21214spnknnMkMπ=+++⎡⎤⎢⎥⎢⎥⎣⎦(4这里的h(n为窗函数。由式(3,可以得到((1(,21(cos214214(1(,cMcpnMknnMMkMpnkπ+−−⎡⎤=++−−⎢⎥⎢⎥⎣⎦=−(5类似地(((,21(sin214214(1(,sMspnMknnMMkMpnkπ−−⎡⎤=++−−⎢⎥⎢⎥⎣⎦=−(6上述式子表明对于k=0,1,",2M–1,pc(n,k和ps(n,k满足对称或反对称性质,因此,计算X(k,k748电子与信息学报第32卷=0,1,",M–1,可以通过计算序号为偶数的X(k,即k=0,2,4,",2M–2得到。对于偶数k,式(3变为((((((((,2(cos21414(cos412141442141(1(cas,40,1,,1cpnknnMkMnknkMnknMkMππππ⎡⎤=+++⎢⎥=⎢⎥⎣⎦⎡⎤++++⎢⎥⎢⎥⎣⎦−++=−−"(7其中cascossinθθθ=+。类似地((((((((,2(sin21414(sin412141442141(1(cas,40,1,,1skpnknnMkMnknkMnknMkMππππ⎡⎤=+++⎢⎥=⎢⎥⎣⎦⎡⎤++++⎢⎥⎢⎥⎣⎦++=−−"(8将式(1改写为(((csXkXkjXk=−(9这里的Xc(k和Xs(k分别代表X(k的实部和虚部,其定义为210(((,MccnXkxnpnk−==∑(10a210(((,,=0,1,,1MssnXkxnpnkkM−==−∑"(10b从式(5和式(6,容易得到1(21(1(MccXMkXk+−−=−(11a(21=(1(,=0,1,,1MssXMkXkkM−−−−"(11b将式(7代入式(10a,得到(10(2(1((2141((1McnkXkxnhnnkπ...