In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

1 Crore+ students have signed up on EduRev. Have you?

This efficient use of memory is important for designing fast hardware to calculate the FFT. The term in-place computation is used to describe this memory usage.

Decimation in Time Sequence

In this structure, we represent all the points in binary format i.e. in 0 and 1. Then, we reverse those structures. The sequence we get after that is known as bit reversal sequence. This is also known as decimation in time sequence. In-place computation of an eight-point DFT is shown in a tabular format as shown below −

 

POINTSBINARY FORMATREVERSALEQUIVALENT POINTS
00000000
10011004
20100102
30111106
41000011
51011015
61100113
71111117

 

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

Decimation in Frequency Sequence

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

Let the sequence be  In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE) 

We will group two points into one group, initially. Mathematically, this sequence can be written as;

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

Now let us make one group of sequence number 0 to 3 and another group of sequence 4 to 7. Now, mathematically this can be shown as;

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

Let us replace n by r, where r = 0, 1 , 2….(N/2-1). Mathematically,

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

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

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

We can further break it into two more parts, which means instead of breaking them as 4-point sequence, we can break them into 2-point sequence.

The document In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE) is a part of the Electronics and Communication Engineering (ECE) Course Signals and Systems.
All you need of Electronics and Communication Engineering (ECE) at this link: Electronics and Communication Engineering (ECE)
32 videos|76 docs|63 tests
Download as PDF

Download free EduRev App

Track your progress, build streaks, highlight & save important lessons and more!

Related Searches

Exam

,

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

,

Important questions

,

Previous Year Questions with Solutions

,

Sample Paper

,

practice quizzes

,

Extra Questions

,

Free

,

Summary

,

pdf

,

shortcuts and tricks

,

Viva Questions

,

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

,

study material

,

Semester Notes

,

past year papers

,

ppt

,

mock tests for examination

,

In-Place Computation - Notes | Study Signals and Systems - Electronics and Communication Engineering (ECE)

,

Objective type Questions

,

MCQs

,

video lectures

;