Scribd Logo
Upload

Welcome to Scribd!

  • 683 views

    Dif FFT

    Uploaded by

    Gayathri Rajendran
    The document discusses the decimation-in-frequency (DIF) fast Fourier transform (FFT) algorithm. DIF-FFT decomposes an N-point discrete Fourier transform (DFT) into recursive N/2-point DFTs by separating the even and odd frequency indexes. This results in a flowgraph structure with input in natural order and output in bit-reversed order. The inverse DFT can be computed using the FFT by conjugating the input, running the forward FFT, and conjugating and normalizing the output. Non-power-of-two DFT sizes can also be handled by factorizing N.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Dif FFT

    Uploaded by

    Gayathri Rajendran
    683 views16 pages
    The document discusses the decimation-in-frequency (DIF) fast Fourier transform (FFT) algorithm. DIF-FFT decomposes an N-point discrete Fourier transform (DFT) into recursive N/2-point DFTs by separating the even and odd frequency indexes. This results in a flowgraph structure with input in natural order and output in bit-reversed order. The inverse DFT can be computed using the FFT by conjugating the input, running the forward FFT, and conjugating and normalizing the output. Non-power-of-two DFT sizes can also be handled by factorizing N.

    Original Title

    DIF-FFT

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses the decimation-in-frequency (DIF) fast Fourier transform (FFT) algorithm. DIF-FFT decomposes an N-point discrete Fourier transform (DFT) into recursive N/2-point DFTs by separating the even and odd frequency indexes. This results in a flowgraph structure with input in natural order and output in bit-reversed order. The inverse DFT can be computed using the FFT by conjugating the input, running the forward FFT, and conjugating and normalizing the output. Non-power-of-two DFT sizes can also be handled by factorizing N.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    683 views16 pages

    Dif FFT

    Uploaded by

    Gayathri Rajendran
    The document discusses the decimation-in-frequency (DIF) fast Fourier transform (FFT) algorithm. DIF-FFT decomposes an N-point discrete Fourier transform (DFT) into recursive N/2-point DFTs by separating the even and odd frequency indexes. This results in a flowgraph structure with input in natural order and output in bit-reversed order. The inverse DFT can be computed using the FFT by conjugating the input, running the forward FFT, and conjugating and normalizing the output. Non-power-of-two DFT sizes can also be handled by factorizing N.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 16

    FFT using Decimation in frequency

    DIF-FFT

    Presentation by:
    S.KARTHIE
    Assistant Professor/ECE
    SSN College of Engineering
    Objective
    At the end of the session, students will be able
    to understand,

    • DIF-FFT algorithm

    • Computation of IDFT using FFT


    Decimation-In-Frequency FFT Algorithm

    • Introduction: Decimation in
    frequency is an alternate way of
    developing the FFT algorithm

    • It is different from decimation in


    time in its development, although it
    leads to a very similar structure
    Decimation-In-Frequency FFT Algorithm

    • Consider the original N −1


    X[k] = ∑ x[n]WNnk
    DFT equation …. n=0

    • Separate the first half and the second half


    of time samples:
    ( N / 2)−1 N −1
    X[k] = ∑ x[n]WNnk + ∑ x[n]WNnk
    n=0 n= N / 2
    ( N / 2)−1 ( N / 2)−1
    = ∑ x[n]WNnk + WN( N / 2)k ∑ x[n + ( N / 2)]WNnk
    n=0 n=0
    ( N / 2)−1
    = ∑
    n=0
    [ ]
    x[n] + (−1)k x[n + ( N / 2)] WNnk

    • Note that these are not N/2-point DFTs


    Decimation-In-Frequency FFT Algorithm
    (N / 2)−1
    X[k] = ∑ [x[n] + (−1) k x[n + ( N / 2)]]WNnk
    n=0

    • For k even, let k = 2r


    (N / 2)−1 ( N / 2)−1
    X[k] = ∑ [x[n] + (−1) 2r
    ]
    x[n + ( N / 2)] WNn2r = ∑ [x[n] + x[n + ( N / 2)]]WNnr/ 2
    n=0 n=0

    • For k odd, let k = 2r +1


    ( N / 2)−1
    X[k] = ∑
    n=0
    [ ]
    x[n] + (−1)2r (−1)x[n + (N / 2)] WNn(2r+1)

    ( N / 2)−1
    = ∑ [x[n] − x[n + (N / 2)]]WNn WNnr/ 2
    n=0
    • These expressions are the N/2-point DFTs
    of x[n] + x[n + ( N / 2)] and [x[n] − x[n + ( N / 2)]]WNn
    Decimation-In-Frequency FFT Algorithm

    • Split the DFT equation into even and odd frequency indexes
    N −1 N / 2 −1 N −1
    X [ 2r ] = ∑ x[n]W n 2r
    N = ∑ x[n]W n 2r
    N + ∑ x[n]WNn 2 r
    n =0 n =0 n= N / 2

    • Substitute variables to get


    N / 2 −1 N / 2 −1 N / 2 −1
    X [ 2r ] = ∑
    n =0
    x[n]Wn 2r
    N + ∑
    n =0
    x[n + N / 2]WN ( n+ N / 2)2 r
    = ∑ ( x[n] + x[n + N / 2])W
    n =0
    nr
    N /2

    • Similarly for odd-numbered frequencies


    N / 2 −1
    X [ 2r + 1] = ∑ ( x[n] − x[n + N / 2])W
    n =0
    n( 2 r +1)
    N /2

    6
    Decimation-In-Frequency FFT Algorithm
    Decimation-In-Frequency FFT Algorithm
    Continuing by decomposing the odd and even output points we
    obtain
    Decimation-In-Frequency FFT Algorithm

    … and replacing the N/4-point DFTs by butterflys we obtain


    Decimation-In-Frequency FFT Algorithm

    • Final flow graph for 8-point decimation in frequency


    • DIF structure with input natural, output bit reversed

    10
    Using FFTs for inverse DFTs
    • We’ve always been talking about forward
    DFTs in our discussion about FFTs …. what
    about the inverse FFT?
    N −1 N −1
    1
    x[n] = N ∑ X[k]WN ; X[k] = ∑ x[n]WNkn
    −kn
    k =0 n=0
    • One way to modify FFT algorithm for the
    inverse DFT computation is:
    – Replace WNk by WN− k wherever it appears
    – Multiply final output by 1/ N

    • This method has the disadvantage that it


    requires modifying the internal code in the
    FFT subroutine
    A better way to modify FFT code for IDFT
    • Taking the complex conjugate of both sides of
    the IDFT equation:
    *
    N −1
     N −1

    x * [n] = N1 ∑ X * [k ]W Nkn ; or x[n] = N1 ∑ X * [k ]W Nkn 
    k =0  k =0 
    • This suggests that we can modify the FFT
    algorithm for the inverse DFT computation by the
    following:
    – Complex conjugate the input DFT coefficients
    – Compute the forward FFT
    – Complex conjugate the output of the FFT and
    multiply by 1/N
    – This method has the advantage that the
    internal FFT code is undisturbed; it is widely
    used.
    FFT structures for other DFT sizes

    • Can we do anything when the DFT


    size N is not an integer power of 2
    (the non-radix 2 case)?

    • Yes! Consider a value of N that is


    not a power of 2, but that still is
    highly factorable …
    Summary
    The DIF FFT is the transpose of the DIT FFT

    • To obtain flowgraph transposes:


    – Reverse direction of flowgraph arrows
    – Interchange input(s) and output(s)

    • DIT butterfly: DIF butterfly:

    • Comment:
    – We will revisit transposed forms again in our discussion of
    filter implementation
    Summary
    The DIF FFT is the transpose of the DIT FFT
    • Comparing DIT and DIF structures:
    DIT FFT structure: DIF FFT
    structure:

    • Alternate forms for DIF FFTs are


    similar to those of DIT FFTs
    Thank You

    You might also like