際際滷

際際滷Share a Scribd company logo

Decimation in Time

S
SURAJ KUMAR SAINI

This document discusses the decimation-in-time (DIT) algorithm for computing the discrete Fourier transform (DFT) in a more efficient manner than directly calculating all N points. DIT works by splitting the input sequence into smaller sequences, computing smaller DFTs, and recombining the results. Specifically, it separates the input into even and odd samples, computes partial DFTs on each, and combines them using a "butterfly" structure. This structure implements each step of the algorithm with one multiplication, reducing the complexity from N^2 operations to N^2/2 + N operations. The document provides an example of an 8-point DFT computed using the DIT algorithm and butterfly structure.

1 of 13
Downloaded 26 times
Decimation-In-Time Suraj Kumar Saini ID: 2015KUEC2015 Department of Electronics and Communication Engineering Indian Institute of Information Technology Kota Suraj Kumar Saini (IIIT) DSP 1 / 13
Overview 1 Discrete Fourier Transform 2 Decimation-In-Time 3 Radix-2 DFT Algorithm 4 Butter鍖y Structure 5 Complexity in DIT 6 Inverse Discrete Fourier Transform Suraj Kumar Saini (IIIT) DSP 2 / 13
Discrete Fourier Transform The DFT pair was given as : X[k] = N1 n=0 x[n]ej(2/N)kn x[n] = 1 N N1 k=0 X[k]ej(2/N)kn Baseline for computational complexity: Each DFT coe鍖cient requires N complex multiplications N-1 complex additions All N DFT coe鍖cients require N2 complex multiplications N(N-1) complex additions Suraj Kumar Saini (IIIT) DSP 3 / 13
Continue... Most fast methods are based on symmetry properties Symmetry: W k N [N n] = W kn N = (W kn N ) Periodicity in n and k: W kn N = W k[n+N] N = W [k+N]n N Suraj Kumar Saini (IIIT) DSP 4 / 13
Decimation-In-Time DIT algorithm is used to calculate the DFT of a N-point sequence. First step of process of decimation is splitting a sequence in smaller sequences. A sequence of 16 numbers can be splitted in 2 sequences of 8. Further, Each sequence of 8 can be be splitted in two sequences of 4. Subsequently each sequence of 4 can be splitted in two sequences of two. Suraj Kumar Saini (IIIT) DSP 5 / 13
Decimation-In-Time Separate x[n] into two sequence of length N/2 sequence. Even indexed samples in the 鍖rst sequence Odd indexed samples in the other sequence X[k] = N1 n=0 x[n]ej(2/N)kn = N1 n,even x[n]ej(2/N)kn + N1 n,odd x[n]ej(2/N)kn Substitute variables n=2r for n even and n=2r+1 for odd X[k] = N/21 r=0 x[2r]W 2rk N + N/21 r=0 x[2r + 1]W (2r+1)k N = G[k] + W k NH[k] Suraj Kumar Saini (IIIT) DSP 6 / 13
8-point Radix-2 DFT Algorithm Repeat until were left with two-point DFTs Suraj Kumar Saini (IIIT) DSP 7 / 13
Continue... Final 鍖ow graph for 8-point decimation in time Suraj Kumar Saini (IIIT) DSP 8 / 13
Butter鍖y Structure Cross feed of G[k] and H[k] in 鍖ow diagram is called a butter鍖y, due to shape We can implement each butter鍖y with one multiplication Suraj Kumar Saini (IIIT) DSP 9 / 13
Complexity in DIT 8-point DFT example using Decimation-in-time Total complexity N2 /2 + N complex multiplications N2 /2 + N complex additions More e鍖cient than direct DFT Suraj Kumar Saini (IIIT) DSP 10 / 13
Example Suraj Kumar Saini (IIIT) DSP 11 / 13
Inverse Discrete Fourier Transform Suraj Kumar Saini (IIIT) DSP 12 / 13
Thank you! Questions and Suggestions Suraj Kumar Saini (IIIT) DSP 13 / 13

More Related Content

Decimation in Time

  • 1. Decimation-In-Time Suraj Kumar Saini ID: 2015KUEC2015 Department of Electronics and Communication Engineering Indian Institute of Information Technology Kota Suraj Kumar Saini (IIIT) DSP 1 / 13
  • 2. Overview 1 Discrete Fourier Transform 2 Decimation-In-Time 3 Radix-2 DFT Algorithm 4 Butter鍖y Structure 5 Complexity in DIT 6 Inverse Discrete Fourier Transform Suraj Kumar Saini (IIIT) DSP 2 / 13
  • 3. Discrete Fourier Transform The DFT pair was given as : X[k] = N1 n=0 x[n]ej(2/N)kn x[n] = 1 N N1 k=0 X[k]ej(2/N)kn Baseline for computational complexity: Each DFT coe鍖cient requires N complex multiplications N-1 complex additions All N DFT coe鍖cients require N2 complex multiplications N(N-1) complex additions Suraj Kumar Saini (IIIT) DSP 3 / 13
  • 4. Continue... Most fast methods are based on symmetry properties Symmetry: W k N [N n] = W kn N = (W kn N ) Periodicity in n and k: W kn N = W k[n+N] N = W [k+N]n N Suraj Kumar Saini (IIIT) DSP 4 / 13
  • 5. Decimation-In-Time DIT algorithm is used to calculate the DFT of a N-point sequence. First step of process of decimation is splitting a sequence in smaller sequences. A sequence of 16 numbers can be splitted in 2 sequences of 8. Further, Each sequence of 8 can be be splitted in two sequences of 4. Subsequently each sequence of 4 can be splitted in two sequences of two. Suraj Kumar Saini (IIIT) DSP 5 / 13
  • 6. Decimation-In-Time Separate x[n] into two sequence of length N/2 sequence. Even indexed samples in the 鍖rst sequence Odd indexed samples in the other sequence X[k] = N1 n=0 x[n]ej(2/N)kn = N1 n,even x[n]ej(2/N)kn + N1 n,odd x[n]ej(2/N)kn Substitute variables n=2r for n even and n=2r+1 for odd X[k] = N/21 r=0 x[2r]W 2rk N + N/21 r=0 x[2r + 1]W (2r+1)k N = G[k] + W k NH[k] Suraj Kumar Saini (IIIT) DSP 6 / 13
  • 7. 8-point Radix-2 DFT Algorithm Repeat until were left with two-point DFTs Suraj Kumar Saini (IIIT) DSP 7 / 13
  • 8. Continue... Final 鍖ow graph for 8-point decimation in time Suraj Kumar Saini (IIIT) DSP 8 / 13
  • 9. Butter鍖y Structure Cross feed of G[k] and H[k] in 鍖ow diagram is called a butter鍖y, due to shape We can implement each butter鍖y with one multiplication Suraj Kumar Saini (IIIT) DSP 9 / 13
  • 10. Complexity in DIT 8-point DFT example using Decimation-in-time Total complexity N2 /2 + N complex multiplications N2 /2 + N complex additions More e鍖cient than direct DFT Suraj Kumar Saini (IIIT) DSP 10 / 13
  • 11. Example Suraj Kumar Saini (IIIT) DSP 11 / 13
  • 12. Inverse Discrete Fourier Transform Suraj Kumar Saini (IIIT) DSP 12 / 13
  • 13. Thank you! Questions and Suggestions Suraj Kumar Saini (IIIT) DSP 13 / 13