Exp-3 Fast Fourier Transform

-

Fast Fourier Transform(FFT)

A  Fast Fourier transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components. FFT is manually verified and performed using flowgraphs.




  • FFT is much faster than DFT and more efficient as it requires less number of real and complex additions and multiplication.
  • The computation is considerably reduced from M2N2 to MNlogMlogN

Comments

  1. Gopala15 May 2018 at 06:59

    Why would one use FFT over DFT?

    ReplyDelete
  2. Unknown15 May 2018 at 07:01

    Besides FFT, which are the other methods?

    ReplyDelete
  3. Rutwik Pandit15 May 2018 at 07:05

    Why is FFT faster than DFT

    ReplyDelete
    Replies
    1. Unknown15 May 2018 at 08:39

      If N samples are present, DFT takes N^2 operations while FFT takes only N*log(N) operations. Hence FFT is much faster than DFT.

      Delete
  4. Tejveer Singh15 May 2018 at 07:15

    Why do we have to reduce the computation to MNlogMlogN form ?

    ReplyDelete
    Replies
    1. Unknown15 May 2018 at 08:40

      The lesser the number of computations, the higher is the speed.

      Delete
  5. Unknown15 May 2018 at 07:32

    FFT seems difficult at first but what a wonderful tool!

    ReplyDelete
  6. Koumudhi Deshpande15 May 2018 at 07:50

    This comment has been removed by the author.

    ReplyDelete
  7. Anonymous15 May 2018 at 07:53

    It's also interesting to follow work on hardware optimization for efficient FFT in embedded systems. This is crucial in making FFT accessible to small handheld devices making the use of more sophisticated modulation schemes possible for wireless communication.

    ReplyDelete
  8. Koumudhi Deshpande15 May 2018 at 07:56

    The increase in the efficiency of time complexity by using FFT is so fascinating!

    ReplyDelete
  9. Unknown15 May 2018 at 09:02

    What is the difference between DIT FFT and DIF FFT ?

    ReplyDelete
    Replies
    1. Unknown15 May 2018 at 21:57

      In the case of decimation in time , we split(decimate) the time domain samples into even and odd numbered ones , on the other hand we split the frequency samples into even and odd numbered ones.

      Both the algorithms have (N/2)log2(N) complex multiplications and Nlog2(N) complex additions. The difference is we give inputs in bit reversed order in case of DIT while we get frequency samples in bit reversed order in DIF.

      Delete

Post a Comment

Popular posts from this blog

Exp- 4 Filtering of Long Data Sequence using Overlap Add and Overlap Save method

-
Overlap Add and Overlap Save method are used for filtering long data sequences. Such a long data sequence would need a very high order FFT- which is not feasible and the process can only start after we've obtained the entire data sequence which leads to a delay. The long data sequence is broken into smaller parts and performed FFT analysis. It is then fitted with one another, the overlapped portion is discarded in Overlap Save Method whereas it is added in OAM to get required output sequence.
Read more

Exp-2 Discrete Fourier Transform

-
This practical really helped me understand DFT in a greater depth. It helped me connect the knowledge sir taught in the class, and aquire a greater understanding. In  mathematics , the  discrete Fourier transform  ( DFT ) converts a finite sequence of equally-spaced  samples  of a  function  into a same-length sequence of equally-spaced samples of the  discrete-time Fourier transform  (DTFT), which is a  complex-valued  function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. To understand DFT better, we've performed discrete Fourier transform of a 4 point sequence by coding it. What I learned in that experiment is: 1) Results by DFT are always periodic about the number of input values. 2)The spectrum is discrete from o to pi. 3)Upon zero-padding the input signal, the length of the input signal increased- which increases the frequency spacing. 4)As frequ...
Read more