321_088-147CP-TW

跳到主要內容區

:::

321_088-147CP-TW

發佈日期 : 2009-04-29

發明專利說明書
	※申請案號：
	※申請日期：　　　　　　　　　　※ＩＰＣ分類：

一、發明名稱： (中文/英文)
	可選擇之固定係數濾波器裝置 (全文下載)
二、申請人：共人
	指定為應受送達人

三、發明人：

◎專利代理人：


四、聲明事項

	□主張專利法第二十七條第一項國際優先權：
	□主張專利法第二十九條第一項國內優先權：
	□ 主張專利法第二十六條微生物：
□ 熟習該項技術者易於獲得，不須寄存

五、中文發明摘要：
	在本發明提出一新類型的固定係數遞迴架構來計算二的冪次方長度之離散餘弦轉換。應用數論理論，此提出之固定係數遞迴架構由探討轉換基底的週期性來發展，從而形成一完全剩餘數系或一完全奇剩餘數系。基於原始資料的互換排列，正負改變與零值插補，此遞迴濾波架構只需要固定的乘法器，而優於需要通用乘法器的其它遞迴架構。在有限字元長度的機器中，我們發現適當地選擇濾波係數，在轉換時可達成較低捨去(rotund-off)誤差。

六、英文發明摘要：


七、指定代表圖：
（一）本案指定代表圖為：
（二）本代表圖之元件代表符號簡單說明：


八、本案若有化學式時，請揭示最能顯示發明特徵的化學式：


九、發明說明：
	[發明內容] 本案係為一種可選擇之固定係數濾波器裝置，係用於遞迴計算一N點離散餘弦轉換(DCT)。離散餘弦轉換(DCT)已經被廣泛的應用在影像與語音信號處理，壓縮及有關於頻譜分析與參數估測等領域[1]。所以DCT的簡單實現法之發展變得非常重要[2]。在近幾年來，正交轉換的遞迴實現已經獲得重視，因為此遞迴實現擁有簡單結構與部份區域通信(local communication)的特性[3-15]。Goertzel首先使用有限三角數列的週期性來減少離散富利葉轉換(DFT)的計算[3，4]。Goertzel的遞迴架構不但節省計算量，而且簡化實現的複雜度。最近，有數種離散餘弦轉換的規則遞迴演算法被提出[4-15]。任意長度轉換離散餘弦轉換與反離散餘弦轉換的遞迴演算法在[5-7]中提出。在[8]中，正與反DCT轉換的遞迴運算之架構亦被述及。轉換二的冪次方長度DCT於一些群的遞迴架構在[9]中提出。在[10-13]中，遞迴結構能擴展到一般性的離散弦波轉換(discrete sinusoidal transforms)。在[14]中，二維遞迴DCT/IDCT的VLSI 設計擁有模組化，規則化與可調階化的特性。在[20]中，全數位式遞迴計算DFT的演算法及其遞迴架構被提出。在 [21]中，計算FFT的算術處理單元被串列的組合，而其每一級皆為遞迴計算架構。在[22]中，算術運算單元為遞迴型式且不必須要用到乘法器。而通用型二階遞迴數位濾波器在[23]中提出。在[24]中，兩個實數數列輸入的FFT計算，以兩個遞迴FFT架構來實現。這些遞迴演算法亦顯示超大型積體電路實現時的一些優點。當我們用先前作者發展出的遞迴演算法計算離散餘弦轉換時，在遞迴架構中，他們的濾波係數須隨著各個頻率成份改變。每一組的濾波係數只能用來計算一個指定的轉換輸出。此意謂著我們應該要使用可變係數乘法器於遞迴IIR 濾波器中，以獲得所有的轉換結果。因此，一可變係數乘法器需要一般通用型乘法器，此通用型乘法器有N個儲存的乘數(multiplicands)，如果轉換的長度是為N。除此之外，一些濾波係數能將IIR濾波器移至接近不穩定的狀態，而此狀態將造成一些遞迴結果不精確，特別是在有限字元長度的機器之下。而我們能增加處理器的字元長度來克服這個問題。但無論如何，擁有長字元的高速乘法器在硬體上是相當昂貴的。如此，在遞迴架構的缺點為在實際應用上需要非常快速與精確的處理核心，例如IIR濾波乘法器。 Chau與Siu在[15]中提出一固定係數遞迴架構來計算質數長度的DCT。然而，最常用的DCT長度為二的冪次方。在[16]中，用來實現時域錯亂消除技術(TDAC) 的固定係數遞迴架構被提出來討論。由於離散餘弦轉換(DCT)已經被廣泛的應用在影像與語音信號處理，壓縮及有關於頻譜分析與參數估測等領域，所以DCT的簡單實現法之發展變得非常重要。因為遞迴(recursive)實現擁有簡單結構與部份區域通信(local communication)的特性，能簡化實現的複雜度。而遞迴 DCT的VLSI設計擁有小晶片面積，模組化，規則化與可調階化的優點。所以，DCT的遞迴演算法在最近獲得發展與重視。而本案的目的即在於提出一新類型的固定係數遞迴架構來計算二的冪次方長度之離散餘弦轉換。應用數論理論，此提出之固定係數遞迴架構由轉換基底的週期性，可形成一完全剩餘系或完全奇剩餘系。基於原始資料的互換排列，正負改變與零值插補，此遞迴濾波架構只需要固定係數的乘法器，其在實現的架構上非常簡單，而優於需要通用乘法器的其它傳統遞迴架構。在有限字元長度的機器中，我們的方法可適當地選擇濾波係數，能避免先前方法會有的接近不穩定狀態，在轉換時可達成較低的捨去 (round-off)誤差。為了達上述目的，本案提出一種可選擇之固定係數濾波器裝置，以迴遞計算一N點離散餘弦轉換(DCT)，其包括：一資料處理單元，係將一原始資料依位置互換，正負改變及零值插補完成2N點新輸入數據以計算該N點離散餘弦轉換之係數值；以及一二階(Second Order)濾波器架構，係連接至該資料處理單元，該濾波器架構係用以選擇一固定係數，並以完成排序之2N點新輸入數據，經2N個濾波器之迴遞運算以完成該N點離散餘弦轉換。其中N為二的冪次方。而該N點離散餘弦轉換為一離散餘弦轉換第二型(DCT-Ⅱ)。因應該離散餘弦轉換第二型之計算，該二階濾波器係具一固定迴圈係數及一固定輸出係數。固定迴圈係數為2cos(qπ/2N)，而固定輸出係數為- ，而q值為可選擇之正整數需與2N互質且為較大，但不得大於N-1。當然，資料處理單元係依m之秩序讀取y[n]，其中n與m滿足q(2m+1)=(2n+1)(2k+1)mod4N，若n大於N-1，則y[n]補零，其中正負符號為(-1)^r4且r₄= [(2n+1)(2k+1)/4N]。運算子，[x]為取x的整數部份。離散餘弦轉換第二型通稱離散餘弦轉換DCT。其次，N點離散餘弦轉換亦可為一離散餘弦轉換第三型 (DCT-Ⅲ)。因應該離散餘弦轉換第三型之計算，該二階濾波器架構係具一固定迴圈係數及一固定輸出係數。固定迴圈係數為2cos(qπ/2N)，而該固定輸出係數為cos(qπ/2N)。 q值為可選擇之正整數需與2N互質且為較大，但不得大於 N-1。因應該離散餘弦轉換第三型之計算，該資料處理單元係依m之秩序讀取y[n]，其中n與m滿足 n(2k+1)mod2N=qm mod2N，若n大於N-1，則y[n]補零，其正負符號則為(-1)^r3且r₃=[n(2k+1)/2N] 離散餘弦轉換第三型係為逆散餘弦轉換(IDCT)。再者，N點離散餘弦轉換更可為一離散餘弦轉換第四型 (DCT-IV)。因應該離散餘弦轉換第四型之計算，該二階濾波器架構係具一固定迴圈係數及一固定輸出係數。固定迴圈係數為2cos(qπ/2N)，而該固定輸出係數為 -cos(qπ/4N)。q值為可選擇之正整數，需與2N互質，且為較大，但不得大於N-1。而該資料處理單元係依m之秩序讀取y[n]，其中n與m滿足q(2m+1)=(2n+1)(2k+1)mod4N，若n大於N-1，則y[n]補零，其中正負符號為(-1)^r4且r₄= [(2n+1)(2k+1)/4N]。本案得藉由下列圖式及詳細說明，俾得一更深入之了解：圖一：本案計算DCT-Ⅲ的固定係數遞迴架構。圖二：本案計算DCT-Ⅳ的固定係數遞迴架構。圖三：本案計算DCT-Ⅱ的固定係數遞迴架構。圖四：本案固定係數乘法器2cos(47π/128)的實現。圖五：本案資料處理單元的實現法1。圖六：本案資料處理單元的實現法2。圖七：本案遞迴濾波器接近不穩定狀態的極點位置。圖八：本案遞迴濾波器穩定狀態的極點位置。發明敘述 1．離散餘弦轉換之簡介離散餘弦轉換(DCT)能分類為四種型式。最為人們所熟知的離散餘弦轉換及其反轉換為離散餘弦轉換第二型(DCT- II)與第三型(DCT-III)。由於存在有相似的數式，如果比率的修改與指標的改變可以被忽略，一種類型的反轉換可以是其它類型的正轉換。例如，DCT-II的反轉換等於DCT- III的正轉換，而DCT-III的反轉換相對於DCT-II的正轉換。為了簡易起見，我們在以下的推導中省略離散餘弦轉換的比率因數。因此，為大家所熟知的離散餘弦轉換第二型與第三型表示為 1， (2) 由於在發展DCT-II遞迴演算法時需要使用到DCT-IV，其轉換表示如下所述 1，...，N-1， (3) 當我們利用先前的遞迴方法計算離散餘弦轉換時[5， 6，7]，他們的遞迴架構中之濾波係數是相關於其對映的頻率成份。在下面的段落，我們將發展有固定係數的遞迴架構來實現這些離散餘弦轉換。 2．固定係數的遞迴離散餘弦結構因為三種不同型式的離散餘弦轉換使用到不同的推導過程，我們將在下面三小節分別描述其固定係數遞迴架構。由於最常用的離散餘弦轉換長度為二的冪次方，所以以下的討論將特別注重N=2^M的情況。 2-1．DCT-III的固定遞迴架構描述於(2)的N點DCT-III持有離散餘弦基底方程式，其對於指標n與k存在著周期性。現在我們將注意力放在整數式，(2k+1)n/2N，它是關於離散餘弦基底方程式的最重要指標。然後，我們能表示(2)式為在此r₃=[n(2k+1)/2N]和m₃=[n(2k+1)mod 2N。運算子，[x]為取x的整數部份，而模運算子，[p mod 2N]為表示小於 2N的正整數，在p加或減2N的倍數之後。因為基底方程式可為，則在(4)式的 DCT-III變成為了要探索基底方程式的週期性，我們將預視一些有用的數論(number theory)特性與理論[18，19]。定義1：一個有P個整數的集合a₁，a₂...，a_p是一個模 P的完全剩餘數系(complete residue system in modulo P)若且惟若a_i≠a_j，(mod P)，i≠ j。理論1：令(a，P)=1。且令r₁，r₂，...，r_P是一個模P的完全剩餘數系。然後，ar₁+b， ar₂+b，...，ar_P+b也是一個模P的完全剩餘數系，在此b是一任意的整數。在定義1中，此完全剩餘數系，{a₁，a₂，...，a_p}描述模P的所有可能值。在理論1中，(p，q)=1，意指P與 q的最大公因數為1，即為p與q互質。從定義1中，明顯地{n mod 2N\|for n=0，1， 2，...，2N-1}描述模2N的一個完全剩餘數系。在理論1 (a=2k+1，P=2N and b=0)，我們知道(2k+1，2N)=1，因為N是二的冪次方。因此，{m₃\|for n=0，1，2，...， 2N-1}也為相同的模2N的完全剩餘數系。為了要使用完全剩餘系的觀念，我們延展(2)，(4)與(5) 的總合指標到2N-1， y(n)=0 for n=N，N+1，...，(2N-1) (6) 使用這些N個假輸入與以上的特性，我們能改變DCT-III 的總合指標，從n到m如下 m=m₃=n(2k+1)mod 2N。 (7) 如此，DCT-III變成而k=0，1，...，N-1。因為{m=n(2k+1)mod 2N︱for n=0，1，...，(2N-1)}建構一個完全剩餘數系，m與n是頻域相關的一對一映射，如(7)所述。如此改變總合指標，從n到m，將不會改變最後的結果。式(8)與(9)明顯表示DCT-III轉換變成一固定的轉換，如果頻域相關的互換，正負改變與零值內插數列被應用，y_k(m)為新的輸入值。現在，對於(8)式可發展一固定遞迴架構。用2N-1-m代替m於(8)式，則依據使用與[6]相似的程序，可得遞迴公式如下 Y₃(k,j)=cos(θ)y_k(j)-y_k(j-1)+2cos(θ)Y₃(k,j-1)-Y₃(k,j-2)。 (12) 基於遞迴指標j，可得(12)式的z-transform如下在(13)式，經過2N-1次的遞迴後，可得Y₃(k)=(- 1)Y₃(k，2N-1)。圖1顯示發展的DCT-III之固定係數遞迴架構。固定的迴圈濾波係數為2cos(π/2N)，此係數每一遞迴迴圈執行一次。然而，固定的輸出係數cos(π/2N)與輸出符號係數-1，只有在求每一頻域輸出時執行。 2-2．DCT-IV的固定遞迴架構描述於(3)式的N點DCT-IV擁有離散餘弦基底方程式，而n與k指標具有週期性。用相似的方法，我們只需要觀察整數因式，(2n+1)(2k+1)/4N。如此，DCT-IV可表示為在此r₄=[(2n+1)(2k+1/4N]與m₄=[(2n+1)(2k+1)mod 4N]。為了探索週期性質，我們將定義其它的剩餘系。定義2：有P個奇整數的集合a₁，a₂，...，a_P，是一個模 2P的完全奇數剩餘數系(complete odd residue system in modulo 2P)若且為若a_i ≠a_j(mod 2P)，i≠j。由定義2，明顯地{(2n+1)mod 4N︱for n=0，1， 2，...，2N-1}建構一個模4N的完全奇數剩餘數系。此完全奇數剩餘系，{1，3，5，...，4N-1}，是一種減少剩餘數系(redueed residue system)[18，19]。因為 (2k+1)(2n+1)對任意的整數n與k而言為奇數，則 (2n+1)(2k+1)mod 4N對任意的整數n與k而言必為奇數。由理論1及令a=2k+1，P=2N與b=0，{(2n+1)(2k+1) mod 4N︱for n=0，1，2，...，2N-1}，包含2N個不同的奇整數，也建構一個模4N的完全奇數剩餘數系。然而，{(2n+1)mod 4N︱for n=0，1，...，N-1}，擁有N個不同的奇整數r₀，r₁，...，r_N-1，只提供一半的模 4N完全奇數剩餘系。由理論1與(2k+1，4N)=1，我們可知{(2n+1)(2k+1)mod 4N︱for n=0，1，...，N-1}也能建構一半的模4N完全奇數剩餘數系。類似上一段落的討論，我們能增加(3)與(14)的總合指數到2N-1，靠著增補與 (6)相似的假資料。如此，我們能定義一新的輸入數列而n=0，1，2，...，N-1。為了簡單，令y_k(m)=(2m+1). 由(15)(16)，在輸入資料的零值插補，互換排列，與正負改變，則DCT-IV轉換可表示為而k=0，1，...，N-1。為了計算(17)式，開始發展其遞迴架構如下。用2N- 1-m代替m代入(17)，則用類似的方法，可得遞迴公式如下， Y₄(k,j)=cos(θ/2)[y_k(j)-y_k(j-1)]+2cos(θ)Y₄(k,j-1)-Y₄(k,j-2)。(20) 基於時間遞迴指數j，我們可得(20)式的z-transform如下，在(21)式，經過2N-1次的遞迴後，可得Y₄(k)=(-1)Y₄(k， 2N-1)。圖二顯示發展的DCT-IV之固定係數遞迴架構。固定的迴圈濾波係數為，2cos(π/2N)，此係數每一遞迴迴圈執行，然而，固定的輸出係數，-cos(π/4N)，只有在求每一頻域輸出時執行一次。 2-3．DCT-II的固定係數遞迴架構敘述於(1)式的N點DCT-II轉換擁有離散餘弦基底方程式。由先前的討論，我們先探討其整數因式，(2n+1)k/2N。因為對偶數k而言(k，2N)≠1，由理論1，{(2n+1)k mod 2N︱for n=0，1，2，...，N-1}不能建構N個不同的整數而形成任何的模2N完全剩餘系或減少剩餘系。為了要獲得DCT-II的固定係數遞迴架構，我們建議必須先做DCT-II到DCT-IV的轉換. 由離散餘弦的三角特性，我們可知等式如下[17] 應用(1)，(3)與令 (n)=2cos(θ_n)y(n)， (24) 可得DCT-II與DCT-IV的關係如下在此θ_n=(2n+1)π/4N。由(1)，可知。如果先用 DCT-IV固定係數遞迴架構計算(n)的DCT-IV轉換，再應用(25)遞迴算出所DCT-II係數。圖3顯示實現DCT-II的固定係數遞迴架構。為了獲得(n)，頻域獨立的加權程序需要N個乘法。然而，這程序能合併入正規的視窗方程式。因此一般而言，可省略掉(n)的計算。 3．具選擇性的固定遞迴結構在前面的討論可之知，式(13)與(21)的IIR濾波器實際上是邊際穩定(marginal stable)，因為其在單位圓上產生共軛極點(conjugate poles)。在DCT-II，DCT-III與DCT- IV遞迴迴圈的濾波係數皆為2cos(π/2N)，而此值接近於 2。在此狀況下，此IIR濾波器在單位圓上接近有兩個雙重極點，將產生近似不穩定狀態。值得注意的是，此近似不穩定狀態也發生在所有之前談過的遞迴架構，當計算較低頻係數時。而此近似不穩定狀態造成一些遞迴結果不正常的放大，對於轉換結果產生不精確的值，特別是在有限字元長度機器時。反之，如果我們能選擇非常小的迴圈係數，則對遞迴DCT架構的round-off誤差將有很大的改善。在此章節，我們將提出一個方法來選擇固定係數以得到更精確的DCT遞迴結果。 3-1．DCT-III具選擇性的固定遞迴結構對於DCT-III的固定遞迴架構，為了選擇迴圈濾波器使其在有限字元長度下得到更精確的轉換值，利用數論理論，我們能進一步擴展3-1節發展的架構。由理論1，能進一步選擇a=q，P=2N and b=0，在此 q與2N互質，也就是說(q，2N)=1。如此，{qm' mod 2N︱for m'=0，1，2，3，...，2N-1}也可以造成模2N 的完全剩餘系。擴展(8)與(9)，能獲得一改進互換輸入數列，一對一對映，由y_k(m)到y_'k(m')如下 y'k(m')=(-1)^[qm'/2N]y_k(m)， (26) 在此映射m到新的指數m' m=qm'mod 2N (27) 如此，我們能重寫(8)式為而k=1，2，...，N-1。在(28)式中，用2N-1-m'替代m'，則DCT-III轉換可寫成令，定義依據使用與[6]相似的程序，可得遞迴公式如下 Y₃(k,j)=cos()y'_k)-y'_k(j-1)+2cos ()Y₃(k,j-1)-Y₃(k,j-2)。 (31) 基於遞迴指標j，可得(31)式的z-transform如下在(32)式，經過2N-1次的遞迴後，可得。在圖1中，如果固定迴圈係數，固定輸出係數與輸出符號係數分別改為2cos(qπ/2N)，cos(qπ/2N)與(-1)q，則可表示(32)式。 3-2．DCT-IV具選擇性的固定遞迴結構類似前節的討論，由理論1，能選擇a=q，P=4N and b=0，此q與4N互質，亦即(q，4N)=1。如此，我們得知 {q(2m'+1)mod 4N︱m'=0，1，2，3，...，2N-1}也建構模4N的完全奇數剩餘系。擴展使用(15)與(16)，我們能獲得一對一改進互換輸入數列，由如下在此指標映射為為了簡單起見，我們令，而m'=0， 1，...，2N-1。則此改進的DCT-III轉換變成而k=1，2，...，N-1。在(35)式中，用2N-1-m'替代m'，則DCT-IV可寫為依據使用與[6]相似的程序，可得新遞迴公式如下基於遞迴指標j，可得(39)式的z-transform如下在(40)式，經過2N-1次的遞迴後，可得Y₄(k)=(-1)^qY₄(k,2N-1)。在圖2中，如果固定迴圈係數與固定輸出係數分別改為 2cos(qπ/2N)與(-1)^qcos(qπ/4N)，則可表示(40)式。基於 3-3節所述，應用(40)式的DCT-IV改進遞迴架構，我們能遞迴地計算DCT-II係數。有選擇性固定係數的DCT-II遞迴結構能用圖三表示，如果固定迴圈係數與固定輸出係數分別改為2cos(qπ/2n)與(-1)^qcos(qπ/4N)。 4．精確度與複雜度的比較為了比較精確度與複雜度，不同DCT之演算法在有限字元長度的機器中被實現並模擬。如果我們在64位元電腦計算處理直接DCT輸出的無雜訊結果，表1，2與3對應於計算64點，16點與8點DCT-III轉換在不同字元長度的平均SNR值。所有的模擬結果顯示，此提出的固定係數遞迴演算法，在有限字元長度的機器中執行時，於 q=47(N=64)，q=15(N=16)，q=7(N=8)達到最佳的精確度。當q=1時，此提出的固定係數DCT遞迴演算法產生最嚴重的round-off誤差，特別是在大的轉換長度時 (N=64)。當我們沒有適當的選擇遞迴迴圈的係數時，遞迴濾波器的極點會非常接近，如圖7所示，會產生接近不穩定的狀態。而當我們適當的選擇遞迴迴圈的係數時，改為 2cos(qπ/2N)後，會避免掉不穩定的狀態，此時遞迴濾波器的極點被拉開至適當的位置，如圖8所示。因為遞迴的次數N 為有限長度，並不是無限的長度，所以不會有不穩定的狀態發生。在用直接實現法計算時，其為乘加結構，如(1)， (2)與(3)式所示，似FIR濾波器架構，亦可看成是一種遞迴運算，其被乘數之餘弦值是可變的，且大小不同，變動範圍很大，所以會產生較大的round-off誤差。而在我們提出的遞迴演算法上，在適當的選擇乘法的固定餘弦值後，其餘弦值往小，變動範圍小，所以會產生較小的round-off誤差，因此我們提出的遞迴演算法，其SNR值會比直接實現法為佳。傳統的可變係數遞迴演算法，平均而言，對於轉換結果產生較大的round-off誤差，因為他們在較低的頻率成份時，有大的round-off誤差。在可變係數遞迴架構中，第一個頻率成份將有類似固定係數遞迴演算法選擇q=1時的品質。值得注意的是，在許多分析與壓縮的應用上，較低頻率成份通常比高頻率成份來得重要。例如，如果轉換結果的SNR值要達到80dB左右，對於我們提出的固定係數 DCT-III遞迴演算法，在q=47與N=64時，我們應該選擇18 位元的機器。在表1中，我們能看出傳統的遞迴方法，其 SNR值只能到達約45。5dB，因此他們需要24位元的機器來維持其SNR值到達80dB。由以上的模擬結果，我們能公正的評估比較這些遞迴演算法的計算複雜度與throughput率。傳統的遞迴演算法，在計算一個輸出時，需要2N個加法與N+1個乘法。而我們提出的演算法，在計算一個輸出時，需要4N+1個加法與 2N+1個乘法。而傳統的遞迴架構，需要2個通用型乘法器，2個加法器與2個delay buffer於DCT-III的計算。而我們提出的遞迴架構需要2個固定型乘法器，3個加法器，2個delay buffer與資料處理單元於DCT-III的計算。對於傳統的遞迴架構，要實現一個24位元的通用型乘法器，需要24個加法器於24位元機器中，才能達到80dB 的SNR值。然而要實現一個固定係數的乘法器，例如，運算元2cos(47π/128)=0.810482628₁₀= 0.1100111101110111₂，如圖4所示，我們只有用到6個加法器，在18位元長度機器中達到80dB的精確度。因此，我們提出的固定係數遞迴架構只需要一非常低的硬體複雜度。對於DCT-III與DCT-IV的資料處理單元裝置，首先提出一種完全以ROM為基礎的位址產生器，如圖5所示，我們循序地將輸入資料寫入RAM中，而ROM的內容為事先計算好的n(2k+1)mod 2N=qm' mod 2N或 (2n+1)(2k+1)mod 2N=q(2m'+1)mod 2N的計算，儲存了n到m'的對映次序與符號改變，而達成m'到n的指標變換。而第二種提出的資料處理單元裝置，如圖6所示，此位址產生器包含1個加法器，1個計數器，1個移位器，1個比較器，1個ROM與1個FIFO暫存器。以 N=64為例，在DCT-III的狀態下，計數器的輸出週期數列為{0，1，2，...，127}，而FIFO暫存器的出始內容為 {0，1，2，...，127}。在DCT-IV的狀態下，計數器的輸出週期數列為{1，3，5，...，127}，而FIFO暫存器的初始內容為{1，3，5，...，127}。直接使用加法器7LSB位元的模運算，實際上不需要任何的計算。使用6個LSB位元來定址RAM，而進位位元來控制正負改變。值得注意的是，此兩種資料處理單元裝置在1個clock cycle能產生1 個前處理完的資料，以供以後的遞迴運算使用。由以上的討論可知，所有DCT遞迴結構的瓶頭在於濾波器迴圈係數的乘法器。傳統的64點DCT-III遞迴結構，利用24位元的通用型乘法器，需要64次的遞迴。此傳統可變係數遞迴結構的throughput率，對於每個轉換輸出而言，被限制在要經過1536個24位元的加法。而我們提出的固定係數64點DCT-III遞迴結構，需要6個加法的固定係數乘法器及128次的遞迴。因此，此提出的固定係數遞迴結構的throughput率，對於每個轉換輸出而言，只限制在768個18位元的加法。因此，我們提出的固定係數遞迴結構能優於傳統方法，達到超過2倍快的throughput 率。因為latency delay只發生在遞迴計算部份，所以此提出的遞迴結構與傳統遞迴方法比較，將只有一半的latency delay。特點及功效在本發明提出一新類型的固定係數遞迴架構來計算二的冪次方長度之離散餘弦轉換。應用數論理論，此提出之固定係數遞迴架構由轉換基底的週期性來發展，從而形成一完全剩餘系或一完全奇剩餘系。而基於原始資料的互換排列，正負改變與零值插補，此遞迴濾波架構只需要用到固定的乘法器，此固定的乘法器具有很低的硬體複雜度，而優於需要高複雜通用乘法器的其它傳統遞迴架構。在另一方面，本發明可適當地選擇固定濾波係數，從而避免接近不穩定狀態，在轉換時可達成較低的round-off誤差。就實用性而言，遞迴離散餘弦轉換(DCT)可被廣泛的應用在影像與語音信號處理，壓縮及有關於頻譜分析與參數估測等領域。且遞迴實現擁有簡單結構與份區域通信的特性，能簡化實現的複雜度。而遞迴DCT的VLSI設計擁有小晶片面積，模組化，規則化與可調階化的優點。就新穎性而言，本案提出一新穎的固定係數遞迴架構來計算二的冪次方長度之離散餘弦轉換。基於原始資料互換排列，正負改變與零值插補的排序裝置，此遞迴濾波架構只需要用到固定的乘法器，而優於需要高複雜通用乘法器的其他傳統遞迴架構。另外進步性方面，本案可適當地選擇固定濾波係數，從而避免接近不穩定狀態，在轉換時可達成較低的round-off誤差。本案得由熟悉本技藝之人士任施匠思而為諸般修飾，然皆不脫如附申請專利範圍所欲保護者。參考文獻之論文： [1] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms, Advantages Applications, Academic Press, Inc., 1990. [2] S. C. Chan and K. L. Ho, "Direct Methods for Computing Discrete Sinusoidal Transforms," IEE Proceedings-F, Vol. 137, No. 6, pp 433-442, 1990. [3] A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing, Prentice Hill, 1989. [4] G. Goertzel, “An Algorithm for the Evaluation of Finite Trigonometic Series,” American Math. Monthly, Vol. 65, pp. 34-35, Jan. 1958. [5] L. P Chau and W. C. Siu,“Recursive Algorithm for the Discrete Cosine Transform with general length,”Electron. Lett., Vol. 30, pp. 197-198, 1994. [6] Z. Wang, G. A. Jullien and W. C. Miller,“Recursive Algorithms for the Forward and Inverse Discrete Cosine Transform with Arbitrary length,”IEEE Signal Processing Letters, Vol. 1, pp. 101-102, 1994. [7] M. F. Aburdene, J. Zheng and R. J. Kozick,“Computation of Discrete Cosine Transform Using Clenshaw‘s Recurrence Formula,”IEEE Signal Processing Letters, Vol. 2, No. 8, pp. 155-156, 1995. [8] H. C. Chiang and J. C. Liu,“Regressive Implementations for the Forward and Inverse MDCT in MPEG Audio Coding,”IEEE Signal Processing Lett., Vol. 3, pp. 116- 118, 1996. [9] Y. H. Chan, L. P. Chau and W. C. Siu;“Efficient Implementation of Discrete Cosine Transform Using Recursive Filter Structure,”IEEE Transactions on Circuits and Systems for Video Technology, Vol. 4, No. 6, pp. 550-552, 1994. [10] K. J. R. Liu and C. T. Chiu,“Unified Parallel Lattice Structures for Time-Recursive Discrete Cosine/Sine/Hartley Transforms,”IEEE Transactions on Signal Processing, Vol. 41, No. 3, pp. 1357-1377, 1993 [11] K. J. R. Liu, J. F. JaJa and C. T. Chiu,“Theoretical Analysis for Recursive Computation of Discrete Sinusoidal Transforms,”Proceedings of IEEE Region 10's Ninth Annual International Conference, 1994. [12] K. J. R. Liu, C. T. Chiu, R. K. Kolagotla and J. F. JaJa, “Optimal Unified Architectures for the Real-Time Computation of Time-Recursive Discrete Sinusoidal Transforms,”IEEE Transactions on Circuits and Systems for Video Technology, Vol. 4, No. 2, pp.168-180, 1994. [13] E. Frantzeskakis, J. S. Baras and K. J. R. Liu,“Time- Recursive Computation and Real-Time Parallel Architectures : A Framework,”IEEE Transactions on Signal Processing, Vol. 43, No. 11, pp.2762-2774, 1995. [14] V. Srinivasan and K. J. R. Liu,“VLSI Design of High-Speed Time-Recursive 2-D DCT/IDCT Processor for Video Applications,”IEEE Transactions on Circuits and Systems for Video Technology, Vol. 6, No. 1, 1996. [15 ] L. P. Chau and W. C. Siu,“Direct Formulation for the Realization of Discrete Cosine Transform Using Recursive Structure”, IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, Vol. 42, No. 1, 1995. [16] D. Y. Chan, J. F. Yang and S. Y. Chen,“Regular Implementation Algorithms of Time Domain Aliasing Cancellation”, accepted in IEE Proceedings-Vision, Image and Signal Processing. [17] Z. Wang, G. A. Jullien and W. C. Miller,“Recursive Algorithm for the Discrete Cosine Transform with Regular Structure,”Proceedings of the 36^thMidwest Symposium on Circuits and Systems, Vol.2, 1993. [18] C. Y. Hsiung, Elementary Theory of Numbers, World Scientific, 1992. [19] I. Niven, H. S. Zuckerman and H. L. Montgomery, An Introduction to the Theory of Numbers, John Wiley & Sons, Inc., 1991. 國外相關專利檢索： [20] G. M. Dillard,“Method and Apparatus for Computing the Discrete Fourier Transform Recursively”, Patent Number: 4023028, Date of Patent: May 10, 1977. [21] K. Niwa,“Serial FFT Processing Unit”, Patent Number:4058715, Date of Patent: Nov. 15, 1977. [22] K. Niwa,“Arithmetic Unit for DFT and/or IDFT Computation”, Patent Number: 4080661, Date of Patent: Mar. 21, 1978. [23] H. J. Butterweck, C. P. Meer and G. Verkroost, “Recursive Digital Filter”, Patent Number: 4569030, Date of Patent: Feb. 4, 1986. [24] J. D. Marchant,“Method of Performing Real Input Fast Fourier Transforms Simultaneously on Two Data Streams”, Patent Number: 4612626, Date of Patent: Sep. 16, 1986. [25]M. L. Liou, M. T. Sun and L. Wu,“Two Dimensional Discrete Cosine Transform Processor”, Patent Number: 4791598, Date of Patent: Dec. 13, 1988. [26] P. Duhamel,“Device for Computing A Digital Transform of A Signal”, Patent Number: 4831574, Date of Patent: May 16, 1989. [27] S. M. C. Borgers and E. A. P. Habraken,“Television Transmission System Using Transform Coding”, Patent Number:4831440, Date of Patent: May 16, 1989. [28] B. Riolfo,“Circuit for Computing the Quantized Coefficient Discrete Cosine Transform of Digital Signal Samples”, Patent Number: 4849922, Date of Patent: July 18, 1989. [29] R. Woudsma, D. C. H. Chong, B. T. Mcsweeney, S. M. C. Borgers and E. A. P. Habraken,“One Dimensional Linear Picture Transformer”, Patent Number: 4881192, Date of Patent: Nov. 14, 1989. [30] R. Friedlander and R. Retter,“Recycling DCT/IDCT Integrated Circuit Apparatus Using A Single Multiplier/Accumulator and A Single Random Access Memory”, Patent Number: 5053985, Date of Patent: Oct. 1, 1991. [31] K. J. Ray Liu and C. T. Chiu,“Optimal Unified Architectures for the Real Time Computation of Time- Recursive Discrete Sinusoidal Transforms”, Patent Number: 5339265, Date of Patent: Aug. 16, 1994. [圖式簡單說明] 圖一本案計算DCT-Ⅲ的固定係數遞迴架構。圖二本案計算DCT-Ⅳ的固定係數遞迴架構。圖三本案計算DCT-Ⅱ的固定係數遞迴架構。圖四本案固定係數乘法器2cos(47π/128)的實現。圖五本案資料處理單元的實現法1。圖六本案資料處理單元的實現法2。圖七本案遞迴濾波器接近不穩定狀態的極點位置。圖八本案遞迴濾波器穩定狀態的極點位置。

十、申請專利範圍：
	1.一種可選擇之固定係數濾波器裝置，以迴遞計算一N點離散餘弦轉換(DCT)，其包括：一資料處理單元，係將一原始資料依位置互換，正負改變及零值插補完成2N點新輸入數據以計算該N點離散餘弦轉換之係數值；以及一二階(Second Order)濾波器架構，係電連接至該資料處理單元，該濾波器架構係用以選擇一固定係數，並以完成排序之2N點新輸入數據，經2N個濾波器之迴遞運算以完成該N點離散餘弦轉換。　　2.如申請專利範圍第1項所述之可選擇之固定係數濾波器裝置，其中N為二的冪次方。　　3.如申請專利範圍第1項所述之可選擇之固定係數濾波器裝置，其中該N點離散餘弦轉換為一離散餘弦轉換第二型(DCT-Ⅱ)。　　4.如申請專利範圍第３項所述之可選擇之固定係數濾波器裝置，其中因應該離散餘弦轉換第二型之計算，該二階濾波器係具一固定迴圈係數及一固定輸出係數。　　5.如申請專利範圍第4項所述之可選擇之固定係數濾波器裝置，其中該固定迴圈係數為2cos(qπ/2N)，而固定輸出係數為-cos。　　6.如申請專利範圍第5項所述之可選擇之固定係數濾波器裝置，其中q值為可選擇之正整數需與2N互質且為較大，但不得大於N-1。　　7.如申請專利範圍第6項所述之可選擇之固定係數濾波器裝置，其中該資料處理單元係依m之秩序讀取y[n]，其中n與m滿足q(2m+1)=(2n+1)(2k+1)mod4N，若n大於N-1，則y[n]補零，其中正負符號為(-1)r4且r4=「(2n+1)(2k+1)/4N。　　8.如申請專利範圍第3項所述之可選擇之固定係數濾波器裝置，其中該離散餘弦轉換第二型通稱離散餘弦轉換DCT。　　9.如申請專利範圍第1項所述之可選擇之固定係數濾波器裝置，其中該N點離散餘弦轉換為一離散餘弦轉換第三型(DCT-Ⅲ)。　　10.如申請專利範圍第9項所述之可選擇之固定係數濾波器裝置，其中因應該離散餘弦轉換第三型之計算，該二階濾波器架構係具一固定迴圈係數及一固定輸出係數。　　11.如申請專利範圍第10項所述之可選擇之固定係數濾波器裝置，其中該固定迴圈係數為2cos(qπ/2N)，而該固定輸出係數為cos(qπ/2N)。　　12.如申請專利範圍第11項所述之可選擇之固定係數濾波器裝置，其中q值為可選擇之正整數需與2N互質且為較大，但不得大於N-1。　　13.如申請專利範圍第12項所述之可選擇之固定係數濾波器裝置，其中因應該離散餘弦轉換第三型之計算，該資料處理單元係依m之秩序讀取y[n]，其中n與m滿足n(2k+1)mod2N=qm mod2N，若n大於N-1，則y[n]補零，其正負符號則為(-1)r3且r3=「n(2k+1)/2N。　　14.如申請專利範圍第9項所述之可選擇之固定係數濾波器裝置，其中該離散餘弦轉換第三型係為逆散餘弦轉換(IDCT)。　　15.如申請專利範圍第1項所述之可選擇之固定係數濾波器裝置，其中該N點離散餘弦轉換為一離散餘弦轉換第四型(DCT－Ⅳ)。　　16.如申請專利範圍第15項所述之可選擇之固定係數濾波器裝置，其中因應該離散餘弦轉換第四型之計算，該二階濾波器架構係具一固定迴圈係數及一固定輸出係數。　　17.如申請專利範圍第16項所述之可選擇之固定係數濾波器裝置，其中該固定迴圈係數為2cos(qπ/4N)，而該固定輸出係數為- cos(qπ/4N)。　　18.如申請專利範圍第17項所述之可選擇之固定係數濾波器裝置，其中q值為可選擇之正整數，需與2N互質，且為較大，但不得大於N-1。　　19.如申請專利範圍第18項所述之可選擇之固定係數濾波器裝置，其中該資料處理單元係依m之秩序讀取y[n]，其中n與m滿足q(2m+1)=(2n+1)(2k+1)mod4N，若n大於N-1，則y[n]補零，其中正負符號為(-1)r4且r4=「(2n+1)(2k+1)/4N。


十一、圖式：

瀏覽數:

分享

登入成功