跳到主要內容

[訊號與系統] 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$




留言

這個網誌中的熱門文章

[數學分析] 什麼是若且唯若 "if and only if"

數學上的 if and only if  ( 此文不討論邏輯學中的 if and only if,只討論數學上的 if and only if。) 中文翻譯叫做  若且唯若 (or 當且僅當) , 記得當初剛接觸這個詞彙的時候,我是完全不明白到底是甚麼意思,查了翻譯也是愛莫能助,畢竟有翻跟沒翻一樣,都是有看沒有懂。 在數學上如果看到 if and only if  這類的句子,其實是表示一種 雙條件句 ,通常可以直接將其視為" 定義(Definition)" 待之,今天要分享的是這樣的一個句子如何用比較直觀的方法去看他 假設我們現在有 兩個邏輯陳述句 A 與  B. 注意到,在此我們不必考慮這兩個陳述句到底是什麼,想表達什麼,或者到底是否為真(true),這些都不重要。只要知道是兩個陳述即可。 現在,考慮新的陳述:  "A if and only if B" 好了,現在主角登場,我們可以怎麼看待這個句子呢? 事實上我們可以很直覺的把這句子拆成兩部分看待,也就是 "( A if B ) and ( A only if B )" 那麼先針對第一個部分  A if B  來看, 其實這句就是說  if B then A, 更直白一點就是 "if B is true, then A is also true".  在數學上等價可以寫為 "B implies A" .  或者更常用一個箭頭符號來表示 "B $\Rightarrow$  A"  現在針對第二個部分  A only if B 此句意指  "If B is not true, then A is also not true". 所以如果已知 A is true,  那麼按照上句不難推得 B is also true 也就是說  A only if B  等價為 "If A is true then B is also true". 同樣,也可以寫作   "A implies B"   或者用箭頭表示  "A   $\Rightarrow$     B".

[數學分析] 淺談各種基本範數 (Norm)

這次要介紹的是數學上一個重要的概念: Norm: 一般翻譯成 範數 (在英語中 norm 有規範的意思,比如我們說normalization就是把某種東西/物品/事件 做 正規化,也就是加上規範使其正常化),不過個人認為其實翻譯成 範數 也是看不懂的...這邊建議把 Norm 想成長度就好 (事實上norm是長度的抽象推廣), 也許讀者會認為好端端的長度不用,為何又要發明一個 norm 來自討苦吃?? 既抽象又艱澀。 事實上想法是這樣的: 比如說現在想要比較兩個數字 $3$ , $5$ 之間的大小,則我們可以馬上知道 $ 3 < 5 $;同樣的,如果再考慮小數與無理數如 $1.8753$ 與 $\pi$,我們仍然可以比較大小 $1.8753 < \pi = 3.1415...$ 故可以發現我們有辦法對 "純量" 做明確的比大小,WHY? 因為前述例子中 $3$, $5$, $1.8753$ or $\pi$ 其各自的大小有辦法被 "measure "! 但是如果是現在考慮的是一組數字 我們如何去measure 其大小呢?? 比如說 \[x:=[1, -2, 0.1, 0 ]^T \]上式的大小該是多少? 是 $1$? $-2$? $0.1$??? 再者如果更過分一點,我們考慮一個矩陣 \[A = \left[ {\begin{array}{*{20}{c}} 1&2\\ 3&4 \end{array}} \right] \],想要知道這個矩陣的大小又該怎麼辦?? 是 $1$ ? $2$ 還是 $4$ ?..其實現階段我們說不清楚。 也正是如此,可以發現我們確實需要新的 "長度" 的定義來幫助我們如何去 measure 矩陣/向量/甚至是函數的大小。 故此,我們首先定義甚麼是Norm,(也就是把 "長度" or "大小" 的本質抽離出來) ================== Definition: Norm 考慮 $V$ 為一個向量空間(Vector space),則我們說  Norm 為一個函數 $||\cdot|| : V \rightarrow \mathbb{R}$ 且滿足下列性質