The Fastest Fourier Transform In The West

November 23, 2022 by Dave Walker 22 Comments

An interesting aspect of time-varying waveforms is that by using a trick called a Fourier Transform (FT), they can be represented as the sum of their underlying frequencies. This mathematical insight is extremely helpful when processing signals digitally, and allows a simpler way to implement frequency-dependent filtration in a digital system. [klafyvel] needed this capability for a project, so started researching the best method that would fit into an Arduino Uno. In an effort to understand exactly what was going on they have significantly improved on the code size, execution time and accuracy of the previous crown-wearer.

A complete real-time Fourier Transform is a resource-heavy operation that needs more than an Arduino Uno can offer, so faster approximations have been developed over the years that exchange absolute precision for speed and size. These are known as Fast Fourier Transforms (FFTs). [klafyvel] set upon diving deep into the mathematics involved, as well as some low-level programming techniques to figure out if the trade-offs offered in the existing solutions had been optimized. The results are impressive.

Fastest FFT code benchmarking results in ms — Benchmarking results showing speed of implementation versus the competition (ApproxFFT)

Not content with producing one new award-winning algorithm, what is documented on the blog is a masterclass in really understanding a problem and there are no less than four algorithms to choose from depending on how you rank the importance of execution speed, accuracy, code size or array size.

Along the way, we are treated to some great diversions into how to approximate floats by their exponents (French text), how to control, program and gather data from an Arduino using Julia, how to massively improve the speed of the code by using trigonometric identities and how to deal with overflows when the variables get too large. There is a lot to digest in here, but the explanations are very clear and peppered with code snippets to make it easier and if you have the time to read through, you’re sure to learn a lot! The code is on GitHub here.

If you’re interested in FFTs, we’ve seen them before around these parts. Fill your boots with this link of tagged projects.

Blinking An Arduino LED, In Julia

June 20, 2022 by Elliot Williams 11 Comments

The Julia programming language is a horrible fit for a no-frills microcontroller like the ATMega328p that lies within the classic Arduino, but that didn’t stop [Sukera] from trying, and succeeding.

All of the features that make Julia a cool programming language for your big computer make it an awful choice for the Arduino. It’s designed for interactivity, is dynamically typed, and leans heavily on its garbage collection; each of these features alone would tax the Mega to the breaking point. But in its favor, it is a compiled language that is based on LLVM, and LLVM has an AVR backend for C. Should just be a simple matter of stubbing out some of the overhead, recompiling LLVM to add an AVR target for Julia, and then fixing up all the other loose ends, right?

Well, it turns out it almost was. Leaning heavily on the flexibility of LLVM, [Sukera] manages to turn off all the language features that aren’t needed, and after some small hurdles like the usual problems with volatile and atomic variables, manages to blink an LED slowly. Huzzah. We love [Sukera’s] wry “Now THAT is what I call two days well spent!” after it’s all done, but seriously, this is the first time we’ve every seen even super-rudimentary Julia code running on an 8-bit microcontroller, so there are definitely some kudos due here.

By the time that Julia is wedged into the AVR, a lot of what makes it appealing on the big computers is missing on the micro, so we don’t really see people picking it over straight C, which has a much more developed ecosystem. But still, it’s great to see what it takes to get a language designed around a runtime and garbage collection up and running on our favorite mini micro.

Thanks [Joel] for the tip!