Algorithm (OA for linear convolution) Evaluate the best value of N and L H = FFT(h,N) (zero-padded FFT) 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 (add the overlapped output blocks) i = i+L end
區塊長度的選擇
當 x[n] 的長度 N' 和 h[n] 的長度 M 相差太大時（例如 M < log2N' ），直接摺積（不透過圓周摺積和 FFT ）反而最快。而當 N' 和 M 差不多在同一個數量級時，不用分割，也就是只有一塊長度 L = N' 的區塊去做 FFT 即可。而當 N' 比 M 大了不少，卻沒大太多時，區塊長度 L 就需要選擇。除了與 N' 和 M 相關以外，也要考慮當兩者相除有餘數時，剩下一小段的輸入可能會造成浪費。
Rabiner, Lawrence R.; Gold, Bernard. Theory and application of digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall. 1975: pp 65–67. ISBN 0-13-914101-4. 引文格式1维护：冗余文本 (link)
Helms, H., Fast Fourier transform method of computing difference equations and simulating filters, IEEE Transactions on Audio and Electroacoustics, 1967, 15(2): 85–90 [2008-06-23], （原始内容于2019-06-30）
DSP class Fall 2005 Lecture08[永久失效連結] at The University of Texas at Arlington
行進 06, 2023
重疊, 相加之摺積法, overlap, method, 是一種區塊摺積, block, convolution, sectioned, convolution, 可以有效的計算一個很長的信號, 和一個, 濾波器, 的離散摺積, displaystyle, begin, aligned, star, stackrel, mathrm, infty, infty, cdot, cdot, aligned, 其中, 之外為零, 算出重疊的輸出區塊, 另一種區塊摺積的作法, 重疊, 儲存之摺積法則是將輸入區塊重疊, 目录. 重疊 相加之摺積法 Overlap add method 是一種區塊摺積 block convolution sectioned convolution 可以有效的計算一個很長的信號 x n 和一個 FIR 濾波器 h n 的離散摺積 y n x n h n d e f m h m x n m m 1 M h m x n m displaystyle begin aligned 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 aligned 其中 h m 在 1 M 之外為零 重疊 相加之摺積法算出重疊的輸出區塊 另一種區塊摺積的作法 重疊 儲存之摺積法則是將輸入區塊重疊 目录 1 算法 1 1 伪代码 2 區塊長度的選擇 3 相關條目 4 參考文獻 5 外部連結算法 编辑 图1 重叠 相加法 概念上 這個做法是選用一個較短的適當長度 L 來切割 x n 計算 x n 的子數列濾波後的結果 yk n 然後連接起來成為 y n 並考慮到一個長度 L displaystyle L 和長度 M displaystyle M 的有限長度離散信號 做摺積之後會成為長度 L M 1 displaystyle L M 1 的信號 x k n d e f x n k L n 1 2 L 0 otherwise displaystyle x k n stackrel mathrm def begin cases x n kL amp n 1 2 ldots L 0 amp textrm otherwise end cases 則 x n k x k n k L displaystyle x n sum k x k n kL 而因為摺積是線性非時變運算 所以 y n 可被表示為 y n k x k n k L h n k x k n k L h n k y k n k L displaystyle begin aligned y n left sum k x k n kL right star h n amp sum k left x k n kL star h n right amp sum k y k n kL end aligned 其中 y k n d e f x k n h n displaystyle y k n stackrel mathrm def x k n star h n 在 1 L M 1 之外為零 每個 yk n 長度 L M 1 displaystyle L M 1 以間隔 L displaystyle L 位移後相加 所以輸出是由互相重疊的區塊相加而成 因此稱為重疊 相加之摺積法 儘管一時看不出切割成區塊的好處為何 但考慮到對任何 N L M 1 displaystyle N geq L M 1 以上每段的摺積都等價於 x k n displaystyle x k n 和 h n displaystyle h n 做 N displaystyle N 點圓周摺積 不夠的部分補上零 zero padding 如此一來因為圓周摺積可以藉由圓周摺積定理 y k n IFFT FFT x k n FFT h n displaystyle y k n textrm IFFT left textrm FFT left x k n right cdot textrm FFT left h n right right 轉換成三次 N displaystyle N 點快速傅立葉變換和 N displaystyle N 次乘法 使原本每段 O N2 的運算量減少至 O N logN 速度大幅增加 伪代码 编辑 Algorithm OA for linear convolution Evaluate the best value of N and L H FFT h N zero padded FFT i 1 while i lt 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 add the overlapped output blocks i i L end區塊長度的選擇 编辑當 x n 的長度 N 和 h n 的長度 M 相差太大時 例如 M lt log2N 直接摺積 不透過圓周摺積和 FFT 反而最快 而當 N 和 M 差不多在同一個數量級時 不用分割 也就是只有一塊長度 L N 的區塊去做 FFT 即可 而當 N 比 M 大了不少 卻沒大太多時 區塊長度 L 就需要選擇 除了與 N 和 M 相關以外 也要考慮當兩者相除有餘數時 剩下一小段的輸入可能會造成浪費 相關條目 编辑離散摺積 圓周摺積 快速傅立葉變換 重疊 儲存之摺積法參考文獻 编辑Rabiner Lawrence R Gold Bernard Theory and application of digital signal processing Englewood Cliffs N J Prentice Hall 1975 pp 65 67 ISBN 0 13 914101 4 引文格式1维护 冗余文本 link Helms H Fast Fourier transform method of computing difference equations and simulating filters IEEE Transactions on Audio and Electroacoustics 1967 15 2 85 90 2008 06 23 原始内容存档于2019 06 30 外部連結 编辑Matlab 页面存档备份 存于互联网档案馆 使用 Matlab 函數 fftfilt m 實作重疊 相加之摺積法 DSP class Fall 2005 Lecture08 永久失效連結 at The University of Texas at Arlington 取自 https zh wikipedia org w index php title 重疊 相加之摺積法 amp oldid 70496989, 维基百科，wiki，书籍，书籍，图书馆，
