Method and system for finite impulse response (FIR) digital filtering

1. A computer readable medium storing executable instructions which, when executed by a processor, cause the processor to perform a method for finite impulse response (FIR) digital filtering, the method comprising:

receiving an input sample block of L input samples of a signal;

extending the input sample block to generate an extended sample block of length N, wherein the L input samples are preceded by N−L values;

computing an N-point Discrete Fourier Transform (DFT) of the extended sample block to generate a frequency domain sample block;

adding the computed frequency domain sample block to a reverse time-ordered set of previously generated frequency domain sample blocks as a newest frequency domain sample block in the reverse time-ordered set;

computing a spectral multiplication of each of K newest frequency domain sample blocks in the reverse time-ordered set of previously generated frequency domain sample blocks with a corresponding frequency domain filter block in a time-ordered set of K frequency domain filter blocks of a FIR filter;

adding the K results of the K spectral multiplications to generate an output spectral block;

computing an N-point inverse DFT of the output spectral block to generate a time domain output block; and

discarding N−L samples in the time domain output block to generate L filtered output samples,

wherein NH is a length of the FIR filter, M is a length of each of K time domain filter blocks of the FIR filter, L=M, K=ceil (NH/M), and N≧L+M−1.

2. The computer readable medium of claim 1 , wherein the N−L values are N−L samples from another input sample block immediately preceding the input sample block.

3. The computer readable medium of claim 1 , wherein L=M=N/2.

4. The computer readable medium of claim 1 , wherein the method further comprises:

segmenting an impulse response of the FIR filter into K time domain filter blocks; and

computing an N-point Discrete Fourier Transform (DFT) of each of the K time domain filter blocks to generate the K frequency domain filter blocks.

5. The computer readable medium of claim 1 , wherein adding the computed frequency domain sample block comprises removing an oldest frequency domain sample block from the reverse time-ordered set.

6. The computer readable medium of claim 5 , wherein removing an oldest frequency domain sample block comprises replacing the oldest frequency domain sample block with the computed frequency domain sample block.

7. The computer readable medium of claim 1 , wherein the N-point DFT is implemented with a Fast Fourier Transform (FFT) algorithm and the N-point inverse DFT is implemented with an inverse FFT algorithm.

8. A digital system comprising:

a processor; and

a memory storing software instructions, wherein when executed by the digital signal processor, the software instructions cause the digital system to perform a method for finite impulse response (FIR) digital filtering, the method comprising:

receiving an input sample block of L input samples of a signal;

extending the input sample block to generate an extended sample block of length N, wherein the L input samples are preceded by N−L values;

computing an N-point Discrete Fourier Transform (DFT) of the extended sample block to generate a frequency domain sample block;

adding the computed frequency domain sample block to a reverse time-ordered set of previously generated frequency domain sample blocks as a newest frequency domain sample block in the reverse time-ordered set;

computing a spectral multiplication of each of K newest frequency domain sample blocks in the reverse time-ordered set of previously generated frequency domain sample blocks with a corresponding frequency domain filter block in a time-ordered set of K frequency domain filter blocks of a FIR filter;

adding the K results of the K spectral multiplications to generate an output spectral block;

computing an N-point inverse DFT of the output spectral block to generate a time domain output block; and

discarding N-L samples in the time domain output block to generate L filtered output samples,

wherein NH is a length of the FIR filter, M is a length of each of K time domain filter blocks of the FIR filter, L=M, K=ceil (NH/M), and N≧L+M−1.

9. The digital system of claim 8 , wherein the N−L values are N−L samples from another input sample block immediately preceding the input sample block.

10. The digital system of claim 8 , wherein L=M=N/2.

11. The digital system of claim 8 , wherein the method further comprises:

segmenting an impulse response of the FIR filter into K time domain filter blocks; and

computing an N-point Discrete Fourier Transform (DFT) of each of the K time domain filter blocks to generate the K frequency domain filter blocks.

12. The digital system of claim 8 , wherein adding the computed frequency domain sample block comprises removing an oldest frequency domain sample block from the reverse time-ordered set.

13. The digital system of claim 12 , wherein removing an oldest frequency domain sample block comprises replacing the oldest frequency domain sample block with the computed frequency domain sample block.