# 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) ? – Fat32 Aug 2 '18 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. – Jason R Aug 2 '18 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? – robert bristow-johnson Aug 2 '18 at 21:40
• @robertbristow-johnson Yes i'm sorry I didn't add matched filter tag as well! – VMMF Aug 2 '18 at 21:53
• @JasonR Nice idea! – VMMF Aug 2 '18 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. – Fat32 Aug 2 '18 at 21:34
• I have just downloaded the book could you please name the section – VMMF Aug 2 '18 at 21:55