- Asked 2/11
- 2073 Chaitra · 6 marks
8-point DIF-FFT of {1,−1,3,2,1,1,3,−2}
Short answer
Use radix-2 DIF FFT with outputs in bit-reversed order. X(k)={8, −4.2426−j1.4142, −4, 4.2426−j1.4142, 8, 4.2426+j1.4142, −4, −4.2426+j1.4142}.
Find 8-point DFT of sequence x[n] = {1, −1, 3, 2, 1, 1, 3, −2} using Decimation in frequency Fast Fourier Transform (DIFFFT) algorithm.
Method: radix-2 decimation in frequency (N = 8, 3 stages)
Each butterfly: A' = A + B, B' = (A − B)·W. Stage 1 pairs n and n + 4 (twiddle W₈ⁿ on the difference), stage 2 pairs n and n + 2 (W₄ⁿ), stage 3 pairs adjacent samples (W₂⁰ = 1). The outputs come out in bit-reversed order.
x(n) = {1, -1, 3, 2, 1, 1, 3, -2}
| Position | Input x(n) | After stage 1 | After stage 2 | After stage 3 |
|---|---|---|---|---|
| 0 | 1 | 2 | 8 | 8 |
| 1 | -1 | 0 | 0 | 8 |
| 2 | 3 | 6 | -4 | -4 |
| 3 | 2 | 0 | 0 | -4 |
| 4 | 1 | 0 | 0 | −4.2426 − j1.4142 |
| 5 | 1 | −1.4142 + j1.4142 | −4.2426 − j1.4142 | 4.2426 + j1.4142 |
| 6 | 3 | 0 | 0 | 4.2426 − j1.4142 |
| 7 | -2 | −2.8284 − j2.8284 | 4.2426 − j1.4142 | −4.2426 + j1.4142 |
Output positions 0, 1, 2, 3, 4, 5, 6, 7 hold X(0), X(4), X(2), X(6), X(1), X(5), X(3), X(7) (bit-reversed). Rearranging:
Result:
X(0) = 8
X(1) = −4.2426 − j1.4142
X(2) = -4
X(3) = 4.2426 − j1.4142
X(4) = 8
X(5) = 4.2426 + j1.4142
X(6) = -4
X(7) = −4.2426 + j1.4142
Check: Σx(n) = 8 = X(0); the result equals the direct 8-point DFT.
Answer: X(k) = {8, −4.2426 − j1.4142, -4, 4.2426 − j1.4142, 8, 4.2426 + j1.4142, -4, −4.2426 + j1.4142}.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- 8-point DFT by FFT of {1,−1,2,2,1,1,2,2} · Digital Signal Analysis and Processing, chapter 7 · asked 4×
- 8-point DIF-FFT of {1/2,1/2,1/2,1/2,0,0,0,0} · Digital Signal Analysis and Processing, chapter 7
- 8-point DIF-FFT of {1,1,2,2,1,1,2,1} · Digital Signal Analysis and Processing, chapter 7
- 8-point DIT-FFT of {1,1,0,1,0,1,2} · Digital Signal Analysis and Processing, chapter 7 · asked 3×
- 8-point DIT-FFT of {1,1,0,0,1,1,2} · Digital Signal Analysis and Processing, chapter 7 · asked 3×
- How fast is FFT; X(7) by DIT-FFT · Digital Signal Analysis and Processing, chapter 7 · asked 2×
- DIF-FFT butterfly; compute X(2) and X(1) · Digital Signal Analysis and Processing, chapter 7
- Discrete and Fast Fourier Transform · Computational Techniques in Civil Engineering, chapter 2
- Fourier series of square wave and DFT · Instrumentation and Measurement, chapter 2
- FFT algorithm and program · Computational Techniques in Civil Engineering, chapter 2
- 4-point DFT of {0, 1, 2, 3} · Signals and Systems, chapter 3
All Digital Signal Analysis and Processing chapter 7 questions →