The Fastest Fourier Transform In The West

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.

Stanislaw playing notes on his MIDI keyboard, with the LEDs on the LED strip lighting up right above the note he's playing, driven by the Raspberry Pi that runs a script based on the Pianolizer toolkit

Pianolizer Helps Your Musical Projects Distinguish Notes

[Stanislaw Pusep] has gifted us with the Pianolizer project – an easy-to-use toolkit for music exploration and visualization, an audio spectrum analyzer helping you turn sounds into piano notes. You can run his toolkit on a variety of different devices, from Raspberry Pi and PCs, to any browser-equipped device including smartphones, and use its note output however your heart desires. To show off his toolkit in action, he set it up on a Raspberry Pi, with Python code taking the note data and sending color information to the LED strip, displaying the notes in real time as he plays them on a MIDI keyboard! He also created a browser version that you can use with a microphone input or an audio file of your choosing, so you only need to open a webpage to play with this toolkit’s capabilities.

He took time to make sure you can build your projects with this toolkit’s help, providing usage instructions with command-line and Python examples, and even shared all the code used in the making of the demonstration video. Thanks to everything that he’s shared, now you can add piano note recognition to any project of yours! Pianolizer is a self-contained library implemented in JavaScript and C++ (which in turn compiles into WebAssembly), and the examples show how it can be used from Python or some other language.

[Stanislaw] also documented the principles behind the code, explaining how the note recognition does its magic in simple terms, yet giving many insights. We are used to Fast Fourier Transform (FFT) being our go-to approach for spectral analysis, aka, recognizing different frequencies in a stream of data. However, a general-purpose FFT algorithm is not as good for musical notes, since intervals between note frequencies become wider as frequency increases, and you need to do more work to distinguish the notes. In this toolkit, he used a Sliding Discrete Fourier Transform (SDFT) algorithm, and explains to us how he derived the parameters for it from musical note frequencies. In the end of the documentation, he also gives you a lot of useful references if you would like to explore this topic further!

What are you going to build with this? Maybe, a box that records you playing the flute and instantly turns it into sheet music? Or, perhaps, an AI that continues the song for you when you stop?

Continue reading “Pianolizer Helps Your Musical Projects Distinguish Notes”

FFT display on 16x16 RGB LED grid

Art Project Fast And Fouriously Transforms Audio Into Eye Candy

Fast Fourier Transforms. Spectrum Analyzers. Waterfall displays. Not long ago, such terms were reserved for high end test gear. But oh, how things have changed! It’s no surprise to many Hackaday readers that modern microcontrollers have transformed the scene as they become more powerful and as a result are endowed with more and more powerful software libraries. [mircemk] has used such a library along with other open source software combined with mostly off the shelf hardware to create what he calls the DIY FFT Spectrum Analyzer. Rather than being a piece of test gear, this artful project aims to please the eye.

The overall build is relatively simple. Audio is acquired via a line-in jack or a microphone, and then piped into an ESP32. The ESP32 runs the audio through the FFT routine, sampling, slicing, and dicing the audio into 16 individual bands. The visual output is displayed on a 16 x 16 WS2812 Led Matrix. [mircemk] wrote several routines for displaying the incoming audio, with a waterfall, a graph, and other visualizations that are quit aesthetically pleasing. Some of them are downright mesmerizing! You can see the results in the video below the break.

Of course the build doesn’t stop with slapping some hardware and a few passive components together. To really be finished, it needs to be encased in something worth displaying. [mircemk] does not disappoint, as a beautiful 3D-printed enclosure wraps it all up nicely.

We think that the final product is great, and it reminds us of some of the very things that inspired us early on in our hacking careers. We would love to see this project integrated with an Interactive Musical Art Installation of any kind, the more esoteric the better. Perhaps a 555 timer synth could fit the bill? Be sure to share your own hacks with us via the Tip Line!

Continue reading “Art Project Fast And Fouriously Transforms Audio Into Eye Candy”

Even Faster Fourier Transforms On The Raspbery Pi Zero

Oftentimes in computing, we start doing a thing, and we’re glad we’re doing it. But then we realise, it would be much nicer if we could do it much faster. [Ricardo de Azambuja] was in just such a situation when working with the Raspberry Pi Zero, and realised that there were some techniques that could drastically speed up Fast Fourier Transforms (FFT) on the platform. Thus, he got to work.

The trick is using the Raspberry Pi Zero’s GPU to handle the FFTs instead of the CPU itself. This netted Ricardo a 7x speed upgrade for 1-dimensional FFTs, and a 2x speed upgrade for 2-dimensional operations.

The idea was cribbed from work we featured many years ago, which provided a similar speed up to the very first Raspberry Pi. Given the Pi Zero uses the same SoC as the original Raspberry Pi but at a higher clock rate, this makes perfect sense. However, in this case, [Ricardo] implemented the code in Python instead of C as suits his use case.

[Ricardo] uses the code with his Maple Syrup Pi Camera project, which pairs a Coral USB machine learning accelerator with a Pi Zero and a camera to achieve tasks such as automatic licence plate recognition or facemask detection. Fun!

Big Mouth Billy Bass Channels Miley Cyrus

Here’s a Big Mouth Billy Bass with extra lip thanks to Alexa. If you’re not already familiar, Big Mouth Billy Bass is the shockingly popular singing animatronic fish designed to look like a trophy fish mounted to hang on your wall. In its stock condition, Billy uses a motion sensor to break into song whenever someone walks by. It’s limited to a few songs, unless you like to hack things — in which case it’s a bunch of usable parts wrapped in a humorous fish! Hackaday’s own [Bob Baddeley] combined the fish with an Amazon Echo Dot, connecting the two with an ATtiny84, and having Billy speak for Alexa.

[Bob] had a few problems to solve, including making Billy’s mouth move when there was audio playing, detecting when the Echo was on, moving the motors and playing the audio. After a bit of research and a lot of tweaking, a Fast Fourier Transform algorithm designed for the ATtiny was used was used to get the mouth moving. The mouth didn’t move a lot because of the design of the fish, and [Bob] modified it a bit, but there was only so much he could do.

It’s all well and good for the fish to lie there and sing, but [Bob] wanted Billy to move when Alexa was listening, and in order the detect this, the best bet was to watch for the Dot’s light to turn on. He tried a couple of things but decided that the simplest method was probably the best and ended up just taping a photo-resistor over the LED. Now Billy turns to look at you when you ask Alexa a question.

With a few modifications to the Dot’s enclosure, everything now fits inside the original mounting plaque and, after some holes were drilled so the Dot could hear, working. Billy has gone from just a few songs to an enormous entire library of songs to sing!

We’ve seen Alexa combined with Big Mouth Billy Bass before, but just demos and never an excellent guide like [Bob’s].  The nice thing about this guide is that once you’ve hacked the hardware, it’s a breeze to add new functionality using Alexa skills.

Continue reading “Big Mouth Billy Bass Channels Miley Cyrus”

Hackaday Prize Entry: Open Source FFT Spectrum Analyzer

Every machine has its own way of communicating with its operator. Some send status emails, some illuminate, but most of them vibrate and make noise. If it hums happily, that’s usually a good sign, but if it complains loudly, maintenance is overdue. [Ariel Quezada] wants to make sense of machine vibrations and draw conclusions about their overall mechanical condition from them. With his project, a 3-axis Open Source FFT Spectrum Analyzer he is not only entering the Hackaday Prize 2016 but also the highly contested field of acoustic defect recognition.

open_fft_machineFor the hardware side of the spectrum analyzer, [Ariel] equipped an Arduino Nano with an ADXL335 accelerometer, which is able to pick up vibrations within a frequency range of 0 to 1600 Hz on the X and Y axis. A film container, equipped with a strong magnet for easy installation, serves as an enclosure for the sensor. The firmware [Ariel] wrote is an efficient piece of code that samples the analog signals from the accelerometer in a free running loop at about 5000 Hz. It streams the digitized waveforms to a host computer over the serial port, where they are captured and stored by a Python script for further processing.

From there, another Python script filters the captured waveform, applies a window function, calculates the Fourier transform and plots the spectrum into a graph. With the analyzer up and running, [Ariel] went on testing the device on a large bearing of an arbitrary rotating machine he had access to. A series of tests that involved adding eccentric weights to the rotating shaft shows that the analyzer already makes it possible to discriminate between different grades of imbalance.

The HackadayPrize2016 is Sponsored by:

Ping Pong Spectrum Analyzer

A spectrum analyzer is a pretty useful tool for working with signals where the size of the frequency components matter. Usually, the display is a screen. Sometimes, you see it done with LEDs. [Mag Laboratories] did it with ping pong balls.

The device uses a processor to calculate a Fourier transform, cutting an audio signal into 16 frequency bands. The processor converts each of these values to a PWM output that drives small fans. The fans blow the ping pong ball up the tube proportional to the fan speed. You can see the result in the video below.

Continue reading “Ping Pong Spectrum Analyzer”