Faster-Than-Fast Fourier Transform

First time accepted submitter CanEHdian writes "MIT news reports on research done resulting in a Faster-than-fast Fourier Transform algorithm. 'At the Association for Computing Machinery's Symposium on Discrete Algorithms (SODA) this week, a group of MIT researchers will present a new algorithm that, in a large range of practically important cases, improves on the fast Fourier transform. Under some circumstances, the improvement can be dramatic — a tenfold increase in speed. The new algorithm could be particularly useful for image compression, enabling, say, smartphones to wirelessly transmit large video files without draining their batteries or consuming their monthly bandwidth allotments.'"

Comments

transmit large video files

[TaoPhoenix]

In before _____.

Key phrase:

"smartphones to wirelessly transmit large video files without ... consuming their monthly bandwidth allotments."

Everyone see the connection to the Copyright Mayhem this week?

Bueller?

Security

[TaoPhoenix]

Doesn't some part of Internet Security (of ____, I'll leave that to my betters to explain) rely on Fourier properties?

So if we can bust those "Faster than Fast", what next?

Re:Security

[SuricouRaven]

Nope. FFTs are used in many fields, but cryptography is not one of them. Not since the old analog radio scramblers of decades past.

Re:Security

[gnasher719]

Nope. FFTs are used in many fields, but cryptography is not one of them. Not since the old analog radio scramblers of decades past.

Informative and wrong. When you calculate powers of 4096 bit numbers, the fastest way to calculate the 4096 bit products is convolution via FFT.

Re:Security

[Anonymous Coward]

The fastest algorithms for multiplying large integers employ FFT. Some cryptosystems multiply large integers...

Re:Security

[Anonymous Coward]

Nope. FFTs are used in many fields, but cryptography is not one of them. Not since the old analog radio scramblers of decades past.

Informative and wrong. When you calculate powers of 4096 bit numbers, the fastest way to calculate the 4096 bit products is convolution via FFT.

These matrices are not sparse, though, and thus the algorithms under discussion are not suitable, or any faster than FFT.

Re:Security

[SuricouRaven]

I was not aware that the mathematics of multiplication were equivilent to the FFT. Interesting. I'm not sure how to multiply via convolution though, other than the obvious trivial cheat of a 1x1 matrix.

Re:Security

[Damnshock]

Multiplications in time domain = convolution in transformed domain

Sometimes it's easier to go to the transformed domain, convolute and then go back to time domain :)

Re:Security

[misof]

Yes, FFT may be used in cryptography. But this is unrelated, as the first post in this thread talks about security. FFT has no connection to the security of cryptosystems.

As far as I'm aware, the security of *absolutely no* cryptosystem used in practice depends in any way on the FFT.

Yes, FFT gives us a way to multiply big integers quickly. But all cryptosystems that use big integers already *do* assume that everyone *can* multiply big integers quickly. Even if there was a ten-times speedup, this would mean absolutely no danger to their security.

(And one final nitpick: FFT is not the fastest way to multiply 4096-bit integers, those are still considered fairly short and you would probably gain a better performance out of some simpler-but-asymptotically-slower algorithm.)

Re:Security

[Doc Ruby]

One of the compelling mathematical insights of Fourier's mathematics is that convolution is a multiplication in a complementary space (spectrum vs frequency). Along with the insight that multiplication in radix space is addition in logarithm space, these completely transformed (pun intended) the human understanding of space and the numbers with which we describe it.

Re:Security

[SuricouRaven]

Oh, I know that part. I'm just trying to see how it could be applied to more rapidly multiply large numbers.

Re:Security

[atrizzah]

For numbers that are small enough to fit in your processor's registers, multiplication is a constant-time process. But when dealing with numbers much larger than your processor's word-length (more than 4 bytes), you have to resort to the long-mulitplication algorithm. As it turns out, multiplying polynomials is exactly the same as convolution, and is O(n^2), and long multiplication is a special case of polynomial multiplication, where the variable is fixed:

525 * 343 = (5x^2 + 2x + 5) (3x^3 + 4x + 3), for x = 10

So for two large numbers, rather than going through the long process of convolving the digits (long-multiplying), you do the following process:

1. take the FFT of the digit sequence of each number, O(n*log(n))
2. multiply point by point, O(n)
3. take the IFFT of that result, O(n*log(n))

Re:Security

[atrizzah]

I might also add that unless your numbers have a whole bunch of zeros, they aren't sparse, so the algorithm in the paper above doesn't help you. The algorithm in the paper basically says the more zeros you have in your inputs to your FFT, the faster you can do the FFT. This is mostly useful in data compression, where you intentionally throw out coefficients to save space. Although, most compression algorithms use variations of the discrete cosine transform (DCT) instead of the FFT. The DCT is very similar to the FFT, but not sure if the algorithm in the paper can also be used to speed up the DCT

Re:Security

[Anonymous Coward]

Great write-up about the symmetry between multiplication and convolution

Re:Security

[wikdwarlock]

I think, next, we go straight to plaid.

Re:Security

[ChrisMaple]

Much of the analysis of multiplication of big numbers is based on the assumption that multiplication of machine-sized numbers is much more expensive than addition of machine-sized numbers. If that is true, then there are (recursive descent) algorithms that are faster than O(n^2). However, if addition is just as expensive as multiplication, the number of digits at which fancy algorithms become worthwhile is larger.

Re:Security

[shic]

One of the compelling mathematical insights of Fourier's mathematics...

Perhaps not an ideal way to ask a question, but you sound authoritative. :)

Can you recommend a book for someone who's broadly familiar with Fourier transforms who wants to get to grips with all of "Fourier's mathematics" rather than just some limited aspects of it as exposed by a particular practical application?

Re:Security

[jasno]

I'll second the request. What I've generally found is that there is a gulf between the things taught in a standard calc I/II class and what is needed to understand most books on Fourier transforms. I've got a few books on FTs, but damn if I can understand them.

Re:Security

[theskipper]

If you don't mind me chiming in...unless things have changed, the benchmark textbooks are Oppenheim and Willsky "Signals and Systems" then Oppenheim and Schafer "Discrete-Time Signal Processing".

For some reason these two books have drawn violently differing reactions/reviews. But they worked just fine for me back in the day. Try the library first because as textbooks, they're expensive.

Re:Security

[ceoyoyo]

Most fast DCT algorithms are actually a slight modification of the FFT algorithm, so it's very, very likely that the algorithm in the article would work for DCTs as well.

Re:Security

[Doc Ruby]

I learned about Fourier's math by programming FFTs under the guidance of a genius mentor, and applying them in DSP for image processing a couple of decades ago, and I've seen the principles in action since then. I can't recommend a book, but another post in this thread did.

Re:Security

[lachlan76]

The introductory signal processing textbook that I have is Lathi's "Signal Processing and Linear Systems". If you don't want to see it from the signal processing side, then any book covering introductory PDEs should have some Fourier Series. Alternatively, have a look at this.

Doesn't sound THAT useful

[tempmpi]

It doesn't improve the regular FFT but only sparse variants. Image or Audio compression nearly always uses the regular non-sparse FFT.

Re:Doesn't sound THAT useful

[Anonymous Coward]

The paper claims the opposite: "Images and audio data are equally sparse. This sparsity provides the
rationale underlying compression schemes such as MPEG and JPEG."

Re:Doesn't sound THAT useful

[MojoRilla]

This isn't right. The proposed algorithm is better on sparser signals, but is a regular FFT. The point is that many things we want to compress are sparse, or at least have pieces that are sparse. In JPEG, for example, images are broken into 8x8 pixel blocks and then DCT'ed (which is similar to FFT). Many of those blocks might be sparse, and benefit from this new approach, even if the most complex blocks aren't and don't benefit.

Re:Doesn't sound THAT useful

[Anonymous Coward]

I'm only awake due to a bathroom break, so I may not be the most clear-minded at the moment, but subtracting coefficients from the bins seems like a pretty obvious permutation of algorithmic techniques to try, and having 2/3 probability of a correct FT analysis doesn't seem like an inspiring trade-off (skimmed... perhaps they explain ways to improve this?) Is this anything more than a highly specialized, not particularly practical version of the algorithm? I'm used to working on algorithms which are much more general-case (e.g., new solutions for SCALAPACK problems).

Re:Doesn't sound THAT useful

[fph il quozientatore]

Yeah, but a big-O improvement may do you no good if you only need n=8...

Re:Doesn't sound THAT useful

[dkf]

Yeah, but a big-O improvement may do you no good if you only need n=8...

Depends on what sort of complexity it is. When the complexity function is larger than polynomial, even n=8 can be worrying. (I remember working with algorithms that were O(EXP^2(n)) at one point, many years ago; they had combinatorial searches over a system where the test function was itself an NP-Hard problem. Nasty, and we couldn't use the structure of the problem to restrict anything too much either. Suffice to say that at the time we were having problems finding supercomputers large enough to run our code...)

Re:Doesn't sound THAT useful

[fph il quozientatore]

The complexity of FFT is O(n\log n).

Re:Doesn't sound THAT useful

[atrizzah]

Most compression algorithms don't use the FFT at all, they use the DCT. And while the signals aren't usually sparse, the heart of the compression process is throwing out non-zero coefficients that are very small. Of course, you have to do the DCT first to find out which coefficients's are small enough to be thrown out. But, at the very least, this could be useful in the decoding process.

Re:Doesn't sound THAT useful

[ceoyoyo]

Nitpick: EVERYTHING that's worth compressing is sparse. Compression exploits the sparsity of almost every signal we find interesting. You can go ahead and lossily compress non-sparse data, but you won't be happy with the result.

Wonder how it'd "work" on cats.

[sethstorm]

So the cat gets transformed even faster.

(apologies to XKCD)

Re:Wonder how it'd "work" on cats.

[Anonymous Coward]

So the cat gets transformed even faster.

(apologies to XKCD)

Be glad it's not the furrier transform of your cat :)

Re:Wonder how it'd "work" on cats.

[sethstorm]

Mine's dead, so I'd be kind of worried about any kind of spontaneous transforms.

Potentially huge digital A/V benefits

[sound vision]

Lossy compression such as MP3, AAC, and according to TFS also video compression, are all fundamentally based on FFT (fast fourier transforms). Depending on how well this new specific method works, we could see decreases in the time it takes to encode all this stuff. Which can be quite a long time... have you ever tried to do a 2-pass MPEG 4 conversion on a feature-length digital video? Video encoding doesn't scale well to multiple cores either, so nowadays when performance increases coming mostly from adding more cores... video encoding hasn't been getting faster at the same pace it used to. I'm thinking this new FFT algorithm could make a big difference in encoding speeds.

Additionally, I know lots of audio (and I'm assuming video) effects, DSPs of the kind you find in Adobe Audition, Audacity, et al., rely on FFTs. Computing such effects could get a lot faster. With increases in both the speed of adding effects, and compression afterwards, we might be seeing a significant speedup in the overall digital audio/video-editing process.

Re:Potentially huge digital A/V benefits

[Anonymous Coward]

Who holds the patents for this? That's the most important question.

Re:Potentially huge digital A/V benefits

[drinkypoo]

Video encoding doesn't scale well to multiple cores either,

Welp, that is patently false. Video encoding is embarassingly parallel in any case where video has keyframes and the video is sufficiently long to hand a roughly equal number of chunks of video (keyframe to keyframe) to each core.

Re:Potentially huge digital A/V benefits

[alexhs]

I'm thinking this new FFT algorithm could make a big difference in encoding speeds.

I'm not so sure. It has the potential to make a big difference in decoding speed :
I would think that the input signal is not that sparse, but rather that it has plenty of small components. The goal of the compression is to remove the smallest components as unnoticeable noise. Only after that step you get a sparse signal. So what you can actually improve significantly is technically the inverse FFT (which uses basically the same algorithm as the FFT), used for decoding.

Re:Potentially huge digital A/V benefits

[Anonymous Coward]

I have implemented (baseline) h264 on GPU, and I tuned it for at least 6 month. The FFT (actually fastDCT variant), only took 20% of the runtime, because it was done 4x4 blocks, it was the most parallel part of the codec, the easiest to implement. By far, the lossless compression, and the motion estimation are more complicated. Especially motion estimation, which is very important for good bitrate / quality in a video codec.
So this wouldn't really speed up h264 like video codes..(only a little bit).

Re:Potentially huge digital A/V benefits

[Anne Thwacks]

Well, maybe not "IS", but "can be", under some circumstances, when data is dynamic. If data is static, there is often no benefit.

And yes, I have done 8-bit integer FFTs. Loads of them!

Re:Potentially huge digital A/V benefits

[SuricouRaven]

Maybe on audio, but on video the FFT itsself is only a tiny part of the encoding time. The really slow part is finding motion vectors, which is a completly seperate part, and usually the slowest one.

Video encoding actually should scale fantastically to multible cores - it's almost linear, in theory. It's just that very few encoders support it due to the complexity of multithreading what is already a very complicated program.

Re:Potentially huge digital A/V benefits

[Rockoon]

Lossy compression such as MP3, AAC, and according to TFS also video compression, are all fundamentally based on FFT (fast fourier transforms).

Actually, most (if not all?) of these lossy compression schemes are based on the discrete cosine transform, not the discrete fourier transform. That is definitely true for MP3 and AAC, and also true for JPEG which most video encoders probably use for key frames.

Re:Potentially huge digital A/V benefits

[nahdude812]

Absolutely. I have 4 dual core CPU's in my machine. When I encode video, all four are clocking at about 90-95%. Encoding an hour of video takes in the neighborhood of 10-15 minutes per pass depending on the movie, and my hardware is even a few years old, plus I'm typically decoding at the same time from a different source (eg, DVD).

Re:Potentially huge digital A/V benefits

[Rockoon]

Correct. FFT is used to compute the DFT. What was your point again?

FFT is probably not as efficient as a naive method, on general purpose hardware, in the case of small block sizes like what JPEG is based on (16 samples.)

You simply arent going to get an order-of-magnitude step improvement with FFT when N is small, but you have to pay the various overheads (non-linear memory access and the calculation of those pointers) anyways. This is similar to how optimized bubblesort beats the crap out of quicksort for very small lists, as quicksort has a lot of overhead (recursive calls, guessing a good pivot, etc..) that simply ends up not being justified for small N.

Re:Potentially huge digital A/V benefits

[jcdr]

I was also surprised to to discover that even in a simple JPEG compression, the Huffman codec take a big part of the time.

Re:Potentially huge digital A/V benefits

[AmiMoJo]

What TFA skips over though is how suitable this algo is for implementation on GPUs or with newer SIMD instruction sets designed to accelerate FFTs. It might be the case that even if the GPU has to do more calculations it can do them more efficiently than the CPU can implement this new form of FFT.

Re:Potentially huge digital A/V benefits

[tepples]

Video encoding actually should scale fantastically to multible cores - it's almost linear, in theory. It's just that very few encoders support it due to the complexity of multithreading what is already a very complicated program.

What's so complex about splitting video into five-minute chunks (or, in multipass encoding, keyframe-to-keyframe chunks) and handing each off to one core?

Re:Potentially huge digital A/V benefits

[SuricouRaven]

nothing much, if you're going file-to-file and have plenty of memory - but most encoders are made to also handle live streaming.

Re:Potentially huge digital A/V benefits

[ChrisMaple]

The same sorts of improvements that can be applied to DFT can be applied to DCT. The underlying concept is the same, and the methods for improvement follow therefrom.

Re:Potentially huge digital A/V benefits

[ceoyoyo]

A good optimized FFT is generally more efficient than the naive DFT algorithm on power of two signals with > 4 samples on modern hardware. By the time you hit 16 you should definitely be in the FFT range, particularly if you're doing a bunch of them. If you look at the FFTw library, most of the algorithms for transforming power of two signals are radix-4.

Re:Potentially huge digital A/V benefits

[ceoyoyo]

A signal is sparse if it requires less than the naively expected amount of information to represent adequately. Virtually all interesting signals are sparse, video especially so.

Basically what you do now is calculate the transform (usually a DCT, but fast DCT algorithms usually use the FFT anyway), then throw away the small coefficients. What this algorithm does is not calculate (most of) those small coefficients in the first place.

Re:Can it be done effectivly without an FPU?

[Alex Belits]

DSP with Arduino

What is wrong with this picture?

Processors used in Arduino (Atmel 8-bit AVR series) are minimal, general-purpose microcontrollers, a replacement for earlier PIC microcontrollers. Using them for DSP is only slightly less stupid than building DSP boards entirely out of individual discrete transistors. There is A WHOLE FUCKING CATEGORY OF IC dedicated to DSP, plenty of microcontroller-style yet high-performance SoC suitable for DSP, and FPGA with DSP-specific blocks.

But noooo, ignorant people such as yourself, would rather recommend the most un-DSP-ish device in the world just because it comes bundled with Java-based IDE that runs on your beloved wiiiiiiiiindows and has the ugliest editor ever written since xedit.

Wish I could understand the details of FFTs

[Viol8]

I'm sure I'm not the only person who completely understands what a FFT does but simply can't get his head around the actual implementations details. I simply don't get how a signal of many mixed frequencies which essentially means the amplitude is moving all over the place can travel through some equations and a neat list of the fundamental and harmonics can pop out. Its mathematical magic to me. Wish I could "get" it. But I guess I'll just have to settle for using it.

Re:Wish I could understand the details of FFTs

[lachlan76]

In the DFT case the signal is merely a finite number of samples, so you can forget about the time-dependence and look at it as a long vector. If you sit down and work out the maths, you find that the vectors corresponding to the constant function and the various sinusoids are linearly independent.

All you're really doing then is solving a system of linear equations---they don't just have to be sinusoids, you could find the coefficients for any linearly independent set of functions. You could just as easily replace one of the sinusoids with an exponential function and still get coefficients out such that you could do your weighted sum of vectors and get back your original function.

Re:Wish I could understand the details of FFTs

[Viol8]

I'm afraid you lost me at "long vector"

"sit down and work out the maths"

Ah , if only I could. But I'd settle for understanding it first! :o)

Re:Wish I could understand the details of FFTs

[expatriot]

I only got FFT by working forward from different frequency sine ways to triangle, sawtooth, square, and other waves. After you do this, you realize it must be possible to go the other way.

A very coarse FFT can be calculated by multiplying the waveform by two square waves that are 90 degrees out of phase and summing each sequence. If there is no component corresponding to the square wave frequency, the two totals will be near zero.

Re:Wish I could understand the details of FFTs

[lachlan76]

"Sit down and work out the maths" is really just code for "here's one I prepared earlier". If you're keen on this sort of thing, read a bit about solving systems of linear equations, and you will hopefully be able to look at the problem, exclaim "this is trivial!" and live forever happy in the knowledge that it is indeed theoretically soluble (as I tried to describe above) without having to concern ones self with the computational subtleties that suck all of the fun out of it.

MIT OCW have a set of videos on linear algebra if your curiosity is sufficient to justify chewing up some time on it. Probably some of the most useful partially-post-high-school maths that one can learn. Here is a free textbook on it.

Re:Wish I could understand the details of FFTs

[gnasher719]

Well, that is not what FFT does. You have to look at plain old FT (Fourier Transform) first, not FFT (Fast Fourier Transform), and better CFT (Continuous Fourier Transform) first.

CFT transforms a continuous signal into continuous frequencies, and it does that by integrating the input signal multiplied by a complex sine wave. The mathematics for that is reasonably understandable, doing the calculations is horribly difficult.

FT does an approximation of CFT, by first changing the input signal to discrete values (like 44,100 per second for music), calculating only discrete frequencies, (440 Hz, 441 Hz, 442 Hz...) and replacing the integral with a sum. So you calculate for each point the sum of (input signal times sine wave). For each of n inputs you add n values, for a total of n^2 products.

FFT or Fast FT uses a clever algorithm and properties of the sine function to reduce the number of calculations to about n * log (n). Understanding FFT has nothing to do anymore with your problem; it just is understanding a clever optimization.

Re:Wish I could understand the details of FFTs

[scum-e-bag]

It's beautiful, isn't it.

I read the linked articles and it dawned on me. So very beautiful.

I'm glad there are others. :))

Re:Wish I could understand the details of FFTs

[serviscope_minor]

I simply don't get how a signal of many mixed frequencies which essentially means the amplitude is moving all over the place can travel through some equations and a neat list of the fundamental and harmonics can pop out.

But it's easiest to start with the O(n^2) DFT, not the FFT.

As always, the only way to truly understand it is to work out the maths. But, it it helps, let's try a simple one.

Imagine you have some vectors in 4D called a, b, c, d and are respectively [1 0 0 0 ] [0 1 0 0 ] [0 0 1 0] and [0 0 0 1].

You can see by inspection that a.a = 1, b.b=1 etc, but a.b=0 and so on. I.e. if you dot two of the same vectors you get exactly 1, otherwise you get exactly 0. I will call this property 1.

Now imagine you have 4 numbers, e, f, g, h. With suitable choices, you can make up any 4D vector by doing v = ae + bf + cg + dh.

Using property 1, you can see v.a = a.(ae + bf + cg + dh) = e. In other words if you multiply the new vector with one of the original vectors, the amount of that original vector pops out.

You can trivially verify this. Clearly in this case, v = [e f g h] and so it's obvious that e corresponde to the amount of [1 0 0 0] in v.

Now here's the fun part. Everything except for the trivial verification above only usef property 1. The only requirement is on the dot products, and it still works.

Try it with the four vectors [1 1 1 1]/sqrt(4), [1 1 -1 -1]/sqrt(4) [1 -1 0 0]/sqrt(2) and [0 0 1 -1]/sqrt(2). You can verify Property 1 very easily. Yiu can now take any 4D vector and find out how much of [1 1 -1 -1] there is in it, using the same method as above.

We still haven't done the DFT (ot FFT) yet. Actually, we've just covered the Haar Wavlet transform.

Nothing above is limited to 4 dimensions. It will work equally well in 100, 1000 or 1024 dimensions. You just need more vectors. You can at this point almost certainly invent all sorts of patterns of vectors (in 2^N dimensions) that fit Property 1.

Well, here's a special one. Imagine that i is the index of a point in the vector, and so goes from 0 to 2^N-1.

You can make vectors where the elementts are cos(n*i*pi / (2^N-1)) and sin(n*i*pi/(2^N-1) for various values of n. You will find that they all satisfy Property 1. So now you can find out how much of those cos and sin vectors are in your original vector v.

Or, in other words you cna find out how much of a certain frequence is in there.

And that's the DFT in a nutshell.

If you do some manipulation, you can se that this maths is just a matrix times a vector:

e a_vector v_0
f = b_vector v_1
g c_vector * v_2
h d_vector v_3

In general there is no O(N log N) method to perform this multiplication. But for certain problewm structures (like the FFT) there are faster algorithms, but they're still doing the same maths.

Another fun fact is that any matrix whose rows satisfy Property 1 is a rotation matrix. So, you're just rotating your data. And you can get a Fourier transform by masically making everything bigger until its continuous. So there you see, a Fourier transform is just a rotation in an infinite dimensional space.

Ta da.

Re:Wish I could understand the details of FFTs

[lachlan76]

Rereading your comment, I think I may have slightly misunderstood what you were saying. If you have produced a digital signal by sampling an analogue one (i.e. if you look at the values of a signal at various points) over a finite, the DFT (or the FFT as its most popular algorithm) will not tell you what the fundamental frequency is.

You can get an approximation by making assumptions about the nature of the signals that you sample, but this is not the best way to do it, and those assumptions are normally that the signal contains frequencies in a range only half the sample rate.

Re:Wish I could understand the details of FFTs

[Damnshock]

Well, you can write any sinusoid in form of exponentials, that's why it still works ;)

Re:Wish I could understand the details of FFTs

[lachlan76]

Sorry, I meant to say a real exponential. It's probably true for more than one as well, but that means more than one line of Octave code to check (or some kind of conscious thought).

Re:Wish I could understand the details of FFTs

[Splab]

Why is it, math books and people into math uses words like "obvious" or "you can very easily"; it really really destroys your readers enthusiasm for reading what you are doing.

Yes, it might very well be obvious and trivial to you, but it sure as hell make me feel dumb when I don't get the obvious in the first pass.

Other than that, nice intro to FT.

Re:Wish I could understand the details of FFTs

[Viol8]

Ok , I think I understand what you're on about but if amplitudes are additive wouldn't they cancel out over the course of N whole waveform samples because you'd be adding the positive and negative values together? Or do you just sample N+1/2 waveforms?

Re:Wish I could understand the details of FFTs

[Delgul]

It is actually quite simple provided you have at least some basic math skills. Don't try to wrap your head around the math involved just yet. Just do this:

1) Have a look at http://en.wikipedia.org/wiki/Fourier_transform and only look at Definition and Introduction.
2) Get some tool like Matlab or Octave (the last one is OSS)
3) Generate a pure sine wave signal and put that through the formula's you found in 1). You should get a single spike in your results
4) Now add a second sine wave with a different frequency to the first signal. and put that signal through the same formulas. You should find two spikes.
5) Try experimenting with this, adding signals and experiencing how the amplitude and frequency impacts the spike height and position.

When you have a feeling for this, THAT is the time to read the entire article. You will find it easier to understand.

You now have a reasonable understanding of the Fourier Transform. The Fast Fourier Transform or classic FFT is no more than some mathematical trick to make these calculations faster and actually it has it's drawbacks, like your nr of sample must be a power of 2 and some other stuff I won't go into here, although these are acceptable in most practical cases. This new FFT transform seems to be a lossy variant of FFT which will impact the resulting signal, negating the contribution of frequency area's with low energy content. It could be especially useful in situation where that loss of information is acceptable as it is in sound and video to some degree. However, I did not really read up on this new method so I could be off the mark...

Re:Wish I could understand the details of FFTs

[lachlan76]

The distinction I suppose is between conclusions that one can work out by inspection or immediate application of theorem, rather than by taking a detour through intermediate steps. It's probably not quite so cut-and-dry, but that's how I tend to see things. Such turns of phrase are just about part of the jargon.

It almost functions as a punctuation mark to reassure the paranoid (which sometimes is practically everyone) that "no, this next bit really is what it looks like".

Re:Wish I could understand the details of FFTs

[stewbee]

Here is a description that I received that finally made FFT/DFT click for me. I hope it helps you too. First of all, an FFT is just a subset of computation for the DFT, so they really compute the same things. It's just that one is faster than the other. Now look at the formal definition of the fourier transform. It is the integral of your time (or spacial, but I will use time) function times e^(j2*pi*f*t) over time, The exponent is nothing more than a rotating phasor as a function of time at frequency of f. Now choose a single frequency (say 60 Hz). this phasor rotates at this rate. Now the integral is over time, so in the span of one second, the phasor will rotate 60 time (obvious i know, but work with me here). If there is a component of the time signal of interest that resonates with 60 Hz, the integral acts as a way to sum up all of these values that are in resonance which then results in a peak at 60 Hz. If there are no 60 Hz components in the time signal (say there is one at 75 Hz instead), the 60 Hz phasor will not have a peak since phasors at 60 Hz are orthogonal to 75 Hz sinusoids (sin(n*2*pi*t*f)*sin(m*2*pi*f*t) = 0 for m != n).

So in summary, the exponential phasor term is just a means to weight the time signal across all frequencies. I hope this helps.

Re:Wish I could understand the details of FFTs

[John.P.Jones]

Rather than understanding the FFT (an O(nlgn) algorthim for computing the DFT which is normally an O(n^2) operation) you should first understand how the basic DFT equation works, which is independent for each of the frequencies. It just takes each of the n elements in your discrete signal and multiplies it by a (complex) sinusoidal function of that frequency and sums them. If the data is correlating well with the sine wave the magnitudes of these products will be larger and of a consistent sign (+ for direct correlation and - for anti-correlation, small numbers for uncorrelated values). Then you can see that the DFT works and then it is an algorithmic exercise that the FFT produces the same result in less computations.

Re:Wish I could understand the details of FFTs

[atrizzah]

Most of the time, when people talk about taking the FFT of a signal, they really mean the STFT, which breaks the signal into small blocks, and then takes the FFT of each block indepently, the result being known as the analysis frames of the signal. Either way, it fundamentally comes down to this: you have a discrete (sampled) signal of finite-length N (N could be really large for the full FFT, or something like 1024 for an STFT), and the amount of information (bandwidth) of that signal is fundamentally limited by the time interval between the samples (see Shannon-Nyquist sampling theorem).

Forget Fourier for a second, linear algebra alone says that you are free to transform that signal into another representation by multiplying it with a set of basis functions, and it will always take just N coefficients, so long as your basis functions are linearly independent. The best sets of linearly independent basis functions are also orthogonal, because that means each of your N coefficients is representing an independent part of your original signal.

As it turns out, the set of sinusoids that are harmonics of the sinusoid with period N (up until the sinusoid with a period of just two samples) are linearly independent and orthogonal, and therefore, are completely sufficient to describe a signal of length N. Fourier was one of the first to use sinusoidal bases, hence his eponymous transform. Mind you, once again, that N could be the length of the original signal, or just the length of the STFT blocks of your signal fragments. We typically use STFT because for most real-world signals, meaningful ideas of frequency content are a time-local thing. When you listen to music, for example, frequency only really has meaning over windows of a sound signal that are up to 1/20 of a second. So taking the FFT of an entire audio file all at once will give you the frequency content of the entire file, but that has little perceptual or musical meaning.

But, there is a problem with the STFT. Using exactly N sinusoids to represent a block of data doesn't work correctly if your data has frequencies that don't fit into exactly N samples. In other words, the FFT only produces meaningful measurements of frequency if the signal is periodic in the window length. In reality, this is always the case, because the STFT process of chopping the signal into blocks is not at all careful about making sure those blocks don't snip the signal at awkward points. The result of taking the FFT of a block that has awkwardly clipped edges is known as "spectral leakage": the appearance of frequency content in sidebands close to the real frequency, which makes the output not the ideal spike at the measured frequency. To combat this, we use windowing functions, which don't totally fix the problem, but they do make it much, much better.

Hopefully that sheds a little light on the topic

Re:Wish I could understand the details of FFTs

[serviscope_minor]

Yes, it might very well be obvious and trivial to you, but it sure as hell make me feel dumb when I don't get the obvious in the first pass.

I didn't have the time to write out in full everything, so I left out the parts I believed to be obvious. I was hoping that the "obvious" bits involved straightforwards use of things already assumed known with no intermediate steps, foe example calculating the dot products between vectors already given.

The word is supposed to indicate that usage, rather than the (much more annoying) it can be shown or (worse) the proof is left as an exercise to the reader.

In the other case about e and [1 0 0 0], I honestly can't think of any way of breaking that down further. If it isn't obvious to the reader then I don't know how to explain it better.

Other than that, nice intro to FT.

Thanks :)

Re:Wish I could understand the details of FFTs

[rrohbeck]

DFT and friends rely on the orthogonality of sine waves: If you convolve your signal with a sine wave, you extract the amplitude of that particular harmonic because all other signal components average out to zero.
Do that for each frequency of interest and you have your DFT.
FFT is just a tricky arrangement of the calculations for signals that are a power of two in size based on divide-and-conquer and the properties of the sine/cosine functions.
Disclaimer: It's been over 20 years since I did the math.

Re:Wish I could understand the details of FFTs

[Splab]

Just avoid stating the "obvious" part; and yeah, "left as an excersice" to the reader haunted me through CS - always felt it meant, the auther had no idea either, but sure as hell wouldn't confess to it :-)

Re:Wish I could understand the details of FFTs

[marcosdumay]

It is simpler in linear algebra. I guess that is the theory where DFT and FFT are simpler. So if you want to understand them, read a book about linear algebra, and read about the FFT again.

Re:Wish I could understand the details of FFTs

[Anonymous Coward]

I agree, though it doesn't work the other way: you don't necessarily understand something just because you can code it.

Re:Wish I could understand the details of FFTs

[onemorechip]

FT does an approximation of CFT, by first changing the input signal to discrete values (like 44,100 per second for music), calculating only discrete frequencies, (440 Hz, 441 Hz, 442 Hz...) and replacing the integral with a sum. So you calculate for each point the sum of (input signal times sine wave). For each of n inputs you add n values, for a total of n^2 products.

Er, that's not a Fourier transform (which is a continuous representation of a continuous signal) but a discrete Fourier transform (DFT).

Re:Wish I could understand the details of FFTs

[Danny Rathjens]

Young man, in mathematics you don't understand things. You just get used to them. -- John von Neumann
Reply to Felix T. Smith who had said "I'm afraid I don't understand the method of characteristics." -- as quoted in The Dancing Wu Li Masters: An Overview of the New Physics (1984) by Gary Zukav footnote in page 208. http://en.wikiquote.org/wiki/John_von_Neumann

Re:Wish I could understand the details of FFTs

[ceoyoyo]

Take a signal. You can figure out the amplitude of any particular frequency in that signal by correlating it with a sinusoid of the frequency of interest. Correlation (in this context) is just multiplying the two signals together, point by point, then summing up. The Fourier transform basically says that if you want to know what the frequency spectrum is, you do this basic operation for all the frequencies in the spectrum. The discrete Fourier transform tells you, based on the sampling you did on the signal, which frequencies you need to calculate so you only have to do a finite number.

The fast Fourier transform is a neat trick based on the observation that the discrete spectrum of the whole signal can be trivially calculated from the discrete spectra of the original signal either divided in two halves or into odd and even samples. Since the DFT is a N^2 operation, it's usually faster to do two DFTs of length N/2 than it is to do one of length N. You keep applying this trick, dividing the signals in half, then the halves in half, etc. until it's not worth dividing them any further, usually when they're 2 or 4 points long, although you can go all the way down to one point if you want: the Fourier transform of a signal sample is a null operation.

Re:Wish I could understand the details of FFTs

[ceoyoyo]

Whoops. Replied to a reply to your post by accident. See: http://science.slashdot.org/comments.pl?sid=2630002&cid=38767088

Re:Wish I could understand the details of FFTs

[ceoyoyo]

"If you're keen on this sort of thing, read a bit about solving systems of linear equations, and you will hopefully be able to look at the problem, exclaim "this is trivial!""

Noooo! That's not the kind of understanding the OP seems to want. Someone with a really deep understanding of linear algebra might be able to make the connection between the matrix formulation of the DFT and the intuitive understanding of what's actually going on, but I've almost universally found that isn't the case. The matrix formulation is very nice for doing things WITH the DFT, but not for understanding the DFT itself.

To get an intuitive understanding of the DFT you need to sit down with Python or MatLab or whatever your language of choice is, make a signal, calculate the correlations with some sinusoids, then add those sinusoids together, etc.

"You construct the matrix A" is very often the best way to prove something is true, but I've found is very rarely, if ever, the way to teach someone to understand WHY it's true.

Re:Wish I could understand the details of FFTs

[ceoyoyo]

The math can be instructive, but it's tough to get a practical feeling for the CFT because you need a bunch of optical equipment. ;)

Re:Wish I could understand the details of FFTs

[lachlan76]

If you're looking for an understanding of what the DFT computes, sure. But the OP was more interested in how it works than what it does, so all of the Matlab in the world won't do much good. If you try to actually write out the DFT matrix, you're overdoing it for this purpose---that it is possible to write the transformation from frequency-domain to time-domain as a multiplication by an invertible matrix is enough, since then the DFT is then just the solution of a system of linear equations.

You don't need a deep knowledge of linear algebra for the finite-length discrete-time case, just the basics that everyone studying maths/science/engineering gets taught in the first couple of months of university. The point that I was trying to make was that for finite-length discrete-time signals, all that you're really doing is solving a system of linear equations like every man and his dog can do after a bit of training---that your coefficients happen to be uniformly-sampled complex exponentials doesn't really matter until you start thinking about efficient implementation.

Re:Can it be done effectivly without an FPU?

[rev0lt]

While I do argue with your point, there are a ton of devices that would benefit from it. Why do you think the implementations of FFT for 8/16-bit microcontrollers such as the 8051 are so popular? DSPs are popular in applications that make heavy use of FFT, but there are a ton of general purpose implementations that require FFT algoritms, ranging from multitone generation/decoding to D/A conversion. Why should I use 2 ICs (plus assorted external logic) on a given circuit, if I can easily do it in software on my general-purpose microcontroller, that besides the integrated ram and rom, also bundles me with a serial port, multiple I/O ports and a ton of "extra" features, at a fraction of the price?

Re:Can it be done effectivly without an FPU?

[mikael_j]

Well, if for some reason someone is already using Arduino boards to do a bunch of stuff it might make sense if it was just fast enough. But yeah, if you have a choice it doesn't make much sense to pick an Arduino for this task.

So far the only "usefulness" I've seen in the Arduino has been for that retro kick, being artificially limited to the kind of environment I haven't had to work in for a long time, but if I wanted to build something useful I'd probably at least want a 16-bit processor these days, the difference in price is negligible for any hobby project (hell, a 32-bit processor probably wouldn't be a major budget concern considering what you're likely to spend on the rest of your hardware when building something)...

Whoa

[HappyClown]

Let me get this straight - you're saying you woke up in the middle of the night intending to take a dump, and somehow ended up posting about complex mathematical algorithms on the Internet instead? Respect.

Re:Whoa

[K. S. Kyosuke]

Let me get this straight - you're saying you woke up in the middle of the night intending to take a dump, and somehow ended up posting about complex mathematical algorithms on the Internet instead? Respect.

If the dump takes a long time (which it sometime does), what else is one supposed to do in the meantime, sitting on the toilet bowl with a laptop in one's lap?

Re:Whoa

[AmiMoJo]

This is why I will never buy a used laptop, at least until it has been through an industrial disinfection process.

I hope it was a low spec laptop too, wouldn't want to get burned in that position.

Re:Whoa

[rrohbeck]

I would think that somebody who is smart enough for these kinds of questions is also smart enough to know the relationship between nutrition and constipation and how to avoid it :)

Re:Whoa

[tepples]

This is why I will never buy a used laptop, at least until it has been through an industrial disinfection process.

If Lysol products are enough to disinfect a toilet, why not to disinfect a laptop's chassis? (But you'd probably want to use something else around the screen so as not to damage the coating.)

hope it was a low spec laptop too, wouldn't want to get burned in that position.

Which is one reason why I carry a 10" laptop with an Atom CPU. But I'm thinking of ditching this Dell sometime soon; I've had ASUS and Acer netbooks that ran cooler.

Re:Whoa

[Just Some Guy]

He started out intending a discreet colon transform.

Re:Whoa

[Tablizer]

Let me get this straight - you're saying you woke up in the middle of the night intending to take a dump, and somehow ended up posting about complex mathematical algorithms on the Internet instead?

I get frustrated and end up doing it the other way around.
   

It could be huge

[Anonymous Coward]

In a cell phone or wi-fi, there are FFTs all over the place. They use them for things you would never suspect ... even if you have taken a DSP course. In modern radios (cell phones or anything else connected wirelessly) the DSP is the main chip.

Every time you find a computationally efficient way to do something, you improve battery life. So, phones can stay the same size and take advantage of even more streaming content.

Re:It could be huge

[YoopDaDum]

It's actually not very applicable to telecommunications. Yes, FFTs are a key item to all OFDM/OFDMA based protocols like WiFi and WiMAX/LTE. But the content is definitely not sparse at all. Each FFT bin is a carrier frequency. In OFDM when transmitting all carriers are used, so clearly not sparse.
In OFDMA only some carriers could be used if the network is lightly loaded, but this can change in real time and you may not know if it's sparse or not in advance (in LTE for example, a device only get its own allocation ahead of time). The worst case will be common, and less efficient than a simple FFT.
That's why the authors mention picture or video or instrument based sounds. Here you can have significant cases with sparse content in the frequency domain, and be quite sure to win on average.

Re:It could be huge

[CurryCamel]

Mod parent up. First (only?) comment under this news with techincal, on-topic and informative content!

Re:Can it be done effectivly without an FPU?

[digitig]

I agree with the AC -- it would be cool. [S]he didn't suggest using it in commercial applications, just as a fun thing to do. With a possible ten-fold increase in speed, DSP that was out of the Arduino's range comes within it, so there are now more things the Arduino can do. That's cool. If you want to simply buy a purpose-built DSP chip that's fine, but in this place of all places don't knock the geeks who want to build the thing at home from the lowest-level components practicable.

Autotune

[X.Coward]

Does this mean we get better and faster autotune?

Faster Mersenne Prime Calculations?

[DarkHelmet]

From what I know, the Great Internet Mersenne Prime Search (GIMPS) uses a Fast Fourier Transform to quickly find the square of a number. This is a required part of the Lucas-Lehmer test (the test that determines if the number is prime).

If this form of FFT can do fast squaring, it will reduce the amount of time taken to find new, large primes.

This is a potentially exciting development in this field.

Re:Faster Mersenne Prime Calculations?

[gnasher719]

If this form of FFT can do fast squaring, it will reduce the amount of time taken to find new, large primes.

It wouldn't, because it only works when your data contains many zeroes. The products in GIMPS are of pseudo-random data, so I would expect half the bits to be non-zero, and almost none of the numbers involved to be zero.

Re:Can it be done effectivly without an FPU?

[rev0lt]

Not every FFT implementation is floating-point (I believe fixed-point implementations are quite more common than floating-point ones), and software-based floating point is not "somewhat slow", is "slow as hell". For many applications, fixed-point and good ol' lookup tables (either complete tables or sample points with interpolation) do the trick rather well.

Nice. More tuning! :)

[msobkow]

No matter how good you think the latest and greatest algorithm is, there is usually someone who can come up with a way to improve on it.

For example, I DO know how to structure the probes done by MSS Code Factory such that you could stuff the rule base in Oracle and use some very Oracle-specific syntax to do the probes in one query, taking the first record from a sorted result set as your "answer" to the probe. I've written similar queries for other databases, but they're constrained by how many levels deep you want to write the query for. As there is no telling how deep the query would be for MSS Code Factory, and I don't want to tie myself to an expensive product like Oracle, what I have now is pretty much the best I can do at the moment. Maybe some day I'll come up with more tuning ideas, but not right now.

Kudos to the FFT team. I look forward to reading the details, though my memory of FFT math is pretty old, fuzzy, and shaky nowadays.

I used to be heavily into computer graphics and audio processing in the university days, but I've spent decades focusing on business programming instead. Unless you really LOVE graphics and sound, and want a job in a very narrow field (including video games), I think it's inevitable that you put away the toys and pick up the tools of industry that will earn you a pay cheque.

It's not the algo that's sparse, it's the signal

[Nicolas MONNET]

Saying that compression uses the regular "non-sparse" algorithm is rather meaningless; they use what is available, and I don't believe there was a sparse-optimized algo until now.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Can it be done effectivly without an FPU?

[dintech]

The Spectrum Analyser. This is one of the most common uses is staring you right in the face in almost every mp3 player.

The interesting thing is that the greater time window over which the FFT operates, you can observe finer frequency detail within that particular window at the expense of how quickly the graph or bars change over time (in simplistic terms). I wonder how this new algo will change the frequency detail/transient time detail trade-off. Do we see more detail in both domains? Less? The same?

the MAFIAA obviously

[RotateLeftByte]

They will try to keep this under wraps as anything that speeds up video encoding/decoding will be classes as anti Hollywood and a tool for piracy.
Standby for a few mysterious disappearances of any public copies of the algorithm.

Re:the MAFIAA obviously

[semi-extrinsic]

Please, enlighten me, how do public copies of algorithms "disappear"? Counterpoint: deCSS, the release of (master) keys for AACS and HDCP.

Anyway, we can just publish it as a poem and it's protected under free speech:

Now help me, Muse, for
I wish to tell a piece of
controversial math.

Re:Can it be done effectivly without an FPU?

[ThatsLoseNotLoose]

Slashdot could really use a +1 Insightful but Unnecessarily Dickish mod.

Re:Can it be done effectivly without an FPU?

[Anonymous Coward]

A year ago, there was still easily an order of magnitude difference in price going from AVR to 32-bit microcontroller land in base deve hardware alone. You say that for one hobby item the price difference (say $10 --->$100) is neglible, because they are both smallish numbers relative to income... 1) You need to learn multiplication 2) A lot of hobbyists have the desire to do their own version of "ubiquitous" computing.. Your "negligible" price difference theory breaks down in all the cases I'm familiar with.

And please spare me with examples of ultra cheap 32-bit systems, which I know always exist at any given moment. I still remember that time when the TI eval robot had a leaked promo code. That thing took down TIs website and then of course was promptly gone... When assisting a local youth group with a robotics project I looked at numerous "inexpensive" ARM options, only to find that at any given time product availability in this domain is *inconsistent*. Say what you will, but there is almost always an Arduino clone around, and if you fry it, you don't care. If you get a special on a 32-bit ARM system, good luck buying another in 3 months.

In my business, if you absolutely *NEED* a dev board you must still be prepared to pay $300-1000 bucks for the base board alone. I'm a day-job embedded product designer that also works with hobbyists at a hackerspace, so I am not hung up on any one usage and I can tell anybody that thinks that AVRs are irrelevant are still full of shit.. Where is your raspberry pi available for sale, fucker?

"Tenfold"?

[KramberryKoncerto]

TFA trivializes the result. A reduction of up to 90% the speed is not theoretically interesting at all - it could always be overridden by difference in architecture and implementation, often making older algorithms faster. There are many better ways to describe the reduction in time complexity to the laymen.

Re:"Tenfold"?

[KramberryKoncerto]

Typo: A reduction of up to 90% the "time"...

Re:"Tenfold"?

[Captain Segfault]

This result was rather interesting for SODA because it wasn't an improvement in time complexity over the best known algorithm. There are asymptotically faster previously known algorithms for computing sparse FFTs, but they aren't actually faster than the current (extremely optimized) FFT implementations unless the output is extremely sparse.

This algorithm isn't quite as asymptotically fast but it has a much better constant factor, so it is more likely to be effective in practice on inputs which are not extremely large and/or outputs which are not extremely sparse.

Re:"Tenfold"?

[ceoyoyo]

No, it doesn't trivialize the result. This is not an improvement in O order, as the FFT is over the DFT. It's an improvement in the average case time. Worst case performance is the same order as the FFT. I suspect that for most applications the speedup really is a factor X, where X is closely related to the sparsity of the signal.

Re:Can it be done effectivly without an FPU?

[introcept]

The interesting thing is that the greater time window over which the FFT operates, you can observe finer frequency detail within that particular window at the expense of how quickly the graph or bars change over time (in simplistic terms). I wonder how this new algo will change the frequency detail/transient time detail trade-off. Do we see more detail in both domains? Less? The same?

This is a property of the Discrete Fourier transform itself. For a certain window size there are only a discrete number of frequencies that you can calculate.
  The larger your window-> The more frequenecies you can see (at the expense of a longer sampling time)

FFT algorithms simply try to compute the DFT quickly, this advance is significant for paractical applications but doesn't change the underlying mathematics.

Re:Can it be done effectivly without an FPU?

[Bill Currie]

I fully expect it to be the same, as it comes down to information content. It's just not possible to extract information that isn't there, no matter what algorithm you use. Same problem as with "Enhance!" in the movies.

Re:Can it be done effectivly without an FPU?

[Fraggy_the_undead]

No reason to shout. Let people have their hobby! I think AVR and similar inexpensive microprocessors are a great way to get started in "not purely software" hackery. And if Arduino and the likes make it even easier, the better! Just because not everyone was born with a keyboard in their hand, typing into emacs, doesn't mean they don't have the right to explore the realm of programming with whatever editor and platform they like. Sure, there are a lot of applications these 8-bit MCUs are ill-suited for, but let them figure that out by themselves. It's a learning process, but you in your arrogance shout at AC because he/she wished for something you think is impossible. And maybe it is, but the way you communicate that is somewhat arrogant. There are plenty of paths to becoming an educated hacker and if it's via a Java-based IDE on Windows that's just as well.

Re:Can it be done effectivly without an FPU?

[introcept]

While I too am sick of seeing dinky little Arduino projects, there are plenty of good reasons to be doing FFT on low power micros.
For example, the company I work for designs battery powered wireless sensors: They have to be compact, consume minimal power and have minimal components for manufacture. We've got a single ATMega processor that sits between a sensor and a radio, doing, among other things, FFT and other 'DSP' functions to compress the data before we spend our precious milliamps transmitting it.
It really is the cheapeast, lowest power way to get the job done, sometimes a hardware DSP is overkill.

Re:Can it be done effectivly without an FPU?

[SuricouRaven]

It's more than a property of the DFT - it's a much deeper mathematical truth than that. The same fundamental mathematics is used to derive the uncertainty princible in quantum mechanics: For a signal to be perfectly defined in frequency it must be infinite in time, and vice versa. When you apply the same to quantum wave-functions... the uncertainty limit isn't a limit on measurements. It's a limit on what the universe is capable of representing.

Re:Can it be done effectivly without an FPU?

[SuricouRaven]

They do well when you need something a little more powerful and extensible than a PIC, but still need to watch the power consumption - and the shield system and standardised communication allowed for economy of scale in peripherals. You can take an arduino and just wire it to an ethernet interface, or a bluetooth interface, or an 11g interface, or an SD card reader, or all sorts of other forms of IO, without having to worry overly about compatibility. Plug and play for embedded computing.

Re:Can it be done effectivly without an FPU?

[YoopDaDum]

A math coprocessor is designed to speed-up floating point computations. But a FFT can be applied to integers too, and there are plenty of integer based FFT applications (telecom, audio...). In this case a basic FPU will not help you. On such a small processor as in the Arduino any use of the FFT will likely be integer based, with a small FFT size (think coarse spectrum analyzer for example).

The reason I say "basic FPU" above is that it seems to me most vector engines can also operate on integers, not only on floats. So they're not strictly FPU only anymore. And such vector units can typically also be used to speed-up integer FFTs, using a FFT specific addressing scheme (search for "Butterfly diagram" in wikipedia if you're interested). But then we're far from an Arduino ;)

Re:Can it be done effectivly without an FPU?

[Rising Ape]

The interesting thing is that the greater time window over which the FFT operates, you can observe finer frequency detail within that particular window at the expense of how quickly the graph or bars change over time (in simplistic terms). I wonder how this new algo will change the frequency detail/transient time detail trade-off. Do we see more detail in both domains? Less? The same?

That's a consequence of a fundamental mathematical relationship between the frequency and time domains and has nothing to do with the algorithm itself. A signal of length L can be exactly represented by a Fourier series of frequencies 0, 1/L, 2/L, 3/L... etc., with nothing in between, so there's no finer detail to see.

FTS applications...

[geogob]

As a scientist in the filed of Fourier Transform Spectroscopy I find this perspective quite interesting, even though it is not that different from other techniques we tried to apply in the field to improve performance. Needless to say, we are quite dependent on FFT performances in this field, even more since the deployment of Imagine FTS systems. Any improvement in FFT performance is noteworthy.

Lets see if its one of those "fields" where drastic performance improvement can be met! Regardless, it's quite an interesting break for signal processing.

Re:Can it be done effectivly without an FPU?

[thegarbz]

Actually a very large number of projects you see out there in the hobby arena are the opposite. It's a case of people throwing 8-bit microcontrollers at simple problems that can more easily / better be solved with either some discrete parts, logic ICs, or even analogue circuits.

Currently I use 8bit AVRs (not Arduinos) for most of my projects, but when I look around I find I have the opposite opinion to you. I have a digital radio complete with 128x64 pixel screen and a menu system that goes 3-4 levels deep that all runs on an 8bit microcontroller. There are projects out there that collect data from various forms then transmit wirelessly to a datalogger. There's even entire web servers running on 8bit microcontrollers. What I'm really wondering is what kind of an incredibly complex project do you have that requires more than what's available in most common $10 8-bit microcontrollers?

Also 16bit microcontrollers and worse still ARMs, comes with an even larger feature set than the standard AVR that powers the Arduino. This has some repercussions including making software more complicated (more registers to juggle which could be good or bad), often means a more complicated footprint (how many 16bit microcontrollers come in a 12pin DIP package), and sadly for several companies also means no decent free developer tools or a crippled compiler.

So ... just what kind of supercomputer are you building with your fancy 16bits? :-)

Another use -- Emergency News Broadcasting

[Taco Cowboy]

Another use that I can see for this technology is to use it for emergency and impromptu news broadcasting, especially when faced with dictatorial authorities (like Iran/China/Syria) which will do anything to stop unfavorable news from getting out to the world

Re:Another use -- Emergency News Broadcasting

[X0563511]

We already have that (eg, this wouldn't do much)... and in such cases an FFT would end up being used in, perhaps, some filtering on the audio.

You probably wouldn't be using SDR (where FFT is critical) for this - it's possible, but a cheap and rugged transceiver with a random-wire antenna is probably more practical here. (and on such a transceiver, the FFT, if used at all, would likely only be used in the DSP circuit - which merely helps the operator understand what he's receiving. Filters for RX and TX would be actual hardware.)

Re:Another use -- Emergency News Broadcasting

[X0563511]

In companion to my other reply to you, I forgot to mention:

Of the equipment itself, the hardest thing (from the 'fighting against the dictatorial authorities) is going to be keeping the antenna both mobile and hidden. Depending on what you're trying to do, this might be cumbersome, and you most definitely don't want to be in a fixed position - reusing the same transmission site is going to get your ass radio-direction-found...

To complicate that, most directional (read: high gain, more difficult to RDF or jam) antennas are fairly obvious - only simple dipoles and such (omnidirectional) are going to be easy to hide in plain sight.

Re:Another use -- Emergency News Broadcasting

[Anonymous Coward]

how does this have anything to do with the Fourier Transform? do people here even know what the Fourier Transform is?

Re:Another use -- Emergency News Broadcasting

[Gordonjcp]

It depends what you're trying to achieve. These days you might well be using SDR for this, because it's easier to do all the filtering and processing digitally and then bang the quadrature output through an upconverter.

For simple FM or AM broadcast, you could do it "all analogue" easily. For SSB - which I will admit is more geared to communications than broadcast - you are far better using SDR at least for your exciter. Crystal filters and phasing-type generators are a pain in the arse to construct and require carefully matched components. To do it in SDR it's a Hilbert transform, multiply with the rotating vector to shift it to your IF, and then apply an FIR filter to lop off the bits you don't want. Simple.

Re:Another use -- Emergency News Broadcasting

[X0563511]

True enough. and a Tayloe is easy to build as well.

Theoretical Minimum Joules Per Bit?

[Doc Ruby]

Has research established a theoretical minimum amount of joules required to transmit one bit of info, at the limits of computation?

Re:Theoretical Minimum Joules Per Bit?

[GlobalEcho]

Has research established a theoretical minimum amount of joules required to transmit one bit of info, at the limits of computation?

I would think that would be coming from the Planck constant, so something like hbar per second. But then to achieve a given level of reliability there would have to be some extra juice.

Re:Theoretical Minimum Joules Per Bit?

[Doc Ruby]

Does it matter how long it takes to transmit the bit, to determine the minimum energy required? If so, if the time is infinite, does it require infinitesimal energy?

Ok , I guess I'm mathematically a bit thick but...

[Viol8]

... how do you get from a load of say 16 bit samples into vectors? If I have sin wave sample data in an array such as the following:

0,5,10,5,0,-5,-10,-5,0

how does that then become a sequence of vectors to calculate the FT?

Re:Well put, & REALISTIC... apk

[msobkow]

I've no idea. I've been using JDBC for the past 15 years, or ODBC for .Net, and it's been 3-4 years since I last touched Oracle. The tuning tricks I was taught 20 years ago still seem to work though, and for most databases, not just Oracle.

I have 30+ years of RDBMS experience, having cut my teeth on the very earliest releases of Oracle, Sybase, and Ingres back when I was working for NorTel in around '89. I was on a project tasked to write real life applications with each of them so the company could compare performance. So three of us each developed our approaches independently, focusing on one database, but working together to make sure we were implementing the same business solution in each case.

While my database assignment was Ingres 1.0, I learned a lot about the differences from our design meetings, and went from there to Florida, where I soon became an Oracle DBA-level resource, brought on as a query tuning expert by Orange County's GIS department, AT&T's Payroll Processing department, and a couple others. I tuned a 27 hour GIS department query to run in 2-3 hours, and took AT&T's payroll processing down to around 20% of the run time.

When it comes to databases, I know my schite, but that doesn't mean I know ALL the tricks by any means. The more I learn, the more I realize how much I don't know.

For example, I've never used Oracle's C/C++ OCI APIs.

Re:Can it be done effectivly without an FPU?

[turing_m]

Slashdot could really use a +1 Insightful but Unnecessarily Dickish mod.

What is wrong with this picture?

Moderation categories already encompass both categories mentioned, and are an improvement on a simple "like" or "dislike". Adding multiple combinations of moderation (e.g. Insightful + Flamebait or Informative + Troll or any of the other 90 combinations you would needlessly add to the slashdot moderation system) is only slightly less stupid than allowing the herd of cats that is the slashdot moderator community to just create arbitrary moderation categories out of thin air any time they feel like it. There ARE TWO WHOLE FUCKING CATEGORIES OF MODERATION already dedicated to "Insightful but Unnecessarily Dickish", namely Insightful and Flamebait. The general idea is that on average the +1 from the Insightful and the -1 from the Flamebait cancel each other out, and people checking the moderations on their comments over time will come to realize they should be less of a dick but retain their level of insight.

But noooo, ignorant people such as yourself, would rather recommend slashdot implement the most arbitrary and poorly architected moderation system in the world just so you can get the +5 insiiiiiiiiightful. (And even if you would argue that Dickish!=Flamebait you are proposing a new 11th moderation category for "insightful but Unecessarily Dickish" worth a +1, which would result in the sizable misanthropic subset of slashdot users who would actually TRY to get their posts moderated as your wondrous new moderation category, thinking it is an improvement over plain old insightful.)

Re:Ok , I guess I'm mathematically a bit thick but

[Rockoon]

0,5,10,5,0,-5,-10,-5,0

You can consider them as vectors, but normally they are considered complex numbers.

0 + 0i, 5 + 0i, 10 + 0i, 5 + 0i, ....

Re:Can it be done effectivly without an FPU?

[Doc Ruby]

Except when your device is already made with Arduino, and then it needs to do something new that is DSP. Then you need DSP with Arduino. Even if it's "stupid" it might be necessary. Most application development must use the HW already present in its installed base, or die trying.

Since DSP (or rather NSP, since "Native Signal Processing" is what non-DSP CPUs were needed to do when there was no DSP but only a CPU in the installed base) isn't impossible on microcontrollers, just somewhat impractical on many of them. Yet the AVR ATMega is common in Arduino, and includes a HW multiplier that can be used for multiply-accumulate that is the core of DSP:

The component that makes a dedicated digital signal processor (DSP) specially suit-
able for signal processing is the Multiply-Accumulate (MAC) unit. This unit is
functionally equivalent to a multiplier directly connected to an Arithmetic Logic Unit
(ALU). The megaAVR microcontrollers are designed to give the AVR family the ability
to effectively perform the same multiply-accumulate operation. This application note
will therefore include examples of implementing the MAC operation.

Meanwhile, new Arduino Due boards include ARM processors with HW multipliers.

Even if the processor/microcontroller has no HW MAC, it can do DSP - just less efficiently. If its application needs DSP, it can do it.

Unless the developer just insists it's stupid. Then the Arduino cannot do it. But not because of the chip.

Re:Can it be done effectivly without an FPU?

[Doc Ruby]

Do you have math showing the compression consumes less power than just transmitting the raw data? And that it's less latent to wait for compression than to wait for uncompressed data to finish arriving?

Sample code, or it didn't happen

[SilentTristero]

I started reading the paper, and get the general idea -- but haven't yet checked out the prereqs, pseudorandom spectrum permutations and flat filtering windows. Is there sample code of this algorithm available anywhere?

Re:Sample code, or it didn't happen

[ceoyoyo]

So many people have the highly irritating habit of not writing either specific algorithms or sample code to go along with their papers.

Re:Can it be done effectivly without an FPU?

[gmarsh]

DSP is a *process*, not a *processor*.

You can run the same mathematical processes on a TMS320, DSP56K, FPGA, desktop PC, GPGPU video card, embedded ARM, PIC, AVR, even a 4-bit micro if you feel the need. Sure, a purpose-built DSP might be a bit faster at it than a microcontroller, but if the processor you choose is fast enough to run your DSP-like algorithm at the speed you need, what's the damn problem?

Case in point, there's really nothing better suited for decoding MP3/AAC audio than a DSP chip - a proper DSP can rip through filterbanks, MDCTs, etc. Yet almost every MP3 player on the market decodes these formats with an ARM core.

And back to the Arduino... AVRs have an 8x8->16 multiplier, post-increment/decrement addressing, and can run up to 20MHz so they're actually not that bad a choice for simple DSP algorithms that don't need a lot of dynamic range. An AVR has no trouble doing DTMF decoding on values captured from the ADC, or running a few DDS channels to generate sine waves and throw them out a PWM channel, despite those being classical DSP applications.

- Signed, someone who does DSP for a living.

Re:Can it be done effectivly without an FPU?

[Anonymous Coward]

Slashdot could REALLY use a +1 Insightful but Unnecessarily Dickish mod.

Re:Can it be done effectivly without an FPU?

[introcept]

Do you have math showing the compression consumes less power than just transmitting the raw data?

Lots of it, the power budget drives the design of the entire sensor.
The micro-controller uses a lot less energy than the packet radio so it makes sense to process the raw sensor data on-board and transmit information such as fourier coefficients, integrals and other statistics. Every packet saved is another fraciton of a second the radio can be powered down.

It's a fairly common technique with sensor networks to process raw signals at the point of collection and transmit only the useful information, it makes the most use of your bandwidth and in this case energy.

Re:Can it be done effectivly without an FPU?

[Anonymous Coward]

Exactly represented, yes, but not practically so.
Often the signal you are looking for doesn't have a frequency that fits well with the FFT frequency distribution. (The sampling time is not evenly divisable by the signal period time.)
This causes a pure sinus signal at the wrong frequency to be visible as a spread of frequencies where it is almost impossible to see adjacent signals with a lower amplitude.
Being able to calculate DFT with a method that doesn't have the same requirements the FFT algorithm have might give some nice benefits to signal analysis.
I guess we will have to wait until they have presented their method until we know if it will have any practical uses.

Imagine we lived....

[xTantrum]

...in a world where mathematicians patented their Ideas and when after violators with a vengeance.

Re:Can it be done effectivly without an FPU?

[Doc Ruby]

I don't think that Zigbee uses compression by default. Why do you think it doesn't, since Zigbee's main design goal is power efficiency?

Re:SOPA SODA

[TuringTest]

If you mix them they taste terrible. (SOPA = soup in Spanish)

Re:Can it be done effectivly without an FPU?

[rev0lt]

Given that mp3 decoding relies on MDCT, and that you can actually create a "digital" vu-meter (because you speak of mp3 players and bars, I guessed you were talking about it - I have never seen a mp3 player with an actual spectrum analyzer) with ampop-based filters (very common with 80s audio), I don't think the digital vu-meter is that awesome on a piece of high-tech equipment.

Re:Can it be done effectivly without an FPU?

[introcept]

Zigbee power efficiency isn't that great (Have a look at the ANT+ protocol).
Besides, this is lossy compression on a well understood signal. It would be stupid to transmit 1000 bytes of raw data when we only need a dozen bytes of information.

And......

[stanlyb]

And, do you know the most important area where this faster algorithm could be used? Yep, you are right, cryptography.

Re:Can it be done effectivly without an FPU?

[19thNervousBreakdown]

It could also use a bloo bloo bloo mod, now go fuck yourself.

mp3s are already in the frequency domain

[Anonymous Coward]

if you're running your EQ off of the time domain signal derived from the mp3, you're doing it wrong. :)

Re:mp3s are already in the frequency domain

[dintech]

Not EQ, though you can do FFT -> EQ -> FFT but it introduces latency that other methods avoid.

Re:Can it be done effectivly without an FPU?

[Erich]

Sure. Most DSPs don't have floating point. Looks like the AVR has an 8x8 multiply, so that really helps. Most DSPs use 16x16 multiplies, accumulating with a 32 bit or larger accumulator. That's going to take several instructions on an 8 bit micro, but it's certainly feasible for things like audio with low data rates and small FFTs. On the other hand, if you're using an Arduino to do audio FFT for things like a spectrum analyzer, this technique won't help, since you're not interested in picking up a few signals, but all the frequency bands.

Ahh, Slashdot

[Captain Segfault]

Posting a story about how a presentation will be given at SODA... about a day after SODA ended.

I actually went to this talk, which was scheduled for the first 8:30 AM timeslot as part of their evil conspiracy to get me to wake up early. The approach seemed remarkably straightforward, but I haven't gotten around to actually reading the paper yet -- I was too busy sightseeing around Kyoto.

Re:Can it be done effectivly without an FPU?

[Alex Belits]

You can run the same mathematical processes on a TMS320, DSP56K, FPGA, desktop PC, GPGPU video card, embedded ARM, PIC, AVR, even a 4-bit micro if you feel the need.

You can just as well run it on vacuum tubes or relays, however there are no real-world applications for that -- and the same applies for 8-bit microcontrollers.

An AVR has no trouble doing DTMF decoding on values captured from the ADC,

DTMF is specifically designed to be easy to decode with the worst possible limitations on a decoder. Claiming that it makes a microcontroller capable of DSP would be like saying that a lightbulb can be used to calculate exponents because it can produce a close approximation of a black body radiation spectrum.

or running a few DDS channels to generate sine waves and throw them out a PWM channel, despite those being classical DSP applications.

In name only. There is no actual processing involved.

- Signed, someone who does DSP for a living.

So do I, however I don't count trivial operation on tables of precomputed values as "DSP".

Re:Ok , I guess I'm mathematically a bit thick but

[serviscope_minor]

.. how do you get from a load of say 16 bit samples into vectors? If I have sin wave sample data in an array such as the following:

It's a single vector, not vectors (pllural): that's the important distinction. All the samples form a single vector.

In other words, if you have 1024 samples, then put them into a 1024 dimensional vector.

Does that clear it up?

Re:Can it be done effectivly without an FPU?

[NemoinSpace]

Slashdot could use a Insightful but -1 REALLY Dickish mod.

Re:Can it be done effectivly without an FPU?

[kelemvor4]

Slashdot could really use a +1 Insightful but Unnecessarily Dickish mod.

What is wrong with this picture?

Moderation categories already encompass both categories mentioned, and are an improvement on a simple "like" or "dislike". Adding multiple combinations of moderation (e.g. Insightful + Flamebait or Informative + Troll or any of the other 90 combinations you would needlessly add to the slashdot moderation system) is only slightly less stupid than allowing the herd of cats that is the slashdot moderator community to just create arbitrary moderation categories out of thin air any time they feel like it. There ARE TWO WHOLE FUCKING CATEGORIES OF MODERATION already dedicated to "Insightful but Unnecessarily Dickish", namely Insightful and Flamebait. The general idea is that on average the +1 from the Insightful and the -1 from the Flamebait cancel each other out, and people checking the moderations on their comments over time will come to realize they should be less of a dick but retain their level of insight.

But noooo, ignorant people such as yourself, would rather recommend slashdot implement the most arbitrary and poorly architected moderation system in the world just so you can get the +5 insiiiiiiiiightful. (And even if you would argue that Dickish!=Flamebait you are proposing a new 11th moderation category for "insightful but Unecessarily Dickish" worth a +1, which would result in the sizable misanthropic subset of slashdot users who would actually TRY to get their posts moderated as your wondrous new moderation category, thinking it is an improvement over plain old insightful.)

Were you deliberately trying to make GP's case, or was that an accident?

Any good for sparse approximation?

[SpinyNorman]

Does anyone know if this technique could be used to get a sparse approximation to a non-sparse signal (i.e. assume the signal only has a small number of components, and calculate what they would be to get a best match)?

That would be really useful - for example rather than JPEG/MPEG compression doing a regular FFT and throwing away the high frequency components, maybe you could use the fast sparse algorithm to quickly calculate an approximation in the first place.

Re:Any good for sparse approximation?

[SpinyNorman]

Ha ha - scratch that question - it is an approximation method!

Re:Any good for sparse approximation?

[ceoyoyo]

That's the idea. "Sparsity" doesn't mean it has lots of zeros, it means it has lots of values that you don't particularly care about (usually those that are close to zero.

Re:Can it be done effectivly without an FPU?

[X0563511]

So, you're talking about telemetry?

Re:Can it be done effectivly without an FPU?

[goertzenator]

DSP with Arduino

What is wrong with this picture?

There's nothing wrong with this picture. The Arduino is for hobbyists to learn and play, not for designing cost effective production grade products. If Arduino users can do DSP on their boards, the more power to them. Note that the upcoming Arduino Due is a Cortex-M3 (32 bit, 96MHz, no-FPU); this thing could do a fair amount of DSP compared to older Arduinos.

Re:Can it be done effectivly without an FPU?

[ortholattice]

the uncertainty limit isn't a limit on measurements. It's a limit on what the universe is capable of representing.

Only partially true. What many people don't know is that Heisenberg's derivation was slightly wrong because while it modeled the thing being measured with quantum mechanics, it incorrectly modeled the measuring device classically.

A rigorous analysis using qm for both was done Ozawa in 2003 (see http://arxiv.org/abs/1201.1833 which shows the correct uncertainty equations on p. 2).

From http://www.sciencedaily.com/releases/2012/01/120116095529.htm "In order to describe the fundamental uncertainty and the additional disturbance due to the measuring process, both particle and measurement device have to be treated in the framework of quantum theory,...But the product of error and disturbance can be made arbitrarily small -- even smaller than Heisenberg's original formulation"

Re:Can it be done effectivly without an FPU?

[rev0lt]

You can just as well run it on vacuum tubes or relays, however there are no real-world applications for that -- and the same applies for 8-bit microcontrollers.

Here you go - a 8051 FFT application note and implementation http://www.silabs.com/Support%20Documents/TechnicalDocs/an142.pdf

DTMF is specifically designed to be easy to decode with the worst possible limitations on a decoder. Claiming that it makes a microcontroller capable of DSP would be like saying that a lightbulb can be used to calculate exponents because it can produce a close approximation of a black body radiation spectrum.

Yes, and you also have DTMF decoding "on a chip" if you want it. But most "fast" 8-bit microcontrollers can handle the Goertzel Algorithm just fine.

Re:Limitation may be on capabilities of meat engin

[colinrichardday]

I don't know that I would have expressed this the way the GP did, but SuricouRaven is correct. Given a nonzero, time-limited signal, its Fourier transform can not be band limited, and vice versa.

If you weren't made of meat, perhaps the thing you think is a universal constant would be a variable. You can't actually know, because individual humans by definition cannot attain objectivity; it can only be approximated.

If objectivity can only be approximated, how do we know that your definitions are correct?

Limits on your perception and comprehension can be demonstrated to exist, therefore you can't know what all the limitations of the external universe are for certain

But one of the ways of thinking about Heisenberg uncertainty involves how we interact with particles. We would like to use particles that are both low energy (to not greatly affect the momentum of the particle we're trying to observe) and low wavelength (to get a better fix on its position). We just don't have such particles, at least not yet.

Re:Can it be done effectivly without an FPU?

[felipekk]

Slashdot could REALLY use a +1 Insightful but Unnecessarily Repetitive mod.

Sparse in frequency

[amstrad]

The point of this FFT improvement is for signals that are sparse in the frequency domain, not spatial domain. Most images _are_ sparse in frequency due to discretization during data collection.

Re:Can it be done effectivly without an FPU?

[morgauxo]

Dude, did someone replace your valium with caffeine today? Or were you molested by an Atmega chip as a child? You need a day off! Go get acquainted with the strange orange ball in the sky!

But what about the IFFT?

[Dogbertius]

But what about the inverse FFT? So I can FFT something quicker, but what about when I want to go the other way? ;)

Re:But what about the IFFT?

[sethstorm]

You get a dog that can meow and has a lot of fur.

Re:Can it be done effectivly without an FPU?

[Asmodae]

Aliasing can be avoided by having a high enough sampling frequency.

Re:Can it be done effectivly without an FPU?

[Asmodae]

More accurately, the number of frequency bins an FFT has is based on the number of samples you start with, which is based on the sampling rate times time, which ultimately gets back to Nyquist. You can only represent frequencies in the FFT that are within the nyquist rate, and an FFT has a number of frequency bins related to the number of samples being processed. The actual physical time of the sample window is a fall out of that combination of factors. Crank up the sampling rate over they same time period and you get more frequency bins and more accurate FFTs, contrary to what some of the other posters are going on about.

Re:Can it be done effectivly without an FPU?

[tepples]

I have a digital radio complete with 128x64 pixel screen and a menu system that goes 3-4 levels deep that all runs on an 8bit microcontroller.

More than that: Every NES game you ever played runs on an 8-bit microcontroller.

Re:Can it be done effectivly without an FPU?

[Asmodae]

What? Engineering difficulties occur in the sampling rates, the accuracy and noise floor of the A/D, and the hardware WAY before any quantum effects enter the picture. For FFT accuracy, the fundamental math is information theory and Nyquist.

Re:Can it be done effectivly without an FPU?

[Alex Belits]

Here you go - a 8051 FFT application note and implementation http://www.silabs.com/Support%20Documents/TechnicalDocs/an142.pdf [silabs.com]

Just because I can run FFT on a large abacus, does not mean that anyone should.

Yes, and you also have DTMF decoding "on a chip" if you want it. But most "fast" 8-bit microcontrollers can handle the Goertzel Algorithm just fine.

And those chips are obsolete now because microcontrollers caught up with them, and can do more in less space/cost/consumed current. This is not the case with DSP.

+/-1, Inciteful

[tepples]

The general idea is that on average the +1 from the Insightful and the -1 from the Flamebait cancel each other out

Then why not just create a new menu option "Inciteful" that doesn't affect a comment's score but spends two mod points to give the poster this message?

FFT avoids explicit sin/cos computation

[peter303]

In the "old days" these would take much longer than the integration calculations. by using a trig-identity you compute the new ones from power of two of the old ones using simple math. Or these days with large core memories you can pre-tabulate them, if you reuse the same lengths over and over.

Re:Can it be done effectivly without an FPU?

[Asmodae]

I think the parent is getting at a problem I see at my job fairly frequently. Professional Firmware and DSP developers that have no knowledge about the effects or consequence of their code on the hardware itself. Ultimately re-implementing something that used to run fine in 1/10th the ram, and 1/40th the processor cycles (or less) in a brand new dual core DSP and still can't figure out why they aren't meeting performance requirements. I've seen these guys demand a bigger, faster, more power hungry CPU to run their code when a previous version that was literally a fraction of the capability ran the same algorithm.

True Story: I'm an FPGA dev, and I was helping out software guys debug why the DSP was completely missing messages and seemed to be dropping data. Turns out doing a thousand lines of heavy DSP INSIDE the interrupt handler is probably going to hang up the CPU and cause it to miss interrupts. The worst part was the blank stares we got when we told them this, and had to explain why that was a bad thing.

It seems the idea of actually writing good, fast, and power efficient code is a dying art because it's perceived as 'not necessary'. In some instances this thinking is correct (e.g. desktop computers), but in the embedded space where you're trying to keep the cost of final products down and minimize power usage, grabbing the fastest DSP part that TI makes is probably not always the best solution... but it's what you get when you think it's automatically OK/good to 'do everything in software'. There are costs and penalties to account for.

For pure hobbyists, none of this really applies, but I suspect that a good many of the people that do this stuff as a hobby are also at least tangentially involved in it in some way at their jobs, so it serves to bring up the considerations.

Re:Can it be done effectivly without an FPU?

[somersault]

Same problem as with "Enhance!" in the movies.

The "Fast and Fouriers"?

Re:Can it be done effectivly without an FPU?

[Asmodae]

There are costs and consequences for any particular hardware choice. Modern MP3 players (and/or phones) need a general purpose CPU for many of the things they do and then use that to do decode since a separate extra part is the worse option. If the device didn't already HAVE a general purpose CPU, then an arm core is probably not the best option to solve an individual DSP problem.

Re:Can it be done effectivly without an FPU?

[HiggsBison]

I think they're still working on the Whoosh mod.

(Well crafted, turing_m!)

PFFT...

[almitydave]

That's a pretty fast Fourier transform.

Re:Can it be done effectivly without an FPU?

[nomel]

But, that's why this is interesting.

Where you might not have been able to squeeze in an FFT algorithm, now you might be able to.

But...for the price of an official Arduino, you could probably afford multiple DSP chips.

Re:Can it be done effectivly without an FPU?

[GrandTeddyBearOfDoom]

Time frequency uncertainty is a known issue in signal processing, and an explanation can be found early on in A Wavelet Tour of Signal Processing, for example. The post you are replying to stated that this is a fundamental property of the discrete Fourier transform, which it is.

Re:Can it be done effectivly without an FPU?

[ChrisMaple]

You can only represent frequencies in the FFT that are within the nyquist rate

That's almost true. However, if you know in advance that outside of a certain frequency range the signal is zero, the technique of subsampling can be used. The limit is bandwidth, not frequency.

Re:Can it be done effectivly without an FPU?

[Asmodae]

Fair enough, you can also under sample, and then use the aliased image if you know that the frequency range the alias lands on does not contain data. As you say, a bandwidth problem. But in the context of the original statement, it isn't the time length of the sample set, so much as the number of samples per unit time that determines FFT fidelity, time is part of it, but it's not independent.

Re:What about patents

[CurryCamel]

No, beacuse applying a new FFT algorithm (which now is readily published) to old problems is considered obvious for anyone skilled in the art. But if you could find a completely *new* thing to do with this algorithm, that wasn't possible earlier because Fast Fourier Transform wasn't fast enough - that you might be able to patent. A much more lucrative plan would be to search half a dozen of these old patents, implment them with the new algorithm and publish papers on these. Then collect you PhD, and get a cozy, moderately paying job.

Re:Can it be done effectivly without an FPU?

[fliptout]

I gotta say, putting a lot of code in the interrupt handler for a microcontroller/digital signal controller/dsp is a huge fail. That seems like something firmware engineers with an undergrad EE degree and a bit of experience should know. Even a software engineer with no low level hardware knowledge probably could have read in the DSP's programming guide that the ISR's execution would block the ISR from being triggered again.

Oh yeah, former TI dsp apps engineer here.

Re:Can it be done effectivly without an FPU?

[digitalsolo]

Slashdot could REALLY use a +1 Insightful but Unnecessarily Repetitive mod.

Re:Can it be done effectivly without an FPU?

[turkeyfish]

Problem is of course, one can not know regardless of bandwidth for certain that outside a certain frequency range the signal is zero. One can only assume that it is close to zero. One can not "crank up" sampling rates to infinity to overcome this as every system has finite limits and hence error. The original paper spends much time discussing the nature of the error bounds for precisely this reason.

Re:Can it be done effectivly without an FPU?

[dtmos]

It seems the idea of actually writing good, fast, and power efficient code is a dying art

Boy, give this guy a gold star. Exactly for the reason he states (most people today learn programming by programming for desktop computers), finding a good embedded software person for battery-powered, portable applications is becoming a unicorn search.

Every time I hear someone say that they're burned out on software, and can't stand the thought of writing another line of server or game or PC code, I always suggest a change of venue from desktop to embedded software -- a change that, once (s)he adapts to the realities of life on a AAA or hearing-aid battery, will typically take a programmer from project commodity to project savior.

Misleading title

[SoftwareArtist]

Here's the first sentence of the abstract: "We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal." Did you notice the word "approximation" in there? Right. This is an algorithm for calculating an approximation to the Fourier transform, not the actual Fourier transform. There are, to be sure, lots of problems where that's exactly what you want, and this algorithm could be really useful for them. There are also a lot of problems where that's not useful at all, and you need the exact transform. In any case, calling this a "Faster-Than-Fast Fourier Transform" is just wrong. It isn't a Fourier transform. It's an approximation to the Fourier transform.

Re:Misleading title

[SpinyNorman]

But even a regular FFT requires you to pre-specify the accuracy in terms of (maximum) number of components, so the difference appears a bit more subtle.

I wonder what the difference is between doing a length-k FFT of an n-dimensional signal vs doing a k-sparse approximation to it using this algorithm?

Re:Misleading title

[SoftwareArtist]

Not true. A discrete Fourier transform is an exact, lossless transform. Given N components in the time domain, it produces N components in the frequency domain. You can then apply the inverse transform, and you're guaranteed to get back precisely the N numbers you started with. The algorithm in this paper is not an exact transform. If you apply it, then apply the inverse transform, you will get back a different set of numbers from the ones you started with.

Re:Can it be done effectivly without an FPU?

[ceoyoyo]

The same. The frequency-time resolution tradeoff is a fundamental property, and the short-time DFT makes that tradeoff efficiently.

Re:Can it be done effectivly without an FPU?

[ceoyoyo]

He's not saying that the time-frequency resolution tradeoff is due to quantum physics effects. He's saying that the two uncertainty principles are related. They are. We're talking about pure theory here, with no engineering difficulties. And yes, the fundamental math is information theory and Nyquist (which is ALSO very similar to the fundamental math of quantum physics). The equations for the two uncertainty principles have exactly the same form.

An ideal, theoretical, continuous signal that is time-limited has limited spectral resolution. An ideal, theoretical, continuous spectrum has limited temporal resolution.

Re:Can it be done effectivly without an FPU?

[Asmodae]

Of course it's a problem. My point was that for all practical issues, engineering difficulties are what imposes the limits before you have to worry about quantum effects.

Yes, it's a property of the DFT. Or more generally Information uncertainty is a property of all discrete systems which sample at fixed intervals, that's what nyquist is all about. If you didn't sample it, you can't know it if there's data outside of your sampled signal's bandwidth it can alias down onto your desired data and cause all kinds of problems.

The post I replied to implied there was something more going on at some fundamental physical level. At the quantum level quantum stuff is happening, sure. In quantum mechanics the uncertainty principle is expressed with a wave function which states the probability of the state of a particle. We don't talk about quantum uncertainties in digital signal processing.

I don't have the textbook you mention so you might provide a better source or link. The stuff I find by googling are not things we deal with in the digital domain. When you start including quantum wave function probabilities in your signal processing algorithms, let me know. :)

Re:Can it be done effectivly without an FPU?

[dintech]

To be specific I'm talking about multi-band graphic analysers, not just overall volume. Most software analysers as far as i was aware are similar underneath to something like Specan32 or even Voxengo Span.

These implement FFT to split up the signal into different composite frequencies. The different bars represent the volume of each of the frequencies. The size of the FFT window contributes to how many 'bars' you can accurately represent.

Re:Can it be done effectivly without an FPU?

[ceoyoyo]

What you say isn't actually wrong, but it's not talking about the same thing. The frequency resolution you can achieve is determined by the amount of time you observe a signal, regardless of how you sample it (the principle holds for ideal continuous signals as well) and conversely, the temporal resolution of a signal you reconstruct is limited by the highest frequency you observe. The DFT (the FFT is just a fast algorithm for the DFT and produces the same result) represents a spectrum efficiently by providing samples that match this fundamental limitation.

Re:Can it be done effectivly without an FPU?

[Asmodae]

hehe, indeed. Cut'n'pasty code reuse no-design fail.

It was test code, written as a throw away proof of concept, on prototype hardware, run on it's own without anything else on the system, that had been grabbed, copied, reused several times and then tried to push into a the real hardware with the full system running at the same time. I did more than one double take when we found it, and again when I saw the real code.

Moral of the story: all code is production code, there is no such thing as throw-away one-off test code. Although that doesn't seem to get through to program managers who write schedules so the cycle repeats. If someone gets a thing working, someone somewhere will think "it worked in the lab, ship it!"

Walsh-Hadamard

[Frank Knarf]

If you really want fast, use discreet Walsh-Hadamard xform and look-up tables.

Re:The example is not accurate

[ceoyoyo]

Virtually all images of any interest (anything that's not just random noise) is sparse in some domain, and the majority are quite sparse in the frequency domain. So yes, this algorithm should help quite a bit.

Re:The Fast lifting wavelet transform still beats

[ceoyoyo]

The null transform beats them both. So does the plus-one transform. What's your point?

Re:Can it be done effectivly without an FPU?

[thegarbz]

The problem is experiences differ with different components. Some microcontrollers have a concept of configurable interrupt priority, where a running ISR can be interrupted yet again by a different ISR. I got bitten by this when I switched to AVR. I had a timing loop running and assumed that it would get priority over a simple key press as one of my previous designs (Yes I'm a lazy coder, but it worked for me previously :-P). Anyway first time I hit the keypress the timing loop stopped dead, held the output, and blew the LEDs connected to them due to over current.

I made a dumb assumption without reading the 300 page datasheet. I can imagine how someone will do the same.

Re:Can it be done effectivly without an FPU?

[muridae]

Turns out doing a thousand lines of heavy DSP INSIDE the interrupt handler

I'm not a computer engineer, or EE, or signals person, but even I can tell you why that would fail. Sounds like the problem is not that people program general purpose chips, but that someone hired general purpose programmers to write DSP code. DSP is a beast, it's its own subset of programming that requires knowledge of physics (waves and nyquist) that some programmers don't know. Or maybe the problem really was that your programmers don't know what a bloody interrupt is, and shouldn't even be writing embedded programs.

I'm just a software geek who, after a MIPS course, decided that doing neat artsy tricks with smaller and smaller processors was fun. The Arduino works fine for that, even doing minor audio processing. Why? Because $30 for a board and $1 for extra Atmel chips was a cheaper option than a ton of breadboards, some dedicated usb to serial programmers, and a PIC or ARM dev board. Why? Because at the time the Arduino came out, the programmer for a PIC cost $30 or more unless you already had another programmer and could build your own. There was no cheap way into the field unless you knew someone already in the field. Forget digging through a digikey catalog, no one completely new to embedded programming is going to be able to make sense out of the hundred of different JTAG programming cables, and the brand name ones are still insanely expensive compared to a $30 Arduino or close and a usb cable. Only jobs I've gotten to use these skills on are art projects, where something small needs to be hidden out of sight while still being able to control some larger object. Arduino + Java is easier for the artists to read and understand what's going on, and since the board and a wall wart can be hidden in places that a even a mini ITX motherboard couldn't, and is quieter, it makes it an easy sell. Yeah, you do crazy things that the chip wasn't designed for, so what? Sure, the Java programming language sucks, but if you need to you can get around that if you know C. And you can learn AVR C by reading the datasheets and knowing enough C++; I did anyways.

Re:Can it be done effectivly without an FPU?

[thegarbz]

For pure hobbyists, none of this really applies, but I suspect that a good many of the people that do this stuff as a hobby are also at least tangentially involved in it in some way at their jobs, so it serves to bring up the considerations.

This is quite a key bit here. While doing EE I and most of my friends were heavily screwing around with microcontrollers. Some of them just plainly threw in the towel trying to debug code and many still don't understand the concepts of an interrupt properly.

I later tutored some embedded practical project design courses at the same uni. I quickly got a reputation for being an arse marker because I came down quite heavily on students when I would do something as simple as press a button and note that the software registered the press twice, or that the display dimmed, stuttered or got brighter, classic examples of ISRs not playing nice. The excuse I always got is that it's a minor glitch or bug.

Their smiles faded when I told them it's more a sign that they don't understand the platform they are coding on, and to solve that "minor glitch" could mean a complete re-think in the way they've structured their code.

Re:Can it be done effectivly without an FPU?

[Asmodae]

Turns out doing a thousand lines of heavy DSP INSIDE the interrupt handler

I'm not a computer engineer, or EE, or signals person, but even I can tell you why that would fail. Sounds like the problem is not that people program general purpose chips, but that someone hired general purpose programmers to write DSP code. DSP is a beast, it's its own subset of programming that requires knowledge of physics (waves and nyquist) that some programmers don't know. Or maybe the problem really was that your programmers don't know what a bloody interrupt is, and shouldn't even be writing embedded programs.

As you say, it requires several skill sets at once. Embedded DSP requires extensive theory and mathematical knowledge so you KNOW the stuff, as well as low level hardware knowledge of the target device (either in an FPGA or DSP or GPP) so the code is efficient and fast enough to meet the needs of the platform.

There's more than a few of our signal processing gurus with PHd's that are absolutely brilliant, but have no idea about low level hardware. They can develop algorithms and model them in matlab to prove the ideas are possible. They've taught themselves C, or taken a class or two, so they can program stuff and hack it together. But when their test code tries to get used 'for real', the design problems show up.

Knowing some C does not an embedded programmer make.

Re:Can it be done effectivly without an FPU?

[Doc Ruby]

I don'think Zigbee should assume the data has already been compressed, especially in sensors (like temperature and humidity) integrated entirely into the same microcontroller that controls the Zigbee process.

Yep

[shiftless]

I concur.

Re:Can it be done effectivly without an FPU?

[viperidaenz]

You could stop using an Arduino as a golden hammer and use something designed for DSP, like a dsPIC that has hardware to do more complex math

Re:Can it be done effectivly without an FPU?

[Rising Ape]

I think we're describing the same thing. This phenomenon is just another, less familiar type of aliasing - the "spread of frequencies" you mention will give exactly the same signal in the sampling window as the pure sine wave with a frequency that's a non-integer multiple of 1/the window size, so there's no way for any algorithm to distinguish them. The only way to do that is take your Fourier transform over a larger window, at least for arbitrary input data.

Re:Can it be done effectivly without an FPU?

[Rising Ape]

Not all kinds of aliasing. The one the grandparent described would be a problem even with continuous sampling - it's caused by taking the Fourier transform over a finite length (L) window. Any frequencies which aren't integer multiples of 1/L will be aliased into ones which are.

Re:Can it be done effectivly without an FPU?

[Alex Belits]

"Processing" requires at least existence of a signal input and signal output. Those applications have only output signal.

Re:Can it be done effectivly without an FPU?

[schwaang]

My faith is restored. I salute you.

Re:Can it be done effectivly without an FPU?

[rev0lt]

Yeah it seems those simple bar-displays per frequency I was calling "vu-meter" are also called "spectrum analysers", but it's exactly what you indicated on the link. Most old audio equipment does not use a FFT, but a series of filters (check http://www.electronics-lab.com/blog/?p=7057 , theirs is with nixie tubes, but the principle is the same). Modern mp3 players do not need much effort to reproduce a bar-based spectral analysis, because usually the file format is already encoded on the frequency domain.
Btw, when I think spectrum analyzers, I think of this kind of equipment: http://www.tek.com/spectrum-analyzer/rsa5000 .