Scribd Logo
Upload

Welcome to Scribd!

  • 34 views

    DFT and Sampling Frequency

    Uploaded by

    Nguyen Anh Duc
    This document discusses the discrete Fourier transform (DFT) and fast Fourier transform (FFT). It explains that the DFT provides the amplitude spectrum of a discrete signal at discrete frequency points. The frequency resolution of the DFT is determined by the number of samples and sampling time. The FFT is an efficient algorithm for computing the DFT, breaking down an N-point DFT into multiple smaller DFTs to reduce the computation time from O(N^2) to O(NlogN).

    Copyright:

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

    DFT and Sampling Frequency

    Uploaded by

    Nguyen Anh Duc
    34 views3 pages
    This document discusses the discrete Fourier transform (DFT) and fast Fourier transform (FFT). It explains that the DFT provides the amplitude spectrum of a discrete signal at discrete frequency points. The frequency resolution of the DFT is determined by the number of samples and sampling time. The FFT is an efficient algorithm for computing the DFT, breaking down an N-point DFT into multiple smaller DFTs to reduce the computation time from O(N^2) to O(NlogN).

    Original Title

    DFT and sampling frequency

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses the discrete Fourier transform (DFT) and fast Fourier transform (FFT). It explains that the DFT provides the amplitude spectrum of a discrete signal at discrete frequency points. The frequency resolution of the DFT is determined by the number of samples and sampling time. The FFT is an efficient algorithm for computing the DFT, breaking down an N-point DFT into multiple smaller DFTs to reduce the computation time from O(N^2) to O(NlogN).

    Copyright:

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

    DFT and Sampling Frequency

    Uploaded by

    Nguyen Anh Duc
    This document discusses the discrete Fourier transform (DFT) and fast Fourier transform (FFT). It explains that the DFT provides the amplitude spectrum of a discrete signal at discrete frequency points. The frequency resolution of the DFT is determined by the number of samples and sampling time. The FFT is an efficient algorithm for computing the DFT, breaking down an N-point DFT into multiple smaller DFTs to reduce the computation time from O(N^2) to O(NlogN).

    Copyright:

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

    2.2.4. Discrete Fourier Transform and FFT http://s-mat-pcs.oulu.fi/~ssa/ESignals/sig2_2_4.

    htm

    Previous section

    2.2.4. Discrete Fourier Transform and FFT

    Often we have only (equally spaced) samples f(tk), tk = a + k(b-a)/N, k = 0, 1, ..., N of the signal f(t).
    Then f may be considered to be restricted to the measuring interval [a,b] so that outside of the interval f(t)
    0. Hence

    F(v) = f(t) e-j2 vtdt

    = f(t) e-j2 vtdt

    f(tk ) e-j2 vtk (tk+1-tk)

    = [(b-a)/N] f(tk ) e-j2 vtk

    = (v), v R.

    If a = 0, b = 1, then tk = k/N and we usually denote f(tk) = f(k) and (v) is evaluated at points n = 0, 1, ...,
    N-1.

    Then (v) gets the form

    1
    (n) = f(k) e-j2 kn/N, n = 0, 1, ..., N-1.
    N

    (n) is called an N-point discrete Fourier transform of f. (even in the general case (a,b))

    Obviously | (n)| = | (N-n)| .

    The inverse discrete Fourier transform (IDTF)

    (k) e j2 kn/N = f(n)

    gives the original values f(n), n = 0, 1, ..., N - 1, when (k) are the values of the discrete Fourier
    transform.

    Frequency Resolution

    Assume that the signal is sampled (at least) by the Nyquist frequency, the number of samples is N and that
    the sampling time is T0 seconds ( (a,b)=(0,T) ). Then the sampling interval is T = T0 /N, sampling
    frequency f s = 1/T and the highest frequency of the signal is (at most)

    1 N
    f max = = .
    2T 2T0

    The discrete Fourier transform (DFT) gives the values of the amplitude spectrum at the frequencies 1/T0

    1 of 3 12/14/2009 2:23 AM
    2.2.4. Discrete Fourier Transform and FFT http://s-mat-pcs.oulu.fi/~ssa/ESignals/sig2_2_4.htm

    ,2/T0 , ..., N / 2T0 - 1/T0 but also at N / 2T0 , N / 2T0 + 1/T0 , ..., N/T0 which, by the symmetry, can be
    obtained from the the first N values.

    The frequency resolution of the amplitude spectrum, obtained by DFT, is

    1 1 fs
    f= = = .
    T0 NT N

    In practise DFT often is evaluated at M points, M > N, which means addition of frequency points ( f = 1
    / MT) i.e. interpolation or equivalently in time domain adding zeros after observations (zero padding)
    (increase of sampling time).
    Usually, the spectrum programs give the spectrum at points n = 0, 1, ..., N-1 instead of the true analog
    frequencies. The real analog frequencies can be found if the sampling interval T = T0 /N (or the sampling
    frequency 1/T = N/T0 ) is known. Sometimes the spectrum is given on [ -N / 2T0 , N / 2T0 ] or on [-½,½].

    Example 2.2.3: Finding the analog frequencies

    Fast Fourier Transform, FFT

    Denote W = e-j2 /N and choose N = 2L. Then

    1
    (n) = f(k) Wkn, n = 0, 1, ... , N-1,
    N
    1
    = f(k) Wkn + f(k + N/2) W (k + N/2)n
    N
    1
    = f(k) + f(k + N/2) W nN/2 Wkn
    N

    Since

    1, when n = 2l
    W nN/2 = e-j n = cos n = (-1)n =
    -1, when n = 2l + 1

    is

    1
    (2l) = f(k) + f(k + N/2) W k2l = ½ (l)
    N

    and

    1
    (2l+1) = f(k) - f(k + N/2) W k W k2l = ½ (l)
    N

    where

    1
    (l) = f(k) - f(k + N/2) e-j2 /(N/2) kl
    N/2

    2 of 3 12/14/2009 2:23 AM
    2.2.4. Discrete Fourier Transform and FFT http://s-mat-pcs.oulu.fi/~ssa/ESignals/sig2_2_4.htm

    is the N/2-point DFT of the signal g(k) = f(k) + f(k + N/2) and

    1
    (l) = f(k) - f(k + N/2) e-j2 /(N/2) kl
    N/2

    is the N/2-point DFT of the signal h(k) = Wk [f(k) - f(k + N/2)]. Since N/4 is an integer, ja can further
    be divided into two N/4-point DFT etc. until in the last stage N 1-point transforms are calculated (N = 2L).
    The number of arithmetic operations LN = N log2 N.

    Problems: P18, P19, P20, P21, P24


    Previous section
    Next section
    Contents

    3 of 3 12/14/2009 2:23 AM

    You might also like