Sectional Convolution - Discrete Fourier Transform | Signals and Systems - Electronics and Communication Engineering (ECE) PDF Download

Suppose, the input sequence x(n) of long duration is to be processed with a system having finite duration impulse response by convolving the two sequences. Since, the linear filtering performed via DFT involves operation on a fixed size data block, the input sequence is divided into different fixed size data block before processing.

The successive blocks are then processed one at a time and the results are combined to produce the net result.

As the convolution is performed by dividing the long input sequence into different fixed size sections, it is called sectioned convolution. A long input sequence is segmented to fixed size blocks, prior to FIR filter processing.

Two methods are used to evaluate the discrete convolution −

  • Overlap-save method

  • Overlap-add method

Overlap Save Method

Overlap–save is the traditional name for an efficient way to evaluate the discrete convolution between a very long signal x(n) and a finite impulse response (FIR) filter h(n). Given below are the steps of Overlap save method −

Let the length of input data block = N = L+M-1. Therefore, DFT and IDFT length = N. Each data block carries M-1 data points of previous block followed by L new data points to form a data sequence of length N = L+M-1.

  • First, N-point DFT is computed for each data block.

  • By appending (L-1) zeros, the impulse response of FIR filter is increased in length and N point DFT is calculated and stored.

  • Multiplication of two N-point DFTs H(k) and Xm(k) : Y′m(k) = H(k).Xm(k), where K=0,1,2,…N-1

  • Then, IDFT[Y′m((k)] = y′((n) = [y′m(0), y′m(1), y′m(2),.......y′m(M-1), y′m(M),.......y′m(N-1)]

    (here, N-1 = L+M-2)

  • First M-1 points are corrupted due to aliasing and hence, they are discarded because the data record is of length N.

  • The last L points are exactly same as a result of convolution, so

    y′m (n) = ym(n) where n = M, M+1,….N-1

  • To avoid aliasing, the last M-1 elements of each data record are saved and these points carry forward to the subsequent record and become 1st M-1 elements.
    Sectional Convolution - Discrete Fourier Transform | Signals and Systems - Electronics and Communication Engineering (ECE)

  • Result of IDFT, where first M-1 Points are avoided, to nullify aliasing and remaining L points constitute desired result as that of a linear convolution

Overlap Add Method

Given below are the steps to find out the discrete convolution using Overlap method −

Let the input data block size be L. Therefore, the size of DFT and IDFT: N = L+M-1

  • Each data block is appended with M-1 zeros to the last.

  • Compute N-point DFT.
    Sectional Convolution - Discrete Fourier Transform | Signals and Systems - Electronics and Communication Engineering (ECE)

  • Two N-point DFTs are multiplied: Ym(k) = H(k).Xm(k), where k = 0,,1,2,….,N-1

  • IDFT [Ym(k)] produces blocks of length N which are not affected by aliasing as the size of DFT is N = L+M-1 and increased lengths of the sequences to N-points by appending M-1 zeros to each block.

  • Last M-1 points of each block must be overlapped and added to first M-1 points of the succeeding block.

    (reason: Each data block terminates with M-1 zeros)

    Hence, this method is known Overlap-add method. Thus, we get −

    y(n) = {y1(0), y1(1), y1(2), ... .., y1(L-1), y1(L)+y2(0), y1(L+1)+y2(1), ... ... .., y1(N-1)+y2(M-1),y2(M), ... ... ... ... ... }

The document Sectional Convolution - Discrete Fourier Transform | 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

Top Courses for Electronics and Communication Engineering (ECE)

FAQs on Sectional Convolution - Discrete Fourier Transform - Signals and Systems - Electronics and Communication Engineering (ECE)

1. What is sectional convolution?
Ans. Sectional convolution is a technique used in signal processing to divide a long signal into smaller sections and perform convolution on each section separately. This allows for efficient computation of convolution by reducing the overall complexity.
2. What is the Discrete Fourier Transform (DFT)?
Ans. The Discrete Fourier Transform (DFT) is a mathematical transformation that converts a finite sequence of discrete samples into a sequence of complex numbers representing the frequency components of the original signal. It is widely used in signal processing to analyze and manipulate signals in the frequency domain.
3. How is the Discrete Fourier Transform related to sectional convolution?
Ans. The Discrete Fourier Transform is used in sectional convolution to efficiently compute the convolution of large signals. By decomposing the signal into smaller sections, the convolution can be performed on each section separately using the DFT. This reduces the computational complexity compared to convolving the entire signal directly.
4. What are the advantages of using sectional convolution with the Discrete Fourier Transform?
Ans. Sectional convolution with the Discrete Fourier Transform offers several advantages. Firstly, it reduces the computational complexity by dividing the signal into smaller sections. This makes it more efficient to perform convolution on large signals. Additionally, it allows for parallel processing as each section can be convolved independently. Lastly, it provides a frequency-domain representation of the convolved signal, which can be useful for further analysis and processing.
5. Are there any limitations or drawbacks of using sectional convolution with the Discrete Fourier Transform?
Ans. While sectional convolution with the Discrete Fourier Transform offers many advantages, it also has some limitations. One limitation is the potential introduction of artifacts at the boundaries of the sections due to the division of the signal. This can affect the accuracy of the convolution result. Additionally, the choice of section size can impact the trade-off between computational efficiency and accuracy. Finding the optimal section size depends on the specific application and signal characteristics.
32 videos|76 docs|63 tests
Download as PDF
Explore Courses for Electronics and Communication Engineering (ECE) exam

Top Courses for Electronics and Communication Engineering (ECE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Summary

,

study material

,

Semester Notes

,

Previous Year Questions with Solutions

,

ppt

,

mock tests for examination

,

MCQs

,

past year papers

,

practice quizzes

,

Objective type Questions

,

Sectional Convolution - Discrete Fourier Transform | Signals and Systems - Electronics and Communication Engineering (ECE)

,

Important questions

,

Extra Questions

,

video lectures

,

Free

,

Sample Paper

,

pdf

,

shortcuts and tricks

,

Sectional Convolution - Discrete Fourier Transform | Signals and Systems - Electronics and Communication Engineering (ECE)

,

Sectional Convolution - Discrete Fourier Transform | Signals and Systems - Electronics and Communication Engineering (ECE)

,

Viva Questions

,

Exam

;