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

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]

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

[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

[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

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]

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

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 :)

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

[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

[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: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

[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

[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

[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: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: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.

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: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.

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?

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?

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?

[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?

[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.

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?

[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: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: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: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.

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: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.

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?

[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?

[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!

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]

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?

[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.

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?

[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.