数位讯号处理架构设计期末报告.doc

數 位 訊 號 處 理 架 構 設 計 期 末 報 告壹、 概論DSP 的產生是起於類比信號處理系統的工程師，希望在建造昂貴的系統硬體前，先模擬它們性能。DSP 必須仰賴高速電腦和大多數的數學演算法則。自這些演算法則被確立後，設計者開始找尋可以讓電腦更有效率的電腦結構。隨著數位信號處理的快速發展，越來越多的信號處理用全數位化的方式來進行，即以數位方式來表示、儲存、運算各種信號及信號處理過程中所涉及的各項參數。但在數位的運算上，與加法和減法比起來，乘法不論捋行硬體或軟體的方式都是一個複雜的運算，乘法器的硬體複雜度遠比加法器或delay、shift register等為高，所需的運算時間也較長，因此在做各種數位信號處理架構設計時，我們都希望能儘量避免乘法運算。利用數位資料二進位的特性，我們可以用shift register把一個數左/右移動一位，達到把它乘/除以2的效果。因此如果我們把一個filter的impulse response表示成2的次方項的和，這個filter在實作上就只需要使用加法器和shift register以移動input x(n)達成乘或除以2的次方的效果，頂多只需要一個乘法器來把它的impulse response正規化成我們可以表示的範圍即可，跟直接implement時impulse response的每一項係數都需要一個乘法器相比，大大的降低了硬體的複雜度。本篇報告的主題是Signed Power-of-Two Term Allocation Scheme for the Design of Digital Filters。眾所皆知的，如果將數位濾波器的每一個係數值用signed power-of-two (SPT) 來組成，那實現這個數位濾波器將不需要乘法器。過去幾年，大部份所提出設計數位濾波器的方法，皆是用相同數目的二的次方項( SPT terms )來表示係數。但是在很多的應用上，並不是一定要用相同數目的二的次方項來表示係數，這篇Paper提出了一個對每一個係數分派二的次方項的新方法，它可以最小化整個數位濾位器 二的次方項( SPT terms )的總數，也就是說，當保持整個二的次方項( SPT terms )的數目個定，我們可以用不同數目的二的次方項( SPT terms ) 來表示係數值，進而最小化整個數位濾位器二的次方項( SPT terms )的總數。貳、系統架構圖用此種方法所實現的FIR filter，其組織架構大致如下:（L+1為filter length，N=2 個SPT terms）：Shift register ( 0 1 ) x(n)runningsummer normalizeShift register ( 0 2 ) delayShift register ( 1 1 )x(n-1)Shift register ( 1 2 )delay y(n)delayShift register ( L 1 )x(n-L)Shift register ( L 2 ) 即，我們用2的次方項的和來組成impulse response ，將它表示成的形式，其中，而。以上參數的意義為，我們最多用N個2的次方項來組成一個impulse response的係數（上頁圖中所畫的N=2，impulse response的每一項都是由兩個2的次方項相加組成），而我們可以用的組成元件就只限於共M種。我們設計的目標是，找到最好的和的組合，和最適當的normalize factor，使得我們用數位的方式所組成的filter response，和原來的h(n)最相近。以下將分別介紹2的次方項和這個數列的數學特性、以及如何找到最佳的組合方式。參、2的次方項和的數學特性以下我們介紹的數學特性，其中，N為我們用來組成一個數所用的最多2的次方項( SPT terms )數，為我們所用的2的次方項中最小者。【特性一】2的次方項和在數列上不是均勻分布，數值越大，其分布的空隙越大。這一點是很直觀的，因為在項裡，n值越大，相鄰的兩項（和）差距就越遠。所以幾個項的和，在數值比較大的部分，會呈現兩個可以被表示的數之間跳了一大步，而在這一大步中的所有的數，我們完全無法表示它們的情形。有趣的是，如果我們用的項數不變（N不變），即使我們把能夠表示的resolution不斷加大（M），這個情形並不會改善，唯一可能改善這個情形的方法，是採用更大的N值（用更多2的次方項）。在下圖中做了N=2時（最多用兩項2的次方和），用不同M值所能表示的數，圖中的橫軸為可表示的數，縱軸為M值，比較不同的M值之下兩個2的次方項和，我們發現在接近0的部分，M值越大，所能表示的數就越密，但是在0.75附近卻明顯有一個”溝”，而且M值的增加並沒有明顯改善這個”溝”。接下來我們比較不同N值所造成的效果，下圖中我們取M=6，對N=2和3做圖。在上圖中，我們發現了相當奇妙的效果，在M=6的時候，我們能使用的組成元件種類其實不多，只有6種（）但是當我們使用其中的三項（N=3）來組成一個數時，似乎就可以在1-1之間得到一個相當均勻的分佈，原先在N=2時觀察到的在0.75附近的 ”溝”，縮小到幾乎看不見。所以由此可知，增加使用的項數N對增加我們用2的次方項所能組成的數的resolution (M)，有非常好的效果。因為當N=2時，我們是從M個成分中取2項，再考慮正負號或只用1項（另一項係數為0時）的情形，總共可組成個數值；而當N=3時，我們是從M個成分中取3項，或2項，或1項，總共可組成個數值，增加了相當多的數值。【特性二】如果我們想要用最少的項數來表示一個數值，那在這個最簡單的表示法中，相鄰的2的次方項（例如和）的係數至少要有一個為0，也就是說不可能有連續的不為0的係數。 0 1 1 1 0 -1 1 -1 0 1這一點可以用數學式子說明：1. 考慮相鄰兩項係數為同號的情形，則它們可化簡如下： 2. 考慮相鄰兩項係數為異號的情形，則它們可化簡如下： 因此，由上面式子可知，並非所的數值都是unique的，我們在找impulse response的最佳表示法時，可以善用這個特性來減少需要尋找的組合數。【特性三】由於特性二所描述的化簡方式存在，因此我們使用M個2的次方項成分（由）中的N項來組成其它的數字時，所能表示的數值其總數並非我們在特性一結尾時所描述的組合數，而是如下式：正好使用N項（所有係數皆不為0）時，所有可能的組合數為： 在paper上是使用數學歸納法來證明此式。肆、用2的次方項和來組成filter impulse response的方法首先我們可以觀察到，在上一節的特性一的圖中，2的次方項和所能表示的數在1-1之間，因此我們應該把filter的impulse response正規化至1-1之間，這便是在第貳部分的圖中，唯一的一個乘法器的由來，既然我們將impulse response除以一個normalize factor了，送進來的信號就應該先乘上這個normalize factor，才能讓輸出的信號就是我們真正要的值。至於normalize factor應該要取多少呢？一個簡單的想法是將整個impulse response除以其中絕對值最大的那一項，把它normalize成1或-1，但是這裡還有一些改進的空間，我們可以找到一個最適當的normalize factor，詳述如下：因為在接近1的地方，其實2的次方項和所能表示的數值是較不密集的，且如果我們使用的組合成分中不包含，我們甚至沒有辦法組成1這個數字，因此把impulse response中最大的一項normalize成1，可能不是一個好方法。因為2的次方項和所能表示的數值不是uniformly distributed，我們應該嘗試許多不同的normalize factor，最後選用會產生最小誤差的那一個，通常不同的impulse response，能產生最小誤差的normalize factor也不相同。至於我們嘗試的範圍應是多大呢？在paper上是選用normalize過後，impulse response的最大項絕對值在0.51之間為範圍，且我們可以把normalize過的impulse response和它的2的次方項和近似都乘以2，得到另一個一樣的結果。至於在這個範圍內，我們搜尋的step應該定得多細，就要看搜尋時間和結果的最佳化兩者之間的tradeoff了。至於我們應該使用怎樣的N和M值呢？根據paper上所述，M值通常決定在815之間，而N值對近似結果影響較大，因此在指定時的考慮也比較多，分析如下：1. 因為2的次方項和有數值越大，空隙就越大的特性，且這個特性必需要靠N的增加才能消除，因此在normalize過後h(n)比較大的項，我們應該用比較多的項( N )來近似它，以減小quantization error。在Paper上所提供的策略是，當normalized h(n)0.5時，我們就多用一項來近似這個值。而做如此的改變所增加的總項數其實不會很多，因為真實存在的filter impulse response通常是sin(x)/x的形式，normalize過後，h(n)0.5的其實只有少數幾項。2. 一般來說，整個近似表示法使用的N值加1會造成filter在實作時每一路都多一個shift register，是蠻大的成本，因此要慎重考慮。伍、結綸：如果將數位濾波器的每一個係數值用signed power-of-two (SPT) 來組成，那實現這個數位濾波器將不需要乘法器。大部份設計數位濾波器的方法，皆是用相同數目的 二的次方項( SPT terms )來表示係數。這篇Paper提出了一個對每一個係數分派二的次方項的新方法，它可以最小化整個數位濾位器 二的次方項(SPT terms)的總數，也就是說，當保持整個 二的次方項(SPT terms) 的數目個定，我們可以用不同數目的 二的次方項(SPT terms) 來表示係數值，進而最小化整個數位濾位器 二的次方項(SPT terms)的總數。六、參考文獻：1.”Signed Power-of-Two Term Allocation Scheme for the Design of Digital Filters” , Yong Ching Lim , Rui Yang , Dongning Li , Jianjian Song , IEEE transaction on circu