---
title: "Discrete and Fast Fourier Transform"
subject: "Computational Techniques in Civil Engineering"
chapter: 2
key: "semester_8/computational_techniques_in_civil_engineering:dft-fft-brief"
source: https://www.bctengineer.com/q/semester_8/computational_techniques_in_civil_engineering/dft-fft-brief
site: BCT Engineering
---

# Discrete and Fast Fourier Transform

Computational Techniques in Civil Engineering · Chapter 2: Solutions of linear equations

- Asked in: 2074 Bhadra, 4 marks
- Video: [Lec-21_Frequency Domain Analysis ,Discrete Fourier Transform ,Aliasing | IS |Civil Engineering](https://www.youtube.com/watch?v=_-9xhTO1fO0) — Civil Engineering Department_LJIET
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_8/computational_techniques_in_civil_engineering/dft-fft-brief
- Whole chapter: https://www.bctengineer.com/md/semester_8/computational_techniques_in_civil_engineering/chapter-2

## Question

Describe briefly the Discrete Fourier Transform (DFT) and the Fast Fourier Transform (FFT).

## Short answer

DFT transforms N time samples to N complex frequency components via X_k = sum x_n exp(−i2πkn/N), needing N² operations. FFT recursively splits even/odd samples, reducing work to (N/2)log₂N. Used for spectral analysis of earthquake records, vibration, and wave data.

## Answer

#### Discrete Fourier Transform (DFT)
The DFT converts $N$ equally spaced samples $x_n$ of a signal in the time domain into $N$ complex frequency components $X_k$:
$$
X_k=\sum_{n=0}^{N-1}x_n\,e^{-i2\pi kn/N},\quad k=0,\dots,N-1
$$
and the inverse is
$$
x_n=\frac{1}{N}\sum_{k=0}^{N-1}X_k\,e^{i2\pi kn/N}
$$
$|X_k|$ gives the amplitude and $\arg X_k$ the phase of the component at frequency $f_k=k/(N\Delta t)$. Direct evaluation needs $N^2$ complex multiplications.

#### Fast Fourier Transform (FFT)
The FFT (Cooley and Tukey, 1965) is an efficient algorithm for computing the DFT. For $N=2^m$ it repeatedly splits the sum into even- and odd-numbered samples:
$$
X_k=E_k+W_N^{k}\,O_k,\qquad X_{k+N/2}=E_k-W_N^{k}\,O_k,\qquad W_N=e^{-i2\pi/N}
$$
This "butterfly" operation reduces the work to $\tfrac{N}{2}\log_2N$ multiplications, so $N=1024$ needs about 5,000 operations instead of about $10^6$.

Uses in civil engineering: frequency content of earthquake records, vibration of bridges and buildings, spectral analysis of waves, and signal filtering.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the DFT do?
   A. Converts frequency to time only
   B. Solves linear equations
   C. Converts N samples in time into N complex frequency components
   D. Differentiates a signal
   Answer: C. X_k = sum x_n e^{-i2 pi kn/N}. (Key point: DFT)

2. Direct DFT multiplications?
   A. N log N
   B. N^2
   C. N/2
   D. 2N
   Answer: B. FFT reduces it. (Key point: DFT cost)

3. How does the FFT reduce the work?
   A. Splits the sum into even and odd samples recursively (butterfly), giving (N/2) log2 N multiplications
   B. Ignores high frequencies
   C. Uses fewer samples
   D. Uses iterative refinement
   Answer: A. N = 1024 needs about 5000 operations instead of 10^6. (Key point: FFT idea)

## Related in Computational Techniques in Civil Engineering

- [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

## Related in other subjects

- [8-point DFT by FFT of {1,−1,2,2,1,1,2,2}](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Afft-8pt-73s) — Digital Signal Analysis and Processing, chapter 7, asked 4×
- [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×
- [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
- [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