2
$\begingroup$

Generally when one takes the FFT of a signal it "works" over the whole bandwidth dividing up the spectrum into chunks given by the resolution. If the bandwidth of the signal is 10khz and your resolution is 1000 then each "frequency" represents a chunk of 10hz(each bin is 10hz in size).

The problem with this method is that it gives the same "size" to each bin even though lower frequencies loose resolution. e.g., a 10hz bin around 25hz frequency contains much more information than 10hz at 8kz. This issue is not hard to fix with the analytical FT since it is just a matter of scale. Is it possible adapt the FFT to have a frequency dependent bin-size?

Essentially when we divide up the frequency range into n chunks we want lower frequencies to have more accuracy since they are lower frequencies.

e.g., I might want a resolution of 0.1hz in the lower frequencies and 10hz in the higher frequencies. The problem with the current FFT is that we must use the highest resolution overall. That is, Because I want a 0.1hz resolution in the lower frequencies I MUST have an 0.1hz resolution in the higher resolutions. This means I'll require a much higher n-point transform than I really need.

  • 1
    Have you looked at wavelets? (By the way, I think your description of chunks or bins of the frequency range being represented by individual frequencies in the Fourier analysis is misleading.)2012-07-22
  • 0
    @joriki There is nothing misleading about using the term bins. It is very similar to that of a histogram. I believe you are confused on terminology/understanding my question rather than the term being misleading.2012-07-22
  • 0
    I didn't say that the term "bins" is misleading. I believe your entire description of chunks or bins of frequency range being represented by individual frequencies is misleading. The frequencies in the discrete Fourier analysis stand only for themselves; they don't "represent" any nearby frequencies.2012-07-22
  • 0
    @joriki: I'm sorry but your understanding of the DFT is a bit skewed. The DFT transforms a sequence of numbers to another sequence of numbers BUT when you interpret those numbers to physical meaning then do represent a "wash" or a "bin" of frequencies. There are many reasons for this and in the real world devices that convert signals to the digital domain are not even accurate enough and so each data point represents a "bin" around some point. In any case your only correct if we have infinite accuracy which we don't and the reason why I would like a low-frequency weighted transform.2012-07-22
  • 0
    To see I am correct all you have to do is use any software that displays the fourier transform or spectrogram AND does not interpolate(which hides smooths over the issue). You will notice that lower frequencies are constant over a range that is much larger than for higher frequencies in terms of percentages... and this because the bin size is constant and independent of the frequency. And regardless of what you want to call it, the frequency resolution is independent of the frequency itself. This dictates that higher frequencies have higher resolution in terms of percentage.2012-07-22
  • 4
    I don't think you're use of "correct" is appropriate here. I deliberately didn't say that you were incorrect, since this talk of bins and chunks being represented isn't formal enough to be correct or incorrect. I said that it's misleading, and I said so in the context of a site on mathematics. You may well be right that it has its merits in the context of inaccurate measurements, but I do believe that for someone trying to understand the discrete Fourier transform mathematically it can be misleading.2012-07-22
  • 0
    @joriki Well, we can argue all day long about terminology and what is misleading and what is not and all that. It's irrelevant because it has nothing to do with the question ask. Whether I use the term bin, partition, or whatever is basically irrelevant. In any case the issue has nothing to do with the theoretical nature of the fourier transform BECAUSE it is only an issue when we go into the discrete case... which is generally used for practical things and not for some abstract theoretical reasons.2012-07-22
  • 0
    I'm also not here to try and teach what a DFT is or not and, regardless, if we need to use the concept of "bins" or not on a mathematical foundation ONE sure needs to understand it from a practical perspective. While I could have used another term than "bin", your objection to me trying to use a common term to describe a problem where it actually makes since for most people with "practical" experience is a bit pedantic and counter productive.2012-07-22
  • 0
    This is going to be my last reply here; I don't like being shouted at in caps. Please note that the site is for the benefit of everyone, not just the person asking the question, so if I believe that something is misleading, I point it out irrespective of whether it's central to what the person asking the question is focussing on.2012-07-22
  • 0
    @AbstractDissonance : please be civil. I've removed your last comment.2012-07-23

1 Answers 1

1

It's called the nonequispaced fft or non-uniform discrete Fourier transform:

Code can be found here

  • 0
    I am not referring to a non-uniform independent variable(usually time) but the frequency parameter(w). When you take the FFT of a function you end up with an array of numbers representing the magnitudes of frequencies **EQUALLY** spaced(they are partitioned uniformly just like time is). I do not want them equally spaced. NUDFT is used for non-uniform input sampling while I still have uniform input sampling. It is sort of the reverse of what I want. I want uniform input to non-uniform output rather than non-uniform input to uniform output.2012-07-22
  • 0
    @AbstractDissonance: The Fourier transform is symmetric with respect to "input" and "output"; which domain you call frequency and which you call time is just a matter of convention.2012-07-22
  • 0
    @joriki: No, the transformation itself maybe symmetric in that it is it's own inversion BUT it matters a great deal what you call frequency and what you call time when your signal is time based. It maybe possible to adapt the NUDFT for my needs but as it stands it does not do what I am asking. i.e., it takes the independent variable(whatever you want to call it) as non-uniform and outputs a uniform dependent variable. I want a non-uniform dependent variable. If I were to use the INUDFT to have a non-linear frequency partition THEN how do I get the frequencies in the first place?2012-07-22
  • 0
    @chaohuang What do you mean? If you mean basically use the inverse NUDFT then your wrong and if you would just think about it for a few minutes you would see why. Again, the NUDFT takes a non-unform set of points and gives a uniform set!!!! How the heck can I get a non-uniform set of points out of it IF it only gives a uniform set as output? You then are not understanding the difference between input an output. Now it is true one can use the inverse of the NUDFT to take a uniform set to give a non-uniform set BUT that presupposes several things about the INUDFT that may or may not be true...2012-07-22
  • 0
    For example, does an INUFFT even exist? If so, is it easy enough modify to convert the frequency parameters to the time parameters? Is it unique? Remember, I want to have a specific non-linear output partition that I specify. If the INUFFT returns some special partition then it will not solve my problem.2012-07-22
  • 2
    @AbstractDissonance: Please moderate your combative style. There's no need to imply that people haven't thought about what they wrote for a few minutes (especially people who tried to help you by providing an answer to your question), or to use four exclamation marks, or to describe someone's understanding as "skewed".2012-07-22
  • 0
    @AbstractDissonance: Regarding the content: As far as it makes any sense to distinguish between input and output, I don't see why you're dissatisfied with the method described under the Wikipedia link in the answer. I would have thought that $n$ is the "time" here and is equally spaced, and $z$ represent distinct frequencies that can be chosen arbitrarily. The article describes transformations between these in both directions. What is it that you want to be able to do beyond that?2012-07-22
  • 1
    @AbstractDissonance Calm down man. Did you see the code provided in the answer? They are exactly what you are looking for. The input (time-domain) is uniformly sampled, and the output (frequency domain) is non-uniform. So NUDFT can used for both cases, no matter the non-uniform is in time or frequency domain. [Here](http://141.213.232.243/bitstream/2027.42/85840/1/Fessler70.pdf) is another paper talking about exact what you want.2012-07-22
  • 0
    @joriki: "As a result of this, the computed Discrete Fourier Transform can also consist of unevenly sampled frequency values. It is however also possible to compute uniformly sampled frequency values from an unevenly sampled input signal." Do you not realize that it says nothing about "uniform to non-uniform" It does have non-uniform to non-uniform BUT you don't seem to realize that it is not an arbitrary non-uniform partition to some other arbitrary non-uniform partition but that they are related! Just like the uniform partition is related to the uniform partition in the DFT.2012-07-22
  • 2
    @AbstractDissonance: Here, too, this will be my last reply. Your tendency to quickly assume and claim that others don't "realize" the truth that you see, or that you have to "teach" them, is unconstructive. I don't want to interact in this manner, and I don't think you're increasing your chances of getting helpful answers by interacting this way.2012-07-22
  • 0
    @chaohuang: Thanks, that is what I am looking for. My point is simply that they are different things than what originally was said. (They maybe related in some abstract way BUT it doesn't mean one can just use one in place of the other and have it work). There also seems to be the problem that the same name is used for two different methods. In one case one has NU input and U output and the other it is U-input and NU-output(which is what I am looking for).2012-07-22
  • 0
    @chaohuang If you update your answer to include a link to the new pdf AND explain there is a difference between some NUDFT's and others I'll mark it correct.2012-07-22
  • 0
    @AbstractDissonance you are right, the proper name of the method you're looking for may be [nonequispaced fft](http://www-user.tu-chemnitz.de/~skunis/paper/KunisDiss.pdf)2012-07-22
  • 0
    @AbstractDissonance answer is updated.2012-07-22
  • 0
    @chaohuang thanks.2012-07-22