DSPRelated.com

How the Cooley-Tukey FFT Algorithm Works | Part 4 - Twiddle Factors

Mark Newman December 2, 2024

The beauty of the FFT algorithm is that it does the same thing over and over again. It treats every stage of the calculation in exactly the same way. However, this. “one-size-fits-all” approach, although elegant and simple, causes a problem. It misaligns samples and introduces phase distortions during each stage of the algorithm. To overcome this, we need Twiddle Factors, little phase correction factors that push things back into their correct positions before continuing onto the next stage.


How the Cooley-Tukey FFT Algorithm Works | Part 3 - The Inner Butterfly

Mark Newman November 25, 2024

At the heart of the Cooley-Tukey FFT algorithm lies a butterfly, a simple yet powerful image that captures the recursive nature of how the FFT works. In this article we discover the butterfly’s role in transforming complex signals into their frequency components with efficiency and elegance. Starting with the 2-point DFT, we reveal how the FFT reuses repeated calculations to save time and resources. Using a divide-and-conquer approach, the algorithm breaks signals into smaller groups, processes them through interleaving butterfly diagrams, and reassembles the results step by step.


How the Cooley-Tukey FFT Algorithm Works | Part 2 - Divide & Conquer

Mark Newman November 18, 2024

The Fast Fourier Transform revolutionized the Discrete Fourier Transform by making it much more efficient. In part 1, we saw that if you run the DFT on a power-of-2 number of samples, the calculations of different groups of samples repeat themselves at different frequencies. By leveraging the repeating patterns of sine and cosine values, the algorithm enables us to calculate the full DFT more efficiently. However, the calculations of certain groups of samples repeat more often than others. In this article, we’re going to explore how the divide-and-conquer method prepares the ground for the next stage of the algorithm by grouping the samples into specially ordered pairs.


How the Cooley-Tukey FFT Algorithm Works | Part 1 - Repeating Calculations

Mark Newman November 11, 20244 comments

The Fourier Transform is a powerful tool, used in many technologies, from audio processing to wireless communication. However, calculating the FT can be computationally expensive. The Cooley-Tukey Fast Fourier Transform (FFT) algorithm provides a significant speedup. It exploits the repetitive nature of calculations within the Discrete Fourier Transform (DFT), the mathematical foundation of the FT. By recognizing patterns in the DFT calculations and reusing intermediate results, the FFT vastly reduces the number of operations required. In this series of articles, we will look at how the Cooley-Tukey FFT algorithm works.


The 2024 DSP Online Conference

Stephane Boucher October 28, 2024

Here we go!

This week is the fifth edition of the DSP Online Conference! This milestone year marks our 5th anniversary, and we’re celebrating with a stellar lineup of renowned DSP experts like fred harris, Rick Lyons, Julius Orion Smith III, and Dan Boschen. These industry leaders will be generously sharing their knowledge and insights with the DSP community.

Why Attend?

Even if your schedule is packed this week, purchasing a pass grants you on-demand access to all...


Learn to Use the Discrete Fourier Transform

Neil Robertson September 28, 2024

Discrete-time sequences arise in many ways: a sequence could be a signal captured by an analog-to-digital converter; a series of measurements; a signal generated by a digital modulator; or simply the coefficients of a digital filter. We may wish to know the frequency spectrum of any of these sequences. The most-used tool to accomplish this is the Discrete Fourier Transform (DFT), which computes the discrete frequency spectrum of a discrete-time sequence. The DFT is easily calculated using software, but applying it successfully can be challenging. This article provides Matlab examples of some techniques you can use to obtain useful DFT’s.


The 2024 DSP Online Conference

Stephane Boucher July 10, 2024

We are very excited to announce that the DSP Online Conference is back this year for a fourth year in a row and will take place October 29, 30 and 31.

Unlike traditional DSP conferences, where most talks are highly specialized and tailored to researchers, our conference is designed to be accessible to a broader audience of DSP enthusiasts, from students and practicing engineers to hobbyists and DSP experts.

For this year's edition, we are aiming to provide a program that will be organized...


Model a Sigma-Delta DAC Plus RC Filter

Neil Robertson March 16, 20242 comments

Sigma-delta digital-to-analog converters (SD DAC’s) are often used for discrete-time signals with sample rate much higher than their bandwidth. For the simplest case, the DAC output is a single bit, so the only interface hardware required is a standard digital output buffer. Because of the high sample rate relative to signal bandwidth, a very simple DAC reconstruction filter suffices, often just a one-pole RC lowpass. In this article, I present a simple Matlab function that models the combination of a basic SD DAC and one-pole RC filter. This model allows easy evaluation of the overall performance for a given input signal and choice of sample rate, R, and C.


DAC Zero-Order Hold Models

Neil Robertson January 21, 20242 comments

This article provides two simple time-domain models of a DAC’s zero-order hold. These models will allow us to find time and frequency domain approximations of DAC outputs, and simulate analog filtering of those outputs. Developing the models is also a good way to learn about the DAC ZOH function.


Decimators Using Cascaded Multiplierless Half-band Filters

Neil Robertson November 19, 2023

In my last post, I provided coefficients for several multiplierless half-band FIR filters. In the comment section, Rick Lyons mentioned that such filters would be useful in a multi-stage decimator. For such an application, any subsequent multipliers save on resources, since they operate at a fraction of the maximum sample frequency. We’ll examine the frequency response and aliasing of a multiplierless decimate-by-8 cascade in this article, and we’ll also discuss an interpolator cascade using the same half-band filters.


A Quadrature Signals Tutorial: Complex, But Not Complicated

Rick Lyons April 12, 201364 comments

Introduction Quadrature signals are based on the notion of complex numbers and perhaps no other topic causes more heartache for newcomers to DSP than these numbers and their strange terminology of j operator, complex, imaginary, real, and orthogonal. If you're a little unsure of the physical meaning of complex numbers and the j = √-1 operator, don't feel bad because you're in good company. Why even Karl Gauss, one the world's greatest mathematicians, called the j-operator the "shadow of...


A Fixed-Point Introduction by Example

Christopher Felton April 25, 201122 comments
Introduction

The finite-word representation of fractional numbers is known as fixed-point.  Fixed-point is an interpretation of a 2's compliment number usually signed but not limited to sign representation.  It extends our finite-word length from a finite set of integers to a finite set of rational real numbers [1].  A fixed-point representation of a number consists of integer and fractional components.  The bit length is defined...


Understanding and Preventing Overflow (I Had Too Much to Add Last Night)

Jason Sachs December 4, 2013

Happy Thanksgiving! Maybe the memory of eating too much turkey is fresh in your mind. If so, this would be a good time to talk about overflow.

In the world of floating-point arithmetic, overflow is possible but not particularly common. You can get it when numbers become too large; IEEE double-precision floating-point numbers support a range of just under 21024, and if you go beyond that you have problems:

for k in [10, 100, 1000, 1020, 1023, 1023.9, 1023.9999, 1024]: try: ...

Sum of Two Equal-Frequency Sinusoids

Rick Lyons September 4, 20146 comments

Some time ago I reviewed the manuscript of a book being considered by the IEEE Press publisher for possible publication. In that manuscript the author presented the following equation:

Being unfamiliar with Eq. (1), and being my paranoid self, I wondered if that equation is indeed correct. Not finding a stock trigonometric identity in my favorite math reference book to verify Eq. (1), I modeled both sides of the equation using software. Sure enough, Eq. (1) is not correct. So then I...


Adventures in Signal Processing with Python

Jason Sachs June 23, 201311 comments

Author’s note: This article was originally called Adventures in Signal Processing with Python (MATLAB? We don’t need no stinkin' MATLAB!) — the allusion to The Treasure of the Sierra Madre has been removed, in deference to being a good neighbor to The MathWorks. While I don’t make it a secret of my dislike of many aspects of MATLAB — which I mention later in this article — I do hope they can improve their software and reduce the price. Please note this...


A Beginner's Guide To Cascaded Integrator-Comb (CIC) Filters

Rick Lyons March 26, 202078 comments

This blog discusses the behavior, mathematics, and implementation of cascaded integrator-comb filters.

Cascaded integrator-comb (CIC) digital filters are computationally-efficient implementations of narrowband lowpass filters, and are often embedded in hardware implementations of decimation, interpolation, and delta-sigma converter filtering.

After describing a few applications of CIC filters, this blog introduces their structure and behavior, presents the frequency-domain...


Ten Little Algorithms, Part 2: The Single-Pole Low-Pass Filter

Jason Sachs April 27, 201516 comments

Other articles in this series:

I’m writing this article in a room with a bunch of other people talking, and while sometimes I wish they would just SHUT UP, it would be...


Minimum Shift Keying (MSK) - A Tutorial

Qasim Chaudhari January 25, 201717 comments

Minimum Shift Keying (MSK) is one of the most spectrally efficient modulation schemes available. Due to its constant envelope, it is resilient to non-linear distortion and was therefore chosen as the modulation technique for the GSM cell phone standard.

MSK is a special case of Continuous-Phase Frequency Shift Keying (CPFSK) which is a special case of a general class of modulation schemes known as Continuous-Phase Modulation (CPM). It is worth noting that CPM (and hence CPFSK) is a...


Understanding the 'Phasing Method' of Single Sideband Demodulation

Rick Lyons August 8, 201230 comments

There are four ways to demodulate a transmitted single sideband (SSB) signal. Those four methods are:

  • synchronous detection,
  • phasing method,
  • Weaver method, and
  • filtering method.

Here we review synchronous detection in preparation for explaining, in detail, how the phasing method works. This blog contains lots of preliminary information, so if you're already familiar with SSB signals you might want to scroll down to the 'SSB DEMODULATION BY SYNCHRONOUS DETECTION'...


An Interesting Fourier Transform - 1/f Noise

Steve Smith November 23, 200723 comments

Power law functions are common in science and engineering. A surprising property is that the Fourier transform of a power law is also a power law. But this is only the start- there are many interesting features that soon become apparent. This may even be the key to solving an 80-year mystery in physics.

It starts with the following Fourier transform:

The general form is tα ↔ ω-(α+1), where α is a constant. For example, t2 ↔...


The 2024 DSP Online Conference

Stephane Boucher October 28, 2024

Here we go!

This week is the fifth edition of the DSP Online Conference! This milestone year marks our 5th anniversary, and we’re celebrating with a stellar lineup of renowned DSP experts like fred harris, Rick Lyons, Julius Orion Smith III, and Dan Boschen. These industry leaders will be generously sharing their knowledge and insights with the DSP community.

Why Attend?

Even if your schedule is packed this week, purchasing a pass grants you on-demand access to all...


The 2024 DSP Online Conference

Stephane Boucher July 10, 2024

We are very excited to announce that the DSP Online Conference is back this year for a fourth year in a row and will take place October 29, 30 and 31.

Unlike traditional DSP conferences, where most talks are highly specialized and tailored to researchers, our conference is designed to be accessible to a broader audience of DSP enthusiasts, from students and practicing engineers to hobbyists and DSP experts.

For this year's edition, we are aiming to provide a program that will be organized...


Access to 50+ Sessions From the DSP Online Conference

Stephane Boucher September 21, 2023

In case you forget or didn't already know, registering for the 2023 DSP Online Conference automatically gives you 10 months of unlimited access to all sessions from previous editions of the conference.  So for the price of an engineering book, you not only get access to the upcoming 2023 DSP Online Conference but also to hours upon hours of on-demand DSP gold from some of the best experts in the field.

The value you get for your small investment is simply huge. Many of the...


Sonos, Shut Up and Take My Money! - Is Spatial Audio Finally Here?

Stephane Boucher May 24, 20231 comment

Although I generally agree that money can't buy happiness, I recently made a purchase that has brought me countless hours of pure joy. In this blog post, I want to share my excitement with the DSPRelated community, because I know there are many audio and music enthusiasts here, and also because I suspect there is a lot of DSP magic behind this product. And I would love to hear your opinions and experiences if you have also bought or tried the Sonos ERA 300 wireless speaker, or any other...


A New Related Site!

Stephane Boucher September 22, 20222 comments

We are delighted to announce the launch of the very first new Related site in 15 years!  The new site will be dedicated to the trendy and quickly growing field of Machine Learning and will be called - drum roll please - MLRelated.com.

We think MLRelated fits perfectly well within the “Related” family, with:

  • the fast growth of TinyML, which is a topic of great interest to the EmbeddedRelated community
  • the use of Machine/Deep Learning in Signal Processing applications, which is of...

The 2021 DSP Online Conference

Stephane Boucher September 29, 20211 comment

The 2021 DSP Online Conference is just around the corner and this year again, the program is packed with opportunities for DSP engineers to refresh their DSP skills and learn a few new tricks along the way. 

By registering for the conference, not only will you have full access to all talks, workshops, and Q&A sessions at this year's event, but you'll also gain instant access to all talks from last year's...


The DSP Online Conference - Right Around the Corner!

Stephane Boucher September 20, 2020

It is Sunday night as I write this blog post with a few days to go before the virtual doors of the very first DSP Online Conference open..

It all started with a post in the DSPRelated forum about three months ago.  We had just had a blast running the 2020 Embedded Online Conference and we thought it could be fun to organize a smaller event dedicated to the DSP community.  So my goal with the post in the forum was to see if...


Already 3000+ Attendees Registered for the Upcoming Embedded Online Conference

Stephane Boucher February 14, 2020

Chances are you already know, through the newsletter or banners on the Related sites, about the upcoming Embedded Online Conference.

Chances are you also already know that you have until the end of the month of February to register for free. 

And chances are that you are one of the more than 3000 pro-active engineers who have already registered.

But If you are like me and have a tendency to do tomorrow what can be done today, maybe you haven't registered yet.  You may...


Free Goodies from Embedded World - Full Inventory and Upcoming Draw Live-Streaming Date

Stephane Boucher March 22, 20191 comment

Chances are that you already know that I went to Embedded World a few weeks ago and came back with a bag full of "goodies".  Initially, my vision was to do a single draw for one person to win it all, but I didn't expect to come back with so much stuff and so many development kits.   Based on your feedback, it seems like you guys agree that It wouldn't make sense for one person to win everything as no-one could make good use of all the boards and there would be lots of...


Free Goodies from Embedded World - What to Do Next?

Stephane Boucher March 6, 20193 comments

I told you I would go on a hunt for free stuff at Embedded World in order to build a bundle for someone to win.