區塊摺積

區塊折積，又稱區塊卷積、分段折積、分段卷積、分塊卷積，是一種計算線性離散卷積的方法，在訊號處理以及線性非時變系統領域的應用層面上有相當高的價值。區塊卷積主要常使用於計算一固定離散訊號與另一非固定離散訊號間的線性卷積，且非固定訊號的長度通常較固定方長上許多，一個很具體的例子就是計算一訊號經有限長度濾波器後的輸出。其主要具有兩個優點，第一，其計算複雜度較低，在輸入訊號長度為formula_1時，區塊卷積的計算複雜度為formula_2，而直接對整段輸入訊號進行卷積計算的複雜度為formula_3。第二，當我們要以硬體進行實作時，區塊卷積僅需要單一固定的硬體架構，即可處理不同長度(甚至是無窮長)的輸入，可以像工廠的流水生產線一般連續的接受輸入並同時連續的吐出結果，而如果要直接對整段輸入訊號進行卷積，則需要對不同的輸入長度設計不同的硬體運算架構，在應用上是不切實際並且沒有必要的。目前對於區塊卷積，主流使用的英文專有詞彙為sectioned convolution，但在一些中文圈作者所撰寫的文章中，也可能會採用取「塊」字翻英後的block convolution。計算.區塊卷積的計算核心概念，便是將較長的訊號進行分段，將原先的求卷積問題分解為規模較小的問題，再將結果進行整合，以得到原先問題的結果。但根據將訊號分段以及將結果整合的方式，可以再將區塊卷積細分為兩個類別(會在之後進行說明)。卷積的性質觀察.首先，在對區塊卷積的計演算法進行細分之前，我們需要先了解一些關於卷積的性質，以及關於切分後子問題的結果與母問題結果的關聯。假設有一長度為formula_1的離散訊號(通常很長)：formula_5與一長度為formula_6的離散訊號(通常很短)：formula_7將兩者進行卷積後的結果formula_8，我們可以知道其長度應該為formula_9：formula_10根據卷積的定義，我們可以知道其中formula_11的第formula_12點輸出formula_13，會受到相對應位置的formula_14，以及其向前formula_15點的影響：formula_16這時如果我們將formula_17切出長度為formula_18的小段，並假設起始位置為formula_19：formula_20我們可以發現，其與formula_21進行卷積後的結果formula_22，和原先母問題在對應區段的結果formula_23存在差異，具體來說，formula_24的前段部分少考量了formula_17中formula_26部分的影響，例如在formula_24第一點formula_28就僅考量一項formula_29的影響，和formula_30相差許多：formula_31同理，在formula_32的後段部分也會有類似的問題，少考量了formula_29在段落之後的影響，而只有計算到部分殘留影響的結果。只有在formula_32的中段部分，會與母問題結果formula_11完全相同。而要如何處理這個差異，並透過多段的formula_32還原出formula_11，便是以下兩種方法的最主要區別。重疊-儲存之摺積法.重疊-儲存演算法，便是捨棄子結果formula_32的前後段，只取中段與母結果formula_11相同的部分並進行拼接的演演算法。具體來說，重疊-儲存演算法切分問題的主要考量為母結果formula_11，在實作這個演算法的時候必須先決定將母結果formula_11切分的長度。假設決定將母結果切分為長度formula_42的區間，根據前面的討論，我們可以得知：1.formula_43的長度需要為formula_44才能夠確保formula_42長度的有效區段2.在每次長度為formula_46的計算結果formula_32中，需要捨去前後各formula_48長度的部分3.在第一個區段，因為formula_17在formula_50的區域是沒有資訊的，所以formula_51的長度只需要formula_42即可綜合以上三點，我們可以寫出所需要的切分割槽段描述：formula_53formula_54以及結果的描述：formula_55而重疊-儲存演算法便是得名於其在輸入區段的切分上會有重疊的部分，須將前一個子問題的輸入後半先行儲存再作為下一個子問題的輸入前半。這個演算法的好處在於不需要額外的加法，並且如果在子問題求解時是採取直接計算卷積的方式，可以不用在訊號後面補零。但缺點為同樣的分段數量下，每個子問題會需要處理較長的訊號，子問題計算量可能會較大一些。重疊-相加之摺積法.重疊-相加演算法，則是將子結果formula_32的後段，與下一段子結果formula_32的前段，像拼圖一樣根據對應的編號進行相加，重建出完整母結果formula_11的演演算法。具體來說，重疊-儲存演算法切分問題的主要考量為輸入formula_29，在實作這個演算法的時候必須先決定將輸入formula_29切分的長度。假設決定將輸入切分為長度formula_18的區間，我們可以直接寫出所需要的切分割槽段描述：formula_62以及結果的描述：formula_63這個演算法特別需要注意的便是，重建出的母結果formula_11牽涉到子結果對應專案的相加，要正確地對上才會是正確的結果，例如formula_65就會是兩個子結果的相加：formula_66而重疊-相加演算法便是得名於其在輸出的子結果上會有專案編號重疊的部分，須將其進行相加才能得到母結果。這個演算法的好處在於切分的方式相當直覺，而且在同樣的分段數量下，每個子問題需要處理的訊號長度較短，子問題計算量較小。但缺點為可能需要一些額外的加法，而且就算採取直接計算卷積的方式來計運算元問題，也仍需要補零在訊號後方。複雜度與比較.雖然區塊卷積具有兩種差異不小的演算法，但總體來說，對於每個固定架構的子問題，所需要的計算量都是常數，而子問題的數量則正比於輸入訊號長度formula_1，所以計算複雜度對兩個演算法來說都是formula_2，相較於使用快速傅立葉變換技巧進行整個問題的計算複雜度formula_3要來的低。所以一般來說在formula_1很大時，顯然的使用區塊卷積會較處理整個問題來的有效率。不過，有時候輸入訊號formula_29並不具有足夠的長度可以保證區塊卷積較有效率，又或者在一些極端情況下，直接按定義進行計算卷積可能會更有效率，所以接著便是要稍微談論一下不同主流計算卷積方法的計算量，以及如何根據輸入訊號長度formula_1與固定訊號長度formula_6間的關係選擇演算法。直接計算卷積.如果是根據卷積的定義，直接以乘法及加法計算卷積的話，我們可以知道，每一個formula_17都需要輪流和每一個formula_21進行相乘，所以總共需要的乘法數量為formula_76又因為訊號可能是複數，所以上述的乘法為複數乘法，將其統一以時數乘法進行實作後可以得到需要的實數乘法數為formula_77可以發現，其實直接計算卷積對於輸入長度formula_1來說，其複雜度也是formula_2，但其常數為formula_80，當formula_6增大時，運算量會增加很快，運算效率會不及區塊卷積，但相對的當formula_6落在很小的值時，直接計算卷積可能會是較高效率的計算方法。使用快速傅立葉變換技巧計算卷積.除了直接計算卷積之外，另外一種主流的卷積計算方法，便是透過卷積定理，將卷積的計算化為兩次傅立葉變換相乘後再進行反傅立葉變換的問題，實作如下：formula_83其中formula_84為formula_85點快速傅立葉變換，formula_86為逆變換(形式與快速傅立葉變換相同)，formula_85根據圓周卷積定理必須大於formula_88，而formula_17及formula_21需透過補零來補齊長度。如果採用這個方法，並且假設formula_21為固定不變，可以將formula_92計算一次後儲存備用，那可以得到所需乘法數為：formula_93其中formula_94為formula_85點快速傅立葉變換所需的乘法數，估計為formula_96，乘兩倍是因為需計算formula_97與最後的逆變換，formula_98則是因為formula_99含有formula_85個複數的乘法，統一轉換為實數乘法則是formula_98。將formula_102與formula_94的估計值帶入上面的所需乘法數進行估計，可以得到所需乘法數為：formula_104可以發現，使用快速傅立葉變換技巧計算卷積對於輸入長度formula_1來說，其複雜度是formula_3，但當formula_6大約與formula_1落在接近的數量級時，運算量會較其他方法低上許多。使用區塊卷積搭配快速傅立葉演算法計算卷積.最後，另外一種主流的卷積計演算法便是先利用區塊卷積將問題拆分，再將拆分後的問題透過快速傅立葉演算法來處理，而之所以通常不是搭配直接計算的方式，是因為我們通常會假設拆分過後的問題中，要進行卷積的兩訊號長度會差不多長，而根據前面的討論，我們已經知道使用快速傅立葉轉換來進行計算會有效率的多。而使用區塊卷積搭配快速傅立葉演算法計算卷積的複雜度，和前面兩種方法的計算複雜度只與formula_109有關不同，分段所使用的段落長度formula_110也會很大程度的影響這個方法的計算量。以重疊-相加演算法作為代表，假設採用的分段長度為formula_110，可以得到分段的段數formula_112為：formula_113而每個子問題的實際計算量根據上面可得：formula_114乘上需要解的子問題數可得實際總計算量：formula_115同樣根據上面可再進一步估計得：formula_116可以發現這個計演算法的複雜度為formula_2，並且常數約為formula_118，在formula_119的數值略大時會較採取直接計算會較有效率，但在formula_119與formula_121的數量級接近時，因為formula_119的大小被迫推升，導致比起直接對整段訊號進行快速傅立葉演算法的表現還要差。所以根據上述可以估計這個方法可以展現優勢的區段，大概是界在前面兩種方法的formula_109比例之間。而在實際應用時，因為快速傅立葉轉換的計算量在區域性會有不小的波動，並不如理論值估計那般平滑，所以為了得到較好的計算效率，除了須將上面的計算量視作formula_110的函式，透過數值繪圖的方法或微分，求得在理論估計上最適合的formula_110值之外，還需在求得的最適合子問題大小附近進行找尋，挑選數個可能的合適子問題傅立葉轉換大小，再將反求得的分段長度帶回計算運算量，以求得真正的最佳分段長度formula_110。例如：在formula_127的情況下，求得的理論最適合分段長度為formula_128理論最適合子問題傅立葉轉換大小為formula_129點但在formula_130點傅立葉轉換的計算量有一個明顯的低谷，將由此逆推得到的可能分段長度formula_131與其他可能值都帶回去計算實際計算量後，可以確認formula_132才是最佳的問題分段長度。最後，同樣是基於快速傅立葉轉換的計算量在區域性的波動，在極為特殊的情況下，如果formula_133，我們便有可能使子問題僅需使用formula_134點傅立葉轉換，而在這樣的情況下雖會使用大量的加法，但可不必在傅立葉轉換上使用任何乘法，可能會較直接計算卷積有效率。Jian-Jiun Ding, advanced digital signal processing lecture note , the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2022.重疊-儲存之摺積法重疊-相加之摺積法