Mixing
How to interpret the results of a Discrete Fourier Transform
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I'm trying to understand the Discrete Fourier Transform so that I can understand the Fast Fourier Transform so that I can write a program to calculate it. I know that there are existing libraries that already do this, but if I use one of them I won't understand the maths behind the DFT.
I understand the general theory that you run different frequencies through the DFT and when the frequency matches a frequency in the signal, you get a spike in the amplitude and that the phase of the signal frequency can also be measured.
What I don't understand is which frequencies are represented in the results, and if the amplitude is normalised.
I've been mucking around with signals with only 8 data points. It seems that the wavelengths measured are $8/1$, $8/2$, $8/3$, etc. and the amplitudes seem to be multiplied by 8. I don't understand the usefulness of frequency 0, because it just sums all the data points.
I am wondering, if I have a signal that only is a sine wave at Concert A (440 Hz) with an amplitude of 1, sampled 44100 times per second (CD sample rate), and I do a DFT on the first 2048 samples, how do I detect the frequency at 440 Hz? The wavelength is 100.23 data points, which repeats 20.43 times in my sample. If I understand the measurable frequencies, they must be integer fractions of the sample size, so $2048/20=430.66$ or $2048/21=452.20$. Do I get a partial match for both close frequencies? If this is the case, how do I recognise that the true frequency is 440 Hz? What do the result data look like (the 2048 transformed values)?
fourier-transform fast-fourier-transform
asked Jul 23 at 3:41
CJ Dennis
415211
 |Â
show 1 more comment
up vote
1
down vote
favorite
I'm trying to understand the Discrete Fourier Transform so that I can understand the Fast Fourier Transform so that I can write a program to calculate it. I know that there are existing libraries that already do this, but if I use one of them I won't understand the maths behind the DFT.
I understand the general theory that you run different frequencies through the DFT and when the frequency matches a frequency in the signal, you get a spike in the amplitude and that the phase of the signal frequency can also be measured.
What I don't understand is which frequencies are represented in the results, and if the amplitude is normalised.
I've been mucking around with signals with only 8 data points. It seems that the wavelengths measured are $8/1$, $8/2$, $8/3$, etc. and the amplitudes seem to be multiplied by 8. I don't understand the usefulness of frequency 0, because it just sums all the data points.
I am wondering, if I have a signal that only is a sine wave at Concert A (440 Hz) with an amplitude of 1, sampled 44100 times per second (CD sample rate), and I do a DFT on the first 2048 samples, how do I detect the frequency at 440 Hz? The wavelength is 100.23 data points, which repeats 20.43 times in my sample. If I understand the measurable frequencies, they must be integer fractions of the sample size, so $2048/20=430.66$ or $2048/21=452.20$. Do I get a partial match for both close frequencies? If this is the case, how do I recognise that the true frequency is 440 Hz? What do the result data look like (the 2048 transformed values)?
fourier-transform fast-fourier-transform
asked Jul 23 at 3:41
CJ Dennis
415211
Why don't you just try it? If you don't want to install a library, there are lots of online FFT calculators.
– joriki
Jul 23 at 4:19
@joriki I want to understand DFT, not use a black box. I also don't want to type in 2048 values.
– CJ Dennis
Jul 23 at 4:25
You don't have to type them, you can generate them automatically. And it will help you understand them. You're asking us "What do the result data look like (the $2048$ transformed values)?" How are we less of a black box than the online FFT calculator?
– joriki
Jul 23 at 4:30
@joriki Because a human will say "The reason why we see X at Y is because of Z". A black box can't teach me why.
– CJ Dennis
Jul 23 at 4:32
Please take a look at this guide on how to ask a good question, especially the section "Include your work". In this case, I think showing your own effort would include first taking a look at what the result looks like and then describing what you don't understand about it (e.g. "I don't understand why the result seems to have a sinusoidal form"), rather than asking us to describe something to you that you could easily see for yourself.
– joriki
Jul 23 at 4:37
 |Â
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I'm trying to understand the Discrete Fourier Transform so that I can understand the Fast Fourier Transform so that I can write a program to calculate it. I know that there are existing libraries that already do this, but if I use one of them I won't understand the maths behind the DFT.
I understand the general theory that you run different frequencies through the DFT and when the frequency matches a frequency in the signal, you get a spike in the amplitude and that the phase of the signal frequency can also be measured.
What I don't understand is which frequencies are represented in the results, and if the amplitude is normalised.
I've been mucking around with signals with only 8 data points. It seems that the wavelengths measured are $8/1$, $8/2$, $8/3$, etc. and the amplitudes seem to be multiplied by 8. I don't understand the usefulness of frequency 0, because it just sums all the data points.
I am wondering, if I have a signal that only is a sine wave at Concert A (440 Hz) with an amplitude of 1, sampled 44100 times per second (CD sample rate), and I do a DFT on the first 2048 samples, how do I detect the frequency at 440 Hz? The wavelength is 100.23 data points, which repeats 20.43 times in my sample. If I understand the measurable frequencies, they must be integer fractions of the sample size, so $2048/20=430.66$ or $2048/21=452.20$. Do I get a partial match for both close frequencies? If this is the case, how do I recognise that the true frequency is 440 Hz? What do the result data look like (the 2048 transformed values)?
fourier-transform fast-fourier-transform
asked Jul 23 at 3:41
CJ Dennis
415211
I'm trying to understand the Discrete Fourier Transform so that I can understand the Fast Fourier Transform so that I can write a program to calculate it. I know that there are existing libraries that already do this, but if I use one of them I won't understand the maths behind the DFT.
I understand the general theory that you run different frequencies through the DFT and when the frequency matches a frequency in the signal, you get a spike in the amplitude and that the phase of the signal frequency can also be measured.
What I don't understand is which frequencies are represented in the results, and if the amplitude is normalised.
I've been mucking around with signals with only 8 data points. It seems that the wavelengths measured are $8/1$, $8/2$, $8/3$, etc. and the amplitudes seem to be multiplied by 8. I don't understand the usefulness of frequency 0, because it just sums all the data points.
I am wondering, if I have a signal that only is a sine wave at Concert A (440 Hz) with an amplitude of 1, sampled 44100 times per second (CD sample rate), and I do a DFT on the first 2048 samples, how do I detect the frequency at 440 Hz? The wavelength is 100.23 data points, which repeats 20.43 times in my sample. If I understand the measurable frequencies, they must be integer fractions of the sample size, so $2048/20=430.66$ or $2048/21=452.20$. Do I get a partial match for both close frequencies? If this is the case, how do I recognise that the true frequency is 440 Hz? What do the result data look like (the 2048 transformed values)?
fourier-transform fast-fourier-transform
asked Jul 23 at 3:41
CJ Dennis
415211
asked Jul 23 at 3:41
CJ Dennis
415211
asked Jul 23 at 3:41
CJ Dennis
415211
asked Jul 23 at 3:41
CJ Dennis
415211
415211
Why don't you just try it? If you don't want to install a library, there are lots of online FFT calculators.
– joriki
Jul 23 at 4:19
@joriki I want to understand DFT, not use a black box. I also don't want to type in 2048 values.
– CJ Dennis
Jul 23 at 4:25
You don't have to type them, you can generate them automatically. And it will help you understand them. You're asking us "What do the result data look like (the $2048$ transformed values)?" How are we less of a black box than the online FFT calculator?
– joriki
Jul 23 at 4:30
@joriki Because a human will say "The reason why we see X at Y is because of Z". A black box can't teach me why.
– CJ Dennis
Jul 23 at 4:32
Please take a look at this guide on how to ask a good question, especially the section "Include your work". In this case, I think showing your own effort would include first taking a look at what the result looks like and then describing what you don't understand about it (e.g. "I don't understand why the result seems to have a sinusoidal form"), rather than asking us to describe something to you that you could easily see for yourself.
– joriki
Jul 23 at 4:37
 |Â
show 1 more comment
Why don't you just try it? If you don't want to install a library, there are lots of online FFT calculators.
– joriki
Jul 23 at 4:19
@joriki I want to understand DFT, not use a black box. I also don't want to type in 2048 values.
– CJ Dennis
Jul 23 at 4:25
You don't have to type them, you can generate them automatically. And it will help you understand them. You're asking us "What do the result data look like (the $2048$ transformed values)?" How are we less of a black box than the online FFT calculator?
– joriki
Jul 23 at 4:30
@joriki Because a human will say "The reason why we see X at Y is because of Z". A black box can't teach me why.
– CJ Dennis
Jul 23 at 4:32
Please take a look at this guide on how to ask a good question, especially the section "Include your work". In this case, I think showing your own effort would include first taking a look at what the result looks like and then describing what you don't understand about it (e.g. "I don't understand why the result seems to have a sinusoidal form"), rather than asking us to describe something to you that you could easily see for yourself.
– joriki
Jul 23 at 4:37
Why don't you just try it? If you don't want to install a library, there are lots of online FFT calculators.
– joriki
Jul 23 at 4:19
Why don't you just try it? If you don't want to install a library, there are lots of online FFT calculators.
– joriki
Jul 23 at 4:19
@joriki I want to understand DFT, not use a black box. I also don't want to type in 2048 values.
– CJ Dennis
Jul 23 at 4:25
@joriki I want to understand DFT, not use a black box. I also don't want to type in 2048 values.
– CJ Dennis
Jul 23 at 4:25
You don't have to type them, you can generate them automatically. And it will help you understand them. You're asking us "What do the result data look like (the $2048$ transformed values)?" How are we less of a black box than the online FFT calculator?
– joriki
Jul 23 at 4:30
You don't have to type them, you can generate them automatically. And it will help you understand them. You're asking us "What do the result data look like (the $2048$ transformed values)?" How are we less of a black box than the online FFT calculator?
– joriki
Jul 23 at 4:30
@joriki Because a human will say "The reason why we see X at Y is because of Z". A black box can't teach me why.
– CJ Dennis
Jul 23 at 4:32
@joriki Because a human will say "The reason why we see X at Y is because of Z". A black box can't teach me why.
– CJ Dennis
Jul 23 at 4:32
Please take a look at this guide on how to ask a good question, especially the section "Include your work". In this case, I think showing your own effort would include first taking a look at what the result looks like and then describing what you don't understand about it (e.g. "I don't understand why the result seems to have a sinusoidal form"), rather than asking us to describe something to you that you could easily see for yourself.
– joriki
Jul 23 at 4:37
Please take a look at this guide on how to ask a good question, especially the section "Include your work". In this case, I think showing your own effort would include first taking a look at what the result looks like and then describing what you don't understand about it (e.g. "I don't understand why the result seems to have a sinusoidal form"), rather than asking us to describe something to you that you could easily see for yourself.
– joriki
Jul 23 at 4:37
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
1
down vote
The discrete Fourier transform implicitly regards the input data as periodic. The length of the input data is an integer multiple of the frequencies that the output data correspond to. If you generate the input data from a sinusoidal that has a different period that doesn't evenly divide the length of the data, then you're effectively creating a jump at the point where the first data point follows the last in the periodic continuation. A jump has appreciable Fourier components at all frequencies, and this is superimposed on your signal.
Nevertheless, you do get a signal with a clear maximum around the input frequency. I tried this using this online FFT calculator. In your case, as you calculated, we'd expect the maximum to be around the $21$st and $22$nd output data point (with the first data point corresponding to frequency $0$), and indeed, the first $40$ output values are:
30.322000,0.000000
30.391603,-0.332305
30.619103,-0.635705
30.983132,-0.983397
31.541176,-1.314554
32.258933,-1.685996
33.213385,-2.076468
34.383753,-2.509669
35.850294,-2.989665
37.679693,-3.538320
39.950279,-4.172808
42.781442,-4.897551
46.400390,-5.801462
51.088228,-6.910079
57.343876,-8.338977
66.017176,-10.282208
78.721064,-13.088380
98.974578,-17.487260
136.068697,-25.448952
225.318492,-44.421047
727.024048,-150.774758
-543.414483,118.240910
-191.999756,43.727082
-114.594042,27.275221
-80.661116,20.008091
-61.661208,15.918785
-49.536603,13.289953
-41.141647,11.459233
-35.002598,10.087933
-30.321248,9.041060
-26.630074,8.216618
-23.664950,7.534937
-21.230810,6.967688
-19.199079,6.488785
-17.492157,6.083581
-16.004951,5.723743
-14.733225,5.416510
-13.616822,5.138707
-12.640339,4.905611
-11.768659,4.665358
So it seems you must have been doing something wrong when you got spikes all over the place at roughly the same amplitude.
You can actually calculate the output in closed form in this case by writing the sinusoidals in terms of complex exponentials and summing the resulting partial geometric series.
Edit:
Here's that last suggestion written out.
You have the time-domain signal $sin2pinu t$ with $nu=440textHz$, and you sample it at the frequency $f=44100textHz$, so you have the samples
$$
s_k=sinfrac2pinu kf=frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)
$$
for $0le klt n$, with $n=2048$. Performing a discrete Fourier transform on these samples yields
begineqnarray*
tilde s_j
&=&
sum_k=0^n-1s_kexpleft(frac2pimathrm i jknright)
\
&=&
sum_k=0^n-1frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)expleft(frac2pimathrm i jknright)
\
&=&
frac12mathrm isum_k=0^n-1left(expleft(2pimathrm ileft(frac jn+fracnu fright)kright)-expleft(2pimathrm ileft(frac jn-fracnu fright)kright)right)
\
&=&
frac12mathrm isum_k=0^n-1left(omega_j+^k-omega_j-^kright)
\
&=&
frac12mathrm ileft(frac1-omega_j+^n1-omega_j+-frac1-omega_j-^n1-omega_j-right)endeqnarray*
with $omega_jpm=2pimathrm ileft(frac jnpmfracnu fright)$. The second term dominates and is maximal at $frac jn=fracnu f$ (which in your case is at the fractional value $j=fracnnuf$). It's a phase factor times
$$
fracsin npileft(frac jn-fracnu fright)sinpileft(frac jn-fracnu fright);,
$$
which is a discrete periodic analogue of the $operatornamesinc$ function. Fitting to this functional form might improve your estimate of the frequency from the output data of the Fourier transform.
answered Jul 23 at 5:20
joriki
164k10180328
How do you get from "727.024048,-150.774758", "-543.414483,118.240910" to 440 Hz? As I guessed, there are two results with an error of +/-12 Hz, with the true answer somewhere in between.
– CJ Dennis
Jul 23 at 5:36
@CJDennis: You could interpolate the three greatest magnitudes with a quadratic polynomial to estimate the maximum in the magnitude.
– joriki
Jul 23 at 5:45
@CJDennis: Doing that with Wolfram|Alpha yields a maximum around $20.34$, corresponding to $20.34cdot44100textHz/2048approx438textHz$.
– joriki
Jul 23 at 5:52
@CJDennis: Or you could perform the calculation I suggested in the last paragraph of the answer to get the functional form of the result depending on the input frequency, and then try to use that for a more specific method to estimate the frequency.
– joriki
Jul 23 at 5:54
Possibly, if I understood the last paragraph...
– CJ Dennis
Jul 23 at 9:51
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
The discrete Fourier transform implicitly regards the input data as periodic. The length of the input data is an integer multiple of the frequencies that the output data correspond to. If you generate the input data from a sinusoidal that has a different period that doesn't evenly divide the length of the data, then you're effectively creating a jump at the point where the first data point follows the last in the periodic continuation. A jump has appreciable Fourier components at all frequencies, and this is superimposed on your signal.
Nevertheless, you do get a signal with a clear maximum around the input frequency. I tried this using this online FFT calculator. In your case, as you calculated, we'd expect the maximum to be around the $21$st and $22$nd output data point (with the first data point corresponding to frequency $0$), and indeed, the first $40$ output values are:
30.322000,0.000000
30.391603,-0.332305
30.619103,-0.635705
30.983132,-0.983397
31.541176,-1.314554
32.258933,-1.685996
33.213385,-2.076468
34.383753,-2.509669
35.850294,-2.989665
37.679693,-3.538320
39.950279,-4.172808
42.781442,-4.897551
46.400390,-5.801462
51.088228,-6.910079
57.343876,-8.338977
66.017176,-10.282208
78.721064,-13.088380
98.974578,-17.487260
136.068697,-25.448952
225.318492,-44.421047
727.024048,-150.774758
-543.414483,118.240910
-191.999756,43.727082
-114.594042,27.275221
-80.661116,20.008091
-61.661208,15.918785
-49.536603,13.289953
-41.141647,11.459233
-35.002598,10.087933
-30.321248,9.041060
-26.630074,8.216618
-23.664950,7.534937
-21.230810,6.967688
-19.199079,6.488785
-17.492157,6.083581
-16.004951,5.723743
-14.733225,5.416510
-13.616822,5.138707
-12.640339,4.905611
-11.768659,4.665358
So it seems you must have been doing something wrong when you got spikes all over the place at roughly the same amplitude.
You can actually calculate the output in closed form in this case by writing the sinusoidals in terms of complex exponentials and summing the resulting partial geometric series.
Edit:
Here's that last suggestion written out.
You have the time-domain signal $sin2pinu t$ with $nu=440textHz$, and you sample it at the frequency $f=44100textHz$, so you have the samples
$$
s_k=sinfrac2pinu kf=frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)
$$
for $0le klt n$, with $n=2048$. Performing a discrete Fourier transform on these samples yields
begineqnarray*
tilde s_j
&=&
sum_k=0^n-1s_kexpleft(frac2pimathrm i jknright)
\
&=&
sum_k=0^n-1frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)expleft(frac2pimathrm i jknright)
\
&=&
frac12mathrm isum_k=0^n-1left(expleft(2pimathrm ileft(frac jn+fracnu fright)kright)-expleft(2pimathrm ileft(frac jn-fracnu fright)kright)right)
\
&=&
frac12mathrm isum_k=0^n-1left(omega_j+^k-omega_j-^kright)
\
&=&
frac12mathrm ileft(frac1-omega_j+^n1-omega_j+-frac1-omega_j-^n1-omega_j-right)endeqnarray*
with $omega_jpm=2pimathrm ileft(frac jnpmfracnu fright)$. The second term dominates and is maximal at $frac jn=fracnu f$ (which in your case is at the fractional value $j=fracnnuf$). It's a phase factor times
$$
fracsin npileft(frac jn-fracnu fright)sinpileft(frac jn-fracnu fright);,
$$
which is a discrete periodic analogue of the $operatornamesinc$ function. Fitting to this functional form might improve your estimate of the frequency from the output data of the Fourier transform.
answered Jul 23 at 5:20
joriki
164k10180328
How do you get from "727.024048,-150.774758", "-543.414483,118.240910" to 440 Hz? As I guessed, there are two results with an error of +/-12 Hz, with the true answer somewhere in between.
– CJ Dennis
Jul 23 at 5:36
@CJDennis: You could interpolate the three greatest magnitudes with a quadratic polynomial to estimate the maximum in the magnitude.
– joriki
Jul 23 at 5:45
@CJDennis: Doing that with Wolfram|Alpha yields a maximum around $20.34$, corresponding to $20.34cdot44100textHz/2048approx438textHz$.
– joriki
Jul 23 at 5:52
@CJDennis: Or you could perform the calculation I suggested in the last paragraph of the answer to get the functional form of the result depending on the input frequency, and then try to use that for a more specific method to estimate the frequency.
– joriki
Jul 23 at 5:54
Possibly, if I understood the last paragraph...
– CJ Dennis
Jul 23 at 9:51
add a comment |Â
up vote
1
down vote
The discrete Fourier transform implicitly regards the input data as periodic. The length of the input data is an integer multiple of the frequencies that the output data correspond to. If you generate the input data from a sinusoidal that has a different period that doesn't evenly divide the length of the data, then you're effectively creating a jump at the point where the first data point follows the last in the periodic continuation. A jump has appreciable Fourier components at all frequencies, and this is superimposed on your signal.
Nevertheless, you do get a signal with a clear maximum around the input frequency. I tried this using this online FFT calculator. In your case, as you calculated, we'd expect the maximum to be around the $21$st and $22$nd output data point (with the first data point corresponding to frequency $0$), and indeed, the first $40$ output values are:
30.322000,0.000000
30.391603,-0.332305
30.619103,-0.635705
30.983132,-0.983397
31.541176,-1.314554
32.258933,-1.685996
33.213385,-2.076468
34.383753,-2.509669
35.850294,-2.989665
37.679693,-3.538320
39.950279,-4.172808
42.781442,-4.897551
46.400390,-5.801462
51.088228,-6.910079
57.343876,-8.338977
66.017176,-10.282208
78.721064,-13.088380
98.974578,-17.487260
136.068697,-25.448952
225.318492,-44.421047
727.024048,-150.774758
-543.414483,118.240910
-191.999756,43.727082
-114.594042,27.275221
-80.661116,20.008091
-61.661208,15.918785
-49.536603,13.289953
-41.141647,11.459233
-35.002598,10.087933
-30.321248,9.041060
-26.630074,8.216618
-23.664950,7.534937
-21.230810,6.967688
-19.199079,6.488785
-17.492157,6.083581
-16.004951,5.723743
-14.733225,5.416510
-13.616822,5.138707
-12.640339,4.905611
-11.768659,4.665358
So it seems you must have been doing something wrong when you got spikes all over the place at roughly the same amplitude.
You can actually calculate the output in closed form in this case by writing the sinusoidals in terms of complex exponentials and summing the resulting partial geometric series.
Edit:
Here's that last suggestion written out.
You have the time-domain signal $sin2pinu t$ with $nu=440textHz$, and you sample it at the frequency $f=44100textHz$, so you have the samples
$$
s_k=sinfrac2pinu kf=frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)
$$
for $0le klt n$, with $n=2048$. Performing a discrete Fourier transform on these samples yields
begineqnarray*
tilde s_j
&=&
sum_k=0^n-1s_kexpleft(frac2pimathrm i jknright)
\
&=&
sum_k=0^n-1frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)expleft(frac2pimathrm i jknright)
\
&=&
frac12mathrm isum_k=0^n-1left(expleft(2pimathrm ileft(frac jn+fracnu fright)kright)-expleft(2pimathrm ileft(frac jn-fracnu fright)kright)right)
\
&=&
frac12mathrm isum_k=0^n-1left(omega_j+^k-omega_j-^kright)
\
&=&
frac12mathrm ileft(frac1-omega_j+^n1-omega_j+-frac1-omega_j-^n1-omega_j-right)endeqnarray*
with $omega_jpm=2pimathrm ileft(frac jnpmfracnu fright)$. The second term dominates and is maximal at $frac jn=fracnu f$ (which in your case is at the fractional value $j=fracnnuf$). It's a phase factor times
$$
fracsin npileft(frac jn-fracnu fright)sinpileft(frac jn-fracnu fright);,
$$
which is a discrete periodic analogue of the $operatornamesinc$ function. Fitting to this functional form might improve your estimate of the frequency from the output data of the Fourier transform.
answered Jul 23 at 5:20
joriki
164k10180328
How do you get from "727.024048,-150.774758", "-543.414483,118.240910" to 440 Hz? As I guessed, there are two results with an error of +/-12 Hz, with the true answer somewhere in between.
– CJ Dennis
Jul 23 at 5:36
@CJDennis: You could interpolate the three greatest magnitudes with a quadratic polynomial to estimate the maximum in the magnitude.
– joriki
Jul 23 at 5:45
@CJDennis: Doing that with Wolfram|Alpha yields a maximum around $20.34$, corresponding to $20.34cdot44100textHz/2048approx438textHz$.
– joriki
Jul 23 at 5:52
@CJDennis: Or you could perform the calculation I suggested in the last paragraph of the answer to get the functional form of the result depending on the input frequency, and then try to use that for a more specific method to estimate the frequency.
– joriki
Jul 23 at 5:54
Possibly, if I understood the last paragraph...
– CJ Dennis
Jul 23 at 9:51
add a comment |Â
up vote
1
down vote
up vote
1
down vote
The discrete Fourier transform implicitly regards the input data as periodic. The length of the input data is an integer multiple of the frequencies that the output data correspond to. If you generate the input data from a sinusoidal that has a different period that doesn't evenly divide the length of the data, then you're effectively creating a jump at the point where the first data point follows the last in the periodic continuation. A jump has appreciable Fourier components at all frequencies, and this is superimposed on your signal.
Nevertheless, you do get a signal with a clear maximum around the input frequency. I tried this using this online FFT calculator. In your case, as you calculated, we'd expect the maximum to be around the $21$st and $22$nd output data point (with the first data point corresponding to frequency $0$), and indeed, the first $40$ output values are:
30.322000,0.000000
30.391603,-0.332305
30.619103,-0.635705
30.983132,-0.983397
31.541176,-1.314554
32.258933,-1.685996
33.213385,-2.076468
34.383753,-2.509669
35.850294,-2.989665
37.679693,-3.538320
39.950279,-4.172808
42.781442,-4.897551
46.400390,-5.801462
51.088228,-6.910079
57.343876,-8.338977
66.017176,-10.282208
78.721064,-13.088380
98.974578,-17.487260
136.068697,-25.448952
225.318492,-44.421047
727.024048,-150.774758
-543.414483,118.240910
-191.999756,43.727082
-114.594042,27.275221
-80.661116,20.008091
-61.661208,15.918785
-49.536603,13.289953
-41.141647,11.459233
-35.002598,10.087933
-30.321248,9.041060
-26.630074,8.216618
-23.664950,7.534937
-21.230810,6.967688
-19.199079,6.488785
-17.492157,6.083581
-16.004951,5.723743
-14.733225,5.416510
-13.616822,5.138707
-12.640339,4.905611
-11.768659,4.665358
So it seems you must have been doing something wrong when you got spikes all over the place at roughly the same amplitude.
You can actually calculate the output in closed form in this case by writing the sinusoidals in terms of complex exponentials and summing the resulting partial geometric series.
Edit:
Here's that last suggestion written out.
You have the time-domain signal $sin2pinu t$ with $nu=440textHz$, and you sample it at the frequency $f=44100textHz$, so you have the samples
$$
s_k=sinfrac2pinu kf=frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)
$$
for $0le klt n$, with $n=2048$. Performing a discrete Fourier transform on these samples yields
begineqnarray*
tilde s_j
&=&
sum_k=0^n-1s_kexpleft(frac2pimathrm i jknright)
\
&=&
sum_k=0^n-1frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)expleft(frac2pimathrm i jknright)
\
&=&
frac12mathrm isum_k=0^n-1left(expleft(2pimathrm ileft(frac jn+fracnu fright)kright)-expleft(2pimathrm ileft(frac jn-fracnu fright)kright)right)
\
&=&
frac12mathrm isum_k=0^n-1left(omega_j+^k-omega_j-^kright)
\
&=&
frac12mathrm ileft(frac1-omega_j+^n1-omega_j+-frac1-omega_j-^n1-omega_j-right)endeqnarray*
with $omega_jpm=2pimathrm ileft(frac jnpmfracnu fright)$. The second term dominates and is maximal at $frac jn=fracnu f$ (which in your case is at the fractional value $j=fracnnuf$). It's a phase factor times
$$
fracsin npileft(frac jn-fracnu fright)sinpileft(frac jn-fracnu fright);,
$$
which is a discrete periodic analogue of the $operatornamesinc$ function. Fitting to this functional form might improve your estimate of the frequency from the output data of the Fourier transform.
answered Jul 23 at 5:20
joriki
164k10180328
The discrete Fourier transform implicitly regards the input data as periodic. The length of the input data is an integer multiple of the frequencies that the output data correspond to. If you generate the input data from a sinusoidal that has a different period that doesn't evenly divide the length of the data, then you're effectively creating a jump at the point where the first data point follows the last in the periodic continuation. A jump has appreciable Fourier components at all frequencies, and this is superimposed on your signal.
Nevertheless, you do get a signal with a clear maximum around the input frequency. I tried this using this online FFT calculator. In your case, as you calculated, we'd expect the maximum to be around the $21$st and $22$nd output data point (with the first data point corresponding to frequency $0$), and indeed, the first $40$ output values are:
30.322000,0.000000
30.391603,-0.332305
30.619103,-0.635705
30.983132,-0.983397
31.541176,-1.314554
32.258933,-1.685996
33.213385,-2.076468
34.383753,-2.509669
35.850294,-2.989665
37.679693,-3.538320
39.950279,-4.172808
42.781442,-4.897551
46.400390,-5.801462
51.088228,-6.910079
57.343876,-8.338977
66.017176,-10.282208
78.721064,-13.088380
98.974578,-17.487260
136.068697,-25.448952
225.318492,-44.421047
727.024048,-150.774758
-543.414483,118.240910
-191.999756,43.727082
-114.594042,27.275221
-80.661116,20.008091
-61.661208,15.918785
-49.536603,13.289953
-41.141647,11.459233
-35.002598,10.087933
-30.321248,9.041060
-26.630074,8.216618
-23.664950,7.534937
-21.230810,6.967688
-19.199079,6.488785
-17.492157,6.083581
-16.004951,5.723743
-14.733225,5.416510
-13.616822,5.138707
-12.640339,4.905611
-11.768659,4.665358
So it seems you must have been doing something wrong when you got spikes all over the place at roughly the same amplitude.
You can actually calculate the output in closed form in this case by writing the sinusoidals in terms of complex exponentials and summing the resulting partial geometric series.
Edit:
Here's that last suggestion written out.
You have the time-domain signal $sin2pinu t$ with $nu=440textHz$, and you sample it at the frequency $f=44100textHz$, so you have the samples
$$
s_k=sinfrac2pinu kf=frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)
$$
for $0le klt n$, with $n=2048$. Performing a discrete Fourier transform on these samples yields
begineqnarray*
tilde s_j
&=&
sum_k=0^n-1s_kexpleft(frac2pimathrm i jknright)
\
&=&
sum_k=0^n-1frac12mathrm ileft(expleft(frac2pimathrm inu kfright)-expleft(-frac2pimathrm inu kfright)right)expleft(frac2pimathrm i jknright)
\
&=&
frac12mathrm isum_k=0^n-1left(expleft(2pimathrm ileft(frac jn+fracnu fright)kright)-expleft(2pimathrm ileft(frac jn-fracnu fright)kright)right)
\
&=&
frac12mathrm isum_k=0^n-1left(omega_j+^k-omega_j-^kright)
\
&=&
frac12mathrm ileft(frac1-omega_j+^n1-omega_j+-frac1-omega_j-^n1-omega_j-right)endeqnarray*
with $omega_jpm=2pimathrm ileft(frac jnpmfracnu fright)$. The second term dominates and is maximal at $frac jn=fracnu f$ (which in your case is at the fractional value $j=fracnnuf$). It's a phase factor times
$$
fracsin npileft(frac jn-fracnu fright)sinpileft(frac jn-fracnu fright);,
$$
which is a discrete periodic analogue of the $operatornamesinc$ function. Fitting to this functional form might improve your estimate of the frequency from the output data of the Fourier transform.
answered Jul 23 at 5:20
joriki
164k10180328
edited Jul 23 at 10:48
answered Jul 23 at 5:20
joriki
164k10180328
answered Jul 23 at 5:20
joriki
164k10180328
answered Jul 23 at 5:20
joriki
164k10180328
164k10180328
How do you get from "727.024048,-150.774758", "-543.414483,118.240910" to 440 Hz? As I guessed, there are two results with an error of +/-12 Hz, with the true answer somewhere in between.
– CJ Dennis
Jul 23 at 5:36
@CJDennis: You could interpolate the three greatest magnitudes with a quadratic polynomial to estimate the maximum in the magnitude.
– joriki
Jul 23 at 5:45
@CJDennis: Doing that with Wolfram|Alpha yields a maximum around $20.34$, corresponding to $20.34cdot44100textHz/2048approx438textHz$.
– joriki
Jul 23 at 5:52
@CJDennis: Or you could perform the calculation I suggested in the last paragraph of the answer to get the functional form of the result depending on the input frequency, and then try to use that for a more specific method to estimate the frequency.
– joriki
Jul 23 at 5:54
Possibly, if I understood the last paragraph...
– CJ Dennis
Jul 23 at 9:51
add a comment |Â
How do you get from "727.024048,-150.774758", "-543.414483,118.240910" to 440 Hz? As I guessed, there are two results with an error of +/-12 Hz, with the true answer somewhere in between.
– CJ Dennis
Jul 23 at 5:36
@CJDennis: You could interpolate the three greatest magnitudes with a quadratic polynomial to estimate the maximum in the magnitude.
– joriki
Jul 23 at 5:45
@CJDennis: Doing that with Wolfram|Alpha yields a maximum around $20.34$, corresponding to $20.34cdot44100textHz/2048approx438textHz$.
– joriki
Jul 23 at 5:52
@CJDennis: Or you could perform the calculation I suggested in the last paragraph of the answer to get the functional form of the result depending on the input frequency, and then try to use that for a more specific method to estimate the frequency.
– joriki
Jul 23 at 5:54
Possibly, if I understood the last paragraph...
– CJ Dennis
Jul 23 at 9:51
How do you get from "727.024048,-150.774758", "-543.414483,118.240910" to 440 Hz? As I guessed, there are two results with an error of +/-12 Hz, with the true answer somewhere in between.
– CJ Dennis
Jul 23 at 5:36
How do you get from "727.024048,-150.774758", "-543.414483,118.240910" to 440 Hz? As I guessed, there are two results with an error of +/-12 Hz, with the true answer somewhere in between.
– CJ Dennis
Jul 23 at 5:36
@CJDennis: You could interpolate the three greatest magnitudes with a quadratic polynomial to estimate the maximum in the magnitude.
– joriki
Jul 23 at 5:45
@CJDennis: You could interpolate the three greatest magnitudes with a quadratic polynomial to estimate the maximum in the magnitude.
– joriki
Jul 23 at 5:45
@CJDennis: Doing that with Wolfram|Alpha yields a maximum around $20.34$, corresponding to $20.34cdot44100textHz/2048approx438textHz$.
– joriki
Jul 23 at 5:52
@CJDennis: Doing that with Wolfram|Alpha yields a maximum around $20.34$, corresponding to $20.34cdot44100textHz/2048approx438textHz$.
– joriki
Jul 23 at 5:52
@CJDennis: Or you could perform the calculation I suggested in the last paragraph of the answer to get the functional form of the result depending on the input frequency, and then try to use that for a more specific method to estimate the frequency.
– joriki
Jul 23 at 5:54
@CJDennis: Or you could perform the calculation I suggested in the last paragraph of the answer to get the functional form of the result depending on the input frequency, and then try to use that for a more specific method to estimate the frequency.
– joriki
Jul 23 at 5:54
Possibly, if I understood the last paragraph...
– CJ Dennis
Jul 23 at 9:51
Possibly, if I understood the last paragraph...
– CJ Dennis
Jul 23 at 9:51
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859988%2fhow-to-interpret-the-results-of-a-discrete-fourier-transform%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Why don't you just try it? If you don't want to install a library, there are lots of online FFT calculators.
– joriki
Jul 23 at 4:19
@joriki I want to understand DFT, not use a black box. I also don't want to type in 2048 values.
– CJ Dennis
Jul 23 at 4:25
You don't have to type them, you can generate them automatically. And it will help you understand them. You're asking us "What do the result data look like (the $2048$ transformed values)?" How are we less of a black box than the online FFT calculator?
– joriki
Jul 23 at 4:30
@joriki Because a human will say "The reason why we see X at Y is because of Z". A black box can't teach me why.
– CJ Dennis
Jul 23 at 4:32
Please take a look at this guide on how to ask a good question, especially the section "Include your work". In this case, I think showing your own effort would include first taking a look at what the result looks like and then describing what you don't understand about it (e.g. "I don't understand why the result seems to have a sinusoidal form"), rather than asking us to describe something to you that you could easily see for yourself.
– joriki
Jul 23 at 4:37