Question E7F07:
What function is performed by a Fast Fourier Transform?  

Choices:  
A: Converting analog signals to digital form  
B: Converting digital signals to analog form  
C: Converting signals from the time domain to the frequency domain  
D: Converting signals from the frequency domain to the time domain    

Correct Answer is  C: Converting signals from the time domain to the frequency domain  

To calculate what an FFT does:

- The Fast Fourier Transform (FFT) is an efficient algorithm to compute the Discrete Fourier Transform (DFT), which converts discrete-time samples into their frequency components.

1) Why the correct answer is correct (C)
- The FFT takes a sequence of time-domain samples and produces a spectrum showing how much energy is at each frequency.
- Mathematically, it computes:
  $$X[k] = \sum_{n=0}^{N-1} x[n] \, e^{-j 2\pi kn/N}$$
  where:
  - $x[n]$ = time-domain samples
  - $X[k]$ = frequency-domain bins
  - $N$ = number of points
  - $k$ = bin index

2) Why the other choices are incorrect
- A: Converting analog to digital is done by an ADC (Analog-to-Digital Converter), not an FFT. The FFT operates on already-digitized samples.
- B: Converting digital to analog is done by a DAC (Digital-to-Analog Converter), not an FFT.
- D: Converting frequency domain to time domain is the inverse FFT (IFFT), not the FFT. The IFFT is:
  $$x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k] \, e^{j 2\pi kn/N}$$

3) Useful formulas and rules of thumb
- Frequency resolution of an $N$-point FFT with sample rate $F_s$:
  $$\Delta f = \frac{F_s}{N}$$
- Bin frequencies:
  $$f_k = k \cdot \Delta f = k \frac{F_s}{N}$$
- Maximum unambiguous frequency (Nyquist):
  $$f_{\text{max}} = \frac{F_s}{2}$$
- The FFT is an algorithmic speedup of the DFT: complexity drops from $O(N^2)$ to $O(N \log N)$.

Bottom line: The FFT converts sampled time-domain data to its frequency-domain representation.