Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
This explanation with code may help you: blog.bjornroche.com/2012/07/… –  Bjorn Roche Feb 27 '13 at 19:36
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks a lot! (extra characters) –  L1meta Feb 27 '13 at 12:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.