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.

Can anybody tell me what result of discrete fourier transform means? I know all theoretical stuff and pretty graphs, that it is a change of domain from time to frequency and so on.

But I want to know what result means.

Example 1. Let's say I have a vector of 256 values. Every each of them is equal to 9.81. Result of FFT is 256 numbers equal to 0. Why?

Example 2. Again I have a vector of 256 values. 255 of them are equal to 9.81, and one of them (last one) is equal to 1.00

As a result of FFT transform I get a vector of 256 values, with first 255 ranging between 8.810 and 8.91, and last one equal to 0. What does it mean?

EXAMPLE 3 - REAL LIFE SCENARIO - KEY QUESTION I am recording data from an accelerometer. I record 256 values. Depending on whether I record walking up the stairs, or sitting, I get different result from Fourier Transform ran on this data. What is the significance of each number in the vector of 256 values? The two vectors from fourier transform will be different from each other, by looking at them, what do they tell me about samples from which they originated?

The resultant vector of 256 values represents decomposition of acceleration values into what?

My wrong understanding

I am told that domain becomes frequency instead of time. So numbers along x axis represent frequency. Frequency 1, frequency 2, ... frequency 256. For a sample of 256 numbers.

So my undersanding was:

If I have such sample:

4,8,15,16

then each number has a frequency of 1. So if I plot a graph with x axis that represents, at tick labeled 1 I would put value of 4, and leave tick 2, tick 3 and tick 4 at 0.

If sample was:

4,4,4,4

Then I would have {0,0,0,1}

If sample was:

4,4,8,8

Then I would have {0,2,0,0}

But this is not fourier transform, to me it looks like frequency distribution. Can anybody tell me then what do actual VALUES that I get in return vector mean?

EDIT: To be clear, I am not asking how we arrive at these values. I want to know how to interpret these values, what do they tell me about input.

share|improve this question
1  
In Example 1, only 255 values of $\hat x$ are $0$, and one of them has a nonzero value which depends on the chosen normalization. –  Christian Blatter Jun 8 '13 at 9:36
    
I'm not sure what kind of software you are using to compute these, but Example 2 doesn't look right either. If your program is returning a vector, be careful about the indexing. I suspect that there's a zeroth element you are ignoring, but which contains valuable information, and that the 256th element, which is zero in both of your examples, is actually not part of the answer. The elements of the DFT should be complex numbers. In Example 2 the zeroth element will have different magnitude (but nonzero) than the other 255 elements, which will all have equal magnitude. –  Will Orrick Jun 8 '13 at 9:47
    
I thought that results of DFT are magnitudes of complex numbers? –  LucasSeveryn Jun 8 '13 at 9:50
    
Well, you might want to focus on the magnitudes, which tell you the amplitudes of various frequency components, but the phases are important too since, without them, you can not reconstruct the original signal. If you are looking at magnitudes only, then the numbers in Example 2 should definitely be constant, except for the zeroth component, so the variation between 8.81 and 8.91 looks like some sort of numerical precision issue. –  Will Orrick Jun 8 '13 at 9:59
    
This is possible. Would you be able to explain real life example from the question? –  LucasSeveryn Jun 8 '13 at 10:03

4 Answers 4

up vote 4 down vote accepted

Let me suggest you a game to make it clear: Create the inverse Fourier that means construct a function $Y(t)$ that describes your sequence.

Point all your data versus time. Then start using the following function (in Mathematica or any other math program) (instead of complex expression this is easier to understand the connect to roots of unity):

$$y_i(t,k)= \sum_{n=1}^k \frac{1}{k} \cos\left(\frac{2 \pi (n-1) t}{k}\right)$$

(Discrete)Plot it and test! You may need to add a couple of different such functions $y_i(t,k)$ together (superposition) while every function with different $k$ and also multiplied perhaps with different amplitudes $a_i$ to get your function $Y(t)$ (like playing LEGO):

$$Y(t)=\sum_i a_i\; y_i(t,k)$$

This equation would as good as possible mimic (inverse Fourier) your sequence. If you do so you will understand that the transform is exactly the opposit way, and what its details value for you.

I did this quite often and works great to have sequences comprehensive.

Your first example and a period of $k=2$ for instance trivially:

$$Y(t)=y_1(t,2)= 9.81 \sum_{n=1}^2 \frac{1}{2} \cos\left(\frac{2 \pi (n-1) t}{2}\right)$$

PS: By the way $y_i(t,k)$ converges.

Additional explanation:

I hope I got the set up of your question correctly: You have discrete sequences of data like $\{9.81,...\}$ or $\{9.81,...,1.00,9.81...\}$ on the time line and transform these via Fourier to frequency domain.

Perhaps I understand what is your issue, and this is probably deeper going (frequency/amplitude uncertainty principle). I brought above an exercise (a game that should help) but lets try to answer your questions more directly regarding the values.

Can anybody tell me what result of discrete fourier transform means?

The result of the Fourier Transform as you will exercise from my above description will bring you only knowledge about the frequency composition of your data sequences. That means for example 1 the zero 0 of the Fourier transform tells you trivially that there is no superposition of any fundamental (eigenmode) periodic sequences with corresponding frequencies. This is why I wrote you $Y=y_1$. Your sequence is a periodic eigenmode of itself. Trivially your numbers of value 9.81, how many they might be (256), do not provide any additional information than they have in the sequence itself, because they are just the amplitude of your preiodic sequence which is its own eigenmode. So the Fourier transform tells you: there is a trivial case of frequency of eigenmode sequence and your numbers tell you there is trivial case of amplitudes - i.o.w NOTHING CHANGES in your sequence the behaviour is of no change. In other words you will learn here that the spectrum contains only one eigenmode and that is the sequence itself with a ground amplitude 9.81. Nothing more than this!

The second example is drammatic different. The amplitude $(1.00-9.81)$ (actually the difference) is carrying great information (as for example the location of a particle in physics, certain behaivourial change in the sequence/ accelleration...). However in order to precisely point this out you need a Fourier that contains a spectrum of frequencies. So remind the case of wave and particle in physics, when you want to locate the particle at a certain time/location (analogue to your $(1.00-9.81)$ signal at a certain time) that means precise amplitude, you would need all fundamental frquencies and waves/modes of the spectrum to sum them up and obtain the $(1.00-9.81)$ at a percise certain time point (this is why in my previous message I wrote as good as possible). In an abstract interpretation this superposition and sum up is implicitly done by your measurement instrument, and it points precisely to $(1.00-9.81)$ at a percise certain time point i a sequence. The problem however is that when you have obtained this way a precise $(1.00-9.81)$ at a certain time then you (your device) can not observe the frequencies, because you summed them up (implicitly) in the waves; in reverse if you perform a Fourier transform on the data sequence recorded, as you did, you obtain all the frequencies of the fundamental waves/modes composing your signal $(1.00-9.81)$ but at the cost that you can not more precisely fix the amplitude $(1.00-9.81)$ (of course in process of your decomposition the result is decomposed and scattered).

This is the uncertainty principle of any spectrum/Fourier. Unfortunately what happens in your thought scenario is that you want to perform a Fourier transform but ask for the meaning of the amplitudes ($(1.00-9.81)$). The answer is clear: The Fourier transform / spectrum of frequencies does not give you any information about the amplitude of the superposition.

Side note: At the same time keep into mind that the first example is the buttom line or callibration of the second example.

Annecdotic: The first example is an orchestra of one drum and itself repeating at a certain frquency and 9.81 pitch. The second could be an orchestra of the same drum playing at the same frequency and 9.81 pitch but in addition many instrumental players who are scilent all time except of precisely one instance of time, when playing one singular shot of 1.00 pitch.

For example 3 we learned already that the Fourier transform and the spectrum of frequencies do not give you any information about your absolute values in time domain (pitch)! But it gives you information on how often in a sequence you will change to sit position or vice versa. So if the spectrum shows more high frequencies bandwidth, that means you change often your position and if low frquencies bandwidth it shows you less change position. The Fourier transform will tell you how you behave, whether you accellerate more often up and down or less. It does not give you any information about the amplitudes (uncertainty paradox). Trivially the information about the amplitudes is already what you see in the time domain.

So before interpreting your data decide whether you observe in time domain (amplitudes and absolute value of your data) or frquency domain (frequency, behaviour, change).

The resultant vector of 256 values represents decomposition of acceleration values into what?

Into a spectrum of frequencies that is a characteristic fingerprint of your accellaration behaviour brought in that sequence of data record.

Hope this helps you to better understanding and is Answer to your Question. I still suggest you to do the exercise I proposed. Nothing is better than own experience.

share|improve this answer

It is completely normal to get 0 if the values are equal. This comes from an equality of the roots of unity of powers of 2, and for DFT you always extends to powers of two (esp if you do programming, in order to get from O(N^2) to O(nlogn).

You can see on wikipedia.

What DFT does has to do with polynomials. You can transform your list into a polynomial and then compute the values of that polynomial at the roots of unity of the closest power of 2 which is bigger than the number of items in your list.

Eg. 4,3,4,1 can be represented as $4 x^3 + 3x^2 + 4x+ 1$.

In your 4,4,4,4 example, you would get $4 x^3 + 4x^2 + 4x+ 4$. Because of the fact that DFT evaluates the polynomial at the roots of unity, in this case you will get 0 (you can check this yourself, the root of unity of order 4 is $i$.)

In short, from a list of numbers -> polynomial $p$. let the degree of the polynomial be $k$ with $k$ power of 2. Then if $w_k$ is the basic root of unity of order k, the result of the dft at index $t$ will be $p(w_k)^t$., where $t$ ranges betweeen 0 and $k-1$.

share|improve this answer

You're looking at the frequency of a certain number occuring, but instead it's actually supposed to give you the frequency of the sequence as if it were a wave. For example, if you'd drawn a sine wave on an Etch-a-Sketch, you could get a sequence of discrete values approximating it. That is, $(x,x,x,x)$ would not have a frequency at 4. $(x,y,x,y)$ would have a frequency at 2, but $(x,x,y,y)$ would have a frequency at 4. Ignoring alias frequencies, anyway.

share|improve this answer
    
But what do these values say about input? I am recording data from an accelerometer. I record 256 values. Depending on whether I record walking up the stairs, or sitting, I get different result from Fourier Transform. What is the significance of each number in the vector of 256 values? The two vectors from fourier transform will be different from each other, by looking at them, what do they tell me about samples from which they originated? –  LucasSeveryn Jun 8 '13 at 3:06
    
Well, if you were doing it to music it would give you a graph of what you hear, rather than what the sound wave looks like. So, if you took an accelerometer on a swing set I'd expect you'd see a bump that indicated how rapidly the swing swung as the position of the bump. –  Loki Clock Jun 8 '13 at 3:09
    
Yes, this is all general. I would like to know what do values tell me? For example, what does the value at index 10 mean? –  LucasSeveryn Jun 8 '13 at 3:11
    
If the frequencies are in Hertz, it says how much of the signal is dedicated to the same motion happening 10 times a second. But the point of inventing the Fourier transform is that any signal could be broken down into frequencies - the waves of that frequency are all mixed in to create the wave, and because of wave superposition it's usually not obvious how they relate. The best way to understand what this means is to edit the frequency space version of a familiar function and then look at how the inverse transform changes. –  Loki Clock Jun 8 '13 at 3:16
    
But what if input is in m/s^2? Could you take look at my real life scenario from the question? –  LucasSeveryn Jun 8 '13 at 3:32

Adding to what others have said, you can think of the DFT as decomposing your (discrete) signal into a linear combination of [discrete sample values from] basis functions. The equations for these come directly from the DFT definition:

$$ c_k(i) = cos(2\pi k i/N)\\ s_k(i) = sin(2\pi k i/N) $$ Note that these functions have an amplitude of 1.

So the reason why you get many zero values, and a single non-zero value in example 1 is that your signal can be expressed by just scaling one of these functions, namely where the frequency k = 0 (in this case $c_k(i) = 1$ and $s_k(i)=0$). As mentioned above, the exact result of the DFT here depends on the normalisation, but the idea is that the value is a scaling factor which can be used to obtain the original data.

For example 2, you now have to find a new linear combination to express your data set. This won't be exactly the same since the signal can't fully be expressed by one component (the last value is 1).

Now for example 3. There's a few things you can more easily see from data in frequency domain. For example, say your test person walks up the stairs, then you should see a frequency spike at the frequency of the footsteps. If they go up one step every other second, there will be a spike at $f=0.5$ in your DFT (assuming you sample once per second). Similarly, if you sample 4 times per second, there would be a spike at $f=1/8$.

I'm not sure what kind of information you're expecting to get from the data. Do you have a clear reason for looking at frequency domain data? Do you want to find periodic events that happen during the measurement (and want to know how frequently they occur, and how much of the measurement they make up)? The DFT will give you spikes of various magnitude at these frequencies, e.g. if you're not just walking up the stairs ($f=0.5 Hz$) but also shaking the accelerometer at $f = 3 Hz$ then you'll easily be able to see these two components in the DFT.

For interpretation, keep in mind this is limited to frequencies that you can actually measure with your sampling rate. Also, adding to what you asked above ("what if input is in $m/s^2$"), the interpretation of this entirely depends on your data. Units don't matter for the DFT, since you're just looking at data values. The values are acceleration in this case, so what does it mean that your acceleration periodically changes over time? This goes back to the earlier question of why you're using the DFT in the first place. For example, you could see that major jerks occur at frequencies x, y and z in your data, or filter out some noise with a high-pass filter in order to then compute statistical properties of the space domain data.

share|improve this answer

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.