# real time overlapping buffer for FFT

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

• this reads more like you want to do time scaling. that is making a signal longer without changing the frequency components of the signal. if the signal were an audio signal, it appears you want to make it twice as long without changing the pitch. is that what you want to do? Apr 25, 2018 at 8:45
• Normally, you would use a circular buffer to implement this, the inputs will come in at a certain rate, and you will have to process the data faster than that rate (if it is real-time). Then the pointer to the input block is moved by 1024 instead of 2048, but you consider the frame size to be 2048. If you think this is what you are after, let me know and I will write a more detailed answer.
– hops
Apr 25, 2018 at 15:41
• Hi Hops, I think you understand what I am talking about. The dilemma here is (if I am doing it in real time ) I have to delay the input data stream half frame samples for every frame I process. I am editing more to the original question. I am looking forward to your answers. Thanks!
– Y.Z
Apr 26, 2018 at 9:23
• @hops Hi Hops, I think you understand what I am talking about. The dilemma here is (if I am doing it in real time ) I have to delay the input data stream half frame samples for every frame I process. I am editing more to the original question. I am looking forward to your answers. Thanks!
– Y.Z
May 4, 2018 at 5:49

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.

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
c = concat(a, b)
fft(c)
a = b
end repeat


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] ...

• The OP mentioned that each number represents half a frame, if you consider each frame to be a pair of numbers then the OP's buffering and your buffering are equivalent.
– hops
Apr 25, 2018 at 15:38