Bioelectric signals and processing .pptx

Bioelectric Signals and Processing

1. Bioelectric signals and processing FFT Decimation in frequency

2. Contents Fourier Transform Fast Fourier Transform (FFT) FFT Algorithms FFT Decimation in Frequency

3. Fourier transform A fourier transform is an useful analytical tool that is important for many fields of application in the digital signal processing. In describing the properties of the fourier transform and inverse fourier transform, it is quite convenient to use the concept of time and frequency. In image processing applications it plays a critical role.

4. Fast fourier transform Fast fourier transform proposed by Cooley and Tukey in 1965. The fast fourier transform is a highly efficient procedure for computing the DFT of a finite series and requires less number of computations than that of direct evaluation of DFT. The FFT is based on decomposition and breaking the transform into smaller transforms and combining them to get the total transform.

5. Discrete Fourier Transform The DFT pair was given as Baseline for computational complexity: Each DFT coefficient requires N complex multiplications and N-1 complex additions. All N DFT coefficients require N 2 complex multiplications and N(N-1) complex additions.

6. What is FFT? The fast fourier is an algorithm used to compute the DFT. It makes use of the symmetry and periodicity properties of twiddle factor w N to effectively reduce the DFT computation time. It is based on the fundamental principle of decomposing the computation of DFT of a sequence of length N into successively smaller DFT.

7. Symmetry and Periodicity Symmetry Periodicity

8. FFT algorithm provides speed increase factors, when compared with direct computation of the DFT, of approximately 64 and 205 for 256 point and 1024 point transforms respectively. The number of multiplications and additions required to compute N-point DFT using radix-2 FFT are Nlog 2 N and N/2 log 2 N respectively.

9. Example: The number of complex multiplications required using direct computation is N 2 =64 2 =4096 The number of complex multiplications required using FFT is N/2log 2 N=64/2log 2 64=192 Speed improvement factor =4096/192= 21.33.

10. FFT Algorithms : There are basically two types of FFT algorithms: Decimation in time. Decimation in Frequency.

11. Decimation In Frequency: It is a popular form of FFT algorithm. In this the output sequence x(k) is divided into smaller and smaller subsequences, that is why the name decimation in frequency. Initially the input sequence x(n) is divided into two sequences x1(n) and x2(n) consisting of the first n/2 samples of x(n) and the last n/2 samples of x(n) respectively.

12. Radix-2 DIF- FFT Algorithm Algorithm Principle: To divide N-point sequence x(n) into two N/2-point sequence The Former N/2 point The Latter N/2 point

13. 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 0 1 2 3 butterfly computation 0 1 2 3 0 1 2 3 butterfly computation butterfly computation 0 1 0 1 0 1 0 1 butterfly butterfly butterfly butterfly 4 2 6 1 5 3 7 1 1 1 1

14. To compute the DFT of N-point sequence x(n)

15. Radix-2 DIF- FFT Algorithm To separate the even and odd numbered samples of X(k)

16. Radix-2 DIF- FFT Algorithm

17. Radix-2 DIF- FFT Algorithm Butterfly computation flow graph There are 1 complex multiplication and 2 complex additions

18. N/2-point DFT N/2-point DFT For

19. for

20. Radix-2 DIF- FFT Algorithm The comparison of DIT and DIF The order of samples DIT-FFT : the input is bit- reversed order and the output is natural order DIF-FFT : the input is natural order and the output is bit- reversed order The butterfly computation DIT-FFT : multiplication is done before additions DIF-FFT : multiplication is done after additions

21. Radix-2 DIF- FFT Algorithm Both DIT-FFT and DIF-FFT have the identical computation complexity. i.e. for N=2 L , there are total L stages and each has N/2 butterfly computation. Each butterfly computation has 1 multiplication and 2 additions. Both DIT-FFT and DIF-FFT have the characteristic of in-place computation. A DIT-FFT flow graph can be transposed to a DIF-FFT flow graph and vice versa.

22. THANKYOU