查看“︁重疊-相加之摺積法”︁的源代码

{{NoteTA
|G1=Signals and Systems
|G2=IT
}}
'''重疊-相加之摺積法''' ( ''Overlap-add method'' ) 是一種[[區塊摺積]] ( block convolution, sectioned convolution )，可以有效的計算一個很長的信號 ''x''[''n''] 和一個 [[有限脉冲响应|FIR 濾波器]] ''h''[''n''] 的[[卷积#定义|離散摺積]]。

:<math>
\begin{align}
y[n] = x[n] \star h[n] \ \stackrel{\mathrm{def}}{=} \ \sum_{m=-\infty}^{\infty} h[m] \cdot x[n-m]
= \sum_{m=1}^{M} h[m] \cdot x[n-m]
\end{align}</math>

其中 ''h''[''m''] 在 [1, ''M''] 之外為零。

'''重疊-相加之摺積法'''算出重疊的輸出區塊；另一種區塊摺積的作法，[[重疊-儲存之摺積法]]則是將輸入區塊重疊。

==算法==

[[Image:Depiction of overlap-add algorithm.png|frame|none|图1：重叠-相加法]]

概念上，這個做法是選用一個較短的適當長度 ''L'' 來切割 ''x''[''n''] ，計算 ''x''[''n''] 的子數列濾波後的結果 ''y''<sub>''k''</sub>[''n''] ，然後連接起來成為 ''y''[''n''] 。並考慮到一個長度 <math>L</math> 和長度 <math>M</math> 的有限長度離散信號，做[[卷积|摺積]]之後會成為長度 <math>L+M-1</math> 的信號。

:<math>x_k[n]  \ \stackrel{\mathrm{def}}{=} 
\begin{cases}
x[n+kL] & n=1,2,\ldots,L\\
0 & \textrm{otherwise}
\end{cases}
</math>

則

:<math>x[n] = \sum_{k} x_k[n-kL]\,</math>

而因為[[卷积|摺積]]是[[线性时不变系统理论|線性非時變]]運算，所以 ''y''[''n''] 可被表示為

:<math>
\begin{align}
y[n] = \left(\sum_{k} x_k[n-kL]\right) \star h[n] &= \sum_{k} \left(x_k[n-kL]\star h[n]\right)\\
&= \sum_{k} y_k[n-kL]
\end{align}
</math>

其中 &nbsp;<math>y_k[n] \ \stackrel{\mathrm{def}}{=} \ x_k[n] \star h[n]\,</math>&nbsp; 在 [1, ''L''+''M''-''1''] 之外為零。&nbsp;每個 ''y''<sub>''k''</sub>[''n''] 長度 <math>L+M-1</math> ，以間隔 <math>L</math> 位移後相加，所以輸出是由互相<u>重疊</u>的區塊<u>相加</u>而成，因此稱為''重疊''-''相加''之摺積法。


儘管一時看不出切割成區塊的好處為何，但考慮到對任何 &nbsp;<math>N\ge L+M-1\,</math>&nbsp; 以上每段的[[卷积|摺積]]都等價於 <math>x_k[n]\,</math> 和 <math>h[n]\,</math> 做 <math>N\,</math> 點[[圓周摺積]]&nbsp;，不夠的部分補上零 (zero-padding)。如此一來因為圓周摺積可以藉由[[卷积定理|圓周摺積定理]]

:<math>y_k[n] = \textrm{IFFT}\left(\textrm{FFT}\left(x_k[n]\right)\cdot\textrm{FFT}\left(h[n]\right)\right)</math>

轉換成三次 <math>N\,</math> 點[[快速傅立葉變換]]和 <math>N\,</math> 次乘法，使原本每段 ''O''(''N''<sup>2</sup>) 的運算量減少至 ''O''(''N'' ''logN'')，速度大幅增加。

===[[伪代码]]===

    '''Algorithm''' (''OA for linear convolution'')
    Evaluate the best value of N and L
    H = FFT(h,N)       <font color=green>(''zero-padded FFT'')</font>
    i = 1
    '''while''' i <= Nx
        il = min(i+L-1,Nx)
        yt = IFFT( FFT(x(i:il),N) .* H, N)
        k  = min(i+N-1,Nx)
        y(i:k) = y(i:k) + yt    <font color=green>(''add the overlapped output blocks'')</font>
        i = i+L
    '''end'''

==區塊長度的選擇==

當 ''x''[''n''] 的長度 ''N' '' 和 ''h''[''n''] 的長度 ''M'' 相差太大時（例如 ''M'' < log<sub>2</sub>''N' '' ），直接[[卷积|摺積]]（不透過[[圓周摺積]]和 [[快速傅里叶变换|FFT]] ）反而最快。而當 ''N' '' 和 ''M'' 差不多在同一個[[数量级|數量級]]時，不用分割，也就是只有一塊長度 ''L'' = ''N' '' 的區塊去做 FFT 即可。而當 ''N' '' 比 ''M'' 大了不少，卻沒大太多時，區塊長度 ''L'' 就需要選擇。除了與 ''N' '' 和 ''M'' 相關以外，也要考慮當兩者相除有餘數時，剩下一小段的輸入可能會造成浪費。

==相關條目==

*[[卷积#定义|離散摺積]]
*[[圓周摺積]]
*[[快速傅立葉變換]]
*[[重疊-儲存之摺積法]]

==參考文獻==
*{{Cite book
 | author=Rabiner, Lawrence R.; Gold, Bernard
 | authorlink=
 | coauthors=
 | title=Theory and application of digital signal processing
 | url=https://archive.org/details/theoryapplicatio00rabi
 | date=1975
 | publisher=Prentice-Hall
 | location=Englewood Cliffs, N.J.
 | isbn=0-13-914101-4
 | pages=pp 65-67
}}
*{{citation|author=Helms, H.|title=Fast Fourier transform method of computing difference equations and simulating filters|journal=IEEE Transactions on Audio and Electroacoustics|volume=15(2)|year=1967|pages=85-90|url=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1161905|accessdate=2008-06-23|archive-date=2019-06-30|archive-url=https://web.archive.org/web/20190630230826/https://ieeexplore.ieee.org/document/1161905/?arnumber=1161905|dead-url=no}}

==外部連結==

* [http://www.mathworks.com Matlab] {{Wayback|url=http://www.mathworks.com/ |date=20210505033254 }} 使用 Matlab 函數 fftfilt.m 實作重疊-相加之摺積法
*DSP class Fall 2005 [http://www.uta.edu/faculty/zhouwang/teaching/DSP05/handouts/Lecture08.pdf Lecture08]{{dead link|date=2018年4月 |bot=InternetArchiveBot |fix-attempted=yes }} at The University of Texas at Arlington

[[Category:数字信号处理]]
[[Category:傅里叶分析]]
[[Category:数值分析]]