FIR Filters

Sources:

1. James McClellan, Ronald Schafer & Mark Yoder. (2015). FIR Filters. DSP First (2nd ed., pp. 147-193). Pearson.

Discrete-Time Systems

• Sequence: a discrete-time signal¹.

• Discrete-time system or filter²: a function for transforming one sequence, called the input signal, into another sequence called the output signal.

  

  Block-diagram representation of a discrete-time system

In general, we represent the operation of a discrete-time system by the notation $$\begin{array}{}\text{(1)}& x[n]\stackrel{\mathcal{T}}{⟼}y[n]\end{array}$$ Or $$\begin{array}{}\text{(2)}& y[n]=\mathcal{T}(x[n])\end{array}$$

• $x$: input sequence
• $y$: output sequence
• $\mathcal{T}$: the operator, aka computational process, mapping or function.

$$y[n]=(x[n]{)}^2$$

The Running-Average Filter

• A running average or moving average system: the output is the average of some consecutive values of the input. Such as $$\begin{array}{}\text{(3)}& y[n]=\sum _{k=0}^{M}x[n-k]\end{array}$$ You can also define a running average as $y[n]=\sum _{k=0}^{M}x[n+k]$, $y[n]=\sum _{k=0}^{M}x[n-1+k]$ or whatever.

• The equation like $\text{(3)}$ is called a difference equation. It is a complete description of the FIR system because we can use $\text{(3)}$ to compute the entire output signal for all index values $-\mathrm{\infty }<n<\mathrm{\infty }$.

• A filter that uses only the present and past values of the input is called a causal filter. Thus $\text{(3)}$ is a causal running average.

Example

For a input sequence $x[n]$ with support set $x[0],x[1],x[2]=2,4,6$:

Figure 5.2 a

we define an output sequence $y[n]$:

$$\begin{array}{}\text{(4)}& y[n]=\frac{x[n]+x[n+1]+x[n+2]}{3}\end{array}$$

with $$\begin{array}{rl}& y[0]=\frac{1}{3}(x[0]+x[1]+x[2])\\ & y[1]=\frac{1}{3}(x[1]+x[2]+x[3])\\ & \cdots \end{array}$$

$\text{(4)}$ is the difference equation of this causal running average system.

The General FIR Filter

Definition

We define a $M^{\text{th}}$-order weighted running average/FIR filter of $M+1$ samples. $$\begin{array}{}\text{(5)}& y[n]=\sum _{k=0}^M{b}_{k}x[n-k],\end{array}$$ which can be extended to $b_{0}x[n]+b_{1}x[n-1]+\cdots +b_{M}x[n-M]$.

• FIR system: Finite Input Response system. Because the impulse response sequence $h[n]$ is finite(Illustrated later).
  • $x[n],y[n]$ can be infinite since $n$ can be infinte: $-\mathrm{\infty }<n<\mathrm{\infty }$. But for FIR, the $h[n]$ must be finite.
• The 3-point noncausal running average $\text{(???)}$ is the case where $M=2$ and $b_k=1/3$ in $\text{(5)}$.
• the coefficients $b_k$ are fixed numbers.
• According to $\text{(5)}$, an FIR filter is causal.
  • Note that a noncausal system can be represented by altering $\text{(5)}$ to include negative values of the summation index $k$.
• Usually the $b_k$ coefficients are not all the same, and then we say that $\text{(5)}$ is "weighted".
• It follows from $\text{(5)}$ that the computation of $y[n]$ involves the samples $x[\ell ]$ for $\ell =n,n-1,n-2,\dots ,n-M$ (i.e., $x[n],x[n-1],x[n-2]$, etc):

---

A second defnition: $$\begin{array}{}\text{(6)}& y[n]& =\sum _{\ell =n-M}^n{b}_{n-\ell }x[\ell ],\end{array}$$

which can be extended to $b_{M}x[n-M]+b_{M-1}x[n-M+1]+\cdots +b_{0}x[n]$.

Example

Figure 5.4 llustrates how the causal FIR filter uses $x[n]$ and the past $M$ samples to compute the output.

Figure 5.4

• the weighted average is calculated over the (gray) sliding window of $M+1$ samples.
• When the input signal $x[l]$ has finite length ($N$ samples), the sliding window runs onto and off of the input data, so the resulting output signal also has finite length.

The Unit Impulse Response and Convolution

In this section, we introduce three new ideas: the unit impulse sequence, the unit impulse response, and the convolution sum.

We show that the impulse response provides a complete characterization of the FIR filter, because the convolution sum gives a formula for computing the output from the input when the unit impulse response is known.

Unit Impulse Sequence

The unit impulse: $$\delta [n]=\{\begin{array}{ll}1& n=0\\ 0& n\ne 0\end{array}$$

This notation is also known as the Kronecker delta function.

Shifted Unit Impulse Sequence

Here is the tabular of $\delta [n]$ and $\delta [n-2]$

Unit Impulse Sequence Table

For a shifted unit impulse such as $$\begin{array}{}\text{(7)}& \delta [n-2]\end{array}$$

---

The shifted impulse is a concept that is very useful in representing signals and systems. For example, we can show that the formula $$x[n]=2\delta [n]+4\delta [n-1]+6\delta [n-2]+4\delta [n-3]+2\delta [n-4]$$ is equivalent to defining $x[n]$ by tabulating its five nonzero values:

Unit Impulse Sequence Table 2

It turns out that any sequence³ can be represented by a sum of scaled shifted impulses . The equation $$\begin{array}{rl}x[n]& =\sum _{k}x[k]\delta [n-k]\\ & =\cdots +x[-1]\delta [n+1]+x[0]\delta [n]+x[1]\delta [n-1]+x[2]\delta [n-2]+\cdots \end{array}$$ is true if $k$ ranges over all the nonzero values of the sequence $x[n]$.

Unit Impulse Response Sequence

• The output from a filter is often called the response to the input.

• When the input is the unit impulse, $\delta [n]$, the output is called the unit impulse response (Or impulse response, with unit being understood).

• Notation of unit impulse response: $h[n]$.

• When the input to the FIR filter $\text{(5)}$ is a unit impulse sequence, $x[n]=\delta [n]$, the output is the (unit) impulse response $h[n]$. Substituting $x[n]=\delta [n]$ in $\text{(5)}$ gives the output $y[n]=h[n]$: $$h[n]=\sum _{k=0}^M{b}_k\delta [n-k]=\{\begin{array}{ll}{b}_n& n=0,1,2,\dots ,M\\ 0& \text{ otherwise }\end{array}$$

  Note that because each $\delta [n-k]$ is nonzero only when $n-k=0$, or $n=k$, the impulse response is:

  

  Unit impulse response and coefficients

• In other words, the impulse response $h[n]$ of the FIR filter is identical to the sequence of difference equation coefficients. So the FIR filter is completely defined by the impulse response.

  • In following chapter, we'll show that this characterization is also true for the much broader class of linear time-invariant (LTI) systems.

• Since $h[n]=0$ for $n<0$ and for $n>M$, the "length"⁴ of the impulse response sequence $h[n]$ is finite. This is why the system $\text{(5)}$ is called a FIR system.

The Unit-Delay System

One important system is the operator that performs a delay or shift by an amount $n_0$ $$y[n]=x[n-n_0]$$

When $n_0=1$, the system is called a unit delay.

• The delay system is actually the simplest of FIR filters. $$\begin{array}{rl}y[n]& =b_{0}x[n]+b_{1}x[n-1]+b_{2}x[n-2]+\cdots +b_{n_0}x[n-n_0]\\ & =(0)x[n]+(0)x[n-1]+(0)x[n-2]+\cdots +(1)x[n-n_0]\\ & =x[n-n_0]\end{array}$$

• The impulse response of the delay system is obtained by substituting $\delta [n]$ for $x[n]$.

• $\text{(7)}$ is a delay-by-2 system $y[n]=x[n-2]$ with coefficients $\left\{b_k\right\}=$ $\{0,0,1\}$, its impulse response is: $$h[n]=\delta [n-n_0]=\delta [n-2]=\{\begin{array}{ll}1& n=2\\ 0& n\ne 2\end{array}$$

FIR Filters and Convolution

Since the filter coefficients in $\text{(5)}$ are identical to the impulse response value $h[n]$. We can express a FIR filter in terms of the input and the impulse response. This is called convolution sum: $$\begin{array}{}\text{(8)}& y[n]=\sum _{k=0}^{M}h[k]x[n-k]\end{array}$$ Here we replace $b_k$ in $\text{(5)}$ with $h[k]$.

• The terminology convolution emphasizes that it's an operation between two sequences.

• We use a star $(\ast )$ to represent the operation of evaluating (5.13) for $-\mathrm{\infty }<$ $n<\mathrm{\infty }$ by writing $$\begin{array}{}\text{(9)}& y[n]=h[n]\ast x[n]\end{array}$$ which is read as "the output sequence $y[n]$ is obtained by convolving the impulse response $h[n]$ with the input sequence $x[n]$."

Later, in Section 5-7, we will prove that convolution is the fundamental input-output algorithm for a large class of very useful filters that includes FIR filters as a special case. We will show that a general form of convolution that also applies to infinite-length signals is $$\begin{array}{rl}y[n]& =h[n]\ast x[n]\\ \text{(10)}& & =\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}h[k]x[n-k].\end{array}$$

This convolution sum $\text{(10)}$ has infinite limits to accomodate impulse responses of infinite length, but reduces to $\text{(8)}$ when $h[n]=0$ for $n<0$ and $n>M$.

The Length of a Convolution

If $x[n]$ is nonzero only in the interval $0\le n\le L_x-1$, then for a causal FIR filter having an impulse response of length $L_h=M+1$ samples (because the impulse response is the sequence: h[0], h[1], ..., h[M]), the corresponding output $y[n]$, which is the convolution of $h[n]$ with $x[n]$, can be nonzero only when $n\ge 0$ and $n-M\le L_x-1$, or equivalently, the support set of $y[n]$ is the interval $0\le n\le L_x+M-1$. Thus the length of $y[n]$ is $$\begin{array}{}\text{(11)}& L_y=L_x+L_h-1\end{array}$$

通俗地说, $y[n]$长度 = $x[n]$长度 + $h[n]$长度 - 1.

以下面example为例, $x[n]$的长度是11($L_x=11$), 最后一个非0值位于下标10($L_x-1$), 但由于$M=3$, 因此以$x[10]$为起始点的$M$个值 $x[10],x[11],x[12]$的running average 还是非零: $$y[12]=x[12]\ast h[12]\ne 0,$$ convolution一直持续到下标12($L_x-1+M$).

而convolution是从下标0开始的($\frac{Px[-2]+x[-1]+x[-1]}{3}$), 因此convolution $y[n]$从下标0一直持续到下标12($L_x-1+M$). 其长度为$L_x+M=L_y=L_x+L_h-1$.

When the signals start at $n=0$, it is possible to use the synthetic multiplication table to prove that the formula $\text{(11)}$ is true. Since the length of $x[n]$ is $L_x$, the last nonzero signal value is $x[L_x-1]$. Likewise, for $h[n]$ where $h[L_h-1]$ is the last nonzero value. In the figure, the row for $h[0]x[n]$ starts at $n=0$ and ends at $n=L_x-1$, while the row for $h[L_h-1]x[n-(L_h-1)]$ ends at $n=(L_x-1)+(L_h-1)$. After summing down the columns, we see that the convolution result $y[n]$ starts at $n=0$ and ends at $n=L_h+L_x-2$, so the length of $y[n]$ is $L_x+L_h-1$. Problem P-5.6 considers the general case where the signal $x[n]$ begins at sample $N_1$ and ends at sample $N_2$.

Example

Figure 5.5

Given impulse response $$h[n]=\frac{1}{3}\delta [n]+\frac{1}{3}\delta [n-1]+\frac{1}{3}\delta [n-2]$$ and input $x[n]=\{\begin{array}{ll}1& n=0,1,2,\dots ,10\\ 0& \text{ otherwise }\end{array}$.

The output $y[n]=h[n]\ast x[n]$ has length $L_y=11+3-1=13$.

Filtering the Unit-Step Signal

In previous sections, we have described the FIR filtering of finite-length signals.

But the input signal can also have infinite duration.

An example is the unit-step signal which is zero for $n<0$ and "turns on" at $n=0$ $$u[n]=\{\begin{array}{ll}0& n<0\\ 1& n\ge 0\end{array}$$

The symbol $u[n]$ is reserved for the unit step.

So when we want the input signal to be the unit step we write $x[n]=u[n]$, and the output of an $M^{\text{th }}$-order FIR filter would be $$y[n]=\sum _{\ell =n-M}^n{b}_{n-\ell }u[\ell ]$$ if we use the form in $\text{(5)}$. Since the FIR filter is causal and the unit step starts at $n=0$, the output is zero for $n<0$. Determining the output for $n\ge 0$ can be done by writing out terms

Property of Convolution

convolution is:

1. commutative: $y[n]=h[n]\ast x[n]=x[n]\ast h[n]$

//Proof: TODO

---

1. See↩︎

2. Strictly speaking, a filter is a system that is designed to remove some component or modify some characteristic of a signal, but often the two terms are used interchangeably.↩︎

3. Remember that a sequence is a discrete-time signal.↩︎

4. 这里所谓"length"指的是support set的长度. n可以是无限的, 因此$x[n],y[n],h[n]$也可以是无限的. 但是它们的suport set未必无限. 特别是$h[n]$的长度已经被$\text{(8)}$固定为$M+1$.↩︎