成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	黃聖翔 Huang, Sheng-Hsien
論文名稱：	符合多種應用之有效率的快速/反快速傅立葉轉換編譯器 An Efficient FFT/IFFT Compiler for Different Applications
指導教授：	謝明得 Shieh, Ming-Der
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2006
畢業學年度：	94
語文別：	英文
論文頁數：	98
中文關鍵詞：	無線區域網路、正交分頻多工系統、快速/反快速傅立葉轉換、編譯器
外文關鍵詞：	Compiler, OFDM, Wireless LAN, FFT/IFFT
相關次數：	點閱：130 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

隨著通訊應用的普及與網路時代的來臨，網路對人們來說，已經是生活的一部分。近年來，由於無線網路的發達，擺脫了以往有線網路佈線的限制，無論何時何地皆可自由地上網，進而使得人們對於無線通訊的需求日益增長。無線區域網路 ( Wireless LAN ) 發展至今，隨著不同應用的需求，不同的規範與標準也應蘊而生，對今日的電腦及通訊產業而言，無線應用儼然已成為一個重要的觀念及技術。
在現有的數位通訊系統中，正交分頻多工系統 (OFDM)是常被使用之調變技術。正交分頻多工系統與傳統單載波調變系統最大的差異之處，乃是它採用了多載波調變的技術，此方法目前已規範於802.11x、DAB、DVB等應用標準中，從硬體實現的觀點而言，可透過快速傅立葉及反傅立葉轉換 (FFT/IFFT) 的運算來達到調變與反調變之目的。但是不同應用標準意謂著有不同之FFT/IFFT規格需求，同時，在同一數位通訊系統亦可能包含不同的操作模式，因此，如何設計一個能夠滿足不同的通訊系統標準及操作模式所需的調變解調電路的系統，將是一項挑戰；而本論文便是針對此一課題，提出如何製作一有效率之 FFT/IFFT 編譯器來符合快速電路設計之目的，進而作為後續更深入研究之基礎。

With　the　emergence　of　internet　services　and　pervasion　of　communication　applications,　internet　and　wireless　communication　have　become　a　part　of　our　life.　Wireless　network　can　reach　where　the　traditional　network　cannot　do.　This　makes　the　applications　of　wireless　network　more　widespread.　To　date,　different　wireless　LAN　standards　have　emerged　from　different　applications　and　each　standard　has　its　own　uniqueness　and　application　ranges.
Of　the　existing　digital　communication　systems,　the　Orthogonal　Frequency　Division　Multiplexing　(OFDM)　technique　has　been　widely　used　in　performing　signal　modulation.　Compared　with　the　traditional　single-carrier　frequency　modulation　technique,　OFDM　adopts　multi-carrier　modulation　which　has　been　adopted　in　many　practical　wireless　systems　such　as　802.11x,　DAB　and　DVB,　etc.　Regarding　the　hardware　implementation,　the　OFDM　can　be　fulfilled　by　employing　the　(inverse)　fast　Fourier　transform　(FFT/IFFT).　In　fact,　different　standards　or　operation　modes　imply　different　requirements　or　specifications　for　the　associated　FFT/IFFT;　therefore,　different　design　methodology　should　be　applied.　It　would　be　a　challenge　if　a　unified　FFT/IFFT　architecture　is　to　be　designed.　In　this　thesis,　we　investigate　how　to　develop　an　efficient　FFT/IFFT　compiler　for　different　applications.　Based　on　our　development,　not　only　a　dedicated　FFT/IFFT　module　can　be　easily　prototyped　for　fast　system　verification,　but　also　the　resulting　compiler　can　be　used　as　a　basis　for　more　advanced　research　in　the　future.

TABLE　OF　CONTENTS　　　　　　　　　　　　　　　　　　　                viii
LIST　OF　TABLES　　　　　　　　　　　　　　　　　　　　　　                x
LIST　OF　FIGURES　　　　　　　　　　　　　　　　　　　　                 xii
Chapter　1　Introduction　　　　　　　　　　　　　　　　　　                1
1　FFT　Overview　　　　　　　　　　　　　　　　　　　　　                1
2　Motivation　　　　　　　　　　　　　　　　　　　　　　                 3
3　Organization　of　this　Thesis　　　　　　　　　　　　                 5
Chapter　2　FFT Algorithm　　　　　　　　　　　　　　　　　                 6
1　General　Algorithm　　　　　　　　　　　　　　　　　　                 6
1.1　Decimation-In-Time　(DIT)　FFT　Algorithms　　　　　                 7
1.2　Decimation-In-Frequency　(DIF)　FFT Algorithms　　　                12
2　High-Radix　Algorithm　　　　　　　　　　　　　　　　                 18
2.1　Radix-4　DIF　FFT　Algorithm　　　　　　　　　　　　                18
2.2　Radix-8　DIF　FFT　Algorithm　　　　　　　　　　　　                21
3　Split-Radix　DIF　FFT　Algorithms　　　　　　　　　　                 25
3.1　Raidx-2/4　DIF　FFT　Algorithm　　　　　　　　　　　                26
3.2　Radix-2/8　DIF　FFT　Algorithm　　　　　　　　　　　                28
4　Complexity　Analysis　　　　　　　　　　　　　　　　　                32
Chapter　3　FFT/IFFT　Architecture　　　　　　　　　　　　                 38
1　Pipelined　FFT　Architecture　　　　　　　　　　　　　                39
1.1　Radix-2　Single-path　Delay　Feedback　(R2SDF)　　　                42
1.2　Radix-2　Multi-path　Delay　Commutator　(R2MDC)　　                 47
2　Memory-Based　FFT　Architecture　　　　　　　　　　　                 53
2.1　Ping-Pong　Mode　of　the　Memory　Management　Strategy　            55
2.2　In-Place　Mode　of　the　Memory　Management　Strategy　             56
3　A　Unified　FFT/IFFT　Architecture　　　　　　　　　　　	            58
Chapter　4　FFT/IFFT　Compiler　Design	　　　　　　　　　             60
1　Implementation　Strategy　　　　　　　　　　　　　　　　　            61
1.1　Parametrizable　Architecture　　　　　　　　　　　　　　            61
1.2　Parametrizable　Memory　Access　　　　　　　　　　　　　            65
2　Building　Block　　　　　　　　　　　　　　　　　　　　　             68
3　FFT/IFFT　Compiler　Flow　　　　　　　　　　　　　　　　　            72
4　Specification　　　　　　　　　　　　　　　　　　　　　　             74
4.1　Specification　of　the　128-Point　R23SDF　　　　　　　             74
4.2　Specification　of　the　128-Point　R23MDC　　　　　　　             77
4.3　Specification　of　the　128-Point　Memory-Based　FFT　Architecture　80
4.4　Synthesis Result　　　　　　　　　　　　　　　　　　　　　　　　　　82
4.5　Analysis　of　Suitable　Applications　　　　　　　　　　　　　　　　85
Chapter　5　Verification　and　Performance　　　　　　　　　　　　　　　　 88
1　Cost　Function　and　Derivation　　　　　　　　　　　　　　　　　　　 88
2　C　Simulation　Model　　　　　　　　　　　　　　　　　　　　　　　　　89
3　Verification　Plan　　　　　　　　　　　　　　　　　　　　　　　　　　90
4　Performance　Evaluation　　　　　　　　　　　　　　　　　　　　　　　 91
Chapter　6　Conclusions　and　Future Work　　　　　　　　　　　　　　　　　93
1　Conclusions　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 93
2　Future　Work　　　　　　　　　　　　　　　　　　　　　　　　　　　　　93
References　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 96
                                    

[1]　J.　W.　Cooley　and　J.　W.　Tukey,　“An　algorithm　for　the　machine　calculation　of　complex　Fourier　series,”　Math.　Comput.,　vol.　5,　no.　5,　pp.　87–109,　1965.
[2]　S.　Bouguezel,　M.O.　Ahmad　and　M.N.S.　Swamy,　“Improved　radix-4　and　radix-8　FFT　algorithms,”　IEEE　Transactions　on　Digital　Object　Identifier　vol.　3,　pp.　561–564,　May　2004.
[3]　A.V.　Oppenheim,　R.W.　Schafer　and　John　R.　Buck,　“Discrete-time　signal　processing,”　Prentice-Hill,　Second　Edition,　1999.
[4]　Pierre　Duharnel　and　H.　Hollmann,　“Split　radix　FFT　algorithm,”　Electron.　Lett.,　vol.　20,　no.　1,　pp.　14–16,　Jan.　5,　1984.
[5]　D.　Takahashi,　“An　extended　split-radix　FFT　algorithm,”　IEEE　Signal　Processing　Letters,　vol.　8,　no.　5,　pp.　145–147,　May　2001.
[6]　L.　Jia,　Y.　Gao,　J.　Isoaho,　and　H.　Tenhunen,　“A　new　VLSI-oriented　FFT　algorithm　and　implementation,”　Proc.　Eleventh　Annu.　IEEE　Int.　ASIC　Conf.,　pp.　337–341,　1998.
[7]　S.　Bouguezel,　M.O.　Ahmad,　and　M.N.S.　Swamy,　“Arithmetic　complexity　of　the　split-radix　FFT　algorithms,”　Proc.　International　Conference　on　Acoustics,　Speech,　and　Signal　Processing,　2005　(ICASSP　'05),　vol.　5,　pp.　V/137–V/140,　March.　18-23,　2005.
[8]　L.R.　Rabiner　and　B.　Gold,　“Theory　and　application　of　digital　signal　processing,”　Prentice-Hill,　Inc.,　1975.
[9]　E.H.　Wold　and　A.M.　Despain,　“Pipeline　and　parallel　pipeline　FFT　processors　for　VLSI　implementation,”　IEEE　Trans.　Comput.,　vol.　C-33,　pp.　414–426,　May　1984.
[10]　A.M.　Despain,　“Fourier　transform　computer　using　CORDIC　iterations,”　IEEE　Trans.　Comput.,　vol.　C-23,　pp.　993–1001,　Oct.　1974.
[11]　G.　Bi　and　E.V.　Jones,　“A　pipelined　FFT　processor　for　word-sequential　data,”　IEEE　Trans.　Acoust.,　Speech,　Signal　Processing,　vol.　37,　pp.　1982–1985,　Dec.　1989.
[12]　S.　He　and　M.　Torkelson,　“A　new　approach　to　pipeline　FFT　processor,”　Proc.　The　10th　International　Parallel　Processing　Symposium.　pp.　766–770,　April　1996.
[13]　S.　He　and　M.　Torkelson,　“Designing　pipeline　FFT　processor　for　OFDM　(de)　modulation,”　1998　URSI　International　Symposium　on　Signals,　Systems,　and　Electronics,　1998　(ISSSE　98),　pp.　257–262,　1998.
[14]　W.-C.　Yeh　and　C.-W.　Jen,　“High-speed　and　low-power　split-radix　FFT,”　IEEE　Transactions　on　Signal　Processing,　vol.　51,　no.　3,　pp.　864–874,　March　2003.
[15]　J.　García,　J.　A.　Michell,　and　A.　M.　Burón,　“VLSI　configurable　delay　commutator　for　a　pipeline　split　radix　FFT　architecture,”　IEEE　Trans.　Signal　Processing,　vol.　47,　pp.　3098–3107,　Nov.　1999.
[16]　E.E.　Swartzlander,　W.K.W.　Young,　and　S.J.　Joseph,　“A　radix-4　delay　commutator　for　fast　Fourier　transform　processor　implementation,”　　　　　　　　　　IEEE　Journal　of　Solid-State　Circuits,　vol.　19,　Issue　5,　pp.　702–709,　Oct　1984.
[17]　C.C.W.　Hui,　T.J.　Ding,　and　J.V.　McCanny,　“A　64-point　Fourier　transform　chip　for　video　motion　compensation　using　phase　correlation,”　IEEE　Journal　of　Solid-State　Circuits,　vol.　31,　Issue　11,　pp.　1751–1761,　Nov.　1996.
[18]　Y.N.　Chang　and　K.K.　Parhi,　“An　efficient　pipelined　FFT　architecture,”　IEEE　Transactions　on　Circuits　and　Systems　II:　Analog　and　Digital　Signal　Processing,　vol.　50,　Issue　6　pp.　322–325,　June　2003.
[19]　C.　Ediz,　M.　Richard,　and　C.S.　Kale,　“A　integrated　256-point　complex　FFT　processor　for　real-time　spectrum　analysis　and　measurement,”　Proc.　IEEE　Instrumentation　and　Measurement　Technology　Conference,　pp.　96–101,　1997
[20]　J.A.　Hidalgo,　J.　Lopez,　F.　Arguello,　and　E.L.　Zapata,　“Area-efficient　architecture　for　fast　Fourier　transform,”　IEEE　Transactions　on　Circuits　and　Systems　II:　Analog　and　Digital　Signal　Processing,　vol.　46,　Issue　2,　pp.　187–193,　Feb.　1999
[21]　L.G.　Johnson,　“Conflict　free　memory　addressing　for　dedicated　FFT　hardware,”　IEEE　Trans.　Circuits　and　Systems　–　II:　Analog　and　Digital　Signal　Processing,　vol.　39,　no.　5,　pp.　312–316,　May　1992.
[22]　H.F.　Lo,　M.D.　Shieh,　C.M.　Wu,　“In-place　memory　addressing　of　FFT　hardware　implementation　for　DAB　system,”　Proc.　11th　VLSI　Design/CAD　Symposium,　Taiwan,　pp.　315–318,　August　2000.
[23]　M.M.　Jamali,　S.C.　Kwatra　and　D.H.　Shetty,　“Module　generation　based　VLSI　implementation　of　a　demultiplexer　for　satellite　communications,”　Proc.　IEEE　International　Symposium　on　Circuits　and　Systems,　vol.　4,　pp.　364–367,　1996.
[24]　A.　Delaruelle,　J.　Huisken,　J.V.　Loo　and　F.　Welten,　“A　channel　demodulator　IC　for　digital　audio　broadcasting,”　Proc.　IEEE　Custom　Integrated　Circuits　Conference,　pp.　47–50,　1994.
[25]　Z.　Guoping　and　F.　Chen,　“Parallel　FFT　with　CORDIC　for　ultra　wide　band,”　Proc.　15th　IEEE　International　Symposium　on　Personal,　Indoor　and　Mobile　Radio　Communications　(PIMRC　2004),　vol.　2,　5-8　pp.　1173–1177,　Sept.　2004.
[26]　C.　Shuni　and　C.　Burrus,　“A　prime　factor　FTT　algorithm　using　distributed　arithmetic,”　IEEE　Transactions　on　Acoustics,　Speech,　and　Signal　Processing,　vol.　30,　no.　2,　pp.　217–227,　Apr　1982.

校內：2009-07-31公開
校外：2009-07-31公開

簡易檢索 / 詳目顯示

相關論文