On Thu, 02 Mar 2017 10:43:24 +0100, Michael Plet <me@home.com> wrote:>On Wed, 01 Mar 2017 22:34:49 GMT, eric.jacobsen@ieee.org wrote: > >>On Wed, 01 Mar 2017 21:55:33 +0100, Michael Plet <me@home.com> wrote: >> >>>On Wed, 01 Mar 2017 20:31:16 GMT, eric.jacobsen@ieee.org wrote: >>> >>>>On Wed, 01 Mar 2017 10:57:36 +0100, Michael Plet <me@home.com> wrote: >>>> >>>>>Hi Group >>>>> >>>>>I'm sorry about posting all my formulas without any delay. >>>>>I just wanted to get them out there while they are new, so that other >>>>>people can use them if they want. >>>>> >>>>>Michael Plet >>>> >>>>Can I ask what your interest is in pursuing this? Is it academic >>>>interest or something else? Are you open to criticism on these? >>>> >>>>Feel free to contact me privately if you prefer. I was going to >>>>email you directly, but I suspect that me@home.com isn't actually your >>>>address. >>>> >>>> >>>> >>>>--- >>>>This email has been checked for viruses by Avast antivirus software. >>>>https://www.avast.com/antivirus >>> >>> >>>I have a background in Computer Science and Mathematics. >>>The reason I got interested in DSP is because of my love of music. >>>I want to and have already used DSP to analyse music. >>> >>>For that reason I derived my first formula. >>>Because I also like mathematical puzzles I enjoyed deriving more >>>formulas. >>> >>>I realise that a single formula is not enough to analyse a piece of >>>music with many events in both frequency and time. >>>I am very much open to criticism. >>> >>>Michael >> >>This sort of frequency interpolation has been around for a long time >>(many decades), with a lot of work having been done for subtle >>optimizations for various different applications. I've been involved >>directly in the context of signal processing for communication systems >>on this particular topic since the mid-1990s. The matlab/octave test >>suite I linked earlier was done during that early research, but I have >>a more developed test suite now that allows fairly quick testing and >>analysis of different methods. I plugged yours in over the last couple >>of days to see how it compared to other estimators. >> >>As I mentioned early on, the two-term estimators like you initially >>proposed generally suffer frequency-dependent errors, and it appears >>that yours is not an exception. You indicated in the results you >>posted that you used a phase of ~0.785 (radians, presumably), and at >>that particular phase the errors are masked. When I tried it there >>are substantial frequency-dependent errors at other phases, and the >>usual one that happens with two-term estimators is at zero frequency >>offset and zero phase, which also seems to be a problem with your >>two-term estimator. Yours also seems to have difficulty at pi >>radians and a few other phases. Randomizing the signal phase across >>trials helps to show whether the estimator is robust in these >>conditions. >> >>Even when the phase is favorable, though, the perforrmance is not >>favorably comparable to other estimators with much lower computational >>complexity. This is fairly typical, though, and I think may be part >>of why two-term estimators aren't very popular or at least don't get >>much attention. >> >>The last estimator you posted, using three terms, is not bad but is >>not as good as the usual estimators used as references (Candan's, >>Liao's, etc.), and is MUCH MUCH more computationally intensive. For >>that reason there isn't much motivation to use yours when there are >>better-performing estimators with much less computational complexity. >>I suspect that perhaps the large number of computations in yours, >>including transcendental functions, just adds a lot of accumulated >>quantization noise. >> >>Here are some results, with no added noise, which is the more >>interesting case for the bias-corrected estimators: >> >>http://ericjacobsen.org/Files/p5fintrpsims.jpg >> >>Your three-term estimator is the solid green trace. There are a >>number of other estimators in the same trials, including my old, >>simple one (black circles), my estimator with Candan's simple bias >>correction (blu x), Candan's complete estimator (magenta dots), Liao >>and Lo's correction to the QMJ estimator (red circles), and Lonnemo's >>estimator (black +). The bias-corrected or low-bias estimators are >>nearly indistinguishable at this level. >> >>Fig 1 is just the estimated frequency vs the test number, with test #1 >>being no frequency offset and then incrementing 1/10th of a bin offset >>with each test (so that test #6 is halfway between bins). The >>vertical axis is bin number. This just shows that the estimators are >>generally working. >> >>Fig 2. is the statistical variance of each estimator vs offset. Each >>offset has 5000 trials with random phase at each trial. >> >>Fig 3 is the statistical bias of each estimator vs offset. >>. >>FWIW, at this time the usual reference estimator for performance at >>high SNR is Candan's, because it matches the best performance with >>anything else out there and has the least relative computational >>complexity. >> >>For reference, Candan's estimator is computed as follows: >> >>First, compute delta using Jacobsen's (my) estimator, where y is the >>three-element complex-valued vector of the peak magnitude sample and >>the two adjacent samples. delta is then the interbin fractional >>error of the initial fequency estimate using only the peak bin. >> >>delta=real((y(1)-y(3))/((2*y(2))-y(1)-y(3))); >> >>Candan's estimator is then: >> >>freq=pkind+(atan((pi/tstlen)*c*delta))/(pi/tstlen); >> >>Where the resulting estimated frequency is in bins, pkind is the index >>of the peak magnitude sample, tstlen is the length of the DFT, and c >>is Candan's bias correction term which can be precomputed: >> >>c=tan(pi/tstlen)/(pi/tstlen); % Candan's correction term. >> >>In comparison your estimator requires numerous transcendental function >>computations as well as square roots, etc. For lower SNRs the noise >>tends to dominate performance so the simpler estimators tend to be >>preferable, e.g., mine with Candan's bias correction, which is just: >> >>delta=c*real((y(1)-y(3))/((2*y(2))-y(1)-y(3))); >> >>i.e., my estimator with one additional multiply. That's the blue x >>in the performance plots. >> >>There's a natural tradeoff between computational complexity and >>performance, with more complexity required for the higher SNR case >>where the estimator bias tends to dominate performance. Depending on >>the exact circumstances and desired properties (bias in middle or >>edges, max variance in middle or edges, etc., etc.), the tradeoffs may >>favor particular estimators over others, and there are a large number >>of existing estimators to pick from. >> >>In some applications divide operations are expensive and avoiding them >>is useful. For those applications other algorithms, like dichotomous >>search, may be favorable where the estimate is iterated down to the >>desired accuracy using (e.g.) vector multiplication with interpolating >>vectors. >> >>So it really does depend on what an implementer wants to accomplish >>and what tradeoffs are important in a particular application and >>implementation. If you're doing pitch detection that is a far >>different animal and other algorithms come into play. The estimators >>analyzed here pretty much all assume a single tone at the input, and >>if there is any other correlated energy present the performance can >>degrade substantially. If you're interested in music, pitch >>detection with signals rich in frequency content is also highly >>studied and gets discussed here from time to time, but the solutions >>are very different than the single-tone cases studied here. >> >> >> >>--- >>This email has been checked for viruses by Avast antivirus software. >>https://www.avast.com/antivirus > > >Thank you very much for taking the time to test my formula. > >I was a little puzzled by the first picture. It seems to indicate that >all the estimators are exact. >I thought some of them were approximations.The errors are so small at that scale, especially with no noise added, that they all look "exact". The variance and bias plots show the differences as tested, which are still small but the expanded scale highlights the different behaviors.>From a pure mathematical point of view my formulas are exact >regardless of phase and amplitude. >Of course as you say, quantization errors can occur when implementing >on a computer. > >I can understand from the discussion below that you used a complex >signal for testing. >I have only used DSP for real signals (music), so my formulas for bin >values have been based on real signals. >If it is possible for you to do a test with real signals as input, I >would appreciate that very much.Yes, this makes a big difference as the performance may be very different for a real-valued input. I probably won't have time to re-do the sim with a real input for a while, and the other estimators would no longer be comparable because they were all developed for complex input. I would point out, too, that there are a lot of advantages to mixing the audio spectrum to complex baseband and doing the processing as a complex-valued signal. In other words, mix the signal down by fs/4 so that the center of the bandwidth is at DC. That mixing operation can be done with only multiplies of +/- 1 and zero, so there is no loss of precision or distortion added. Mixing down to complex baseband allows the FFT size to be cut in half, so the processing complexity of the mix is more than made up for. The significant difference for the FFT coefficient interpolators is that at complex baseband there will only be one tone for a real-valued sinusoidal input instead of two (the tone and it's mirror at the negative frequency). This means that the sinx/x envelope of the spectral response (or dirichlet kernel if you prefer) will always be symmetric and independent of the bin number. Since a real-valued tone is made up of two complex exponential signals (at the positive and negative frequencies), their sidelobes interfere in a frequency-dependent manner which makes the frequency interpolation much more complicated. This helps explain why the complexity of your interpolator is much higher than those based on complex-valued inputs. So mixing to baseband helps in more than one way in this particular case, both in a substantial reduction in complexity by halving the size of the FFT, and by greatly simplifying the coefficient interpolating algorithm. I think this is also one reason why the vast majority of the frequency interpolating algorithms use complex inputs, because it is a much simpler, cleaner process. I think this is also why real-input optimized FFT algorithms aren't as common as one might otherwise think as discussed in the other thread. There is no loss of information or generality by mixing to complex baseband, but sometimes there are reasons to keep things in the real-valued domain, so your interpolator may be useful for those cases despite the complexity. The performance wasn't bad for complex inputs, so it may be very good for real-valued inputs. Fingers crossed I may be able to check that later in my simulations. --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
Sorry about the many posts
Started by ●March 1, 2017
Reply by ●March 2, 20172017-03-02
Reply by ●March 2, 20172017-03-02
>> >>Thank you very much for taking the time to test my formula. >> >>I was a little puzzled by the first picture. It seems to indicate that >>all the estimators are exact. >>I thought some of them were approximations. > >The errors are so small at that scale, especially with no noise added, >that they all look "exact". The variance and bias plots show the >differences as tested, which are still small but the expanded scale >highlights the different behaviors. > > >>From a pure mathematical point of view my formulas are exact >>regardless of phase and amplitude. >>Of course as you say, quantization errors can occur when implementing >>on a computer. >> >>I can understand from the discussion below that you used a complex >>signal for testing. >>I have only used DSP for real signals (music), so my formulas for bin >>values have been based on real signals. >>If it is possible for you to do a test with real signals as input, I >>would appreciate that very much. > >Yes, this makes a big difference as the performance may be very >different for a real-valued input. I probably won't have time to >re-do the sim with a real input for a while, and the other estimators >would no longer be comparable because they were all developed for >complex input. > >I would point out, too, that there are a lot of advantages to mixing >the audio spectrum to complex baseband and doing the processing as a >complex-valued signal. In other words, mix the signal down by fs/4 >so that the center of the bandwidth is at DC. That mixing operation >can be done with only multiplies of +/- 1 and zero, so there is no >loss of precision or distortion added. Mixing down to complex >baseband allows the FFT size to be cut in half, so the processing >complexity of the mix is more than made up for. > >The significant difference for the FFT coefficient interpolators is >that at complex baseband there will only be one tone for a real-valued >sinusoidal input instead of two (the tone and it's mirror at the >negative frequency). This means that the sinx/x envelope of the >spectral response (or dirichlet kernel if you prefer) will always be >symmetric and independent of the bin number. Since a real-valued tone >is made up of two complex exponential signals (at the positive and >negative frequencies), their sidelobes interfere in a >frequency-dependent manner which makes the frequency interpolation >much more complicated. This helps explain why the complexity of >your interpolator is much higher than those based on complex-valued >inputs. > >So mixing to baseband helps in more than one way in this particular >case, both in a substantial reduction in complexity by halving the >size of the FFT, and by greatly simplifying the coefficient >interpolating algorithm. I think this is also one reason why the >vast majority of the frequency interpolating algorithms use complex >inputs, because it is a much simpler, cleaner process. I think this >is also why real-input optimized FFT algorithms aren't as common as >one might otherwise think as discussed in the other thread. > >There is no loss of information or generality by mixing to complex >baseband, but sometimes there are reasons to keep things in the >real-valued domain, so your interpolator may be useful for those cases >despite the complexity. The performance wasn't bad for complex >inputs, so it may be very good for real-valued inputs. Fingers >crossed I may be able to check that later in my simulations. > > > >--- >This email has been checked for viruses by Avast antivirus software. >https://www.avast.com/antivirusThis is very interesting. Mixing to complex baseband is completely new to me. I will look into that. Thank you for the explanation. Computational performance is not important to me. I don't intend to do realtime processing. Michael
Reply by ●March 3, 20172017-03-03
On Wednesday, March 1, 2017 at 12:55:39 PM UTC-8, Michael Plet wrote:> ... >.I have a background in Computer Science and Mathematics. >.The reason I got interested in DSP is because of my love of music. >.I want to and have already used DSP to analyse music. >=20 >.For that reason I derived my first formula. >.Because I also like mathematical puzzles I enjoyed deriving more >.formulas. >=20 >.I realise that a single formula is not enough to analyse a piece of >.music with many events in both frequency and time. >.I am very much open to criticism. >=20 >.MichaelMichael Since you like music, math and puzzles, let me pose a puzzle for you to con= sider. First, some background. The discrete Fourier family transform music/voice schemes for both compress= ion for storage and transmission and for analysis/synthesis for generation = and analysis require the use of (non-rectangular) windowed overlapped trans= forms. Windowing and overlap are required to maintain fidelity of signal ch= anges in amplitude (required even if only to start and stop a tone) and fre= quency (which serve as important cues in music and speech). For an example of such a system look at a PhD thesis: A SYSTEM FOR SOUND ANALYSIS/TRANSFORMATION/SYNTHESIS BASED ON A DETERMINISTIC PLUS STOCHASTIC DECOMPOSITION By Xavier Serra October 1989 at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=3D10.1.1.76.2306&rep=3Dre= p1&type=3Dpdf I don't intend to sell you on this system or any particular window choice, = but the thesis provides a useful example and a discussion of historical and= implementation issues and some useful background references. My puzzle for you is to find an exact estimator for frequency in a windowed= transform. That's still a bit of a wide topic, so let me give more backgro= und and narrow it down some. There is a family of windows called "cosine sum" windows that have the char= acteristic that they can be applied in the time domain, but also in the fre= quency domain where they are applied by convolving the Fourier coefficients= with a small kernel. For example, the classic von Hann window has the kern= el coefficients: -1/4 +1/2 -1/4. This issue has already been examined by John Burgess[1] who developed an al= gorithm for up to 4-term cosine sum windows. (In Burges terms the von Hann = is a two coefficient window, by symmetry.) But Burgess' algorithm is not ex= act. He substitutes a small argument for sine of the small argument, but it= is general up to 4 terms. I suspect (hope) that choosing a cosine sum window will simplify the puzzle= . If you pick a cosine sum window already used in a music analysis/synthesi= s scheme and only find a solution for that set of constants, the algorithm = need not be general, simplifying a little more (more hope). Such an algorithm would be not only on-topic in comp.dsp, but also somethin= g that would actually be useful for people who follow comp.dsp to use! Dale B. Dalrymple [1] Burgess paper: Accurate analysis of multi-tone signals using a DFT John C. Burgess J. Acoust. Soc. Am. 116 (1), July 2004
Reply by ●March 3, 20172017-03-03
Don't ever apologize for posting 2 an unmoderated group on the internet. It's pretty much a lonely hearts club so anybody who posts something is adding to the conversation
Reply by ●March 3, 20172017-03-03
On Fri, 3 Mar 2017 10:38:34 -0800 (PST), dbd <d.dalrymple@sbcglobal.net> wrote:>On Wednesday, March 1, 2017 at 12:55:39 PM UTC-8, Michael Plet wrote: >> ... >>.I have a background in Computer Science and Mathematics. >>.The reason I got interested in DSP is because of my love of music. >>.I want to and have already used DSP to analyse music. >> >>.For that reason I derived my first formula. >>.Because I also like mathematical puzzles I enjoyed deriving more >>.formulas. >> >>.I realise that a single formula is not enough to analyse a piece of >>.music with many events in both frequency and time. >>.I am very much open to criticism. >> >>.Michael > >Michael > >Since you like music, math and puzzles, let me pose a puzzle for you to consider. > >First, some background. > >The discrete Fourier family transform music/voice schemes for both compression for storage and transmission and for analysis/synthesis for generation and analysis require the use of (non-rectangular) windowed overlapped transforms. Windowing and overlap are required to maintain fidelity of signal changes in amplitude (required even if only to start and stop a tone) and frequency (which serve as important cues in music and speech). > >For an example of such a system look at a PhD thesis: >A SYSTEM FOR SOUND ANALYSIS/TRANSFORMATION/SYNTHESIS >BASED ON A DETERMINISTIC PLUS STOCHASTIC DECOMPOSITION >By Xavier Serra October 1989 >at: >http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.2306&rep=rep1&type=pdf > >I don't intend to sell you on this system or any particular window choice, but the thesis provides a useful example and a discussion of historical and implementation issues and some useful background references. > >My puzzle for you is to find an exact estimator for frequency in a windowed transform. That's still a bit of a wide topic, so let me give more background and narrow it down some. > >There is a family of windows called "cosine sum" windows that have the characteristic that they can be applied in the time domain, but also in the frequency domain where they are applied by convolving the Fourier coefficients with a small kernel. For example, the classic von Hann window has the kernel coefficients: -1/4 +1/2 -1/4. > >This issue has already been examined by John Burgess[1] who developed an algorithm for up to 4-term cosine sum windows. (In Burges terms the von Hann is a two coefficient window, by symmetry.) But Burgess' algorithm is not exact. He substitutes a small argument for sine of the small argument, but it is general up to 4 terms. > >I suspect (hope) that choosing a cosine sum window will simplify the puzzle. If you pick a cosine sum window already used in a music analysis/synthesis scheme and only find a solution for that set of constants, the algorithm need not be general, simplifying a little more (more hope). > >Such an algorithm would be not only on-topic in comp.dsp, but also something that would actually be useful for people who follow comp.dsp to use! > >Dale B. Dalrymple > >[1] Burgess paper: >Accurate analysis of multi-tone signals using a DFT >John C. Burgess >J. Acoust. Soc. Am. 116 (1), July 2004Thank you Dale. That is a great mathematical puzzle (and challenge). Give me a couple of days and I'll see what I can come up with. Michael
Reply by ●March 3, 20172017-03-03
> >Michael > >Since you like music, math and puzzles, let me pose a puzzle for you to >consider. >[...snip...]> >My puzzle for you is to find an exact estimator for frequency in a >windowed transform. That's still a bit of a wide topic, so let me givemore>background and narrow it down some. > >There is a family of windows called "cosine sum" windows that have the >characteristic that they can be applied in the time domain, but also inthe>frequency domain where they are applied by convolving the Fourier >coefficients with a small kernel. For example, the classic von Hannwindow has the>kernel coefficients: -1/4 +1/2 -1/4. >[...snip...] Dale, It's nice of you to challenge Michael, but I can tell you that I have run down this path and it is either incredibly complicated or not possible. Furthermore, it is not necessary. First, the reason it is not possible, or extremely difficult, is due to the nature of the bin value formula for a pure tone. The best form of this equation for this purpose is the one I give as Equation 25 in my blog article "DFT Bin Value Formulas for Pure Real Tones" which can be found here: https://www.dsprelated.com/showarticle/771.php The bugaboo is the cos( beta_k ) term in the denominator. Generalizing a window function that can be implemented as "convolving the Fourier coefficients with a small kernel." Let's call K = ( k_{-1} k_0 k_1 ) be such a kernel. An example would be the Von Hann coefficients you provided of ( -1/4 +1/2 -1/4 ) Let's call the bins of an unwindowed DFT Z_k, and the bins of the windowed one W_k. W_k = ( Z_{k-1} Z_k Z_{k+1} ) dot K Deriving an exact formula for W_k would lead to an expression that has a cubic equation of cos( alpha ) in the denomitator and a quadratic equation of cos( alpha ) in the numerator which would include mixed values of U and V (which both also contain alpha). Solving for an exact frequency equation means manipulating the equations for W_{k-1}, W_k, and W_{k+1} (for a 3 bin equation) in order to eliminate the M, U, and V unknowns. If this is doable, and I'm not sure it is, it leaves you with a cubic equation of cos( alpha ). There is a generalized way to solve cubic equations, but it is much more complicated than the quadratic formula. Once you have solved for cos( alpha ), choosing the correct root, then the value of alpha will yield your frequency. If you step up to a five value kernel, you will similarly get a fifth degree equation for cos( alpha ) for which there is no general analytic solution available. Second, it is not necessary. The primary reason for employing a window function is to reduce the size of the side lobes (aka "spectral leakage") for all the tones in the signal. The conventional thinking[1] is the side lobes are undesirable because they can interfere with, and even mask, other tones that are in the signal. There is a better way to deal with this problem that I am working up to in my series of blog articles. It involves building a list of the tones that are present and iteratively calculating their parameters. It converges rapidly to very accurate values. In the case of a noiseless signal consisting of steady tones through the analysis frame, it converges to an exact answer. In the case of analyzing music, the latter assumption is generally not true. I have some other tricks that make it true on a piecemeal basis which I am currently working on coding (among other things). Yes, this also involves the concept of tone trajectories mentioned in the Phd thesis you referenced. Ced [1] "On the use of Windows for Harmonic Analysis with the Discrete Fourier Transform", fredrick j harris --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●March 3, 20172017-03-03
On Fri, 03 Mar 2017 16:31:55 -0600, "Cedron" <103185@DSPRelated> wrote:>> >>Michael >> >>Since you like music, math and puzzles, let me pose a puzzle for you to >>consider. >> >[...snip...] >> >>My puzzle for you is to find an exact estimator for frequency in a >>windowed transform. That's still a bit of a wide topic, so let me give >more >>background and narrow it down some. >> >>There is a family of windows called "cosine sum" windows that have the >>characteristic that they can be applied in the time domain, but also in >the >>frequency domain where they are applied by convolving the Fourier >>coefficients with a small kernel. For example, the classic von Hann >window has the >>kernel coefficients: -1/4 +1/2 -1/4. >> >[...snip...] > > >Dale, > >It's nice of you to challenge Michael, but I can tell you that I have run >down this path and it is either incredibly complicated or not possible. >Furthermore, it is not necessary. > >First, the reason it is not possible, or extremely difficult, is due to >the nature of the bin value formula for a pure tone. The best form of >this equation for this purpose is the one I give as Equation 25 in my blog >article "DFT Bin Value Formulas for Pure Real Tones" which can be found >here: > >https://www.dsprelated.com/showarticle/771.php > >The bugaboo is the cos( beta_k ) term in the denominator. Generalizing a >window function that can be implemented as "convolving the Fourier >coefficients with a small kernel." > >Let's call K = ( k_{-1} k_0 k_1 ) be such a kernel. An example would be >the Von Hann coefficients you provided of ( -1/4 +1/2 -1/4 ) > >Let's call the bins of an unwindowed DFT Z_k, and the bins of the windowed >one W_k. > >W_k = ( Z_{k-1} Z_k Z_{k+1} ) dot K > >Deriving an exact formula for W_k would lead to an expression that has a >cubic equation of cos( alpha ) in the denomitator and a quadratic equation >of cos( alpha ) in the numerator which would include mixed values of U and >V (which both also contain alpha). > >Solving for an exact frequency equation means manipulating the equations >for W_{k-1}, W_k, and W_{k+1} (for a 3 bin equation) in order to eliminate >the M, U, and V unknowns. If this is doable, and I'm not sure it is, it >leaves you with a cubic equation of cos( alpha ). There is a generalized >way to solve cubic equations, but it is much more complicated than the >quadratic formula. > >Once you have solved for cos( alpha ), choosing the correct root, then the >value of alpha will yield your frequency. > >If you step up to a five value kernel, you will similarly get a fifth >degree equation for cos( alpha ) for which there is no general analytic >solution available. > >Second, it is not necessary. The primary reason for employing a window >function is to reduce the size of the side lobes (aka "spectral leakage") >for all the tones in the signal. The conventional thinking[1] is the side >lobes are undesirable because they can interfere with, and even mask, >other tones that are in the signal. There is a better way to deal with >this problem that I am working up to in my series of blog articles. It >involves building a list of the tones that are present and iteratively >calculating their parameters. It converges rapidly to very accurate >values. In the case of a noiseless signal consisting of steady tones >through the analysis frame, it converges to an exact answer. > >In the case of analyzing music, the latter assumption is generally not >true. I have some other tricks that make it true on a piecemeal basis >which I am currently working on coding (among other things). Yes, this >also involves the concept of tone trajectories mentioned in the Phd thesis >you referenced. > >Ced > >[1] "On the use of Windows for Harmonic Analysis with the Discrete Fourier >Transform", fredrick j harris >--------------------------------------- >Posted through http://www.DSPRelated.comPlease don't tell me that it is incredibly complicated. Now I have to solve it! Btw, the solution to the cubic equation is one of the most fascinating stories of Mathematics. The men, the methods and the drama. It took place in Italy almost 500 years ago. Michael
Reply by ●March 3, 20172017-03-03
On 3/3/17 5:31 PM, Cedron wrote:>> >> Since you like music, math and puzzles, let me pose a puzzle for you to >> consider. >> > [...snip...] >> >> My puzzle for you is to find an exact estimator for frequency in a >> windowed transform. That's still a bit of a wide topic, so let me give > more >> background and narrow it down some. >> >> There is a family of windows called "cosine sum" windows that have the >> characteristic that they can be applied in the time domain, but also in > the >> frequency domain where they are applied by convolving the Fourier >> coefficients with a small kernel. For example, the classic von Hann > window has the >> kernel coefficients: -1/4 +1/2 -1/4. >> > [...snip...] > > > It's nice of you to challenge Michael, but I can tell you that I have run > down this path and it is either incredibly complicated or not possible. > Furthermore, it is not necessary. > > First, the reason it is not possible, or extremely difficult, is due to > the nature of the bin value formula for a pure tone. The best form of > this equation for this purpose is the one I give as Equation 25 in my blog > article "DFT Bin Value Formulas for Pure Real Tones" which can be found > here: > > https://www.dsprelated.com/showarticle/771.php > > The bugaboo is the cos( beta_k ) term in the denominator. Generalizing a > window function that can be implemented as "convolving the Fourier > coefficients with a small kernel." > > Let's call K = ( k_{-1} k_0 k_1 ) be such a kernel. An example would be > the Von Hann coefficients you provided of ( -1/4 +1/2 -1/4 ) > > Let's call the bins of an unwindowed DFT Z_k, and the bins of the windowed > one W_k. > > W_k = ( Z_{k-1} Z_k Z_{k+1} ) dot K > > Deriving an exact formula for W_k would lead to an expression that has a > cubic equation of cos( alpha ) in the denomitator and a quadratic equation > of cos( alpha ) in the numerator which would include mixed values of U and > V (which both also contain alpha). > > Solving for an exact frequency equation means manipulating the equations > for W_{k-1}, W_k, and W_{k+1} (for a 3 bin equation) in order to eliminate > the M, U, and V unknowns. If this is doable, and I'm not sure it is, it > leaves you with a cubic equation of cos( alpha ). There is a generalized > way to solve cubic equations, but it is much more complicated than the > quadratic formula. > > Once you have solved for cos( alpha ), choosing the correct root, then the > value of alpha will yield your frequency. > > If you step up to a five value kernel, you will similarly get a fifth > degree equation for cos( alpha ) for which there is no general analytic > solution available. > > Second, it is not necessary. The primary reason for employing a window > function is to reduce the size of the side lobes (aka "spectral leakage") > for all the tones in the signal. The conventional thinking[1] is the side > lobes are undesirable because they can interfere with, and even mask, > other tones that are in the signal. There is a better way to deal with > this problem that I am working up to in my series of blog articles. It > involves building a list of the tones that are present and iteratively > calculating their parameters. It converges rapidly to very accurate > values. In the case of a noiseless signal consisting of steady tones > through the analysis frame, it converges to an exact answer. > > In the case of analyzing music, the latter assumption is generally not > true. I have some other tricks that make it true on a piecemeal basis > which I am currently working on coding (among other things). Yes, this > also involves the concept of tone trajectories mentioned in the Phd thesis > you referenced. >well, i'm gonna toss in something i did nearly 2 decades ago: http://ieeexplore.ieee.org/document/969581/ you can get a free copy at researchgate: https://www.researchgate.net/publication/3927319_Intraframe_time-scaling_of_nonstationary_sinusoids_within_the_phase_vocoder if you use a Gaussian window, compute the FFT, and perform the complex logarithm on those results, you can estimate not just the frequency of the sinusoid, but also the linear sweep rate of the frequency and the ramp rate of the amplitude. just by fitting a line to a set of points. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 3, 20172017-03-03
Michael Plet <me@home.com> wrote:>Btw, the solution to the cubic equation is one of the most fascinating >stories of Mathematics. The men, the methods and the drama. It took >place in Italy almost 500 years ago.Being half Italian, and also having lived there, I can report that us Italians are big on drama. Steve
Reply by ●March 4, 20172017-03-04
On Sat, 4 Mar 2017 00:51:02 +0000 (UTC), spope33@speedymail.org (Steve Pope) wrote:>Michael Plet <me@home.com> wrote: > >>Btw, the solution to the cubic equation is one of the most fascinating >>stories of Mathematics. The men, the methods and the drama. It took >>place in Italy almost 500 years ago. > >Being half Italian, and also having lived there, I can report >that us Italians are big on drama. > >StevePope - that is a suitable name for an Italian! Michael
