區(qū)塊折積

　　區(qū)塊折積，又稱區(qū)塊卷積、分段折積、分段卷積、分塊卷積，是一種計算線性離散卷積的方法，在訊號處理以及線性非時變系統(tǒng)領(lǐng)域的應(yīng)用層面上有相當高的價值。

　　區(qū)塊卷積主要常使用于計算一固定離散訊號與另一非固定離散訊號間的線性卷積，且非固定訊號的長度通常較固定方長上許多，一個很具體的例子就是計算一訊號經(jīng)有限長度濾波器后的輸出。其主要具有兩個優(yōu)點，第一，其計算復(fù)雜度較低，在輸入訊號長度為{\displaystyle N}N時，區(qū)塊卷積的計算復(fù)雜度為{\displaystyle\mathrm{O}(N)\!}{\displaystyle\mathrm{O}(N)\!}，而直接對整段輸入訊號進行卷積計算的復(fù)雜度為{\displaystyle\mathrm{O}(N\log N)\!}{\displaystyle\mathrm{O}(N\log N)\!}。第二，當我們要以硬件進行實作時，區(qū)塊卷積僅需要單一固定的硬件架構(gòu)，即可處理不同長度(甚至是無窮長)的輸入，可以像工廠的流水生產(chǎn)線一般連續(xù)的接受輸入并同時連續(xù)的吐出結(jié)果，而如果要直接對整段輸入訊號進行卷積，則需要對不同的輸入長度設(shè)計不同的硬件運算架構(gòu)，在應(yīng)用上是不切實際并且沒有必要的。

　　目前對于區(qū)塊卷積，主流使用的英文專有詞匯為sectioned convolution，但在一些中文圈作者所撰寫的文章中，也可能會采用取“塊”字翻英后的block convolution。

計算

　　區(qū)塊卷積的計算核心概念，便是將較長的訊號進行分段，將原先的求卷積問題分解為規(guī)模較小的問題，再將結(jié)果進行整合，以得到原先問題的結(jié)果。

　　但根據(jù)將訊號分段以及將結(jié)果整合的方式，可以再將區(qū)塊卷積細分為兩個類別(會在之后進行說明)。

卷積的性質(zhì)觀察

　　首先，在對區(qū)塊卷積的計算法進行細分之前，我們需要先了解一些關(guān)于卷積的性質(zhì)，以及關(guān)于切分后子問題的結(jié)果與母問題結(jié)果的關(guān)聯(lián)。

　　假設(shè)有一長度為{\displaystyle N}N的離散訊號(通常很長)：

　　{\displaystyle x[n](n=0,1,\dots,(N-1))}{\displaystyle x[n](n=0,1,\dots,(N-1))}

　　與一長度為{\displaystyle M}M的離散訊號(通常很短)：

　　{\displaystyle h[n](n=0,1,\dots,(M-1))}{\displaystyle h[n](n=0,1,\dots,(M-1))}

　　將兩者進行卷積后的結(jié)果{\displaystyle y[n]=x[n]*h[n]}{\displaystyle y[n]=x[n]*h[n]}，我們可以知道其長度應(yīng)該為{\displaystyle(N+M-1)}{\displaystyle(N+M-1)}：

　　{\displaystyle y[n](n=0,1,\dots,(N+M-2))}{\displaystyle y[n](n=0,1,\dots,(N+M-2))}

　　根據(jù)卷積的定義，我們可以知道其中{\displaystyle y}y的第{\displaystyle n'}{\displaystyle n'}點輸出{\displaystyle y[n']}{\displaystyle y[n']}，會受到相對應(yīng)位置的{\displaystyle x[n']}{\displaystyle x[n']}，以及其向前{\displaystyle(M-1)}{\displaystyle(M-1)}點的影響：

　　{\displaystyle y[n']=\sum _{m=0}^{M-1}x[n'-m]h[m]=x[n'-(M-1)]h[M-1]+x[n'-(M-2)]h[M-2]+\dots+x[n']h[0]}{\displaystyle y[n']=\sum _{m=0}^{M-1}x[n'-m]h[m]=x[n'-(M-1)]h[M-1]+x[n'-(M-2)]h[M-2]+\dots+x[n']h[0]}

　　這時如果我們將{\displaystyle x[n]}{\displaystyle x[n]}切出長度為{\displaystyle L}L的小段，并假設(shè)起始位置為{\displaystyle n_{0}}{\displaystyle n_{0}}：

　　{\displaystyle x_{L}[n]=x[n](n=n_{0},n_{0}+1,\dots,n_{0}+(L-1))}{\displaystyle x_{L}[n]=x[n](n=n_{0},n_{0}+1,\dots,n_{0}+(L-1))}

　　我們可以發(fā)現(xiàn)，其與{\displaystyle h[n]}h[n]進行卷積后的結(jié)果{\displaystyle y_{L}[n]=x_{L}[n]*h[n]}{\displaystyle y_{L}[n]=x_{L}[n]*h[n]}，和原先母問題在對應(yīng)區(qū)段的結(jié)果{\displaystyle y[n]}{\displaystyle y[n]}存在差異，具體來說，{\displaystyle y_{L}[n]}{\displaystyle y_{L}[n]}的前段部分少考量了{\displaystyle x[n]}{\displaystyle x[n]}中{\displaystyle n<n_{0}}{\displaystyle n<n_{0}}部分的影響，例如在{\displaystyle y_{L}[n]}{\displaystyle y_{L}[n]}第一點{\displaystyle y_{L}[n_{0}]}{\displaystyle y_{L}[n_{0}]}就僅考量一項{\displaystyle x}x的影響，和{\displaystyle y[n_{0}]}{\displaystyle y[n_{0}]}相差許多：

　　{\displaystyle y_{L}[n_{0}]=x[n_{0}]h[0]\neq y[n_{0}]=x[n_{0}-(M-1)]h[M-1]+\dots+x[n_{0}]h[0]}{\displaystyle y_{L}[n_{0}]=x[n_{0}]h[0]\neq y[n_{0}]=x[n_{0}-(M-1)]h[M-1]+\dots+x[n_{0}]h[0]}

　　同理，在{\displaystyle y_{L}}{\displaystyle y_{L}}的后段部分也會有類似的問題，少考量了{\displaystyle x}x在段落之后的影響，而只有計算到部分殘留影響的結(jié)果。只有在{\displaystyle y_{L}}{\displaystyle y_{L}}的中段部分，會與母問題結(jié)果{\displaystyle y}y完全相同。而要如何處理這個差異，并透過多段的{\displaystyle y_{L}}{\displaystyle y_{L}}還原出{\displaystyle y}y，便是以下兩種方法的最主要區(qū)別。

重疊-儲存之折積法

　　重疊-儲存算法，便是舍棄子結(jié)果{\displaystyle y_{L}}{\displaystyle y_{L}}的前后段，只取中段與母結(jié)果{\displaystyle y}y相同的部分并進行拼接的算法。

　　具體來說，重疊-儲存算法切分問題的主要考量為母結(jié)果{\displaystyle y}y，在實作這個算法的時候必須先決定將母結(jié)果{\displaystyle y}y切分的長度。

　　假設(shè)決定將母結(jié)果切分為長度{\displaystyle L_{y}}{\displaystyle L_{y}}的區(qū)間，根據(jù)前面的討論，我們可以得知：

　　1.{\displaystyle x_{L}}{\displaystyle x_{L}}的長度需要為{\displaystyle(L_{y}+(M-1))}{\displaystyle(L_{y}+(M-1))}才能夠確保{\displaystyle L_{y}}{\displaystyle L_{y}}長度的有效區(qū)段

　　2.在每次長度為{\displaystyle(L_{y}+2(M-1))}{\displaystyle(L_{y}+2(M-1))}的計算結(jié)果{\displaystyle y_{L}}{\displaystyle y_{L}}中，需要舍去前后各{\displaystyle(M-1)}{\displaystyle(M-1)}長度的部分

　　3.在第一個區(qū)段，因為{\displaystyle x[n]}{\displaystyle x[n]}在{\displaystyle n<0}{\displaystyle n<0}的區(qū)域是沒有資訊的，所以{\displaystyle x_{L0}}{\displaystyle x_{L0}}的長度只需要{\displaystyle L_{y}}{\displaystyle L_{y}}即可

　　綜合以上三點，我們可以寫出所需要的切分區(qū)段描述：

　　{\displaystyle x_{L0}[n]=x[n](n\in 0\sim(L_{y}-1))}{\displaystyle x_{L0}[n]=x[n](n\in 0\sim(L_{y}-1))}

　　{\displaystyle x_{Lk}[n]=x[n](n\in(kL_{y}-(M-1))\sim((k+1)L_{y}-1),k\in 1\sim(\left\lceil{\frac{M+N-1}{L_{y}}}\right\rceil-1))}{\displaystyle x_{Lk}[n]=x[n](n\in(kL_{y}-(M-1))\sim((k+1)L_{y}-1),k\in 1\sim(\left\lceil{\frac{M+N-1}{L_{y}}}\right\rceil-1))}

　　以及結(jié)果的描述：

　　{\displaystyle y[n]=y_{Lk}[n](n\in kL_{y}\sim((k+1)L_{y}-1),k\in 0\sim(\left\lceil{\frac{M+N-1}{L_{y}}}\right\rceil-1))}{\displaystyle y[n]=y_{Lk}[n](n\in kL_{y}\sim((k+1)L_{y}-1),k\in 0\sim(\left\lceil{\frac{M+N-1}{L_{y}}}\right\rceil-1))}

　　而重疊-儲存算法便是得名于其在輸入?yún)^(qū)段的切分上會有重疊的部分，須將前一個子問題的輸入后半先行儲存再作為下一個子問題的輸入前半。

　　這個算法的好處在于不需要額外的加法，并且如果在子問題求解時是采取直接計算卷積的方式，可以不用在訊號后面補零。

　　但缺點為同樣的分段數(shù)量下，每個子問題會需要處理較長的訊號，子問題計算量可能會較大一些。

重疊-相加之折積法

　　重疊-相加算法，則是將子結(jié)果{\displaystyle y_{L}}{\displaystyle y_{L}}的后段，與下一段子結(jié)果{\displaystyle y_{L}}{\displaystyle y_{L}}的前段，像拼圖一樣根據(jù)對應(yīng)的編號進行相加，重建出完整母結(jié)果{\displaystyle y}y的算法。

　　具體來說，重疊-儲存算法切分問題的主要考量為輸入{\displaystyle x}x，在實作這個算法的時候必須先決定將輸入{\displaystyle x}x切分的長度。

　　假設(shè)決定將輸入切分為長度{\displaystyle L}L的區(qū)間，我們可以直接寫出所需要的切分區(qū)段描述：

　　{\displaystyle x_{Lk}[n]=x[n](n\in kL\sim((k+1)L-1),k\in 0\sim(\left\lceil{\frac{N}{L}}\right\rceil-1))}{\displaystyle x_{Lk}[n]=x[n](n\in kL\sim((k+1)L-1),k\in 0\sim(\left\lceil{\frac{N}{L}}\right\rceil-1))}

　　以及結(jié)果的描述：

　　{\displaystyle y[n]=x[n]*h[n]=\sum _{k=0}^{(\left\lceil{\frac{N}{L}}\right\rceil-1)}x_{Lk}[n]*h[n]=\sum _{k=0}^{(\left\lceil{\frac{N}{L}}\right\rceil-1)}y_{Lk}[n]}{\displaystyle y[n]=x[n]*h[n]=\sum _{k=0}^{(\left\lceil{\frac{N}{L}}\right\rceil-1)}x_{Lk}[n]*h[n]=\sum _{k=0}^{(\left\lceil{\frac{N}{L}}\right\rceil-1)}y_{Lk}[n]}

　　這個算法特別需要注意的便是，重建出的母結(jié)果{\displaystyle y}y牽涉到子結(jié)果對應(yīng)項目的相加，要正確地對上才會是正確的結(jié)果，例如{\displaystyle y[L+1]}{\displaystyle y[L+1]}就會是兩個子結(jié)果的相加：{\displaystyle y[L+1]=\underbrace{x[(L+1)-(M-1)]h[M+1]+\dots+x[(L+1)-2]h[2]}_{y_{L}0[L+1]}+\underbrace{x[(L+1)-1]h[1]+x[(L+1)-0]h[0]}_{y_{L}1[L+1]}}{\displaystyle y[L+1]=\underbrace{x[(L+1)-(M-1)]h[M+1]+\dots+x[(L+1)-2]h[2]}_{y_{L}0[L+1]}+\underbrace{x[(L+1)-1]h[1]+x[(L+1)-0]h[0]}_{y_{L}1[L+1]}}

　　而重疊-相加算法便是得名于其在輸出的子結(jié)果上會有項目編號重疊的部分，須將其進行相加才能得到母結(jié)果。

　　這個算法的好處在于切分的方式相當直覺，而且在同樣的分段數(shù)量下，每個子問題需要處理的訊號長度較短，子問題計算量較小。

　　但缺點為可能需要一些額外的加法，而且就算采取直接計算卷積的方式來計算子問題，也仍需要補零在訊號后方。

復(fù)雜度與比較

　　雖然區(qū)塊卷積具有兩種差異不小的算法，但總體來說，對于每個固定架構(gòu)的子問題，所需要的計算量都是常數(shù)，而子問題的數(shù)量則正比于輸入訊號長度{\displaystyle N}N，所以計算復(fù)雜度對兩個算法來說都是{\displaystyle\mathrm{O}(N)\!}{\displaystyle\mathrm{O}(N)\!}，相較于使用快速傅里葉變換技巧進行整個問題的計算復(fù)雜度{\displaystyle\mathrm{O}(N\log N)\!}{\displaystyle\mathrm{O}(N\log N)\!}要來的低。

　　所以一般來說在{\displaystyle N}N很大時，顯然的使用區(qū)塊卷積會較處理整個問題來的有效率。

　　不過，有時候輸入訊號{\displaystyle x}x并不具有足夠的長度可以保證區(qū)塊卷積較有效率，又或者在一些極端情況下，直接按定義進行計算卷積可能會更有效率，所以接著便是要稍微談?wù)撘幌虏煌髁饔嬎憔矸e方法的計算量，以及如何根據(jù)輸入訊號長度{\displaystyle N}N與固定訊號長度{\displaystyle M}M間的關(guān)系選擇算法。

直接計算卷積

　　如果是根據(jù)卷積的定義，直接以乘法及加法計算卷積的話，我們可以知道，每一個{\displaystyle x[n]}{\displaystyle x[n]}都需要輪流和每一個{\displaystyle h[n]}h[n]進行相乘，所以總共需要的乘法數(shù)量為

　　{\displaystyle N\times M}{\displaystyle N\times M}

　　又因為訊號可能是復(fù)數(shù)，所以上述的乘法為復(fù)數(shù)乘法，將其統(tǒng)一以時數(shù)乘法進行實作后可以得到需要的實數(shù)乘法數(shù)為

　　{\displaystyle 3N\times M}{\displaystyle 3N\times M}

　　可以發(fā)現(xiàn)，其實直接計算卷積對于輸入長度{\displaystyle N}N來說，其復(fù)雜度也是{\displaystyle\mathrm{O}(N)\!}{\displaystyle\mathrm{O}(N)\!}，但其常數(shù)為{\displaystyle 3M}{\displaystyle 3M}，當{\displaystyle M}M增大時，運算量會增加很快，運算效率會不及區(qū)塊卷積，但相對的當{\displaystyle M}M落在很小的值時，直接計算卷積可能會是較高效率的計算方法。

使用快速傅立葉變換技巧計算卷積

　　除了直接計算卷積之外，另外一種主流的卷積計算方法，便是透過卷積定理，將卷積的計算化為兩次傅立葉變換相乘后再進行反傅立葉變換的問題，實作如下：

　　{\displaystyle y[n]=x[n]*h[n]=IFFT_{P}(FFT_{P}(x[n])\times FFT_{P}(h[n]))}{\displaystyle y[n]=x[n]*h[n]=IFFT_{P}(FFT_{P}(x[n])\times FFT_{P}(h[n]))}

　　其中{\displaystyle FFT_{P}}{\displaystyle FFT_{P}}為{\displaystyle P}P點快速傅立葉變換，{\displaystyle IFFT_{P}}{\displaystyle IFFT_{P}}為逆變換(形式與快速傅立葉變換相同)，{\displaystyle P}P根據(jù)圓周卷積定理必須大于{\displaystyle(M+N-1)}{\displaystyle(M+N-1)}，而{\displaystyle x[n]}{\displaystyle x[n]}及{\displaystyle h[n]}h[n]需透過補零來補齊長度。

　　如果采用這個方法，并且假設(shè){\displaystyle h[n]}h[n]為固定不變，可以將{\displaystyle FFT_{P}(h[n])}{\displaystyle FFT_{P}(h[n])}計算一次后儲存?zhèn)溆茫强梢缘玫剿璩朔〝?shù)為：

　　{\displaystyle 2MUL_{P}+3P}{\displaystyle 2MUL_{P}+3P}

　　其中{\displaystyle MUL_{P}}{\displaystyle MUL_{P}}為{\displaystyle P}P點快速傅立葉變換所需的乘法數(shù)，估計為{\displaystyle{\frac{3}{2}}P\log _{2}P}{\displaystyle{\frac{3}{2}}P\log _{2}P}，乘兩倍是因為需計算{\displaystyle FFT_{P}(x[n])}{\displaystyle FFT_{P}(x[n])}與最后的逆變換，{\displaystyle 3P}{\displaystyle 3P}則是因為{\displaystyle FFT_{P}(x[n])\times FFT_{P}(h[n])}{\displaystyle FFT_{P}(x[n])\times FFT_{P}(h[n])}含有{\displaystyle P}P個復(fù)數(shù)的乘法，統(tǒng)一轉(zhuǎn)換為實數(shù)乘法則是{\displaystyle 3P}{\displaystyle 3P}。

　　將{\displaystyle P=(M+N-1)\approx(M+N)}{\displaystyle P=(M+N-1)\approx(M+N)}與{\displaystyle MUL_{P}}{\displaystyle MUL_{P}}的估計值帶入上面的所需乘法數(shù)進行估計，可以得到所需乘法數(shù)為：

　　{\displaystyle 3(M+N)(\log _{2}(M+N)+1)\approx 3(M+N)\log _{2}(M+N)}{\displaystyle 3(M+N)(\log _{2}(M+N)+1)\approx 3(M+N)\log _{2}(M+N)}

　　可以發(fā)現(xiàn)，使用快速傅立葉變換技巧計算卷積對于輸入長度{\displaystyle N}N來說，其復(fù)雜度是{\displaystyle\mathrm{O}(N\log N)\!}{\displaystyle\mathrm{O}(N\log N)\!}，但當{\displaystyle M}M大約與{\displaystyle N}N落在接近的數(shù)量級時，運算量會較其他方法低上許多。

使用區(qū)塊卷積搭配快速傅立葉算法計算卷積

　　最后，另外一種主流的卷積計算法便是先利用區(qū)塊卷積將問題拆分，再將拆分后的問題透過快速傅立葉算法來處理，而之所以通常不是搭配直接計算的方式，是因為我們通常會假設(shè)拆分過后的問題中，要進行卷積的兩訊號長度會差不多長，而根據(jù)前面的討論，我們已經(jīng)知道使用快速傅立葉轉(zhuǎn)換來進行計算會有效率的多。

　　而使用區(qū)塊卷積搭配快速傅立葉算法計算卷積的復(fù)雜度，和前面兩種方法的計算復(fù)雜度只與{\displaystyle M,N}{\displaystyle M,N}有關(guān)不同，分段所使用的段落長度{\displaystyle L}L也會很大程度的影響這個方法的計算量。

　　以重疊-相加算法作為代表，假設(shè)采用的分段長度為{\displaystyle L}L，可以得到分段的段數(shù){\displaystyle S}S為：

　　{\displaystyle S=\left\lceil{\frac{N}{L}}\right\rceil\approx{\frac{N}{L}}}{\displaystyle S=\left\lceil{\frac{N}{L}}\right\rceil\approx{\frac{N}{L}}}

　　而每個子問題的實際計算量根據(jù)上面可得：

　　{\displaystyle 2MUL_{P}+3P}{\displaystyle 2MUL_{P}+3P}

　　乘上需要解的子問題數(shù)可得實際總計算量：

　　{\displaystyle 2S\times MUL_{P}+3S\times P}{\displaystyle 2S\times MUL_{P}+3S\times P}

　　同樣根據(jù)上面可再進一步估計得：

　　{\displaystyle{\frac{N}{L}}3(M+L-1)(\log _{2}(M+L-1)+1)\approx{\frac{N}{L}}3(M+L)\log _{2}(M+L)}{\displaystyle{\frac{N}{L}}3(M+L-1)(\log _{2}(M+L-1)+1)\approx{\frac{N}{L}}3(M+L)\log _{2}(M+L)}

　　可以發(fā)現(xiàn)這個計算法的復(fù)雜度為{\displaystyle\mathrm{O}(N)\!}{\displaystyle\mathrm{O}(N)\!}，并且常數(shù)約為{\displaystyle{\frac{3(M+L)}{L}}\log _{2}(M+L)}{\displaystyle{\frac{3(M+L)}{L}}\log _{2}(M+L)}，在{\displaystyle M}M的數(shù)值略大時會較采取直接計算會較有效率，但在{\displaystyle M}M與{\displaystyle N}N的數(shù)量級接近時，因為{\displaystyle M}M的大小被迫推升，導(dǎo)致比起直接對整段訊號進行快速傅立葉算法的表現(xiàn)還要差。

　　所以根據(jù)上述可以估計這個方法可以展現(xiàn)優(yōu)勢的區(qū)段，大概是界在前面兩種方法的{\displaystyle M,N}{\displaystyle M,N}比例之間。

　　而在實際應(yīng)用時，因為快速傅立葉轉(zhuǎn)換的計算量在局部會有不小的波動，并不如理論值估計那般平滑，所以為了得到較好的計算效率，除了須將上面的計算量視作{\displaystyle L}L的函數(shù)，透過數(shù)值繪圖的方法或微分，求得在理論估計上最適合的{\displaystyle L}L值之外，還需在求得的最適合子問題大小附近進行找尋，挑選數(shù)個可能的合適子問題傅立葉轉(zhuǎn)換大小，再將反求得的分段長度帶回計算運算量，以求得真正的最佳分段長度{\displaystyle L}L。

　　例如：在

　　{\displaystyle N=2000,M=17}{\displaystyle N=2000,M=17}

　　的情況下，求得的理論最適合分段長度為

　　{\displaystyle L_{0}=85}{\displaystyle L_{0}=85}

　　理論最適合子問題傅立葉轉(zhuǎn)換大小為

　　{\displaystyle P_{0}=L_{0}+M-1=101}{\displaystyle P_{0}=L_{0}+M-1=101}點

　　但在{\displaystyle 72}72點傅立葉轉(zhuǎn)換的計算量有一個明顯的低谷，將由此逆推得到的可能分段長度

　　{\displaystyle L=72-M+1=56}{\displaystyle L=72-M+1=56}

　　與其他可能值都帶回去計算實際計算量后，可以確認{\displaystyle 56}{\displaystyle 56}才是最佳的問題分段長度。

　　最后，同樣是基于快速傅立葉轉(zhuǎn)換的計算量在局部的波動，在極為特殊的情況下，如果{\displaystyle M\leq 4}{\displaystyle M\leq 4}，我們便有可能使子問題僅需使用{\displaystyle 4}4點傅立葉轉(zhuǎn)換，而在這樣的情況下雖會使用大量的加法，但可不必在傅立葉轉(zhuǎn)換上使用任何乘法，可能會較直接計算卷積有效率。

關(guān)于區(qū)塊折積，小編為大家就分享這些。歡迎聯(lián)系我們合運電氣有限公司，以獲取更多區(qū)塊,折積,區(qū)塊,折積,又稱,卷積,、,分段,分塊相關(guān)知識。