--- title: "8-point DFT by FFT of {1,−1,2,2,1,1,2,2}" subject: "Digital Signal Analysis and Processing" chapter: 7 key: "semester_7/digital_signal_analysis_and_processing:fft-8pt-73s" source: https://www.bctengineer.com/q/semester_7/digital_signal_analysis_and_processing/fft-8pt-73s site: BCT Engineering --- # 8-point DFT by FFT of {1,−1,2,2,1,1,2,2} Digital Signal Analysis and Processing · Chapter 7: Discrete Fourier Transform - Asked in: 2073 Shrawan, 6 marks - Video: [8-Point DFT Solved using Radix-2 DIT FFT Algorithm | Digital Signal Processing Problem Tutorial](https://www.youtube.com/watch?v=9BCirp2Ta6g) — EC Academy - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/digital_signal_analysis_and_processing/fft-8pt-73s - Whole chapter: https://www.bctengineer.com/md/semester_7/digital_signal_analysis_and_processing/chapter-7 ## Question Find 8-point DFT of sequence x[n] = {1, −1, 2, 2, 1, 1, 2, 2} using Fast Fourier Transform algorithm. ## Short answer Use radix-2 DIT FFT with input in bit-reversed order. The 8-point DFT is X(k)={10, −1.4142+j1.4142, −2+j4, 1.4142+j1.4142, 2, 1.4142−j1.4142, −2−j4, −1.4142−j1.4142}. ## Answer The question does not name the algorithm, so DIT-FFT is used. #### Method: radix-2 decimation in time (N = 8, 3 stages) Input in bit-reversed order: x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7). Each butterfly: A' = A + W·B, B' = A − W·B, with W₈⁰ = 1, W₈¹ = 0.7071 − j0.7071, W₈² = −j, W₈³ = −0.7071 − j0.7071. Stage 1 uses W₂ (= ±1), stage 2 uses W₄⁰ = 1 and W₄¹ = −j, and stage 3 uses W₈⁰ … W₈³. x(n) = {1, -1, 2, 2, 1, 1, 2, 2} | Position | Input (bit-reversed) | After stage 1 | After stage 2 | After stage 3 = X(k) | |---|---|---|---|---| | 0 | 1 | 2 | 6 | 10 | | 1 | 1 | 0 | 0 | −1.4142 + j1.4142 | | 2 | 2 | 4 | -2 | −2 + j4 | | 3 | 2 | 0 | 0 | 1.4142 + j1.4142 | | 4 | -1 | 0 | 4 | 2 | | 5 | 1 | -2 | -2 | 1.4142 − j1.4142 | | 6 | 2 | 4 | -4 | −2 − j4 | | 7 | 2 | 0 | -2 | −1.4142 − j1.4142 | **Result:** ```text X(0) = 10 X(1) = −1.4142 + j1.4142 X(2) = −2 + j4 X(3) = 1.4142 + j1.4142 X(4) = 2 X(5) = 1.4142 − j1.4142 X(6) = −2 − j4 X(7) = −1.4142 − j1.4142 ``` Check: Σx(n) = 10 = X(0); the result equals the direct 8-point DFT. **Answer: X(k) = {10, −1.4142 + j1.4142, −2 + j4, 1.4142 + j1.4142, 2, 1.4142 − j1.4142, −2 − j4, −1.4142 − j1.4142}.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What input order does a radix-2 DIT-FFT use? A. Natural order B. Even samples only C. Reverse order D. Bit-reversed order: x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7) Answer: D. DIT takes bit-reversed input and gives natural-order output. (Key point: DIT input order) 2. What is the DIT butterfly? A. A' = A + B, B' = (A - B)W B. A' = A·B, B' = A/B C. A' = A + W, B' = B - W D. A' = A + W·B, B' = A - W·B Answer: D. The twiddle multiplies B before the add and subtract. (Key point: DIT butterfly) 3. What is W8^2 for N = 8? A. -j B. j C. 0.7071 - j0.7071 D. 1 Answer: A. W8^2 = e^(-j pi/2) = -j. (Key point: Twiddle values) 4. X(0) for x = {1, -1, 2, 2, 1, 1, 2, 2} equals? A. 2 B. 8 C. 10, the sum of the samples D. 0 Answer: C. 1 - 1 + 2 + 2 + 1 + 1 + 2 + 2 = 10. (Key point: Check) ## Close variants set in other exams - [8-point DIF-FFT of {1,−1,3,2,1,1,3,−2}](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adifft-8pt-73c) — Digital Signal Analysis and Processing, chapter 7, asked 2× - [8-point DIT-FFT of {1,1,0,1,0,1,2}](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Aditfft-8pt-72k) — Digital Signal Analysis and Processing, chapter 7, asked 3× - [8-point DIT-FFT of {1,1,0,0,1,1,2}](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Aditfft-8pt-70c) — Digital Signal Analysis and Processing, chapter 7, asked 3× ## Related in Digital Signal Analysis and Processing - [8-point DIF-FFT of {1/2,1/2,1/2,1/2,0,0,0,0}](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adif-fft-half-ones) — Digital Signal Analysis and Processing, chapter 7 - [How fast is FFT; X(7) by DIT-FFT](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Afft-speed-x7) — Digital Signal Analysis and Processing, chapter 7, asked 2× - [8-point DIF-FFT of {1,1,2,2,1,1,2,1}](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adifft-8pt-69c) — Digital Signal Analysis and Processing, chapter 7 - [DIT-FFT of {1,1,2,0,1,2,0,1} and spectrum](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adit-fft-spectrum-71s) — Digital Signal Analysis and Processing, chapter 7 - [Why do we need DFT](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Awhy-need-dft) — Digital Signal Analysis and Processing, chapter 7, asked 6× - [FFT of {1,1,2,4,3,1,2,1} by DIT-FFT](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Adit-fft-72c) — Digital Signal Analysis and Processing, chapter 7 ## Related in other subjects - [Discrete and Fast Fourier Transform](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Adft-fft-brief) — Computational Techniques in Civil Engineering, chapter 2 - [Fourier series of square wave and DFT](https://www.bctengineer.com/question.md?key=semester_4%2Finstrumentation_and_measurement%3Afourier-series-square-wave-dft) — Instrumentation and Measurement, chapter 2 - [FFT algorithm and program](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Afft-algorithm-program) — Computational Techniques in Civil Engineering, chapter 2 - [4-point DFT of {0, 1, 2, 3}](https://www.bctengineer.com/question.md?key=semester_4%2Fsignals_and_systems%3Adft-four-point-ramp) — Signals and Systems, chapter 3