Why does fft require a power of 2 sample numbers? [closed]

Question

I'm a beginner in signal processing, I do not know if I'm right but what I understand so far is if I have a signal of 44100 samples I have 22050 frequencies

so if I choose 512 samples for the fft the 43588 samples will not be analyzed I can only edit the spectrum from 44100/512 = 86.1hz to 22050hz if I want to edit the frequency 1hz I'll have to give 441000 samples to the fft but I can only give it or 65536 samples to analyze all the 22050 frequencies then with 65536 given to the fft I can edit up to the frequency 32768hz

Answer 1

to add to what Louis said, normally in both science and in engineering, novel algorithms are more primitive (requiring restrictions, i.e. $N=2^p$) than mature algorithms of the same function. so it's only historical that the first FFTs may have been power of 2 length.

the original Cooley and Tukey Decimation-in-Frequency FFT can be expressed as

$$\begin{align} X[k] &= \sum\limits_{n=0}^{N-1} x[n] e^{-j 2 \pi nk/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + \sum\limits_{n=N/2}^{N-1} x[n] e^{-j 2 \pi nk/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi (n+N/2)k/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + e^{-j 2 \pi (N/2)k/N} \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + e^{-j \pi k} \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + (-1)^k \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \\ \\ &= \begin{cases} \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \quad &k = 2m & \text{(even)}\\ \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} - \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \quad &k = 2m+1 & \text{(odd)} \\ \end{cases} \\ \\ &= \begin{cases} \sum\limits_{n=0}^{N/2-1} (x[n] + x[n+\tfrac{N}{2}]) e^{-j 2 \pi nk/N} \quad &k = 2m \\ \sum\limits_{n=0}^{N/2-1} (x[n] - x[n+\tfrac{N}{2}]) e^{-j 2 \pi nk/N} \quad &k = 2m+1 \\ \end{cases} \\ \\ &= \begin{cases} \sum\limits_{n=0}^{N/2-1} (x[n] + x[n+\tfrac{N}{2}]) e^{-j \pi nk/(N/2)} \quad &k = 2m \\ \sum\limits_{n=0}^{N/2-1} (x[n] - x[n+\tfrac{N}{2}]) e^{-j \pi nk/(N/2)} \quad &k = 2m+1 \\ \end{cases} \\ \\ &= \begin{cases} X_0[m]=\sum\limits_{n=0}^{N/2-1} (x[n]+x[n+\tfrac{N}{2}]) e^{-j \pi n(2m)/(N/2)} \quad &k = 2m \\ X_1[m]=\sum\limits_{n=0}^{N/2-1} (x[n]-x[n+\tfrac{N}{2}]) e^{-j \pi n(2m+1)/(N/2)} \quad &k = 2m+1 \\ \end{cases} \\ \\ &= \begin{cases} X_0[m]=\sum\limits_{n=0}^{N/2-1} (x[n]+x[n+\tfrac{N}{2}]) e^{-j 2 \pi nm/(N/2)} \quad &k = 2m \\ X_1[m]=\sum\limits_{n=0}^{N/2-1} \big((x[n] - x[n+\tfrac{N}{2}]) e^{-j 2 \pi n/N}\big) e^{-j 2 \pi nm/(N/2)} \quad &k = 2m+1 \\ \end{cases} \\ \end{align}$$

So the cost of the original DFT is $N^2$ multiplications and $N(N-1)$ additions. This DIF thing turns it into $\tfrac{N}{2}$ multiplications and $N$ additions plus the cost of two $\tfrac{N}{2}$-size DFTs. The latter would be twice $\left(\tfrac{N}2\right)^2$ multiplications and $\tfrac{N}2(\tfrac{N}2-1)$ additions.

so which is bigger?

$$\begin{align} N^2 &\lessgtr 2\left(\tfrac{N}{2}\right)^2 + \tfrac{N}{2} & \text{multiplications} \\ \\ N(N-1) &\lessgtr 2\tfrac{N}{2}\left(\tfrac{N}{2}-1\right) + N & \text{additions} \\ \end{align}$$

You can work out that the right-hand side is smaller. So here you now know that you can save computation by dividing the problem into two DFT problems of half the size.

The in-place computation (that does not require you to allocate an additional data buffer to "ping-pong" with) indicates that

$$ \begin{align} x[n] &\leftarrow (x[n]+x[n+\tfrac{N}{2}]) \quad &k = 2m \\ x[n+\tfrac{N}{2}] &\leftarrow (x[n] - x[n+\tfrac{N}{2}]) e^{-j 2 \pi n/N} \quad &k = 2m+1 \\ \end{align} $$

and then work on the two $\tfrac{N}2$ sized DFT in a recursive manner.

The bit-reversed addressing comes in that you'll toss the $X_0[m]$ (even $k$) into the "zeroth" half (the earlier half, where $0 \le n < \tfrac{N}2$) and the $X_1[m]$ (odd $k$) into the "oneth" half (the latter half, where $\tfrac{N}2 \le n < N$). (Here is a place where my religion points an accusing finger at MATLAB for enshrining the terms "first half" and "second half", which i won't use.)

So now you save computation by cutting your problem into two halves. Doesn't it stand to reason that you will also save computation, if the two halves are themselves halved into quarters? This is why it is natural and, in my opinion the easiest, to think about and implement an FFT for just powers of two.

Answer 2

It doesn't. An FFT is just a method or implementation of computing a DFT that runs faster if the length (N) can be factored. It runs relatively faster (compared to a DFT of the same length) given a larger number of small prime factors of N, and is simpler for smaller numbers of unique prime factors of N (such as: only one).

Picking just one prime factor, such as the smallest, 2, makes textbook derivations and examples of FFT computations use less ink in the textbook and/or less chalk on the chalkboard.

But many modern FFT libraries are capable of computing an FFT for an N that is a composite product of several other (fairly small) prime factors, not just 2.

Answer 3

I'm not sure it will answer your question but FFT is an algorithm that computes DFT (Discrete Fourier Transform) in a fast way, generally in $O(N \cdot \log_2(N))$ instead of $O(N^2)$. To achieve this the input matrix has to be a power of 2 (here is why) but many FFT algorithm can handle any size of input since the matrix can be zero-padded.

If this is not automatically done you have to choose the next power of 2 if you want to 'keep' all the frequences.