一、小波分析算法的計(jì)算

　　1、Mallat算法［經(jīng)典算法］

　　在小波理論中，多分辨率分析是一個(gè)重要的組成部分。多分辨率分析是一種對(duì)信號(hào)的空間分解方法，分解的最終目的是力求構(gòu)造一個(gè)在頻率上高度逼近L2（R）空間的正交小波基，這些頻率分辨率不同的正交小波基相當(dāng)于帶寬各異的帶通濾波器。因此，對(duì)于一個(gè)能量有限信號(hào)，可以通過(guò)多分辨率分析的方法把其中的逼近信號(hào)和細(xì)節(jié)信號(hào)分離開(kāi)，然后再根據(jù)需要逐一研究。多分辨率分析的概念是S.Mallat在構(gòu)造正交小波基的時(shí)候提出的，并同時(shí)給出了著名的Mallat算法。Mallat算法在小波分析中的地位相當(dāng)于快速傅立葉變換在經(jīng)典傅立葉變換中的地位，為小波分析的應(yīng)用和發(fā)展起到了極大的推動(dòng)作用。

　　MALLAT算法的原理

　　在對(duì)信號(hào)進(jìn)行分解時(shí)，該算法采用二分樹(shù)結(jié)構(gòu)對(duì)原始輸入信號(hào)x（n）進(jìn)行濾波和二抽取，得到第一級(jí)的離散平滑逼近和離散細(xì)節(jié)逼近，再采用同樣的結(jié)構(gòu)對(duì)進(jìn)行濾波和二抽取得到第二級(jí)的離散平滑逼近和離散細(xì)節(jié)逼近，再依次進(jìn)行下去從而得到各級(jí)的離散細(xì)節(jié)逼近對(duì)，即各級(jí)的小波系數(shù)。重構(gòu)信號(hào)時(shí)，只要將分解算法中的步驟反過(guò)來(lái)進(jìn)行即可，但要注意，此時(shí)的濾波器與分解算法中的濾波器不一定是同一濾波器，并且要將二抽取裝置換成二插入裝置才行。

　　2、多孔算法

　　多孔算法是由M.shen于1992年提出的一種利用Mallat算法結(jié)構(gòu)計(jì)算小波變換的快速算法，因在低通濾波器和高通濾波器中插入適當(dāng)數(shù)目的零點(diǎn)而得名。它適用于的二分樹(shù)結(jié)構(gòu)，與Mallat算法的電路實(shí)現(xiàn)結(jié)構(gòu)相似。先將Mallat算法的電路實(shí)現(xiàn)的基本支路作一下變形。令的z變換為，下兩條支路完全等價(jià)，只不過(guò)是將插值和二抽取的順序調(diào)換一下罷了。圖中其它的上下兩條支路也為等效支路，可仿照上面的方法證明。這樣，我們便可由Mallat算法的二分樹(shù)電路結(jié)構(gòu)得出多孔算法的電路級(jí)聯(lián)圖，原Mallat算法中的電路支路由相應(yīng)的等效支路所取代，所以整個(gè)電路形式與Mallat算法非常相似。如果舍去最后的抽取環(huán)節(jié)們實(shí)際上相當(dāng)于把所有點(diǎn)的小波變換全部計(jì)算出來(lái)。

　　3、基干FFT的小波快速算法

　　Mallat算法是由法國(guó)科學(xué)家StephaneG.Mallat提出的計(jì)算小波分解與重構(gòu)的快速算法，能大大降低小波分解與重構(gòu)的計(jì)算量，因此在數(shù)字信號(hào)處理和數(shù)字通信領(lǐng)域中得到了廣泛的應(yīng)用。但是如果直接采用該算法計(jì)算信號(hào)的分解和重構(gòu)，其運(yùn)算量還是比較大。主要體現(xiàn)在信號(hào)長(zhǎng)度較大時(shí)，與小波濾波器組作卷積和相關(guān)的乘加法的計(jì)算量很大，不利于信號(hào)的實(shí)時(shí)處理。故有必要對(duì)該算法作進(jìn)一步的改進(jìn)。眾所周知，F(xiàn)FT是計(jì)算離散傅里葉變換（DFT）的一種快速算法，如能將它和Mallat算法結(jié)合在一起，勢(shì)必會(huì)進(jìn)一步降低小波分解和重構(gòu)的計(jì)算量，事實(shí)證明這一想法是可行的。

　　基于FFT的小波變換快速算法是通過(guò)離散傅里葉變換建立起FFT和mallat算法之何的橋梁，從而將、FFT引入到小波變換中來(lái)，達(dá)到改小波變換快速算法及硬件實(shí)現(xiàn)的研究進(jìn)Mallat算法的目的。

　　當(dāng)信號(hào)長(zhǎng)度較小時(shí)，F(xiàn)FT算法效率不及直接算法;隨著長(zhǎng)度的增加，特別是對(duì)于長(zhǎng)度是2的幕次方的信號(hào)，F(xiàn)FT算法比直接算法更適用，能大大降低計(jì)算t。當(dāng)信號(hào)是長(zhǎng)序列信號(hào)時(shí)，小波分解與重構(gòu)中，濾波器要補(bǔ)很多的零，這對(duì)信號(hào)的實(shí)時(shí)計(jì)算很不利，我們可以采用長(zhǎng)序列快速相關(guān)卷積算法對(duì)信號(hào)進(jìn)行分段后再運(yùn)用FFT算法，提高運(yùn)算速度。

　　4、基于算術(shù)傅里葉變換的小波變換快速算法

　　算術(shù)傅里葉變換（AFT）是1988年由Tufts和Sadasiv提出的一種用Mobius反演公式計(jì)算連續(xù)函數(shù)傅里葉系數(shù)的方法。它具有乘法運(yùn)算t僅為O（N）算法簡(jiǎn)單、并行性好的優(yōu)點(diǎn)。根據(jù)DPT和連續(xù)函數(shù)傅里葉系數(shù)的關(guān)系，可以用AFT計(jì)算DFT。同直接算法相比，APT方法可以將DFT的計(jì)算時(shí)間減少90%，尤其是對(duì)于含有較大素因子，特別是其長(zhǎng)度本身為素?cái)?shù)的DFT，它的速度比傳統(tǒng)的FFT更快。另一方面，Mallat算法的分解和重構(gòu)算法也可由DFT來(lái)計(jì)算，從而將AFT與Mallat算法聯(lián)系了起來(lái)，從而為小波變換快速算法開(kāi)辟了新的途徑。

　　對(duì)于尺度

　　1）為j的快速分解算法步驟如下：

　　1）選定濾波器系數(shù)h（n）和g（n），再根據(jù)FFT的性質(zhì)2，用N點(diǎn)的AFT分別計(jì)算出H（k）和G（k），分別取共扼，進(jìn)而得到H*（k），G*（k）。

　　2）在已知cj（n）的情況下，用N點(diǎn)的AFT求出其DFTCj（k）

　　3）分別計(jì)算出H*（k）Cj（k），G*（k）Cj（k），即C’j（k）和D’j（k）

　　4）用N點(diǎn)的AFT求出C’j+1（k）和D’j+1（k）IDFT，得到C’j+1（n）和D’j+1（n）IDFT，再分別對(duì)它

　　們作二抽取，就可求出Cj+1（n）和Dj+1（n）。

　　在進(jìn)行分解計(jì)算時(shí)，H（k）G（k）只要計(jì)算一次即可。重復(fù)步驟（2）一（4）可實(shí)現(xiàn)下一尺度小波分解，直到達(dá)到規(guī)定的尺度為止。不過(guò)要注意：尺度增加一個(gè)級(jí)別，信號(hào)長(zhǎng)度減半。

　　2）對(duì)于尺度為j+1的快速重構(gòu)算法為：

　　1）對(duì)Cj+1（n）和Dj+1（n）進(jìn)行二插值，得到C’j+1（n）和D’j+1（n）;

　　2）用N點(diǎn)的AFT分別求出h（n）、g（n）的DFTH（k）和G（k）

　　3）用N點(diǎn)的AFT分別求出C’j+1（n）和D’j+1（n）的DFTC’j+1（k）和D’j+1（k）;

　　4）根據(jù)（17）式求出Cj（k），再用N點(diǎn)的AFT進(jìn)行IDFT，可求出cj（n）。

　　5、基于Hermite插值的小波變換模極大值重構(gòu)信號(hào)快速算法

　　信號(hào)在不同尺度上的小波變換模極大值包含了信號(hào)中的重要信息，因此研究如何由小波變

　　換模極大值重構(gòu)信號(hào)是很有意義的。論文提出了一種基于Hermite插值多項(xiàng)式由二進(jìn)小波變換模極大值重構(gòu)信號(hào)的快速算法。數(shù)值試驗(yàn)表明，與S.Mallat提出的經(jīng)典交替投影算法相比，該算法可以在保證重構(gòu)質(zhì)量的前提下簡(jiǎn)化計(jì)算過(guò)程，提高計(jì)算效率，計(jì)算所需時(shí)間與交替投影算法相比大大減少，是一種實(shí)用性較強(qiáng)的信號(hào)重構(gòu)算法。

　　Hermite插值［11］方法是一種具有重節(jié)點(diǎn)的多項(xiàng)式插值方法，由于它要求在節(jié)點(diǎn)處滿足相應(yīng)的導(dǎo)數(shù)條件，因此也稱(chēng)為切觸差值。由于小波系數(shù)模極大值點(diǎn)的導(dǎo)數(shù)為零，這與Hermite插值對(duì)節(jié)點(diǎn)的導(dǎo)數(shù)要求不謀而合，因此我們選用Hermite插值多項(xiàng)式作為改進(jìn)的插值方法。

　　6、強(qiáng)奇異積分方程小波Petrov-Galerkin快速算法

　　通過(guò)構(gòu)造具有高階消失矩、小支集和半雙正交性質(zhì)的分片多尺度小波基底，給出第2類(lèi)強(qiáng)奇異積分方程的小波Petrov-Galerkin快速算法，并證明該算法收斂階達(dá)到最佳，條件數(shù)有界，計(jì)算復(fù)雜性幾乎最佳。構(gòu)造配置泛函的思想，構(gòu)造分片多項(xiàng)式空間Xn上2列具有半雙正交性的小波基，其中一列具有高階消失矩性質(zhì)。