I have a sound file recorded at 44.1 K samples per sec, and some FFT and IFFT algorithms. The sound file is a vector with about $ 2^{17} $ elements.
My objective is to find which of the index values from the output FFT algorithm that corresponds to a frequency above 5000 Hz. So if someone could point out the relationship between the index in the output vector from the FFT, the sample rate and frequency in a Fourier series, that would be awesome. Thanks in advance!
Best Answer
Let $N$ be the number of samples, $I = \{0,...,N-1\}$, and $\phi_n(k) = e^{i 2 \pi\frac{kn}{N}}$, $k,n \in I$. View $\phi_n$ as an element of $\mathbb{C}^N$, ie, $(\phi_n(0),...,\phi_n(N-1))$. Viewed this way, $\{\phi_n \}_{n \in I}$ forms a basis for $\mathbb{C}^N$.
$\phi_n$ can be defined for any $n \in \mathbb{Z}$, but a quick computation shows that $\phi_{N+n} = \phi_{n}$, so there are exactly $N$ functions. Furthermore, $\phi_{N-n} = \phi_{-n}$, so, assuming that $N$ is even and letting $J=\{ -\frac{N}{2}+1, ..., 0,..., \frac{N}{2}\}$, we can consider the basis as the set of functions $\{ \phi_j \}_{j \in J}$.
The DFT of $x \in \mathbb{C}^N$ is the representation of $x$ in terms of the basis $\{\phi_n \}_{n \in I}$ (ignoring scaling, which is irrelevant here).
If $f_s$ the sampling frequency, then $x$ is the sequence of samples of some function at time points $T = \{ \frac{i}{f_s} \}_{i \in I}$. The corresponding frequencies of the DFT are $\Phi = \{ \frac{k}{N} f_s \}_{k \in I}$. Because of the correspondence $\phi_{N-n} = \phi_{-n}$, we see that the non-negative frequency indices are $\{ 0,..., \frac{N}{2}\}$, and the negative frequency indices are $\{ \frac{N}{2}+1, ..., N-1\}$ (corresponding to $\{ -\frac{N}{2}+1,...,-1 \}$).
Consequently, to find the frequencies whose absolute values are greater than or equal to say $F$, we need to find the indices $\{ k | k \in \{ 0,..., \frac{N}{2}\}, \frac{k}{N} f_s \geq F \} \cup \{ k | k \in \{ \frac{N}{2}+1, ..., N-1 \}, \frac{k-N}{N} f_s \leq -F \} $. Or, equivalently, $\{ k | k \in \{ 0,..., \frac{N}{2}\}, k \geq \frac{F N}{f_s} \} \cup \{ k | k \in \{ \frac{N}{2}+1, ..., N-1 \}, k \leq N-\frac{F N}{f_s} \} $.
You have $f_s = 41000$, $N=2^{17}$, $F=5000$. Hence the set of indices is $\{ 15985,...,65536 \} \cup \{ 65537,...,115087\} = \{ 15985,...,115087 \}$.
You need to consult your FFT API to figure out the exact representation details, whether there is zero padding, etc.