real time overlapping buffer for FFT

Question

I am currently using overlap-and-add method for a noise cancellation project. Everything works well so far except that when it comes to the real time, I need to overlap the input signals for FFT input. For example, I am using 2048 points FFT with 1024 overlapping samples from previous frame(50% overlapping rate). I am illustrating here with numbers. Each number represents half frame(1024 samples). So the real time input signal goes like 1-2-3-4-5-6-7-8-9-10, but I want to buffer the signal into 1-2-2-3-3-4-4-5-5-6-6. Is is possible to do that?

I have tried to delay the input data audio stream by half data frame samples(1024). So at the same time, I have to data streams like below:

 1-|2|-|3|-|4|-|5|-|6|-|7|-|8|-|9|-|10|           --input data stream          
   |1|-|2|-|3|-|4|-|5|-|6|-|7|-|8|-|9|-|10|       --delayed data stream
    ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑         

at any given clock cycle, I would want to read like the arrow indicated to feed the input for FFT. But since FFT and the input are operating at the same clock frequency, I can't really get the data for FFT input.

thanks yong

Answer 1

The way that I would implement this would be to have a circular buffer with a slower output pointer than input pointer (or rather an output pointer that considers overlapping frames).

Depending on how quickly you need to perform the FFT and what other operations are happening, the size of the buffer may vary, but it will need to be at least 1.5 times the FFT size. The extra half period can be used to simplify the wrap around issue (assuming you are calling an external library for you FFT and not implementing it yourself). It may be more convenient to use a buffer size that is twice the FFT size or four times the FFT size to maintain a power of 2 for the buffer length.

You are using 2048 in your example, I am going to reduce this to use an FFT size of 8 (for simplicity). I will consider each number in the following sequence to be a single sample (not half a frame as you consider). The input sequence will be $x_1, x_2, x_3, \ldots$ and so on. When the first sample comes, we skip half an FFT size, and put it in there. We retain an input pointer and an output pointer. The input pointer starts at half the FFT size. The output pointer starts at half the FFT size.

So after 4 samples are input, your buffer looks like this. $$ \left\{ 0, 0, 0, 0, x_1, x_2, x_3, x_4, 0, 0, 0, 0 \right\} $$

Now, 4 more samples will enter. These samples should be mirrored at the end and the beginning of the buffer. So, they will look like this. $$ \left\{ x_5, x_6, x_7, x_8, x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8 \right\} $$

When the final sample enters, you call your FFT function on the part of the buffer beginning with $x_1$ and ending with $x_8$ (hopefully it isn't an in-place algorithm, if it is then copy to a temporary buffer first).

Then, the next 4 samples will be input. These replace the first four so your buffer will look like this. $$ \left\{ x_5, x_6, x_7, x_8, x_9, x_{10}, x_{11}, x_{12}, x_5, x_6, x_7, x_8 \right\} $$

Now, call your FFT routine on the part of the buffer that starts with $x_5$ and ends with $x_{12}$. Then input $4$ more (mirroring them to the front and back), and call the routine again.

I hope this clarifies things.

Answer 2

Lets say we have two buffers "a", "b". Both contains 1024 samples, then function concat concatenates both buffers to produce one of length 2048, pseudocode:

a = readSamples(1024)

repeat forever
  b = readSamples(1024)
  c = concat(a, b)
  fft(c)
  a = b
end repeat

Answer 3

Of course it's possible to do that, but it's unclear WHY you would want to do this. Overlap would typically use buffers like this :

frame 1: [1  2  3  4  5  6  7  8] 
frame 2: [5  6  7  8  9 10 11 12]
frame 3: [9 10 11 12 13 14 15 16] ...