DITFFT Lecture Notes

Introduction

• Focus on finding x of k for the given sequence: 1, 2, 3, 4, 4, 3, 2, 1.
• Using DITFFT (Decimation In Time Fast Fourier Transform) algorithm.
• Comparison made with DIFFFT (Decimation In Frequency Fast Fourier Transform).

Understanding DITFFT

• The sequence can be broken down into:
  • X of 0
  • X of 1
  • X of 2
  • X of 3
  • X of 4
  • X of 5
  • X of 6
  • X of 7

Bit Reversal Process

• Explanation of bit reversal for DITFFT:
  • Binary representation must be reversed:
    • 000 -> 000
    • 001 -> 100
    • 010 -> 010
    • 011 -> 110
    • 100 -> 001
    • 101 -> 101
    • 110 -> 011
    • 111 -> 111

Initial Values

• X of 0 = 1
• X of 1 = 2
• X of 2 = 3
• X of 3 = 4
• X of 4 = 4
• X of 5 = 3
• X of 6 = 2
• X of 7 = 1

Butterfly Diagram Construction

1. Start drawing the butterfly diagram using the initial values.
2. Add lines and place cross marks after a gap.
3. Add or put -1 below all the cross marks.
4. Perform calculations for each stage:
   • First stage values:
     • Line 1: 1
     • Line 2: 1 + 4 = 5
     • Line 3: 3 + 2 = 5
     • Line 4: 2 + 3 = 5

Weightage Calculation

• Weightage for DIT FFT:
  • W2 raised to 0 = 1
  • W4 raised to 0 = 1
  • W4 raised to 1 = -j
  • W8 raised to 0 = 1
  • W8 raised to 1 = 0.707 - 0.707j
  • W8 raised to 2 = -j
  • W8 raised to 3 = -0.707 - 0.707j

Final Calculation Steps

1. For each stage, perform the necessary multiplications and additions:
   • Example: 10 + 10 = 20, combined with other terms leads to:
     • Final computations yield:
       • X of 0 = 20
       • X of 1 = 5.828 - 2.414j
       • X of 2 = 0
       • X of 3 = -0.172 - 0.414j
       • X of 4 = 0
       • X of 5 = -5.828 + 2.414j

Conclusion

• The final result for x of k:
  • x of k = [20, 5.828 - 2.414j, 0, -0.172 - 0.414j, 0, -5.828 + 2.414j]

These notes summarize the key points discussed in the DITFFT lecture.