Overlap–add method

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

<table><tbody><tr><td><p>                    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],}      </p></td> <td></td> <td>Eq.1</td></tr></tbody></table>

<p>where 
  
    
      
        h
        [
        m
        ]
        =
        0
      
    
    {\displaystyle h[m]=0}
  
 for 
  
    
      
        m
      
    
    {\displaystyle m}
  
 outside the region 
  
    
      
        [
        1
        ,
        M
        ]
        .
      
    
    {\displaystyle [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>).
</p>

<p>The concept is to divide the problem into multiple convolutions of 
  
    
      
        h
        [
        n
        ]
      
    
    {\displaystyle h[n]}
  
 with short segments of 
  
    
      
        x
        [
        n
        ]
      
    
    {\displaystyle x[n]}
  
:
</p>

x
          
            k
          
        
        [
        n
        ]
         
        ≜
         
        
          
            {
            
              
                
                  x
                  [
                  n
                  +
                  k
                  L
                  ]
                  ,
                
                
                  n
                  =
                  1
                  ,
                  2
                  ,
                  …
                  ,
                  L
                
              
              
                
                  0
                  ,
                
                
                  
                    otherwise
                  
                  ,
                
              
            
            
          
        
      
    
    {\displaystyle x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{otherwise}},\end{cases}}}

<p>where 
  
    
      
        L
      
    
    {\displaystyle L}
  
 is an arbitrary segment length.  Then:
</p>

x
        [
        n
        ]
        =
        
          ∑
          
            k
          
        
        
          x
          
            k
          
        
        [
        n
        −
        k
        L
        ]
        ,
        
      
    
    {\displaystyle x[n]=\sum _{k}x_{k}[n-kL],\,}

<p>and 
  
    
      
        y
        [
        n
        ]
      
    
    {\displaystyle y[n]}
  
 can be written as a sum of short convolutions:
</p>

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)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL],\end{aligned}}}

<p>where the linear convolution 
  
    
      
        
          y
          
            k
          
        
        [
        n
        ]
         
        ≜
         
        
          x
          
            k
          
        
        [
        n
        ]
        ∗
        h
        [
        n
        ]
        
      
    
    {\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]\,}
  
 is zero outside the region 
  
    
      
        [
        1
        ,
        L
        +
        M
        −
        1
        ]
        .
      
    
    {\displaystyle [1,L+M-1].}
  
 And for any parameter 
  
    
      
        N
        ≥
        L
        +
        M
        −
        1
        ,
        
      
    
    {\displaystyle N\geq L+M-1,\,}
  
 it is equivalent to the 
  
    
      
        N
      
    
    {\displaystyle N}
  
-point <a href="/facts/Circular_convolution/krbXy3LH">circular convolution</a> of 
  
    
      
        
          x
          
            k
          
        
        [
        n
        ]
        
      
    
    {\displaystyle x_{k}[n]\,}
  
 with 
  
    
      
        h
        [
        n
        ]
        
      
    
    {\displaystyle h[n]\,}
  
 in the region 
  
    
      
        [
        1
        ,
        N
        ]
        .
      
    
    {\displaystyle [1,N].}
  
  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>:
</p>

<table><tbody><tr><td><p>                              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])\ ),}      </p></td> <td></td> <td>Eq.2</td></tr></tbody></table>

<p>where:
</p>
<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
      
    
    {\displaystyle N}
  
 discrete points, and</li>
<li>
  
    
      
        L
      
    
    {\displaystyle L}
  
 is customarily chosen such that 
  
    
      
        N
        =
        L
        +
        M
        −
        1
      
    
    {\displaystyle 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></ul>

Overlap–add method open-in-new

Overlap–add method