Library / Signal processing and digital filters / DSP-25
Signal processing and digital filters
Usable input block size for FFT convolution
Largest fresh input block whose linear convolution with an M-tap FIR filter still fits in an FFT frame of length Nfft (Nfft ≥ M), for overlap-add filtering.
- Ref
- DSP-25
- Rev
- v1
- Field
- Signal processing and digital filters
- Result
- Lmax [samples]
In overlap-add filtering, an input block of length L convolved with an M-tap filter gives L + M − 1 output samples, which must fit in an FFT frame of Nfft samples. So the largest block is Lmax = Nfft − M + 1. Each output block overlaps the next by M − 1 samples, which are added together.
Largest fresh input block whose linear convolution with an M-tap FIR filter still fits in an FFT frame of length Nfft (Nfft ≥ M), for overlap-add filtering. The M − 1 tail samples of each output block are overlapped with the start of the next.
Calculator
- Fraction of the frame used for fresh input87.5 %
- Overlap added into the next block, M − 132 samples
- Blocks needed for a million input samples4,465 blocks
What drives the result
Each variable is moved across its typical range while the others stay at the values above. The longest bar is the key driver.
- Each 256-point frame can take 224 fresh input samples, 87.5 % of its length, and 32 samples overlap the next block.
- The frame is used efficiently when Nfft is several times M; if M approaches Nfft the transform does little useful work.
Chart data as tables
Ranked variables
| Variable | Typical range | Lowest result | Highest result | Swing (samples) | Local step | Change in result |
|---|---|---|---|---|---|---|
| Nfft FFT length | 64 to 65,540 samples | 32 | 65,500 | 65,470 | +1 samples | +0.446 % |
| M FIR tap count | 1 to 63 taps | 194 | 256 | 62 | +1 taps | −0.446 % |
Sweep of FIR tap count
| FIR tap count (taps) | Largest input block (samples) |
|---|---|
| 1 | 256 |
| 8.75 | 248 |
| 16.5 | 240 |
| 24.25 | 233 |
| 32 | 225 |
| 39.75 | 217 |
| 47.5 | 209 |
| 55.25 | 202 |
| 63 | 194 |
Sweep one variable
Variables and how each one contributes
Largest input block
What the equation gives you. Everything else feeds it.
FFT length
The FFT length, in samples. A longer frame allows a bigger block for the same filter and makes better use of each transform. Raising it by 10 % (to 281.6) moves the result by +11.6 %, from 224 to 250 samples.
FIR tap count
The FIR tap count. A longer filter leaves fewer fresh samples per frame, one for each extra tap. Raising it by 10 % (to 36.3) moves the result by −1.34 %, from 224 to 221 samples.
Worked example with the values above
- Frame length: Nfft = 256 samples; filter length: M = 33 taps.
- Tail: M − 1 = 32 samples must be kept clear at the end of the frame.
- Lmax = 256 − 33 + 1 = 224 samples.
Assumptions and limits
- Finite real sequences indexed from zero and taken as zero outside their stored length.
- Equally spaced samples, and for the circular forms, periodic extension of both sequences.
Common mistakes
- Mixing up the linear and circular forms when an FFT is used.
- Reversing the lag convention for correlation.
- Dividing by N − ℓ where the biased form divides by N.
Statistics and uncertainty
Convolution and correlation sums are exact, so errors come from the data; a delay found from a correlation peak is limited to the sampling interval unless interpolated, and finite records bias the autocovariance by a factor of (N − ℓ)/N.
Where it is used
- Computing filter outputs, delays and covariance by hand for checks.
- Choosing block sizes for fast FFT-based filtering.
Maths you need
- Linear convolution: y[n] = Σ h[j] x[n − j]
- Circular convolution: the same sum with indices wrapped modulo N
- Correlation: a sliding product that measures similarity at each lag