1、一種任意窗函數(shù)的復(fù)數(shù)調(diào)制重疊變換的快速算法葛 云 章 東(南京大學(xué)電子科學(xué)與工程系 南京 210093摘 要:該文提出了一種任意窗函數(shù)的復(fù)數(shù)調(diào)制重疊變換 (MCLT的快速計算方法。針對輸入信號長度為 2M 的 MCLT ,該算法將其轉(zhuǎn)化為長度為 2M 的 II 型離散 Hartley 變換,然后對后者運(yùn)用快速算法。與現(xiàn)有算法相比, 該方法能夠達(dá)到最少的算術(shù)運(yùn)算量。關(guān)鍵詞:音頻處理; 重疊轉(zhuǎn)換; 快速算法; 離散 Hartley 轉(zhuǎn)換New Fast Algorithm for Modulated Complex LappedTransform with Arbitrary Windowing

2、FunctionGe Yun Zhang Dong(Department of Electronic Science and Engineering, Nanjing University, Nanjing 210093, ChinaAbstract : A new algorithm for efficient computation of the Modulated Complex Lapped Transform (MCLT with arbitrary windowing function is presented. For the MCLT of length-2M input da

3、ta sequence, the proposed method is based on computing a length-2M type-II generalized discrete Hartley transform. Comparison with existing algorithms shows that the proposed method achieves the minimal number of arithmetic operations.Key words: Audio processing; Lapped transform; Fast algorithm; Di

4、screte Hartley transform1引言復(fù)數(shù)調(diào)制重疊變換 (MCLT 是一種把實值信 號轉(zhuǎn)化為復(fù)數(shù)域的變換 1, MCLT 的實數(shù)部分與同 一信號的 MLT 相同,而虛數(shù)部分?jǐn)y帶著相位的信 息。因此, MCLT 可被用于需要相位信息的信號處 理問題,如聲學(xué)水印和識別 2。 MCLT 較之離散傅 立葉變換 (DFT的優(yōu)勢在于它的重建公式不是唯一 的,因此,它能夠更加靈活地應(yīng)用于音頻增強(qiáng)和譯 碼系統(tǒng)。由于 MCLT 涉及較多的運(yùn)算, 有關(guān)其快速算法 近年來吸引了學(xué)者的關(guān)注。 Malvar 1進(jìn)一步提出了 一種經(jīng)由長為 2M 的 DFT來計算長度為 2M 的 MLCT 快速算法。 Da

5、i 和 Chen 3發(fā)展了一種以 DCT 為基礎(chǔ)的高效計算 MCLT 的方法, 他們的算法對任 何對稱窗函數(shù)均適用。 對于一個正弦窗, Dai 的算 法相比文獻(xiàn) 1提出的算法需要稍多的算術(shù)運(yùn)算量。 此后, 他們又對該算法提出了改進(jìn) 4, 值得指出的是, 文獻(xiàn) 4中的方法適用于任意窗函數(shù)。 Britanak 5提出 了基于正弦窗函數(shù)的快速算法, Dai 6在此基礎(chǔ)上發(fā) 展,在 M 為二次冪的條件下,提出新的算法,其算 術(shù)運(yùn)算量,基本和文獻(xiàn) 4相似。本文針對任意窗函數(shù)的 MCLT ,提出一種新的 快速算法。 該方法將 MCLT 轉(zhuǎn)換為 GDHT-II 型 7,8, 然后對后者運(yùn)用快速算法。較之已有

6、方法,本文方2009-02-20收到, 2009-07-21改回江蘇省教育廳 (JHB06-01資助課題通信作者:葛云 geyun 法能夠達(dá)到最少的算術(shù)運(yùn)算量。2新型的快速算法一個長度為 2M 的實輸入數(shù)據(jù)序列 x (n , n = 0,1, " ,2M 1,其 MLCT 變換 1定義為21( ( (, , =0,1, 1MnX k x n p n k k M= " (1 其中(, (, (, c sp n k p n k jp n k= (2 ( (, (cos 2121 4cp n k n n M kM =+ (3( (, (sin 2121 4sp n k n n M

7、 kM =+ (4 這里的 h (n 為窗函數(shù)。由式 (3,可以得到 ( 1(,21(cos 21421 4(1 (, cMcp n M kn n M M kMp n k+ =+ = (5 類似地 ( (,21(sin 21421 4(1 (, sMsp n M kn n M M kMp n k =+ = (6 上述式子表明對于 k = 0,1," ,2M 1, p c (n , k 和 p s (n , k 滿足對稱或反對稱性質(zhì),因此,計算 X (k , k748 電 子 與 信 息 學(xué) 報 第 32卷=0,1," , M 1, 可以通過計算序號為偶數(shù)的 X (k , 即

8、 k = 0,2,4," ,2M 2得到。對于偶數(shù) k ,式 (3變?yōu)? ( ( ( ( (,2 c p n k n n M k M n k n k Mn k n Mk M =+ =+ += " (7 其中 cas cos sin =+。類似地 ( ( ( ( ( (,2 s kp n k n n M k M n k n k Mn k n Mk M =+ =+ += " (8 將式 (1改寫為 ( ( ( c s X k X k jX k = (9 這里的 X c (k 和 X s (k 分別代表 X (k 的實部和虛 部,其定義為 210( ( (, M c c

9、 n X k x n p n k = (10a210( ( (, , = 0,1, 1 M s s n X k x n p n k k M = " (10b從式 (5和式 (6,容易得到1(21 (1 ( M c c X M k X k + = (11a (21=(1 (, =0,1, 1M s s X M k X k k M " (11b將式 (7代入式 (10a,得到 (10(2 (1 ( ( 2141 ( (1 M c n k X k x n h n n k = + = = ( ( 2141cas (124n k M +其中( 2sin4h n h n M = (13

10、利用三角函數(shù)性質(zhì)( ( 2sin(cas( cas cas = + (14 式 (12變?yōu)?( ( ( 1(2 (1( ( 2+12+1212 cascas22M kc n X k x n h n n k n kM M = = + (15 類似地( ( ( ( ( 1021(2 (1 ( ( 2sin 42141 (2121212 cascas 22M k s n n X k x n h n M n k n k n k M M = + = + = + + (16令 10(21 ( ( (cas 2M n n k Y k x n h nM =+ = (17 10(21 ( ( (cas 2 =0

11、,1,21M n n k Z k x n h n M k M = + = " (18容易驗證(2 ( , =0,1,21Z M k Y k k M = "(19 式 (15和式 (16變?yōu)?2 (2 (21 kc X k k Y k = +(20(2 (21 (2 (22 (221 ,=0,1, 1ks kX k Z k Z k M k Y M k k M =+ = " (21 有 Y (2M = Y (0。由 式 (17定 義 的 Y (k 是 一 個 輸 入 數(shù) 據(jù) 序 列 ( x n ( h n 的歸一化的長度為 2M 的 GDHT-II , 因而, 可借由

12、 FHT 算法將其算出。 由 Y (k 的值, k =0,1," , 2M 1, MCLT 系數(shù)的實部和虛部 X c (2k 和 X s (2k , k = 0,1," , M 1, 可以很簡單的從式 (20和式 (21獲 取。一旦得到了偶下標(biāo)系數(shù),奇下標(biāo)系數(shù)可由對稱 特性 (11a和 (11b推演出。 實現(xiàn)該算法的流程圖見圖 1。第 3期 葛 云等:一種任意窗函數(shù)的復(fù)數(shù)調(diào)制重疊變換的快速算法 749 圖 1 算法流程圖上述討論表明本文方法的計算復(fù)雜度是一個長 度為 2M 的 GDHT-II ,加上式 (20和式 (21中所需 的算術(shù)運(yùn)算。 對于 GDHT-II 型,可以采

13、用已有的 快速算法提高計算效率。對于 M 為 2的冪次方情 況, 使用文獻(xiàn) 7提出的算法, 長度為 2M 的 GDHT- II 需要 2log M M 次乘法和 23log 4M M +次加法。 此外,輸入信號 ( ( x n h n 需要進(jìn)行 2M 次乘法,式 (20和式 (21的計算中需要 2M 加法。由于因子 可被吸收進(jìn) GHDT 的規(guī)一化因子或者納入 量化部分,故而在式 (20和式 (21中無須乘法運(yùn)算。 因此, 本文方法的總算術(shù)量為 23log 24M M M + 加法和 2log 2M M M +乘法。特別地,當(dāng)使用的窗 函數(shù)為正弦窗時 (這是實際中最常用的情況 ,即 ( ( 2s

14、in21/(4h n n M = +時 , 則 式 (13變 為 ( 1h n =,此時,輸入信號不需要進(jìn)行乘法運(yùn)算, 因此,對 于正弦窗函 數(shù) ,本文方 法的運(yùn)算量為 23log 24M M M +加法和 2log M M 乘法。若 M 不是二次冪的情況, 長度為 2M 的 GDHT- II 可由文獻(xiàn) 8中提出的快速算法計算。在 M 為二次冪的條件下, 本文提出的算法與其 它方法,在計算復(fù)雜度方面的對比,詳見表 1。由 該表可見,對于任意窗函數(shù),本文的算法不僅乘法 運(yùn)算次數(shù)最少 (與文獻(xiàn) 4相同 ,同時也是在現(xiàn)有 MLCT 算法中執(zhí)行加法操作需求最少的。 在文獻(xiàn) 3,4所報告的算法中,作者通

15、過把正弦窗函數(shù)吸收進(jìn) DCT-IV 的核函數(shù),可把 2M -點的 MCLT 系數(shù)的實 部和虛部轉(zhuǎn)換進(jìn)兩個 M -點的 DCT-II 系數(shù)中去。 在 本文的算法中, 通過把正弦窗函數(shù)吸收入 GDHT-IV 核函數(shù), 成功地把 2M -點的 MLCT 系數(shù)的實部和 虛部轉(zhuǎn)換進(jìn)了 2M -點 GDHT-II 系數(shù)的計算。應(yīng)該 指出,文獻(xiàn) 3,4中提出的算法可以被分別應(yīng)用于對 稱窗函數(shù)和任何窗函數(shù)。 本文的算法支持任意函數(shù)。3 結(jié)論本 文 提 出 了 一 種 使 用 任 意 窗 函 數(shù) 進(jìn) 行 高 效表 1 各種算法的計算復(fù)雜度算法 窗函數(shù)選擇 乘法計算量 加法計算量 文獻(xiàn) 1 正弦 M log2M

16、+M 3M log2M +3M 2 對稱 M log2M +3M 文獻(xiàn) 3 正弦 M log2M +M 3M log2M +4M 任意 M log2M +2M 文獻(xiàn) 4正弦 M log2M3M log2M +4M任意 2log +2M M M 本文 方法正弦M log2M23log 24M M M +MCLT 計算的新型算法。 針對一個 length-2M 輸 入數(shù)據(jù)序列的 MCLT , MCLT 系數(shù)的實部和虛部可 經(jīng)由同一信號的長度為 2M GDHT-II系數(shù)得到。對 比于此前的其它算法,本文提出的算法,可達(dá)到實 數(shù)乘法操作數(shù)最小和總算術(shù)操作數(shù)最小,而節(jié)約約 5%的效果。此外,該方法具備規(guī)

17、則的結(jié)構(gòu),故而, 它對軟硬件開發(fā)應(yīng)用均可能有用。參 考 文 獻(xiàn)1Malvar H S. Fast algorithm for the modulated complex lapped transform. IEEE Signal Processing Letters , 2003, 10(1: 8-10. 2Jose Juan Garcia-Hernandez and Mariko Nakano-Miyatake. Data hiding in audio signal using Rational Dither Modulation. IEICE Electronics Express, 2

18、008, 5(7: 217-222. 3Dai Q and Chen X. New algorithm for modulated complex lapped transform with symmetrical window function. IEEE Signal Processing Letters, 2004, 11(12: 925-928. 4Chen X and Dai Q. A novel DCT-based algorithm for computing the modulated complex lapped transform. IEEE Transactions on Signal Processing, 2006, 54(11: 4480-4484. 5Britanak V, Yip Y, and Rao K R. Discrete Cosine and Sine Transforms: General Properties, Fast Algorithms an