Wave Walker DSP

DSP Algorithms for RF Systems

Buy the Book!

Foundations of Digital Signal Processing: Complex Numbers is available Amazon now! Great for young engineers looking for a simple explanation of complex numbers.

Why an FIR Filter Should Have an Odd Length
December 29, 2021

Table of Contents

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: The convolution of the moving average filter h3[n] with the sequence of integers x[n].
Figure 1: The convolution of the moving average filter h3[n] with the sequence of integers x[n].

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.

Figure 2: The head and tail transition periods have been removed from the 3-point moving average FIR filter output, showing a perfect overlap.
Figure 2: The head and tail transition periods have been removed from the 3-point moving average FIR filter output, showing a perfect overlap.

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.

Figure 3: The convolution of a 4-point moving average FIR filter h4[n] with an integer sequence x[n].
Figure 3: The convolution of a 4-point moving average FIR filter h4[n] with an integer sequence x[n].

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].

Figure 4: The non-integer delay from h4[n] cannot be corrected for by removing a 1 or 2 sample delay as in y4[n+1] or y4[n+2].
Figure 4: The non-integer delay from h4[n] cannot be corrected for by removing a 1 or 2 sample delay as in y4[n+1] or y4[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.

Figure 5: The impulse response of an odd length SRRC allows for optimal sampling by being able to select the peak at n=0. An even length SRRC filter does not.
Figure 5: The impulse response of an odd length SRRC allows for optimal sampling by being able to select the peak at n=0. An even length SRRC filter does not.

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:

Leave a Reply