Reply by February 28, 20082008-02-28
On Feb 28, 4:23 am, Tim Wescott <t...@seemywebsite.com> wrote:
snip
> > OK. This will be the third time I've stated this in this thread, so > please pay attention: > > The FFT behaves as if the input data is cyclic, with the > last point in the data being effectively adjoint to the first. > > With most data that's going into an FFT the actual data isn't cyclical, > or it isn't cyclical with a period exactly equal to the length of the > FFT. Thus, the inevitable difference between the first and last points > in the data array generates a false response in the FFT, because the FFT > treats it as whopping huge discontinuity. > > This is the whole reason you need to window data going into an FFT -- to > get rid of the discontinuity that the algorithm will see. >
This seems to be the real cause of the problem - one that I can get rid of by windowing with a window which drops to zero at both ends, or by removing the DC and linear trend and adding them back in after the FFT. I have tried a number of windows, and seem to have solved the problem completely now. I was worried initially that the actual generation process was at fault, but it was just the way I measured the output spectrum leading me to believe that. Thanks Tim, Bharat and Jerry - this has been an extremely educational discussion. Cheers Marc
> -- > > Tim Wescott > Wescott Design Serviceshttp://www.wescottdesign.com > > Do you need to implement control loops in software? > "Applied Control Theory for Embedded Systems" gives you just what it says. > See details athttp://www.wescottdesign.com/actfes/actfes.html
Reply by Jerry Avins February 28, 20082008-02-28
bharat pathak wrote:
> Jerry, > > Thanks for your suggestion. Maybe the point was well mentioned > but I could not understand. Since I am still on the learning > side of the curve, it will take sometime to grasp the fundamentals. > > My suggestion, in case if you want to consider. Please try to > be little bit more patient with people on the forum. All of them are > not as good as you are in DSP, and hence the same concept has > to be told to them multiple number of times so that they can grasp > it. > > Please take this message in good faith. Maybe I am wrong. > > Thanks and Regards > Bharat Pathak > > >> Oh come on; the explanation was given already. Low frequencies >> predominate in i/f^2 noise. Therefore, samples can't be completely >> uncorrelated from their neighbors. Can you take it from there?
Well, my impatience arose from your not having addressed the point when it came up, not from your not knowing. An explanation was given, you seemed to accept it, and then it turns out that you didn't understand it. Here is Tim Wescot's remark way back in the thread: "This gets particularly bad when you try this with data from integrated white noise, because the Nth sample is a random walk away from the 1st; with such high variance your expected step is large. With a double integrator your expected step is _huge_. " The samples are highly correlated once you color the noise. Low frequencies are greatly emphasized. Low frequencies imply a correlation across the FFT data set, but the period is uncertain. Therefore, a rectangular window introduces the same kind of artifacts with 1/f^2 noise that it does with any broadband signal. So a nice tapered window helps. Jerry -- Engineering is the art of making what you want from things you can get. &#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;
Reply by Tim Wescott February 28, 20082008-02-28
On Wed, 27 Feb 2008 20:35:51 -0600, bharat pathak wrote:

>>With most data that's going into an FFT the actual data isn't cyclical, >>or it isn't cyclical with a period exactly equal to the length of the >>FFT. Thus, the inevitable difference between the first and last points >>in the data array generates a false response in the FFT, because the FFT > >>treats it as whopping huge discontinuity. > > Agreed Tim, > > My only doubt is. > > Do you need to window the data if it is gaussianly distributed? > > All this windowing makes sense for periodic data, because only > for that you will get discontinuity at boundaries. A random data > is random anyway. So what additional advantage will you get when > you window random data?? It is anyway discontinous throughout. > > Please clarify. > > Regards > Bharat Pathak > > Arithos Designs > www.Arithos.com
You are confused in at least three ways here: Random data does not have to be independent from point to point. As an extreme example, if I have an algorithm that says "roll one die, then write down the answer 512 times", I can give you a sheet with 512 identical numbers, but it's still random data that is the outcome of a random process. Just because data has a Gaussian distribution doesn't mean that it's from a random process. It _probably_ is, but it isn't _necessarily_. Just because a process is random doesn't mean that its output has a Gaussian distribution. Flipping a coin is a random process, but the distribution of the outcomes is bivariate, which is not at all Gaussian. In this case the data has a huge amount of correlation to past values, so much so that it it highly continuous as it wanders away from the starting point. As such, you shouldn't just _worry_ that it'll have a markedly different value from the start, you can almost _depend_ on it (although with enough experiments you can find a sample that has an arbitrarily small difference). -- Tim Wescott Control systems and communications consulting http://www.wescottdesign.com Need to learn how to apply control theory in your embedded system? "Applied Control Theory for Embedded Systems" by Tim Wescott Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html
Reply by bharat pathak February 27, 20082008-02-27
Jerry,

    Thanks for your suggestion. Maybe the point was well mentioned
    but I could not understand. Since I am still on the learning
    side of the curve, it will take sometime to grasp the fundamentals.
    
    My suggestion, in case if you want to consider. Please try to 
    be little bit more patient with people on the forum. All of them are
    not as good as you are in DSP, and hence the same concept has
    to be told to them multiple number of times so that they can grasp
    it. 

    Please take this message in good faith. Maybe I am wrong.

Thanks and Regards
Bharat Pathak


>Oh come on; the explanation was given already. Low frequencies >predominate in i/f^2 noise. Therefore, samples can't be completely >uncorrelated from their neighbors. Can you take it from there?
Reply by Jerry Avins February 27, 20082008-02-27
Tim Wescott wrote:

   ...

> To be completely correct you shouldn't multiply by -1 in one stage. You > should multiply by i in two. That gets a bit difficult when you're > working with op-amps, of course.
I think the difference is aesthetic (and real). Jerry -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
Reply by Jerry Avins February 27, 20082008-02-27
bharat pathak wrote:
>> With most data that's going into an FFT the actual data isn't cyclical, >> or it isn't cyclical with a period exactly equal to the length of the >> FFT. Thus, the inevitable difference between the first and last points >> in the data array generates a false response in the FFT, because the FFT > >> treats it as whopping huge discontinuity. > > Agreed Tim, > > My only doubt is. > > Do you need to window the data if it is gaussianly distributed? > > All this windowing makes sense for periodic data, because only > for that you will get discontinuity at boundaries. A random data > is random anyway. So what additional advantage will you get when > you window random data?? It is anyway discontinous throughout. > > Please clarify.
Oh come on; the explanation was given already. Low frequencies predominate in i/f^2 noise. Therefore, samples can't be completely uncorrelated from their neighbors. Can you take it from there? Jerry -- Engineering is the art of making what you want from things you can get. &#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;
Reply by Jerry Avins February 27, 20082008-02-27
Tim Wescott wrote:

   ...

> The word "metastable" means a lot of different things depending on > context -- check Wikipedia for a few of them. The definition that I > remember refers to continuous-time integrators, 'on paper' if you will.
Let's not for the metastable state a flip-flop can hang up in if the toggle conditions aren't all met. ... Jerry -- Engineering is the art of making what you want from things you can get. &#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;
Reply by bharat pathak February 27, 20082008-02-27
>With most data that's going into an FFT the actual data isn't cyclical, >or it isn't cyclical with a period exactly equal to the length of the >FFT. Thus, the inevitable difference between the first and last points >in the data array generates a false response in the FFT, because the FFT
>treats it as whopping huge discontinuity.
Agreed Tim, My only doubt is. Do you need to window the data if it is gaussianly distributed? All this windowing makes sense for periodic data, because only for that you will get discontinuity at boundaries. A random data is random anyway. So what additional advantage will you get when you window random data?? It is anyway discontinous throughout. Please clarify. Regards Bharat Pathak Arithos Designs www.Arithos.com
Reply by Tim Wescott February 27, 20082008-02-27
bharat pathak wrote:
> Tim, > >> Check your math. An single integrator is unstable in the BIBO sense, >> because a (bounded) DC input will make the output grow without bound. It > >> does not, however, oscillate. A single integrator, however, _is_ stable > >> in the sense that there are no initial conditions to the system that will > >> cause the output to grow without bound with a zero input -- when I was in > >> school they referred to this sort of thing as a 'metastable' system. > > I checked my math. When it comes to implementation, either you > will model it on machine or hardware. both of them have precision > limitation (fixed or floating), when the output grows beyond the > dynamic range it rolls over and this causes large cycle oscillations. > I was referring to this. Yes definitely on peice of paper there are > no oscillations.
I was referring to theory. In practice you may see oscillations, you may see the number getting "stuck", you may see resistors turn to smoke -- there are many behaviors, all of them beyond the realm of linear system analysis. For Marc's problem he only needs to limit the time that he simulates, and nothing will overflow.
> Metastability is a condition of a Flip-Flop and when > they put 2 flip-flops the probablility of occurence becomes way too > low, to see it in a lifetime of the device. Can you cite a reference > where "metastability of digital integrator" is mentioned. I would > like to enhance my understanding.
The word "metastable" means a lot of different things depending on context -- check Wikipedia for a few of them. The definition that I remember refers to continuous-time integrators, 'on paper' if you will.
>> The FFT acts as if the input data is periodic, so any discontinuities in > >> the data between the first and last samples appears in the FFT result as > >> a signal, just as if that same discontinuity had been smack in the >> middle. This is the whole point of windowing. In this case, the input >> to the system is random noise, and the two integrators will generate a >> considerable bias at the end of the run. This bias must be dealt with >> before anything meaningful can come out of the FFT, and windowing is one > >> way to accomplish this. > > Where is the question of "discontinuity of random data" at boundaries. > I don't understand this please explain. The data itself is random > in nature, so according to me discntinuity at boundaries do not make > sense. In case if you have any document reference, I would like to > read. >
OK. This will be the third time I've stated this in this thread, so please pay attention: The FFT behaves as if the input data is cyclic, with the last point in the data being effectively adjoint to the first. With most data that's going into an FFT the actual data isn't cyclical, or it isn't cyclical with a period exactly equal to the length of the FFT. Thus, the inevitable difference between the first and last points in the data array generates a false response in the FFT, because the FFT treats it as whopping huge discontinuity. This is the whole reason you need to window data going into an FFT -- to get rid of the discontinuity that the algorithm will see. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" gives you just what it says. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by Tim Wescott February 27, 20082008-02-27
Jerry Avins wrote:
> Tim Wescott wrote: > > ... > >> Note that a _double_ integrator is not 'metastable' -- a nonzero state >> in the first integrator will cause the output to grow without bound >> unless you get just the right input to the system. Note also that a >> system with any collection of non-identical poles on the stability >> boundary will be metastable (and pretty weird, too). > > An interesting case of metastability is a pair of cascaded integrators > in which each is driven by the other's output (with an inversion in > there somewhere). An analog implementation is a bit difficult to > stabilize, but digitally, that's fairly easy. Do you recognize the > quadrature oscillator? >
Indeed, and it's one of the cases of a system with a pair of non-identical poles on the stability boundary. To be completely correct you shouldn't multiply by -1 in one stage. You should multiply by i in two. That gets a bit difficult when you're working with op-amps, of course. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" gives you just what it says. See details at http://www.wescottdesign.com/actfes/actfes.html