Scribd Logo
Upload

Welcome to Scribd!

  • 29 views

    Lec2nn 1

    Uploaded by

    VISHVENDRA CHAUHAN
    The document discusses the discrete Fourier transform (DFT) and its inverse (IDFT), their relationship to the discrete-time Fourier transform (DTFT), and how zero padding can be used. It also presents the matrix formulation of the DFT and introduces the fast Fourier transform (FFT) as a more efficient algorithm compared to direct computation of the DFT, with order of complexity reduced from O(N^2) to O(NlogN). The radix-2 FFT algorithm recursively decomposes the DFT computation.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lec2nn 1

    Uploaded by

    VISHVENDRA CHAUHAN
    29 views4 pages
    The document discusses the discrete Fourier transform (DFT) and its inverse (IDFT), their relationship to the discrete-time Fourier transform (DTFT), and how zero padding can be used. It also presents the matrix formulation of the DFT and introduces the fast Fourier transform (FFT) as a more efficient algorithm compared to direct computation of the DFT, with order of complexity reduced from O(N^2) to O(NlogN). The radix-2 FFT algorithm recursively decomposes the DFT computation.

    Original Title

    lec2nn-1

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses the discrete Fourier transform (DFT) and its inverse (IDFT), their relationship to the discrete-time Fourier transform (DTFT), and how zero padding can be used. It also presents the matrix formulation of the DFT and introduces the fast Fourier transform (FFT) as a more efficient algorithm compared to direct computation of the DFT, with order of complexity reduced from O(N^2) to O(NlogN). The radix-2 FFT algorithm recursively decomposes the DFT computation.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    29 views4 pages

    Lec2nn 1

    Uploaded by

    VISHVENDRA CHAUHAN
    The document discusses the discrete Fourier transform (DFT) and its inverse (IDFT), their relationship to the discrete-time Fourier transform (DTFT), and how zero padding can be used. It also presents the matrix formulation of the DFT and introduces the fast Fourier transform (FFT) as a more efficient algorithm compared to direct computation of the DFT, with order of complexity reduced from O(N^2) to O(NlogN). The radix-2 FFT algorithm recursively decomposes the DFT computation.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    DFT AND IDFT

    DFT:
    N
    X −1
    2πkn
    X(k) = x(n)e−j N k = 0, 1, . . . , N − 1
    n=0

    IDFT:
    N −1
    1 X 2πkn
    x(n) = X(k)ej N n = 0, 1, . . . , N − 1
    N
    k=0

    Digital Signal Processing 19 Lecture 2

    R ELATIONSHIP DFT ↔ DTFT

    X(k) = XN (f )⌋f = k
    N

    • Truncation of the signal to length N :



    x(n) n = 0, 1, . . . , N − 1
    xN (n) =
    0 otherwise

    • Sampling of the frequency axis:


    k
    f=
    N

    Digital Signal Processing 20 Lecture 2


    Z ERO PADDING

    If x(n) has length N and we want to evaluate

    N
    X −1
    XN (f ) = x(n)e−j2πf n
    n=0

    at M > N frequency values, calculate the M -point DFT of

    xZP (n) = {x(0), x(1), . . . , x(N − 1), 0, . . . , 0 }


    | {z }
    M −N zeros

    Gives
    XZP (k) = XN (f )⌋f = k
    M

    Digital Signal Processing 21 Lecture 2

    M ATRIX FORMULATION OF DFT

    DFT: X = Wx
    1 H
    IDFT: x= NW X
    j2π
    where (wN = e− N )
         
    x(0) X(0) 1 1 ··· 1
         
    1 N −1
     x(1)   X(1)   wN ··· wN 

       
    x= .. , X =  .. , W = 
     .. .. .. 

     .
      .
     . . . 
         
    N −1 .. (N −1)(N −1)
    x(N − 1) X(N − 1) 1 wN . wN
     −1
    1 1 1
    √ W is a unitary (orthogonal) matrix ⇐⇒ √ W = √ WH
    N N N

    Digital Signal Processing 22 Lecture 2


    FAST F OURIER T RANSFORM (FFT)

    FFT is a fast algorithm for computing the DFT.

    Direct computation Radix-2 FFT


    N
    Complex multiplications N2 2 log2 N
    Order of complexity O(N 2 ) O(N log2 N )
    6
    10

    5
    10

    Complex multiplications
    4
    10

    3
    10

    2
    10

    1
    10

    0
    10
    0 200 400 600 800 1000
    DFT size, N

    Digital Signal Processing 23 Lecture 2

    FFT (R ADIX -2) OBSERVATION

    • Length N sequence x(n), X(k) = FFTN [x(n)]


    – even elements: xe (m) = x(2m), Xe (k) = FFTN/2 [xe (m)]
    – odd elements: xo (m) = x(2m + 1), Xo (k) = FFTN/2 [xo (m)]
    k
    ⇒ X(k) = Xe (k) + e−j2π N Xo (k)

    Digital Signal Processing 24 Lecture 2


    R EMARKS , FFT

    • Several different kinds of FFTs! These provide trade-offs between


    multiplications, additions and memory usage.

    • Other important aspects are parallel computation, quantization effects and bit
    representation in each stage.

    • Renewed interest in FFT algorithms due to OFDM (Orthogonal Frequency


    Division Multiplexing) used in ADSL, Wireless LAN, 4G wireless (LTE) and
    digital radio broadcast (DAB).

    Digital Signal Processing 25 Lecture 2

    You might also like