快速線性迴旋積演算法之設計

MUSTIR > College of Management > Department of International Business > Research Projects in School > Item 987654321/578

Please use this identifier to cite or link to this item: http://120.105.36.38/ir/handle/987654321/578

Title:	快速線性迴旋積演算法之設計
Authors:	楊明錞
Contributors:	國際企業系
Keywords:	餘數系統、代數環、線性迴旋積。
Date:	2010-12
Issue Date:	2011-06-22 11:47:00 (UTC+8)
Abstract:	在數位訊號處理(DSP)中，存在最重要的兩大設計─濾波器和轉換域的運算設計，此兩種技術皆被要求具有快速資料計算處理的能力；由於線性迴旋積是此兩大技術中最基本的運算，故本計畫將提出一套設計快速計算線性迴旋積的演算法。若以數學語言描述兩個N點序列的線性迴旋積，可以表示成兩個(N-1)次多項式相乘模(mod) (x2N-1)。我們利用Skavantzous和 Taylor [26] 所提出的多項式餘數系統觀念，主要是將兩多項式相乘定義在特殊的代數環結構下，使得兩多項式相乘所需的乘法個數最少，達到理論上乘法個數的下限值。使得兩多項式相乘在選取的適當代數體下，達到線性迴旋積理論上最少的乘法個數，即所需乘法個數的複雜度為θ(2N)，其中N表示訊號的輸入長度，此方法的缺點為長度N受到所選有限體Zp (GF(p))的限制，長度N必須滿足被(p-1)/2所整除。為了解決上述有限體大小需擴展到符合2N長度，我們試圖在長度為N的多項式環下，亦可解決線性迴旋積，並且達到理論上最少乘法個數。
Appears in Collections:	[Department of International Business] Research Projects in School

Files in This Item:

File	Description	Size	Format
明新計畫99報告(國企系楊明錞).pdf		301Kb	Adobe PDF	693	View/Open