Overlap–save method

In <a href="/facts/Signal_processing/Npaja6zb">signal processing</a>, overlap–save is the traditional name for an efficient way to evaluate the <a href="/facts/Convolution/PVPrdz9J">discrete convolution</a> between a very long signal 
 
 
 
 x
 [
 n
 ]
 
 
 {\displaystyle x[n]}
 
 and a <a href="/facts/Finite_impulse_response/5u4Gaqcb">finite impulse response</a> (FIR) filter 
 
 
 
 h
 [
 n
 ]
 
 
 {\displaystyle h[n]}
 
:

<table><tbody><tr><td> y [ n ] = x [ n ] ∗ h [ n ]   ≜   ∑ m = − ∞ ∞ h [ m ] ⋅ x [ n − m ] = ∑ m = 1 M h [ m ] ⋅ x [ n − m ] , {\displaystyle y[n]=x[n]*h[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m],}    </td> <td></td> <td>Eq.1</td></tr></tbody></table>

where h[m] = 0 for m outside the region [1, M].
This article uses common abstract notations, such as 
 
 
 
 y
 (
 t
 )
 =
 x
 (
 t
 )
 ∗
 h
 (
 t
 )
 ,
 
 
 {\textstyle y(t)=x(t)*h(t),}
 
 or 
 
 
 
 y
 (
 t
 )
 =
 
 
 H
 
 
 {
 x
 (
 t
 )
 }
 ,
 
 
 {\textstyle y(t)={\mathcal {H}}\{x(t)\},}
 
 in which it is understood that the functions should be thought of in their totality, rather than at specific instants 
 
 
 
 t
 
 
 {\textstyle t}
 
 (see <a href="/facts/Convolution/PVPrdz9J">Convolution#Notation</a>).

The concept is to compute short segments of y[n] of an arbitrary length L, and concatenate the segments together. That requires longer input segments that overlap the next input segment. The overlapped data gets "saved" and used a second time. First we describe that process with just conventional convolution for each output segment. Then we describe how to replace that convolution with a more efficient method.
Consider a segment that begins at n = kL + M, for any integer k, and define:

x
          
            k
          
        
        [
        n
        ]
         
        ≜
        
          
            {
            
              
                
                  x
                  [
                  n
                  +
                  k
                  L
                  ]
                  ,
                
                
                  1
                  ≤
                  n
                  ≤
                  L
                  +
                  M
                  −
                  1
                
              
              
                
                  0
                  ,
                
                
                  
                    
                      otherwise
                    
                  
                  .
                
              
            
            
          
        
      
    
    {\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {otherwise}}.\end{cases}}}

y
          
            k
          
        
        [
        n
        ]
         
        ≜
         
        
          x
          
            k
          
        
        [
        n
        ]
        ∗
        h
        [
        n
        ]
        =
        
          ∑
          
            m
            =
            1
          
          
            M
          
        
        h
        [
        m
        ]
        ⋅
        
          x
          
            k
          
        
        [
        n
        −
        m
        ]
        .
      
    
    {\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-m].}

Then, for 
 
 
 
 k
 L
 +
 M
 +
 1
 ≤
 n
 ≤
 k
 L
 +
 L
 +
 M
 
 
 {\displaystyle kL+M+1\leq n\leq kL+L+M}
 
, and equivalently 
 
 
 
 M
 +
 1
 ≤
 n
 −
 k
 L
 ≤
 L
 +
 M
 
 
 {\displaystyle M+1\leq n-kL\leq L+M}
 
, we can write:

y
        [
        n
        ]
        =
        
          ∑
          
            m
            =
            1
          
          
            M
          
        
        h
        [
        m
        ]
        ⋅
        
          x
          
            k
          
        
        [
        n
        −
        k
        L
        −
        m
        ]
         
         
        ≜
         
         
        
          y
          
            k
          
        
        [
        n
        −
        k
        L
        ]
        .
      
    
    {\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].}

With the substitution 
 
 
 
 j
 =
 n
 −
 k
 L
 
 
 {\displaystyle j=n-kL}
 
, the task is reduced to computing 
 
 
 
 
 y
 
 k
 
 
 [
 j
 ]
 
 
 {\displaystyle y_{k}[j]}
 
 for 
 
 
 
 M
 +
 1
 ≤
 j
 ≤
 L
 +
 M
 
 
 {\displaystyle M+1\leq j\leq L+M}
 
. These steps are illustrated in the first 3 traces of Figure 1, except that the desired portion of the output (third trace) corresponds to 1  ≤  j  ≤  L.
If we periodically extend xk[n] with period N  ≥  L + M − 1, according to:

x
          
            k
            ,
            N
          
        
        [
        n
        ]
         
        ≜
         
        
          ∑
          
            ℓ
            =
            −
            ∞
          
          
            ∞
          
        
        
          x
          
            k
          
        
        [
        n
        −
        ℓ
        N
        ]
        ,
      
    
    {\displaystyle x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],}

the convolutions  
 
 
 
 (
 
 x
 
 k
 ,
 N
 
 
 )
 ∗
 h
 
 
 
 {\displaystyle (x_{k,N})*h\,}
 
  and  
 
 
 
 
 x
 
 k
 
 
 ∗
 h
 
 
 
 {\displaystyle x_{k}*h\,}
 
  are equivalent in the region 
 
 
 
 M
 +
 1
 ≤
 n
 ≤
 L
 +
 M
 
 
 {\displaystyle M+1\leq n\leq L+M}
 
. It is therefore sufficient to compute the N-point <a href="/facts/Circular_convolution/krbXy3LH">circular (or cyclic) convolution</a> of 
 
 
 
 
 x
 
 k
 
 
 [
 n
 ]
 
 
 
 {\displaystyle x_{k}[n]\,}
 
 with 
 
 
 
 h
 [
 n
 ]
 
 
 
 {\displaystyle h[n]\,}
 
  in the region [1, N].  The subregion [M + 1, L + M] is appended to the output stream, and the other values are discarded.  The advantage is that the circular convolution can be computed more efficiently than linear convolution, according to the <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">circular convolution theorem</a>:

<table><tbody><tr><td> y k [ n ]   =   IDFT N (   DFT N ( x k [ n ] ) ⋅   DFT N ( h [ n ] )   ) , {\displaystyle y_{k}[n]\ =\ \scriptstyle {\text{IDFT}}_{N}\displaystyle (\ \scriptstyle {\text{DFT}}_{N}\displaystyle (x_{k}[n])\cdot \ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])\ ),}    </td> <td></td> <td>Eq.2</td></tr></tbody></table>

where:

<ul><li>DFTN and IDFTN refer to the <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">Discrete Fourier transform</a> and its inverse, evaluated over N discrete points, and</li>
<li>L is customarily chosen such that N = L+M-1 is an integer power-of-2, and the transforms are implemented with the <a href="/facts/Fast_Fourier_transform/caT7UUCh">FFT</a> algorithm, for efficiency.</li>
<li>The leading and trailing edge-effects of circular convolution are overlapped and added, and subsequently discarded.</li></ul>

Overlap–save method open-in-new

Overlap–save method