Wave Walker DSP

DSP Algorithms for RF Systems

Buy the Book!

DSP for Beginners: Simple Explanations for Complex Numbers! The second edition includes a new chapter on complex sinusoids.

Why an FIR Filter Should Have an Odd Length

December 29, 2021

Introduction

Today’s DSP Wisdom: odd-lengths are preferable to even-lengths in an FIR filter.

Powers of 2 are ubiquitous in DSP: binary number representations are in base-2, 3 dB is $10\text{log}_{10}(2)$ , and modulations are powers of 2 (BPSK, QPSK, 8-PSK, 16-QAM). The radix-2 FFT is decomposed into 2-input, 2-output butterflies. Upsampling or decimation by 2 can be done efficiently with a half band filter.

I’ve been allured many times by the siren song of choosing DSP parameters solely because they are powers of 2. A natural fallout is I have typically chosen even parameters for things such as filter lengths because they divide cleanly by a power of 2. The downside is that selecting parameters based on ease of coding results can result in unintended consequences in the DSP.

In this example choosing an even length filter incorporates a fractional time delay at the output of the filter which can negatively effect systems which require precise sampling such as sampling symbols from a demodulator or synchronizing a correlation peak to reference signal.

More blogs on FIR Filters:

Odd Length FIR Filter

A motivating example on the usefulness of odd-length FIR filters is taking a 3-point moving average over a sequence of integers from 0 to 16. The 3-point moving average filter is defined by

(1) $\begin{equation*}h_{3}[n] = \left[ \frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right]\end{equation*}$

and the integer sequence

(2) $\begin{equation*}x[n] = \left[ 0, 1, 2, ~ \dots ~, 14, 15, 16 \right].\end{equation*}$

Figure 1 is the result of the convolution

(3) $\begin{equation*}y_{3}[n] = x[n] \ast h_{3}[n].\end{equation*}$

Figure 1 shows a delay of 1 sample in the convolution output. The convolution takes a certain number of samples before it starts producing valid outputs due to the time it takes to ramp up and store enough samples in the tapped delay line. The output delay for an even-symmetric FIR filter can be calculated by [lyons2011, p.212]

(4) $\begin{equation*}\frac{N_{h}-1}{2}\end{equation*}$

where $N_{h}$ is the filter length. For a 3-point moving average filter $N_{h}=3$ the output delay is

(5) $\begin{equation*}\frac{3-1}{2} = 1\end{equation*}$

which is the same delay as in Figure 1.

Ramp Up Delay

The tapped delay line $\textbf{d}$ is initialized with all zeros,

(6) $\begin{equation*}\mathbf{d} = \begin{bmatrix} 0, 0, 0 \end{bmatrix}.\end{equation*}$

The multiplication of $\mathbf{d}$ with the filter weights initially results in zero,

(7) $\begin{equation*}\begin{bmatrix}0 \\0 \\0\end{bmatrix} \mathbf{d} = \begin{bmatrix}1/3 \\1/3 \\1/3\end{bmatrix}\begin{bmatrix}0, 0, 0\end{bmatrix} = 0.\end{equation*}$

The first input sample x[0] is added to the delay line

(8) $\begin{equation*}\mathbf{d} = \left[ 1, 0, 0 \right]\end{equation*}$

and the filter output is

(9) $\begin{equation*}y_{3}[0] =\begin{bmatrix}1/3 \\1/3 \\1/3\end{bmatrix}\begin{bmatrix}1, 0, 0\end{bmatrix} = 1/3.\end{equation*}$

The second input sample x[1] is added to the delay line

(10) $\begin{equation*}\mathbf{d} = \left[ 2, 1, 0 \right]\end{equation*}$

and the filter output is

(11) $\begin{equation*}y_{3}[1] = \begin{bmatrix}1/3 \\1/3 \\1/3\end{bmatrix}\begin{bmatrix}2, 1, 0\end{bmatrix} = 1.\end{equation*}$

The third input sample x[2] is added to the delay line

(12) $\begin{equation*}\mathbf{d} = \left[ 3, 2, 1 \right]\end{equation*}$

and the filter output is

(13) $\begin{equation*}y_{3}[2] = \begin{bmatrix}1/3 \\1/3 \\1/3\end{bmatrix}\begin{bmatrix}3, 2, 1\end{bmatrix} = 2.\end{equation*}$

After a delay of 1 sample the filter produces valid outputs, $y_{3}[n]$ for $n \ge 1$ , as shown in (11) and (13).

Ramp Down Delay

Just as the convolution has a number of samples associated with ramp up it will have a similar ramp down. The delay (4) at the start of the input sequence came from samples needing to ramp up in the tapped delay line. Similarly a ramp down occurs as input samples are leaving the tapped delay line and being replaced with zeros.

It takes $N_{h}$ samples for the tapped delay line to be flushed and from (4) $(N_{h}-1)/2$ samples can be removed from the head of convolution leaving

(14) $\begin{equation*}N_{h} - \frac{N_{h}-1}{2} = \frac{N_{h}+1}{2}\end{equation*}$

samples to be removed from the tail end of the convolution.

Correcting for FIR Filter Delay

From the example in Figure 1, $N_{h} = 3$ , $N_{x} = 15$ the head delay from (4) is

(15) $\begin{equation*}\frac{N_{h}-1}{2} = \frac{3-1}{2} = 1\end{equation*}$

and the tail delay from (14) is

(16) $\begin{equation*}\frac{N_{h}+1}{2} = \frac{4}{2} = 2.\end{equation*}$

Therefore the first sample and last two samples are removed from $y_{3}[n]$ resulting in $y_{3}[n+1]$ as displayed in Figure 2.

Even Length FIR Filter

A 4-point moving average filter $h_{4}[n]$ is convolved with the integer sequence x[n],

(17) $\begin{equation*}y_{4}[n] = h_{4}[n] \ast x[n]\end{equation*}$

which is displayed in Figure 3.

A delay is seen in the filter output $y_{4}[n]$ in Figure 3 similar to the 3-point moving average in Figure 2. However from (4) the delay is

(18) $\begin{equation*}\frac{N_{h}-1}{2} = \frac{4-1}{2} = 1.5\end{equation*}$

which is not an integer number of samples. Figure 4 shows the filter output $y_{4}[n]$ after removing delays by 1 and 2 samples, $y_{4}[n+1]$ and $y_{4}[n+2]$ .

Where the delay-corrected 3-point moving average filter in Figure 2 overlaps perfectly with the input sequence the 4-point moving average filter in Figure 4 has introduced a non-integer sample delay as in (18) that can’t be corrected by removing 1 or 2 samples. Figure 4 shows that $y_{4}[n+1]$ and $y_{4}[n+2]$ straddle the input x[n] due to the non-integer sample delay.

The non-integer sample delay may become a problem in some applications.

Square Root Raised Cosine Filter

A filter with an integer sample delay is particularly important when the output needs to be precisely sampled. An example is a radio receiver sampling symbols at the output of a matched filter. Figure 5 gives the impulse responses for an even and odd length square root raised cosine filter.

The SRRC parameters between the even and odd length SRRC in Figure 5 are identical except that for the time-indexing: the even length filter is designed with non-integer time values. The even length filter does not have the same peak at $n=\pm 0.5$ as the odd length filter at n=0. The result is that the receiver with an even length SRRC filter in it will always have a non-optimal sampling time because it cannot sample the peak at n=0.

You may have noticed that MATLAB’s rcosdesign() function will always give you an odd length. This is why!

Polyphase Filterbanks

In the past I had designed my polyphase filter banks to always have an even number of filter weights because I was overly concerned with computational efficiency. My blindspot was that while I was gaining efficiency I was throwing away fractions of a dB in signal processing gain. This is called “missing the forest for the trees”.

Knowing what I know now I am much more comfortable investing in my signal processing gain by having a handful of zero-weights in my polyphase filterbank coefficients.

Conclusion

Is being off by a 1/2 sample delay a huge deal? No. But consider that the difference between making good systems and GREAT systems is a thousand minuscule tweaks like using odd length filters appropriately.

Here’s an example: one of the most attractive points for getting your algorithm sold, adopted and used is being able to operate at a lower SNR than your competition. Getting down to lower SNR values means saving fractions of a dB everywhere you can and this is one of those tricks that helps get you there. I’ll be sharing more of these tips I’ve learned the hard way in future blog posts.

Resist the urge to make all things, including filter lengths, divisible by 2.

Have you seen the posts on low pass filter design and the half band filter? Ever wondered why their filter lengths are odd? Now you know!

More blogs on FIR Filters:

Wave Walker DSP

DSP Algorithms for RF Systems

Trending

Buy the Book!

Table of Contents

Introduction

Odd Length FIR Filter

Ramp Up Delay

Ramp Down Delay

Correcting for FIR Filter Delay

Even Length FIR Filter

Square Root Raised Cosine Filter

Polyphase Filterbanks

Conclusion

Leave a ReplyCancel reply