# Perform overlap add with available FFT size smaller than filter coefficients

I would like to process 12 to 20 seconds of incoming audio at a sample rate of 44100. I must process this audio in real time in an STM embedded kit (perhaps also an Android Smartphone). I'm trying to detect and count the number of occurrences of a signal of roughly 6500 samples inside the incoming audio. The maximum FFT available is of 1024 samples.

I was thinking about applying overlap-add but the number of coefficients would be 6500 and that's larger than maximum FFT size of 1024. I tried to simulate this in Matlab using fftfilt but the function help says:

If you supply a value for n, fftfilt chooses an FFT length, nfft, of 2^nextpow2(n)and a data block length of nfft - length(b) + 1. If n is less than length(b), fftfilt sets n to length(b).

This makes me think that I'm forced to use an FFT of at least 6500 samples (which I can't) and then process 1 incoming audio sample at a time (super inefficient).

What can I do?

• So you want to replace a matched filter (of length 6500 samples) detector with FFT (of length 1024) ? Aug 2, 2018 at 18:32
• Along with the technique pointed out by Stanley in his answer below, another option is partitioned convolution. Split your long filter into shorter sections and implement each as a separate filter. Then, delay and sum the filter outputs appropriately to reconstruct the response you would have gotten from using the long filter to begin with. Aug 2, 2018 at 19:26
• are you filtering with an FIR filter of 6500 taps? is that what you're doing. is this a matched filter problem? Aug 2, 2018 at 21:40
• @robertbristow-johnson Yes i'm sorry I didn't add matched filter tag as well!
– VMMF
Aug 2, 2018 at 21:53
• @JasonR Nice idea!
– VMMF
Aug 2, 2018 at 22:22

You can make a big FFT out of smaller FFTs

This code implements a 16384 point FFT with a 16 point FFT and 1024 point FFT.

You need only calculate the Twiddle matrix once.

clear all
M=16;
N=1024;
x=sin(linspace(1,M*N,M*N)*2*pi*60/(M*N));  % test signal
X=reshape(x,N,M).'; % form 2D matrix read data in as rows
Twiddle=zeros(size(X));    % make Twiddle matrix
for i=1:M
for k=1:N
Twiddle(i,k)=exp(-1j*2*pi*(i-1)*(k-1)/(N*M));
end
end
X=fft(X); % fft on each column
X=X.*Twiddle;% element by element product
X=fft(X.').' ; %fft on each row
y=reshape(X,N*M,1); % read out as columns
figure(1)
plot(abs(y),'linewidth',2)
title('Composite DFT')
figure(2)
plot(abs(fft(x)),'linewidth',2)
title('Direct DFT')


which is based on a section in

Rabiner, Lawrence R., and Bernard Gold. "Theory and application of digital signal processing." Englewood Cliffs, NJ, Prentice-Hall, Inc., 1975. 777 p. (1975).

I don't have the book handy for a page number, but the section is the table of contents under something like 1D DFT as a 2D FFT.

update

section 6.8 page 371 A unified approach to the fft

• Chapter 6 deals with FFT and discusses various decompositions. Yet no exact page shows the algorthm alone. It's distributed across the sections. Aug 2, 2018 at 21:34