
_START_ARTICLE_
重疊-儲存之摺積法
_START_SECTION_
准代码
_START_PARAGRAPH_
(Overlap-save algorithm for linear convolution)_NEWLINE_   //////// revised by fantastic ////////_NEWLINE_   N = length(x), M = length(h)_NEWLINE_   O = M – 1;   // overlap length must be M-1_NEWLINE_   L = M;       // >=1 is OK_NEWLINE_   P = O + L;_NEWLINE_   H = FFT(h, P);       // just calc once_NEWLINE_   idx = - (O - 1);     // starting index which is offset M-1 in matlab_NEWLINE_   while (idx <= N)_NEWLINE_       i1 = max(1, idx);        // must be >= 1_NEWLINE_       i2 = min(N, idx+P-1);    // must be <= N_NEWLINE_       yt = IFFT( FFT(x(i1:i2), P).*H, P );_NEWLINE_       y(idx:idx+P-M) = yt(M:P);        // discard first M-1 values and concatenate the remaining_NEWLINE_       idx = idx + L;_NEWLINE_   end_NEWLINE_   y = y(1:M+N-1);      // the first M+N-1 values are the convolution result
_START_SECTION_
区块长度的选择
_START_PARAGRAPH_
当 x[n] 的长度N' 和 h[n] 的长度M 相差太大时（例如 M < log₂N' ），直接卷积（不通过循环卷积和 FFT ）反而最快。而当N' 和 M 差不多在同一个数量级时，不用分区，也就是只有一块长度L = N' 的区块去做FFT 即可。而当N' 比 M 大了不少，却没大太多时，区块长度L 就需要选择。除了与N' 和 M 相关以外，也要考虑当两者相除有余数时，剩下一小段的输入可能会造成浪费。