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

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

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

計(jì)算

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

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

卷積的性質(zhì)觀察

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

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

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

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

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

　　將兩者進(jìn)行卷積后的結(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'}點(diǎn)輸出{\displaystyle y[n']}{\displaystyle y[n']}，會(huì)受到相對(duì)應(yīng)位置的{\displaystyle x[n']}{\displaystyle x[n']}，以及其向前{\displaystyle(M-1)}{\displaystyle(M-1)}點(diǎn)的影響：

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

　　這時(shí)如果我們將{\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]進(jìn)行卷積后的結(jié)果{\displaystyle y_{L}[n]=x_{L}[n]*h[n]}{\displaystyle y_{L}[n]=x_{L}[n]*h[n]}，和原先母問題在對(duì)應(yīng)區(qū)段的結(jié)果{\displaystyle y[n]}{\displaystyle y[n]}存在差異，具體來說，{\displaystyle y_{L}[n]}{\displaystyle y_{L}[n]}的前段部分少考量了{(lán)\displaystyle x[n]}{\displaystyle x[n]}中{\displaystyle n<n_{0}}{\displaystyle n<n_{0}}部分的影響，例如在{\displaystyle y_{L}[n]}{\displaystyle y_{L}[n]}第一點(diǎn){\displaystyle y_{L}[n_{0}]}{\displaystyle y_{L}[n_{0}]}就僅考量一項(xiàng){\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}}的后段部分也會(huì)有類似的問題，少考量了{(lán)\displaystyle x}x在段落之后的影響，而只有計(jì)算到部分殘留影響的結(jié)果。只有在{\displaystyle y_{L}}{\displaystyle y_{L}}的中段部分，會(huì)與母問題結(jié)果{\displaystyle y}y完全相同。而要如何處理這個(gè)差異，并透過多段的{\displaystyle y_{L}}{\displaystyle y_{L}}還原出{\displaystyle y}y，便是以下兩種方法的最主要區(qū)別。

重疊-儲(chǔ)存之折積法

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

　　具體來說，重疊-儲(chǔ)存算法切分問題的主要考量為母結(jié)果{\displaystyle y}y，在實(shí)作這個(gè)算法的時(shí)候必須先決定將母結(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))}的計(jì)算結(jié)果{\displaystyle y_{L}}{\displaystyle y_{L}}中，需要舍去前后各{\displaystyle(M-1)}{\displaystyle(M-1)}長度的部分

　　3.在第一個(gè)區(qū)段，因?yàn)閧\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}}即可

　　綜合以上三點(diǎn)，我們可以寫出所需要的切分區(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))}

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

　　這個(gè)算法的好處在于不需要額外的加法，并且如果在子問題求解時(shí)是采取直接計(jì)算卷積的方式，可以不用在訊號(hào)后面補(bǔ)零。

　　但缺點(diǎn)為同樣的分段數(shù)量下，每個(gè)子問題會(huì)需要處理較長的訊號(hào)，子問題計(jì)算量可能會(huì)較大一些。

重疊-相加之折積法

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

　　具體來說，重疊-儲(chǔ)存算法切分問題的主要考量為輸入{\displaystyle x}x，在實(shí)作這個(gè)算法的時(shí)候必須先決定將輸入{\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]}

　　這個(gè)算法特別需要注意的便是，重建出的母結(jié)果{\displaystyle y}y牽涉到子結(jié)果對(duì)應(yīng)項(xiàng)目的相加，要正確地對(duì)上才會(huì)是正確的結(jié)果，例如{\displaystyle y[L+1]}{\displaystyle y[L+1]}就會(huì)是兩個(gè)子結(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é)果上會(huì)有項(xiàng)目編號(hào)重疊的部分，須將其進(jìn)行相加才能得到母結(jié)果。

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

　　但缺點(diǎn)為可能需要一些額外的加法，而且就算采取直接計(jì)算卷積的方式來計(jì)算子問題，也仍需要補(bǔ)零在訊號(hào)后方。

復(fù)雜度與比較

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

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

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

直接計(jì)算卷積

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

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

　　又因?yàn)橛嵦?hào)可能是復(fù)數(shù)，所以上述的乘法為復(fù)數(shù)乘法，將其統(tǒng)一以時(shí)數(shù)乘法進(jìn)行實(shí)作后可以得到需要的實(shí)數(shù)乘法數(shù)為

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

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

使用快速傅立葉變換技巧計(jì)算卷積

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

　　{\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點(diǎn)快速傅立葉變換，{\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]需透過補(bǔ)零來補(bǔ)齊長度。

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

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

　　其中{\displaystyle MUL_{P}}{\displaystyle MUL_{P}}為{\displaystyle P}P點(diǎn)快速傅立葉變換所需的乘法數(shù)，估計(jì)為{\displaystyle{\frac{3}{2}}P\log _{2}P}{\displaystyle{\frac{3}{2}}P\log _{2}P}，乘兩倍是因?yàn)樾栌?jì)算{\displaystyle FFT_{P}(x[n])}{\displaystyle FFT_{P}(x[n])}與最后的逆變換，{\displaystyle 3P}{\displaystyle 3P}則是因?yàn)閧\displaystyle FFT_{P}(x[n])\times FFT_{P}(h[n])}{\displaystyle FFT_{P}(x[n])\times FFT_{P}(h[n])}含有{\displaystyle P}P個(gè)復(fù)數(shù)的乘法，統(tǒng)一轉(zhuǎn)換為實(shí)數(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}}的估計(jì)值帶入上面的所需乘法數(shù)進(jìn)行估計(jì)，可以得到所需乘法數(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)，使用快速傅立葉變換技巧計(jì)算卷積對(duì)于輸入長度{\displaystyle N}N來說，其復(fù)雜度是{\displaystyle\mathrm{O}(N\log N)\!}{\displaystyle\mathrm{O}(N\log N)\!}，但當(dāng){\displaystyle M}M大約與{\displaystyle N}N落在接近的數(shù)量級(jí)時(shí)，運(yùn)算量會(huì)較其他方法低上許多。

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

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

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

　　以重疊-相加算法作為代表，假設(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}}}

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

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

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

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

　　同樣根據(jù)上面可再進(jìn)一步估計(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)這個(gè)計(jì)算法的復(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ù)值略大時(shí)會(huì)較采取直接計(jì)算會(huì)較有效率，但在{\displaystyle M}M與{\displaystyle N}N的數(shù)量級(jí)接近時(shí)，因?yàn)閧\displaystyle M}M的大小被迫推升，導(dǎo)致比起直接對(duì)整段訊號(hào)進(jìn)行快速傅立葉算法的表現(xiàn)還要差。

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

　　而在實(shí)際應(yīng)用時(shí)，因?yàn)榭焖俑盗⑷~轉(zhuǎn)換的計(jì)算量在局部會(huì)有不小的波動(dòng)，并不如理論值估計(jì)那般平滑，所以為了得到較好的計(jì)算效率，除了須將上面的計(jì)算量視作{\displaystyle L}L的函數(shù)，透過數(shù)值繪圖的方法或微分，求得在理論估計(jì)上最適合的{\displaystyle L}L值之外，還需在求得的最適合子問題大小附近進(jìn)行找尋，挑選數(shù)個(gè)可能的合適子問題傅立葉轉(zhuǎn)換大小，再將反求得的分段長度帶回計(jì)算運(yù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}點(diǎn)

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

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

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

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

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