fft overlap add

yoda1976 · Oct 5, 2019

Hello,

I want to do a windowed overlap-add fft/ifft but apparently I have to transmit the audio block directly every time update gets called

I can't hold to it and release it when I want, I get hashed signal on the scope, only one block appears

with a 256 points fft/ifft buffer = [first 128 points][second 128 points][256 points overlapp]

- set the first 128 points on arrival of the first block
- set the second half of the 128 points when I receive the second audio block
- window the first 256 points
- calc the 256 points fft/ifft and return the two audio blocks

how can I achieve that ?

regards

Code:

// 2x128  [-----INPUT DATA-----------]
#define FFT_INPUT_LENGTH AUDIO_BLOCK_SAMPLES*2  // 256
// 2x256  [-----FFT OUTPUT REAL------][-----FFT OUTPUT COMPLEX------]
#define FFT_OUT_LENGTH FFT_INPUT_LENGTH*2       // 512
// 1024   [-----FFT OUTPUT REAL------][-----FFT OUTPUT COMPLEX------][------------OVERLAP ADD----------------------------------]
#define FFT_OUT_OVERLAP_LENGTH FFT_OUT_LENGTH*2 // 1024

float32_t fft_buffer[FFT_OUT_LENGTH]; // fft need double cheese buffer -> 256 samples
arm_cfft_radix4_instance_f32 fft;
arm_cfft_radix4_instance_f32 ifft;
uint32_t doBitReverse = 1;

audio_block_t *blockHigh;
audio_block_t *blockLow;

void Filter::calcFFT(boolean high, audio_block_t *block)
{
    if(!high)
    {
      blockLow = block;
      //-------------------------------- fill first 128 bytes
      for(int i=0;i<AUDIO_BLOCK_SAMPLES;i++)
      {
        int32_t signedValue = block->data[i];
        fft_buffer[i]=0.5+((float32_t)(signedValue))/(float32_t)65535;
      }
    }
    else
    {
      blockHigh = block;
      //-------------------------------- fill second 128 bytes
      for(int i=0;i<AUDIO_BLOCK_SAMPLES;i++)
      {
        int32_t signedValue = block->data[i];
        fft_buffer[i+AUDIO_BLOCK_SAMPLES]=0.5+((float32_t)(signedValue))/(float32_t)65535;
      }
      //---------------------------------------- fill overlap add (256 bytes)
      for(int i=0;i<FFT_INPUT_LENGTH;i++)
      {
        fft_buffer[i+FFT_INPUT_LENGTH]=0;
      }

      //----------------------------------------- ready for fft/ifft

      //apply_window_to_fft_buffer(fft_buffer, window);
      
      // fft here ...
      // ...
      // ifft here ...
      
      transmit(blockLow);
      transmit(blockHigh);

    }
}

void Filter::update()
{
  audio_block_t *block;
  
  block = receiveWritable();
  if (block) {

    calcFFT(flipflop, block);

    flipflop=!flipflop;
    release(block);
    
  }
  
}

PaulStoffregen · Oct 5, 2019

yoda1976 said:
apparently I have to transmit the audio block directly every time update gets called

Why are you transmitting blocks at all? Normally when you analyze audio, you only receive blocks from your input(s) and then release them when you're done using their data.

I can't hold to it and release it when I want,

Yes, you can. The existing FFT objects do this, so maybe look at those for an example.

This code looks very wrong. It's sending 2 different blocks to the same output.

If your object has audio outputs, would would normally transmit 1 block per output, on every update. If you neglect to transmit anything, all other objects in the library are supposed to treat that as if you had transmitted a block of all zero samples.

But there is no situation where you would transmit more than 1 block to the SAME output during a call to update(). If this code runs every other update, you can't transmit 2 blocks and expect the library to buffer the 2nd block and use it later. You would need to do that. The library expects you to transmit only 1 block per update, per output. If you generate 2 blocks at once on every other update, you are responsible for keeping a pointer to the 2nd block, when you transmit and release the 1st block. Then on the next update, you would transmit and release the 2nd block.

Of course, if you have more than 1 output, you would transmit 1 block to each output during an update. For example, here is a piece of filter_variable.cpp, which implements 3 outputs:

Code:

        release(input_block);
        transmit(lowpass_block, 0);
        release(lowpass_block);
        transmit(bandpass_block, 1);
        release(bandpass_block);
        transmit(highpass_block, 2);
        release(highpass_block);
        return;

The 2nd optional parameter to the transmit() function is which output. You need to send 1 block to each output during each update. If you never miss an update, whatever other object receives your audio output stream will get a NULL when it tries to receive. Everything in the library treats that as if you send silence during that update. If you do that every other update, you can expect low frequency buzzing sounds (~172 Hz plus harmonics) since the updates happen at 344 Hz.

DD4WH · Oct 5, 2019

maybe you would also like to have a look here for an example: Brian has implemented such a convolution object, however based on a 1024-point-FFT:

https://forum.pjrc.com/threads/4384...ar-cabinet-simulation-)?highlight=convolution

DerekR · Oct 5, 2019

I found this old test sketch that I wrote a couple of years ago. I think it might do exactly what you are asking about. As it is it doesn't do anything useful:
1: It takes an Audio block, and concatenates it with the previous block to form a data buffer of length 256, windows it with a length 256 Hanning window, and takes the FFT.
2: There is no FFT processing done in this test sketch...
3: It then computes the inverse FFT, and reconstructs the data sequence in length 128 blocks using overlap and add.

It was written to examine the envelope of the reconstructed waveform of STFT (Short Term Fourier Transfom) with 50% overlap. If you look at the output on a scope you'll see it's perfectly uniform.

This version uses arm_rfft_fast_f32() for the FFT's. This is not available in the Teensyduino arm_math - you will have install an updated version of arm_math. It also has a different input/output data format. It shouldn't be difficult to substitute whatever FFT you are using.

Code:

//------------------------------------------------
//
#include "AudioSTFT.h"
#include <Audio.h>
#include <SerialFlash.h>
//
///
// --- Audio Board setup
AudioSynthWaveformSine sine;
AudioSTFT              stft;
AudioOutputI2S         output; 
AudioControlSGTL5000   codec; 
const int myInput = AUDIO_INPUT_LINEIN;
//
AudioConnection  c1(sine,0,  stft,0);
AudioConnection  c5(sine,0,  output,0);
AudioConnection  c6(stft,0,  output,1);
//
// --
void setup() {
  Serial.begin(115200);
  delay(2000);
  AudioMemory(12);
  codec.enable();
  codec.volume(0.5);
  AudioNoInterrupts();
  AudioInterrupts();
  sine.frequency(300);
  sine.amplitude(0.8);
  AudioInterrupts();
  //
}
//
// ---
void loop() {}

Code:

//----------------------------------------------------------------------------------------------
//                            AudioNoiseReduction.cpp
//
// Function: Teensy Audio Board STFT (short-term-Fourier-Transform) test with 50%
//           overlapping FFT windows.
//
// Author:   Derek Rowell
//
// Date:     Jan 17, 2018
//
// Notes;  1) This version uses the arm_math arm_rfft_fast_f32() FFT routines, which are not provided
//          in the old version of the arm DSP library in the standard teensyduino distribution.
//          In order to compile this code you will need to install a later version.
//         2) This version uses a length 256 FFT with a Hanning window and 50% overlap of adjacent
//            sections to provide the 128 sample processing blocks for the Audio Board
//         3) This is a "do nothing" test sketch just to look at the overlap/add reconstruction
// 
//----------------------------------------------------------------------------------------------
//
#ifndef audio_stft_h_
#define audio_stft_h_

#define   Nfft 256
//#include "AudioStream.h"
#include "Audio.h"
#include "arm_math.h"
#include "Arduino.h"
//--
class AudioSTFT : public AudioStream {
public:
  AudioSTFT() : AudioStream(1, inputQueueArray){
    arm_rfft_fast_init_f32(&fft,     Nfft);
    arm_rfft_fast_init_f32(&fft_inv, Nfft);
    for (uint16_t i=0; i<Nfft; i++) {
      hanning[i] = 0.5*(1.0 - cos(2*3.14159*(float(i)/float(Nfft))));
    }
  }
//--
  virtual void update(void);
//--
private:
  arm_rfft_fast_instance_f32   fft;
  arm_rfft_fast_instance_f32   fft_inv;
  audio_block_t  *inputQueueArray[1];
  float    y[Nfft]             = {0.0};       // input buffer
  float    y_prev[Nfft/2]      = {0.0};       // prior input buffer
  float    Y[Nfft]             = {0.0};       // FFT of input

  float    hanning[Nfft]; 
  float    y_out[Nfft]; 
  float    y_out_prev[Nfft]    = {0.0};
};
#endif

Code:

//----------------------------------------------------------------------------------------------
//                            AudioNoiseReduction.cpp
//
// Function: Teensy Audio Board STFT (short-term-Fourier-Transform) test with 50%
//           overlapping FFT windows.
//
// Author:   Derek Rowell
//
// Date:     Jan 17, 2018
//
// Notes;  1) This version uses the arm_math arm_rfft_fast_f32() FFT routines, which are not provided
//          in the old version of the arm DSP library in the standard teensyduino distribution.
//          In order to compile this code you will need to install a later version.
//         2) This version uses a length 256 FFT with a Hanning window and 50% overlap of adjacent
//            sections to provide the 128 sample processing blocks for the Audio Board
//         3) This is a "do nothing" test sketch just to look at the overlap/add reconstruction
// 
//----------------------------------------------------------------------------------------------
//
#include "AudioSTFT.h"
#define forward 0
#define inverse 1
//--
void AudioSTFT::update(void) { 
  audio_block_t *block0;
  block0 = receiveWritable(0); 
  if (!block0)  return;
  //
  for (int i=0; i<Nfft; i++) {
  if (i < AUDIO_BLOCK_SAMPLES) {
    y[i] = y_prev[i];   // Move to end of input buffer
  } else {
    y[i] = float(block0->data[i-AUDIO_BLOCK_SAMPLES])/(32768.0);
    y_prev[i-AUDIO_BLOCK_SAMPLES] = y[i];           // For the next iteration
  }
  }
  //  Take windowed FFT of the input to form Y[k]
  for (int i=0; i<Nfft; i++) {
    y[i] *= hanning[i];          // Window with a Hanning data window (raised cosine)
  }
  //
  arm_rfft_fast_f32(&fft, y, Y, forward);
  // Note: The arm_rfft_fast_f32() function destroys the data in the input buffer :-( (see above)
  // arm_rfft_fast_f32() takes a real input buffer of length Nfft, and returns a complex array of
  // length nFFT containing nFFT/2 complex variable.  It is assumed that the nFFT/2 missing samples
  // are defined through the conjugate symmetry of a Real FFT.
  // -------------------------------------------------
  // We only need to work on half the FFT because of symmetry. Y[0] is a special case.
  // *** Do freq. domain processing here ***
  // Don't process k = 0 (contains DC and Nyquist frequency)
  // -------------------------------------------------
  // Translate back into the time domain and "stitch" (overlap/add) to the output from the previous segment
  arm_rfft_fast_f32(&fft_inv, Y, y_out, inverse);        // Compute the inverse FFT
  //
  // "Stitch" (overlap/add) to the output from the previous segment
  for (int i=0; i<Nfft; i++) {
    if (i<AUDIO_BLOCK_SAMPLES) {
      block0->data[i] = (int)((y_out[i]+y_out_prev[i])*32767.0);  // Overlap/add
    } else {
      y_out_prev[i-AUDIO_BLOCK_SAMPLES] = y_out[i];               // Save for next overlap/add
    }
  }
  transmit(block0, 0);
  release(block0);
}

yoda1976 · Oct 5, 2019

@PaulStoffregen
I never said anything about analysis only...

i need an fft, then do something on the spectrum level, then do an ifft, then send it to the output

I dont need thousands of outputs, just one

overlap-add or overlap-save are methods to overlap audio blocks (cfr fft/ifft or convolution)

I figured I "just" had to keep my own past buffer history and mod only the input block then re-transmit it

yoda1976 · Oct 5, 2019

DD4WH said:
maybe you would also like to have a look here for an example: Brian has implemented such a convolution object, however based on a 1024-point-FFT:

https://forum.pjrc.com/threads/4384...ar-cabinet-simulation-)?highlight=convolution

thx I'll check this out

so far I went back to 64 points fft, I can split the 128 pts audio block in two (so I dont need to hold the current input block)

I'll overlap the current buffer with a copy of the previous treated buffer (adding an offset of 32 points)

yoda1976 · Oct 5, 2019

DerekR said:
It was written to examine the envelope of the reconstructed waveform of STFT (Short Term Fourier Transfom) with 50% overlap.

thx I'll definetely look at this one

fft overlap add

yoda1976

Member

PaulStoffregen

Well-known member

DD4WH

Well-known member

DerekR

Well-known member

yoda1976

Member

yoda1976

Member

yoda1976

Member