Scribd Logo
Upload

Welcome to Scribd!

  • 165 views

    Unit 4 - Digital Signal Processing - WWW - Rgpvnotes.in

    Uploaded by

    Vivek jha
    The document discusses efficient computation of the discrete Fourier transform (DFT) using Fast Fourier Transform (FFT) algorithms. [1] It describes radix-2 FFT algorithms including decimation in time (DITFFT) and decimation in frequency (DIFFFT). [2] DITFFT decomposes the input sequence into even and odd numbered samples, while DIFFFT decomposes the output sequence. [3] The document also discusses decomposition of DFT computation for composite values of N.

    Copyright:

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

    Unit 4 - Digital Signal Processing - WWW - Rgpvnotes.in

    Uploaded by

    Vivek jha
    165 views7 pages
    The document discusses efficient computation of the discrete Fourier transform (DFT) using Fast Fourier Transform (FFT) algorithms. [1] It describes radix-2 FFT algorithms including decimation in time (DITFFT) and decimation in frequency (DIFFFT). [2] DITFFT decomposes the input sequence into even and odd numbered samples, while DIFFFT decomposes the output sequence. [3] The document also discusses decomposition of DFT computation for composite values of N.

    Original Description:

    dsp

    Original Title

    Unit 4 - Digital Signal Processing - Www.rgpvnotes.in

    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 efficient computation of the discrete Fourier transform (DFT) using Fast Fourier Transform (FFT) algorithms. [1] It describes radix-2 FFT algorithms including decimation in time (DITFFT) and decimation in frequency (DIFFFT). [2] DITFFT decomposes the input sequence into even and odd numbered samples, while DIFFFT decomposes the output sequence. [3] The document also discusses decomposition of DFT computation for composite values of N.

    Copyright:

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

    Unit 4 - Digital Signal Processing - WWW - Rgpvnotes.in

    Uploaded by

    Vivek jha
    The document discusses efficient computation of the discrete Fourier transform (DFT) using Fast Fourier Transform (FFT) algorithms. [1] It describes radix-2 FFT algorithms including decimation in time (DITFFT) and decimation in frequency (DIFFFT). [2] DITFFT decomposes the input sequence into even and odd numbered samples, while DIFFFT decomposes the output sequence. [3] The document also discusses decomposition of DFT computation for composite values of N.

    Copyright:

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

    Subject Name: Digital signal Processing

    Subject Code: EC-6002


    Semester: 6th
    Downloaded from be.rgpvnotes.in

    UNIT IV
    FFT algo ith s, deci atio i ti e algo ith , deci atio i f e ue c algo ith , deco positio fo N
    composite number.
    EFFICIENT COMPUTATION OF THE DFT

    FAST FOURIER TRANSFORM ALGORITHMS


    The Fast Fourier Transform is an algorithm that efficiently computes the discrete Fourier transform. The DFT of
    a sequence x (n) of length N is given by a complex valued sequence X (k).

    N-1
    Xk = ∑ � −2� �/� , 0 ≤ k ≤ N-1
    n=0
    Let WN be the complex valued phase factor, which is an Nth root of unity expressed by,
    WN = e j2 ∏ kn / N
    Hence X (k) becomes

    N-1
    Xk = ∑ WNnk, 0 ≤ k ≤ N-1
    n=0

    Similarly IDFT becomes


    N-1
    x(n) = 1/N ∑ X (k) WN-nk, 0 ≤ k ≤ N-1
    k=0

    There are three properties of twiddle factor WN


    1) Symmetry Property WNk+N/2 = -WNK
    2) Periodicity Property WNk+N = WNK

    RADIX-2 FFT
    1. DECIMATION IN TIME (DITFFT)
    N point sequence x (n) be decimated (broken) into two N/2 point data sequences f1(n) and f2(n). f1(n)
    contains even numbered samples of x(n) and f2(n) contains odd numbered samples of x(n). This decimated
    ope atio is called deci atio . “i ce it is do e o ti e do ai se ue ce it is called Decimation in Time .
    Thus
    N point DFT is given as

    Page no: 1 Follow us on facebook to get real-time updates from RGPV


    Downloaded from be.rgpvnotes.in

    Since the sequence x (n) is decimated into even numbered and odd numbered samples, thus
    X(k) = F1(k) + WNk F2(k)

    N-1
    Xk = ∑ WNnk, 0 ≤ k ≤ N-1
    n=0
    N/2-1 N/2-1
    X(k) = ∑ x (2m) WN2mk + ∑ x (2m+1) WNk(2m+1)
    m=0 m=0

    X(k+N/2) = F1(k) - WNk F2(k) (Symmetry property)


    Figure below shows that 8-point DFT can be computed directly and hence no reduction in computation.

    x(0) X 0)
    x(1) X 1)
    x(2) X (2)
    x(3) 8 Point DFT
    X (3)

    x(7) X (7)

    DIRECT COMPUTATION FOR N=8

    EXAMPLE:
    Given x (n) {0, 1, 2, 3}, find X (k) using DIT FFT algorithm.
    SOLUTION:
    Given N = 4
    WNk = e-j(2π/N k
    WN0 = 1 and WN1 = e-j(π/2 = -j
    Using DIT FFT algorithm, X(k) from the given sequence x(n) is shown in figure below Therefore, X(k) =
    { 6, -2+2j, -2, -2, -2-j2}

    x (0) = 0 2 X (0) = 6

    x (2) = 2 -2 X (2) = -2+J2

    W40=1 -1
    x (1) = 1 4 X (1) = -2

    W40=1 -1
    x (3) = 3 -2 X (3) = -2-J2

    W40=1 -1 W41=-j -1

    Page no: 2 Follow us on facebook to get real-time updates from RGPV


    Downloaded from be.rgpvnotes.in

    2. DECIMATION IN FREQUENCY (DIFFFT)


    I DIF N Poi t DFT is spli ted i to N/2 poi ts DFT s. X k is decimated with k even and k odd this is called
    Decimation in frequency(DIF FFT).
    N point DFT is given as

    N-1
    X k = ∑ x (n) WNkn
    n=0

    Since the sequence x(n) is splitted N/2 point samples, thus

    N/2-1 N/2-1
    Xk = ∑ WNkn + ∑ + N/2 WNk(n+N/2)
    m=0 m=0

    N/2-1 N/2-1
    Xk = ∑ WNkn + WNkN/2 + ∑ + N/2 WNkn
    m=0 m=0

    N/2-1 N/2-1
    Xk = ∑ WNkn + (-1) + ∑
    k
    + N/2 WNkn
    m=0 m=0

    N/2-1
    Xk = ∑ x (n) + (-1)k x(n + N/2) WNkn
    N/2-1 m=0
    Xk = ∑ x (n) + (-1)k x(n + N/2) WNkn
    m=0

    Let us split X(k) into even and odd numbered samples

    N/2-1
    X(2k) = ∑ x (n) + (-1)2k x(n + N/2) WN2kn
    m=0

    N/2-1
    X(2k) = ∑ x (n) + (-1)2k x(n + N/2) WN2kn
    m=0

    N/2-1
    X(2k+1) = ∑ x (n)+(-1)(2k+1) x(n + N/2) WN(2k+1)n
    m=0

    Page no: 3 Follow us on facebook to get real-time updates from RGPV


    Downloaded from be.rgpvnotes.in

    Fig 1 shows Butterfly computation in DIF FFT.

    a A= a + b

    b B= (a –b)WNr
    WNr
    Fig 1. BUTTERFLY COMPUTATION

    Fig 2 shows signal flow graph and stages for computation of radix-2 DIF FFT algorithm of N=4

    x(0)
    X(0)
    A

    x(1)
    X(1)
    w4 0
    B

    x(2)
    X(2)
    w4 0 C

    x(3)
    X(3)
    w4 1 D w4 0

    Fig 2. SIGNAL FLOW GRAPH FOR RADIX- DIF FFT N=4

    DECOMPOSITION FO‘ N COMPOSITE NUMBE‘:

    Page no: 4 Follow us on facebook to get real-time updates from RGPV


    Downloaded from be.rgpvnotes.in

    A composite or mixed radix FFT is used when N is a composite number which has more then one prime factor:
    for example N = 6 or 12. For these cases also, efficient DIT and DIF algorithms can be developed. Here we give
    a DIT FFT decomposition and hence N is written as a product of factors such as N = m 1, m2, ….. r.

    If N =m1N1 where N = m1, m2, ….. r, the input sequence x(n) can be separated into m1 subsequences of N1
    elements each. Then the DFT can be written as

    N1-1 N1-1 N1-1


    X(k = ∑ x (nm1) WNnm1k + ∑ x (nm1+1) WN(nm1+1)k + ……………∑ x (nm1+ m1-1) WN(nm1+ m1-1)k
    m=0 m=0 m=0

    DIFFERENCE BETWEEN DITFFT AND DIFFFT


    DIT FFT DIF FFT

    DITFFT algorithms are based upon DIFFFT algorithms are based upon decomposition
    decomposition of the input sequence into of the output sequence into smaller and smaller
    smaller and smaller sub sequences. sub sequences.

    In this input sequence x(n) is decimated into In this output sequence X(k) is considered to be
    even and odd numbered samples decimated into even and odd numbered samples

    Splitting operation is done on time domain Splitting operation is done on frequency domain
    sequence. sequence.

    In DIT FFT input sequence is in bit reversed In DIFFFT, input sequence is in natural order. And
    order while the output sequence is in natural DFT should be read in bit reversed order.
    order.

    Page no: 5 Follow us on facebook to get real-time updates from RGPV


    We hope you find these notes useful.
    You can get previous year question papers at
    https://qp.rgpvnotes.in .

    If you have any queries or you want to submit your


    study notes please write us at
    rgpvnotes.in@gmail.com

    You might also like