Goseeko blog
  • Home
  • Engineering
    • Civil
    • Electronics
    • Computers
  • Science
    • Chemistry
    • Maths
    • Physics
  • Commerce
  • Arts
  • E-Learning
  • Career
  • Exams
  • Scholarships
  • Hiring News
  • Goseeko- Smart Study Material
@2021 - All Right Reserved. Designed and Developed by PenciDesign
Top Posts
Goseeko launches its own certifications for engineering and...
Online certifications which you can get in a...
What is Race around Condition?
What is a Development Plan ?
What is a Co-operative Bank?
What are the properties of Laser?
Top 5 Websites for Academic Research
What is regula-falsi method?
Top 10 Engineering YouTube Channels for Engineers
What is Lorentz Transformation?
What are Toposheets?
What is Pumping and its types?
Electronics

What is FFT?

by Team Goseeko 09/07/2021
written by Team Goseeko 09/07/2021 0 comment

Certain algorithms permit implementations of Discrete Fourier transform with considerable savings in computation time. These algorithms are known as Fast Fourier Transform. Also known as FFT.

FFT algorithms are based on the fundamental principle of decomposing the computation of DFT of sequence length into successively smaller discrete Fourier transforms.

They are basically two classes of FFT algorithms

  • Decimation in time
  • Decimation in frequency

Decimation-in-time algorithm FFT

This algorithm is known as Radix-2 DIT-FFT algorithm which means the number of output points N can be expressed as a power of 2 that is N = 2M  where M is an integer.

Let x(n) be a sequence where N is assumed to be a power of 2. Decimate or break this sequence into two sequences of length N/2 where one sequence consists of even-indexed values of x(n) and the other of odd-indexed values of x(n).

xe(n)  = x(2n)   n= 0,1,……….. N/2-1

xo(n) = x(2n+1)  n= 0,1,……….. N/2 -1

The N-point DFT of x(n) can be written as 

Separating x(n) into even and odd indexed values of x(n) we obtain 

W84 = -1

and W8 5 = – W 81

also W86 = – W82

W87 = – W83

G(0) – H(0) = x(4)

G(1)  – W 81 H(1) = x(5)

G(2) – W82 H(2) = x(6)

G(3) – W83  H(3) = x(7)

Let  us consider one example now, to understand the concept.

Consider the sequence x[n]={ 2,1,-1,-3,0,1,2,1}. Calculate the FFT.

Arrange the sequence as x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7)

Since N=8 find the values W8 0 to W 87

Apply the butterfly diagram to obtain the  values.

Decimation in Frequency

Apart from time sequence, we can represent an N-point sequence in frequency. Let us take a four-point sequence to understand it better.

Let the sequence be x[0],x[1],x[2],x[3]………..x[7]

Mathematically, this sequence will be as follows

Now let us make one group of sequence numbers 0 to 3 and another group of sequence 4 to 7. Now, mathematically this will be as follows

Let us replace n by r, where r = 0, 1 , 2….N/2−1. 

We take the first four points  x[0],x[1],x[2],x[3] initially, and try to represent them mathematically as follows –

Interested in learning about similar topics? Here are a few hand-picked blogs for you!

  • Types of UPS
  • Flip-Flops in sequential circuits
  • What is PLA?
  • What is SMPS?
  • Working of Stepper Motor

Share
0
FacebookTwitterPinterestLinkedinTumblr
previous post
What is z-Transform?
next post
What is Huffman Coding?

You may also like

What is Digital to Analog Converter?

16/05/2022

What is the CB Hybrid Model?

05/05/2022

What is Block Diagram of TV Communication?

05/05/2022

What is Minimum Mode Configuration of 8086?

05/05/2022

What is Boolean Algebra?

25/04/2022

What are CE CB CC transistor configurations?

25/04/2022

What is the Superposition Theorem?

20/04/2022

What is Norton’s Theorem?

20/04/2022

What is the Concept of data communication on...

20/04/2022

How to design a Synchronous counter?

20/04/2022

Leave a Comment Cancel Reply

Save my name, email, and website in this browser for the next time I comment.

Keep in touch

Facebook Twitter Instagram Youtube

Popular Posts

  • 1

    What is Race around Condition?

    03/08/2021
  • 2

    What is a Development Plan ?

    02/08/2021
  • 3

    What is a Co-operative Bank?

    03/08/2021
  • 4

    What are the properties of Laser?

    02/07/2021
  • 5

    Top 5 Websites for Academic Research

    11/07/2021
  • 6

    What is regula-falsi method?

    03/08/2021
  • 7

    Top 10 Engineering YouTube Channels for Engineers

    10/07/2021
  • 8

    What is Lorentz Transformation?

    02/07/2021
  • 9

    What are Toposheets?

    07/07/2021
  • 10

    What is Pumping and its types?

    03/08/2021

Categories

  • Arts
  • Career
  • Chemistry
  • Civil
  • Commerce
  • Computers
  • E-Learning
  • Electronics
  • Engineering
  • Exams
  • Hiring News
  • Maths
  • Physics
  • Scholarships
  • Uncategorized

Read alsox

What is Block Diagram of TV...

05/05/2022

What is Delta Modulation?

27/09/2021

What is the Wein bridge oscillator?

19/01/2022