2017年4月6日 星期四

[訊號與系統] FIR 與 Finite Convolution

在 系統理論 或者 訊號處理 的領域中,我們一般將 濾波器 (filter) 視作可用以移除某特定頻段的訊號 並且僅讓 部分指定的頻段訊號 可以通過 的 系統(system)。

現在 給定 一組 標準 有限脈衝響應濾波器(Finite Impulse Response Filter,  FIR filter) ,其 輸入/輸出之關係可用下列表述
\[
y[n] = \sum_{k = 0}^M b_k x[n -k]
\] 其中 $b_k$ 稱為 FIR 濾波器的係數,$x[\cdot]$ 為輸入訊號,$y[\cdot]$ 為輸出訊號。

Comments:
1. 上述 FIR 的定義中並不要求 未來的輸入訊號,亦即我們僅需要現在與過去的輸入 $x[n], x[n-1],...,x[n-M]$,一般稱此 FIR 為 因果系統 (casual system)
2. 上述 FIR filter 的 輸入/輸出關係 可被視為 有限摺積(finite convolution) 運算
3. 令輸入$x[n]$為具有長度 $L_x$ 的 sequence 且 $h[n]$ 為具有 長度 $L_h$ 的sequence 則其輸出 $y[n]$ 在經過 convolution 運算之後會具有長度
$$
L_y =L_x + L_h -1 \text {( why ? ) }
$$ 4. 在 MATLAB 中 內建函數 filter() 可以用來建構 上述 FIR filter,舉例而言,考慮一組 FIR
\[y[n] = \sum\limits_{k = 0}^3 {\frac{1}{4}} x[n - k] = \frac{1}{4}\left( {x[n] + x[n - 1] + x[n - 2] + x[n-3]} \right)\] 且輸入為 $sin(0.1 \pi n), \;\;\; n=0,1,...,99$ 則 我們可用 MATLAB code 來計算對應的輸出 $y$ 如下:

n = 0:99
x = sin( 0.1 * pi * n);
b = [1/4 1/4 1/4  1/4]
y = filter(b, 1, x)


另外注意到前述我們提及 輸入訊號與其 脈衝響應的和:
\[
y[n] = \sum_{k = 0}^M h[k] x[n -k]\;\;\;\;\;\;\; (*)
\] 上述結果稱作 finite convolution sum 且我們稱輸出 透過 $x[n]$ 與 $h[n]$ 做 convolution 而得。一個 更一般的 輸入/輸出 關係可表為
\[
y[n] = \sum_{k=-\infty}^\infty h[k] x[n-k] \;\;\;\;\; (**)
\]讀者不難發現若我們取 $h[n]=0$ 當 $n<0$ 以及 $n > M$ 時, $(**)$ 退化回 finite convolution 形式 $(*)$。



Example: Impulse Response For 3-Points Averaging System
令 $x[n] := \delta[n]$ 則 脈衝響應
\[
y[n] = \sum_{k = 0}^2 \frac{1}{3} x[n -k]
\]

在 MATLAB 中,convolution 運算可以透過 conv() 來實現:比如說
xx = sin( 0.1*pi*(0:50) )
hh = ones(11,1)/11
yy = conv(hh, xx);


線性非時變 FIR 濾波器

==================
FACT: 考慮 FIR 濾波器
\[
y[n] = \sum_{k = 0}^M b_k x[n -k]
\]則此 FIR 為 線性非時變( linear and time-invariant)
==================

Proof: 首先證明線性。令 $x_1[n]$ 與 $x_2[n]$ 分別為兩輸入,且其對應的輸出分別為
\[\begin{array}{l}
{y_1}[n] = \sum\limits_{k = 0}^M {{b_k}} {x_1}[n - k];\\
{y_2}[n] = \sum\limits_{k = 0}^M {{b_k}} {x_2}[n - k];
\end{array}\]現在考慮前述兩輸入的線性組合,亦即對任意 $\alpha, \beta \in \mathbb{R}$ 定義
\[
x[n] := \alpha x_1[n] + \beta x_2[n]
\]我們觀察
\begin{align*}
y[n] &= \sum\limits_{k = 0}^M {{b_k}} x[n - k]\\
 &= \sum\limits_{k = 0}^M {{b_k}} \left( {\alpha {x_1}[n - k] + \beta {x_2}\left[ {n - k} \right]} \right)\\
 &= \sum\limits_{k = 0}^M {{b_k}} \left( {\alpha {x_1}[n - k]} \right) + \sum\limits_{k = 0}^M {{b_k}} \left( {\beta {x_2}\left[ {n - k} \right]} \right)\\
 &= \alpha \sum\limits_{k = 0}^M {{b_k}} {x_1}[n - k] + \beta \sum\limits_{k = 0}^M {{b_k}} {x_2}\left[ {n - k} \right]\\
 &= \alpha {y_1}\left[ n \right] + \beta {y_2}\left[ n \right]
\end{align*}由於輸出為 $y_1[n],y_2[n]$ 之線性組合,亦即 $y[n] = \alpha y_1[n] + \beta y_2[n]$ ,故可知此 FIR 濾波器為線性。

接著我們證明非時變性質,對任意 $n_0 \in \mathbb{N}$ 考慮時延輸入訊號 $x[n-n_0]$,則不難發現
\[\sum\limits_{k = 0}^M {{b_k}} x[n - {n_0} - k] = y\left[ {n - {n_0}} \right]\]
亦即等量的時延輸入 導致 等量時延輸出,故此系統為非時變。$\square$