Perform overlap add with available FFT size smaller than filter coefficients

Question

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?

Answer 1

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