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.

Time Invariant and Time Varying Filters
September 3, 2021

Table of Contents

Introduction

The response of time invariant filters is independent of time and have filter weights which do not change over time. Time invariance (TI) is a nice quality for filters to have when analyzing them mathematically and have many applications in which adaptation is not needed. Time-varying filters (TV) are common in radio receivers such as equalizers, automatic gain control and polyphase filters. For example an equalizer is time-varying because the filter weights are dependent on previous input samples. Understanding TI filters is necessary for having a proper DSP foundation before moving onto TV filters.

More posts on FIR Filters:

 

Time Invariant FIR Filters

The output of a finite pulse response (FIR) filter h[n] is represented by convolution,

(1)   \begin{equation*}y[n] = x[n] \circledast h[n],\end{equation*}

or alternatively,

(2)   \begin{equation*}\begin{split}y[n] & = \sum_{k=-\infty}^{\infty} x[k] h[n-k] \\& = \sum_{k=-\infty}^{\infty} x[n-k] h[k].\end{split}\end{equation*}

Figure 1 is an example of a FIR filter.

Figure 1: The block diagram for an example FIR filter. Note that the filter weights h[n] have been time-reversed.
Figure 1: The block diagram for an example FIR filter. Note that the filter weights h[n] have been time-reversed.

From(2) it can be seen that x[k] is time reversed, x[-k], and delayed by n samples,

(3)   \begin{equation*}x[n-k] = x[-k+n] = x[-(k-n)].\end{equation*}

Mathematically either x[n] or h[n] could be time reversed and delayed and the same output would be produced. However for easier analysis the convolution will be implemented by time reversing and delaying x[n].

Expanding (2),

(4)   \begin{equation*}\begin{split}y[n] = \dots + h[-2]x[n+2] + h[-1]x[n+1] + h[0]x[n] + h[1]x[n-1] + \dots ~.\end{split}\end{equation*}

Delaying x[n] by T samples and substituting into (4) results in

(5)   \begin{equation*}\begin{split}x[n-T] \circledast h[n] = \dots & + h[-2]h[n+2-T] + h[-1]x[n+1-T] + h[0]x[n-T] \\& + h[1]x[n-1-T] + h[2]x[n-2-T]\dots,\end{split}\end{equation*}

which can be simplified as

(6)   \begin{equation*}y[n-T] = \sum_{k=-\infty}^{\infty} x[k-T] h[n-k],\end{equation*}

and

(7)   \begin{equation*}y[n-T] = x[k-T] \circledast h[n].\end{equation*}

From (7) it can be seen that a delay in x[k] by T samples, x[k-T], results in a delay of the output y[n] by T samples, y[n-T] with no other affects. Figure 2 shows how a delay on an input signal results in the same delay in the output when filtered by a time-invariant FIR filter.

Figure 2: An example of time-invariance in an FIR filter. The input signal is delayed and the corresponding delay is seen in the filter output.
Figure 2: An example of time-invariance in an FIR filter. The input signal is delayed and the corresponding delay is seen in the filter output.

Time Invariant IIR Filters

IIR filters are implemented using a difference equation

(8)   \begin{equation*}y[n] = b_{0}x[n] + b_{1}x[n-1] + \dots + a_{1}y[n-1] + a_{2}y[n-2] + \dots\end{equation*}

which can be written closed-form as

(9)   \begin{equation*}y[n] = \sum_{k=-\infty}^{\infty} \left( b_{k}x[k] + a_{k+1}y[n-k-1] \right).\end{equation*}

An example of an IIR filter is given in Figure 3.

Figure 3: An example of a time invariant IIR filter. Note that an IIR filter can be transformed into an FIR filter by setting all feedback coefficients to zero.
Figure 3: An example of a time invariant IIR filter. Note that an IIR filter can be transformed into an FIR filter by setting all feedback coefficients to zero.

Delaying x[n] by T samples, x[n-T], and substituting into (9) results in

(10)   \begin{equation*}y[n-T] = \sum_{k=-\infty}^{\infty} \left( x[k-T]b_{k} + y[n-k-1]a_{k+1} \right).\end{equation*}

From (10), delaying x[n] by T results in the output being delayed by the same amount, y[n-T], with no other impact. The output y[n] is dependent on the input x[n] and the filter weights ak and bk. The filter weights ak and bk are constant for all time and therefore will not being time-varying. A delay of x[n] therefore corresponds directly to a delay in y[n]. Figure 4 gives an example of time-invariance in an IIR filter.

Figure 4: An example of time-invariance in an IIR filter. Delaying the input signal results in the same delay of the output signal.
Figure 4: An example of time-invariance in an IIR filter. Delaying the input signal results in the same delay of the output signal.

Time-Varying Filters

A decimating FIR filter is a simple case of a time-varying filter. A basic decimation operation is performed by first low-pass filtering and then downsampling, shown in Figure 5.

Figure 5: Decimating by 2 consists of low-pass filtering with h[n] and then downsampling by 2.
Figure 5: Decimating by 2 consists of low-pass filtering with h[n] and then downsampling by 2.

Combining the low-pass filtering with the downsampling operation will reveal the time-varying nature of the filtering operation and will produce computational efficiencies, referred to as a polyphase decimating filter. The low-pass filter output \bar{y}[n] can be written as

(11)   \begin{equation*}\begin{split}\bar{y}[n] & = x[n] \circledast h[n] \\& = \sum_{k} x[n-k]h[k].\end{split}\end{equation*}

Downsampling by 2 discards every other sample. Mathematically, it allows for the opportunity to select even indices,

(12)   \begin{equation*}y[n] = \bar{y}[2n]\end{equation*}

or odd indices,

(13)   \begin{equation*}y[n] = \bar{y}[2n+1].\end{equation*}

Both (12) and (13) are valid and only differ by delaying the input to the downsample by 1 sample. Choosing

(14)   \begin{equation*}\bar{y}[2n]\end{equation*}

and substituting (12) into (11) gives

(15)   \begin{equation*}\bar{y}[2n] = \sum_{k} x[2n-k] h[k].\end{split}\end{equation*}

The filter h[n] produces a single output \bar{y}[n] for each input x[n]. However, the downsampling by 2 operation discards all of the odd indices \bar{y}[2n+1] wasting the computation. The filter h[n] will be rearranged into a polyphase structure to avoid wasting the computation and making the decimation more efficient.

The filter output is arranged into even time indices x[2n] and odd time indices x[2n+1].

(16)   \begin{equation*}\begin{split}\bar{y}[2n] & = \sum_{k ~ \text{even}} x[2n-k]h[k] + \sum_{k ~ \text{odd}} x[2n-k]h[k] \\& = \sum_{k} x[2(n-k)]h[2k] + \sum_{k} x[2(n-k)-1]h[2k-1].\end{split}\end{equation*}

From (16) it can be seen that the even input samples x[2(n-k)] are filtered by the even filter weights h[2k] while the odd input samples x[2(n-k)+1] are filtered by the odd filter weights h[2k+1]. The time index of the input samples x[n] therefore indicates which set of filter weights will be applied. Figure 6 gives the polyphase partitioning and shows how the input switch for x[n] controls which filter weights will be applied.

Figure 6: A decimate by 2 filter implemented with a polyphase filtering structure.
Figure 6: A decimate by 2 filter implemented with a polyphase filtering structure.

The polyphase decimating filter is therefore periodically time-varying as it produces different filter responses based on the time delay of the input signal. Figure 7 gives an example of how the PTV nature of the polyphase decimating filter effects delays on the input signal.

Figure 7: The polyphase filter is a periodically time-varying filter and therefore different delays on the input signal will produce different filter responses. A delay of 1 sample corresponds to different filter weights being applied and a resulting 1/2 sample delay at the output.
Figure 7: The polyphase filter is a periodically time-varying filter and therefore different delays on the input signal will produce different filter responses. A delay of 1 sample corresponds to different filter weights being applied and a resulting 1/2 sample delay at the output.

Note that the decimate by 2 polyphase filter is periodically time-varying (PTV) with a period of 2 samples. Delaying the input signal into the filter by 2k synchronizes the input signal to the periodic nature of the cycling filter weights and the filter response becomes time-invariant under these conditions. Similarly, delaying the input by 2k+1 will also be time-invariant. Figure 7 shows that delaying the input signal by 0 and 2 samples results in the same output signal but with a 1 sample delay. Conversely, delaying the input sample by 1 sample produces a different filter response and results in a 1/2 sample delay.

Other Examples of Time Varying Filters

A subset of time-varying filters include adaptive filters whose filter weights are effected by previous samples of the input signal. Such adaptive filters include equalizers and automatic gain control. Another class of time-varying filters are periodically time varying filters which includes polyphase filters.

Conclusion

Delaying the input to a time invariant filter produces the same delay of the output signal with no other modifications. Time-invariant filters have mathematically useful properties for filter analysis and also form the basis for more sophisticated time-varying filters. A polyphase decimating filter is an example of a periodically time-varying filter because the filter response depends on the time delay of the input signal.

More posts on FIR Filters:

Leave a Reply