區塊折積

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

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

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

計算

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

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

卷積的性質觀察

　　首先，在對區塊卷積的計算法進行細分之前，我們需要先了解一些關于卷積的性質，以及關于切分后子問題的結果與母問題結果的關聯。

　　假設有一長度為{\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))}

　　將兩者進行卷積后的結果{\displaystyle y[n]=x[n]*h[n]}{\displaystyle y[n]=x[n]*h[n]}，我們可以知道其長度應該為{\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))}

　　根據卷積的定義，我們可以知道其中{\displaystyle y}y的第{\displaystyle n'}{\displaystyle n'}點輸出{\displaystyle y[n']}{\displaystyle y[n']}，會受到相對應位置的{\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的小段，并假設起始位置為{\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))}

　　我們可以發現，其與{\displaystyle h[n]}h[n]進行卷積后的結果{\displaystyle y_{L}[n]=x_{L}[n]*h[n]}{\displaystyle y_{L}[n]=x_{L}[n]*h[n]}，和原先母問題在對應區段的結果{\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在段落之后的影響，而只有計算到部分殘留影響的結果。只有在{\displaystyle y_{L}}{\displaystyle y_{L}}的中段部分，會與母問題結果{\displaystyle y}y完全相同。而要如何處理這個差異，并透過多段的{\displaystyle y_{L}}{\displaystyle y_{L}}還原出{\displaystyle y}y，便是以下兩種方法的最主要區別。

重疊-儲存之折積法

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

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

　　假設決定將母結果切分為長度{\displaystyle L_{y}}{\displaystyle L_{y}}的區間，根據前面的討論，我們可以得知：

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

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

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

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

　　{\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))}

　　以及結果的描述：

　　{\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))}

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

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

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

重疊-相加之折積法

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

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

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

　　{\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))}

　　以及結果的描述：

　　{\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]}

　　這個算法特別需要注意的便是，重建出的母結果{\displaystyle y}y牽涉到子結果對應項目的相加，要正確地對上才會是正確的結果，例如{\displaystyle y[L+1]}{\displaystyle y[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]}}{\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 N}N，所以計算復雜度對兩個算法來說都是{\displaystyle\mathrm{O}(N)\!}{\displaystyle\mathrm{O}(N)\!}，相較于使用快速傅里葉變換技巧進行整個問題的計算復雜度{\displaystyle\mathrm{O}(N\log N)\!}{\displaystyle\mathrm{O}(N\log N)\!}要來的低。

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

　　不過，有時候輸入訊號{\displaystyle x}x并不具有足夠的長度可以保證區塊卷積較有效率，又或者在一些極端情況下，直接按定義進行計算卷積可能會更有效率，所以接著便是要稍微談論一下不同主流計算卷積方法的計算量，以及如何根據輸入訊號長度{\displaystyle N}N與固定訊號長度{\displaystyle M}M間的關系選擇算法。

直接計算卷積

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

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

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

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

　　可以發現，其實直接計算卷積對于輸入長度{\displaystyle N}N來說，其復雜度也是{\displaystyle\mathrm{O}(N)\!}{\displaystyle\mathrm{O}(N)\!}，但其常數為{\displaystyle 3M}{\displaystyle 3M}，當{\displaystyle M}M增大時，運算量會增加很快，運算效率會不及區塊卷積，但相對的當{\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根據圓周卷積定理必須大于{\displaystyle(M+N-1)}{\displaystyle(M+N-1)}，而{\displaystyle x[n]}{\displaystyle x[n]}及{\displaystyle h[n]}h[n]需透過補零來補齊長度。

　　如果采用這個方法，并且假設{\displaystyle h[n]}h[n]為固定不變，可以將{\displaystyle FFT_{P}(h[n])}{\displaystyle FFT_{P}(h[n])}計算一次后儲存備用，那可以得到所需乘法數為：

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

　　其中{\displaystyle MUL_{P}}{\displaystyle MUL_{P}}為{\displaystyle P}P點快速傅立葉變換所需的乘法數，估計為{\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個復數的乘法，統一轉換為實數乘法則是{\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}}的估計值帶入上面的所需乘法數進行估計，可以得到所需乘法數為：

　　{\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)}

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

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

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

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

　　以重疊-相加算法作為代表，假設采用的分段長度為{\displaystyle L}L，可以得到分段的段數{\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}}}

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

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

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

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

　　同樣根據上面可再進一步估計得：

　　{\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)}

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

　　所以根據上述可以估計這個方法可以展現優勢的區段，大概是界在前面兩種方法的{\displaystyle M,N}{\displaystyle M,N}比例之間。

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

　　例如：在

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

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

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

　　理論最適合子問題傅立葉轉換大小為

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

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

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

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

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

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