畢業(yè)設計（論文）基于fpga的fft算法設計與實現(xiàn)

1、<p>　　南京郵電大學通達學院</p><p>　　畢 業(yè) 設 計（論 文）</p><p>　　日期： 年 月 日至 年 月 日</p><p>　題 目基于FPGA的FFT算法設計與實現(xiàn)</p><p>　專 業(yè)通信工程</p><p>　學生姓名</p&

2、gt;<p>　班級學號</p><p>　指導教師</p><p>　指導單位通信與信息工程學院</p><p><b>　　摘 要</b></p><p>　　隨著科學技術的飛速發(fā)展，數(shù)字信號處理技術已廣泛應用于通信，衛(wèi)星定位，圖像處理等多個領域。快速傅里葉變換（FFT）作為離散傅里葉變換（DFT）的

3、一種快速算法，它是以DFT為基礎的，并且使DFT的運算時間縮短了幾個數(shù)量級，使得數(shù)字信號處理的實現(xiàn)和運用變得更加的容易。現(xiàn)場可編程門陣列是近年來出現(xiàn)的一種新的可編程邏輯器件，它具有運行速度快，儲存容量大，管腳多等特點。</p><p>　　本文主要研究如何利用FPGA實現(xiàn)FFT處理器,包括算法背景介紹、算法研究、系統(tǒng)結(jié)構(gòu)及各個模塊設計、FPGA實現(xiàn)和測試。設計采用基-2按時間抽取算法,利用Verilog HDL描

4、述的方式對FFT系統(tǒng)進行了設計、仿真、測試等工作。仿真結(jié)果表明其計算結(jié)果達到了一定的精度,運算速度可以滿足一般實時信號處理的要求。</p><p>　　關鍵詞：現(xiàn)場可編程門陣列，快速傅里葉變換，Verilog HDL，蝶形算法</p><p><b>　　ABSTRACT</b></p><p>　　With the rapid develop

5、ment of science and technology, digital signal processing technology has been widely used in communications, satellite positioning, image processing and other fields. Fast Fourier transform (FFT) as a fast algorithm of d

6、iscrete Fourier transform (DFT) which is based on DFT, shortens the operation time of DFT for several orders of magnitude and makes the implementation and use of digital signal processing more easily. Field programmable

7、gate array (fpga) is a new kind of pro</p><p>　　This paper, including four parts of background introduction, algorithm research, system structure and design of each module, and the implementation and testing

8、 of FPGA, mainly studies how to use FPGA to realize the FFT processor. Moreover, this design applies the radix-2 decimation in time algorithm and utilizes the way of Verilog HDL description to design, simulate and test F

9、FT system. The simulation result shows that if the calculation result can achieve a certain accuracy, the arithmetic spee</p><p>　　Keywords: Field Programmable Gate Array, Fast Fourier Transform, Verilog HDL

10、, Butterfly Algorithm</p><p><b>　　目 錄</b></p><p>　　第一章 緒論...............................................................................................1</p><p>　　1.1課

11、題研究背景及意義.............................................................................................1</p><p>　　1.2 FFT算法的發(fā)展現(xiàn)狀.................................................................................

12、..1</p><p>　　1.3 FFT處理器的發(fā)展現(xiàn)狀...............................................................................2</p><p>　　1.4 FPGA實現(xiàn)FFT的優(yōu)越性...........................................................

13、..........................2</p><p>　　1.5本文研究的主要內(nèi)容及主要工作..........................................................................3</p><p>　　FFT算法研究和FPGA技術.........................................

14、...............4</p><p>　　2.1 FFT算法基本原理.................................................................................................4</p><p>　　2.2現(xiàn)場可編程門陣列FPGA技術..............................

15、...............................................6</p><p>　　2.2.1 FPGA器件簡介................................................................................................6</p><p>　　2.2.2 FPGA的原理及優(yōu)

16、點........................................................................................6</p><p>　　2.2.3 FPGA的基本結(jié)構(gòu)............................................................................................

17、7</p><p>　　FFT算法設計與硬件實現(xiàn)結(jié)構(gòu)....................................................8</p><p>　　3.1基于FPGA的系統(tǒng)的開發(fā)......................................................................................8<

18、/p><p>　　3.2硬件描述語言Verilog HDL....................................................................................9</p><p>　　3.3 FFT的硬件實現(xiàn)結(jié)構(gòu)...........................................................

19、.................................10</p><p>　　3.4 提高FFT運算速度和精度的方法......................................................................11</p><p>　　3.4.1 提高FFT處理速度的方法..............................

20、.............................................11</p><p>　　3.4.2 FFT運算精度提高的方法.............................................................................11</p><p>　　FFT處理器的設計與實現(xiàn)..................

21、........................................13</p><p>　　4.1 FFT處理器的設計結(jié)構(gòu)與工作過程....................................................................13</p><p>　　4.2 蝶形運算的設計與實現(xiàn)............................

22、..........................................................14</p><p>　　4.2.1 乘法器設計...................................................................................................14</p><p>　　4.

23、2.2 蝶形運算單元設計.......................................................................................15</p><p>　　4.2.3 蝶形運算單元實現(xiàn)..................................................................................

24、.....15</p><p>　　4.3 塊浮點單元的結(jié)構(gòu)原理和實現(xiàn)..........................................................................16</p><p>　　4.3.1 塊浮點的結(jié)構(gòu)實現(xiàn)............................................................

25、...........................16</p><p>　　4.3.2 運算誤差的分析...........................................................................................17</p><p>　　4.4 地址產(chǎn)生單元設計...........................

26、...................................................................18</p><p>　　4.4.1 蝶形運算數(shù)據(jù)的地址設計...........................................................................18</p><p>　　4.4.2 倒序輸出地

27、址設計.......................................................................................19</p><p>　　4.5 輸入與輸出的RAM模塊設計............................................................................20</p>

28、<p>　　4.6 蝶形運算的數(shù)據(jù)切換模塊的設計......................................................................21</p><p>　　4.7 旋轉(zhuǎn)因子的ROM模塊設計..............................................................................

29、.22</p><p>　　4.7.1 旋轉(zhuǎn)因子的計算...........................................................................................22</p><p>　　4.7.2 ROM設計 .....................................................

30、................................................22</p><p>　　4.7.3 減少旋轉(zhuǎn)因子的讀取操作...........................................................................22</p><p>　　4.8 時序控制單元設計..................

31、............................................................................23</p><p>　　4.9 數(shù)字時鐘管理器的設計......................................................................................24</p><p

32、>　　4.10 FFT的系統(tǒng)實現(xiàn)..................................................................................................24</p><p>　　4.11 快速傅里葉變換（FFT）和逆變換的實現(xiàn)......................................................

33、25</p><p>　　FFT系統(tǒng)的聯(lián)合仿真..................................................................28</p><p>　　5.1 FFT系統(tǒng)的性能分析................................................................................

34、............28</p><p>　　5.1.1 系統(tǒng)的資源利用情況...................................................................................28</p><p>　　5.1.2 系統(tǒng)的速度運行情況.............................................

35、......................................28</p><p>　　5.2 FPGA聯(lián)合仿真驗證.............................................................................................29</p><p>　　5.3 仿真測試結(jié)果及分析............

36、..............................................................................29</p><p>　　結(jié)束語.........................................................................................................32</p&

37、gt;<p>　　致謝.............................................................................................................33</p><p>　　參考文獻................................................................

38、.....................................34</p><p><b>　　第一章 緒論</b></p><p>　　1.1 課題研究背景及意義</p><p>　　隨著數(shù)字技術、電子集成電路技術等各方面技術的全面發(fā)展，數(shù)字信號處理技術已深入到各個科學領域并得到廣泛的運用，將信號處理的發(fā)展發(fā)展到了一個新的高度

39、。但是數(shù)字信號處理基本上是運用時域和頻域兩種方法來解決信號處理的問題，時域方法即為數(shù)字濾波，而頻域方法即為頻域分析，他們同時處理的任務可分為三類：變換、卷積和相關。</p><p>　　其中，DFT的快速算法快速傅里葉變換（FFT）就變成了數(shù)字信號處理的最基本的技術之一，它通過將長序列的DFT分解為多個短序列的DFT進行計算，從而可以使運算量大大減少，并且把DFT的運算速度提升了1~2個數(shù)量級，使得數(shù)字信號處理技

40、術在應用于各種信號的實時處理時變得更加的效率。因此，對FFT及其實現(xiàn)方式的研究很有意義。目前，F(xiàn)FT已廣泛運用在圖像處理、語音識別、雷達處理、遙感遙測、數(shù)字通信、頻譜分析等眾多領域，在不通的應用場合中，需要不同性能要求的FFT處理器。在很多應用領域都要求FFT處理器具有高精度、高速度、容量大和實時處理的性能。因此，使FFT變得更迅捷、更靈活也變得越來越重要。</p><p>　　近年來，現(xiàn)場可編程門列陣（FPGA

41、）以其高性能、高靈活性、友好的開發(fā)環(huán)境、在線可編程等特點，使得基于FPGA的設計可以實時滿足數(shù)字信號處理的要求，在市場競爭中具有很大的優(yōu)勢。這也使得采用并行度更大、速度更快的FPGA芯片來實現(xiàn)FFT成為了必然趨勢。因此，自主研發(fā)基于FPGA芯片的FFT，把FFT實時性的要求和FPGA芯片設計的靈活性集合起來，實現(xiàn)并行算法與硬件結(jié)構(gòu)的優(yōu)化配置，提高FFT的處理速度，使其滿足現(xiàn)代信號處理的高速度、高可靠性的要求，成為了現(xiàn)如今我國數(shù)字信號處理

42、的一個研究點。鑒于這種趨勢，作者將給予FPGA的FFT設計與實現(xiàn)作為研究課題進行研究[1]。</p><p>　　1.2 FFT算法的發(fā)展現(xiàn)狀</p><p>　　快速傅里葉變換（FFT）作為離散傅里葉變換（DFT）的一種快速算法，他并不是一種新的變換。由于直接計算DFT時，DFT的計算量和變換區(qū)間長度N的平方成正比，因此當N較大時，計算量也會變得很大，所以在FFT出現(xiàn)之前，直接用DFT算

43、法進行實時處理是很不切實際的。直到1965年美國庫利（J. W. Cooley）和圖基（J. W. Tukey）提出FFT快速算法，這種情況才得到了相應的解決，自算法突出到現(xiàn)在也已有四十多年的歷史，F(xiàn)FT已有了多種算法，其算法理論也已經(jīng)非常成熟。從FFT算法理論的發(fā)展上看，主要有兩個方向[2]：</p><p>　　組合數(shù)FFT算法，針對FFT變換點數(shù)N等于2的整數(shù)次冪，如基-2算法、基-4算法、基-8算法、實因

44、子算法、分裂基算法及任何組合因子算法，利用系數(shù)的周期性和對稱性，使長序列的DFT分解成更小點數(shù)的DFT，從而大大減少了運算的工作量。</p><p>　　（2）N不等于2的整數(shù)次冪的算法，以維諾格蘭德（S. Winograd）為代表一類傅里葉變換算法，利用下標映射和數(shù)論以及近代數(shù)學的只是，去掉級間的旋轉(zhuǎn)因子，從而減少運算量。</p><p>　　1.3 FFT處理器的發(fā)展現(xiàn)狀</p&

45、gt;<p>　　FFT處理器是FFT算法的硬件實現(xiàn)，針對其硬件實現(xiàn)方案，主要有三種途徑：</p><p>　　（1）利用通用數(shù)字信號處理芯片來實現(xiàn)（DSP處理器）</p><p>　　針對一般數(shù)字信號處理算法的實現(xiàn)，采用通過可編程硬件處理器技術來實現(xiàn)FFT。這種方法具有軟件設計的多用性的優(yōu)點，能夠適用于各種需要FFT運算來進行信號處理的應用場合，靈活方便。但是，通用DSP處

46、理器構(gòu)成的FFT處理機采用循環(huán)編碼算法，程序量小，但存在大量的冗余運算，，需要許多的跳轉(zhuǎn)操作，處理速度較慢，因此難以滿足現(xiàn)代數(shù)字信號處理高速、實時性和大規(guī)模的要求[3]。</p><p>　　（2）利用專用的FFT芯片或用戶定制的專用的集成電路來實現(xiàn)（ASIC）</p><p>　　針對FFT的特有算法，用專用的硬件組成專用的FFT芯片來實現(xiàn)FFT。ASIC在一些特殊功能上表現(xiàn)的相當好，這

47、種實現(xiàn)方式速度快，可靠性高，非常符合實時處理和可靠性要求高的信號處理系統(tǒng)，但專用的FFT芯片不能重新組態(tài)，且可編程能力有限。</p><p>　　（3）利用可編程邏輯器件來實現(xiàn)（以FPGA為代表）</p><p>　　隨著FPGA技術的全面普及，以及FFT算法在各個科學領域的廣泛應用，使用FPGA芯片設計FFT算法正在世界范圍內(nèi)興起。FPGA芯片具有在線可編程能力、硬件結(jié)構(gòu)可重構(gòu)的特點，適

48、合于算法固定、運算量大的數(shù)字信號處理。新近推出的FPGA產(chǎn)品都可采用多層布線結(jié)構(gòu)，更低的核心電壓，更豐富的輸入\輸出管腳，更大容量的邏輯單元，內(nèi)置嵌入式RAM資源，內(nèi)部集成多個數(shù)字鎖相環(huán)，嵌入多個硬件乘法器，所有的這些特點都使得FPGA在數(shù)字信號處理領域中顯示出自己獨有的優(yōu)勢。</p><p>　　因此，利用FPGA來實現(xiàn)FFT變得更有意義。</p><p>　　1.4 FPGA實現(xiàn)FFT

49、的優(yōu)越性</p><p>　　由于成本、系統(tǒng)功耗和面市時間等各種原因，許多視頻、通訊和圖像系統(tǒng)已無法簡單的利用DSP處理器來實現(xiàn)，基于FPGA的信號處理器已廣泛應用于各種信號處理領域。FPGA所固有的靈活性和性能可以讓設計者緊跟新時代、新標準的變化，并且能提供可行的方法來滿足不斷變化的要求。</p><p>　　與DSP相比，F(xiàn)PGA實現(xiàn)FFT的主要優(yōu)越性有：</p><

50、;p>　?。?）利用FPGA實現(xiàn)數(shù)字信號處理最顯著的特點就是高速性能好。FPGA有內(nèi)置的高速乘法和加法器，尤其適用于乘法和累加等重復性的DSP任務。</p><p>　　（2）FPGA的儲存量大。目前，高檔的FPGA中有大量的高速存儲器，不需要外接存儲器便可以實現(xiàn)FFT的實時處理運算，其速度更快，電路也更簡單穩(wěn)定，集成度和可靠性野大幅提高[4]。</p><p>　?。?）FPGA是

51、硬件可編程的，因此也比DSP更加靈活。DSP往往需要外部的接口和控制芯片配合工作，F(xiàn)PGA則不需要，這樣使得硬件更簡單和小型化。</p><p>　?。?）在對FPGA和DSP進行比較時，一個及其重要的系統(tǒng)參數(shù)是輸入\輸出帶寬。除了一些專用引腳外，F(xiàn)PGA上幾乎所有的引腳均可供用戶使用，這使得FPGA信號處理方案具有非常高性能的輸入\輸出帶寬。大量的輸入\輸出引腳和多塊存儲器可讓系統(tǒng)在設計中獲得優(yōu)越的并行處理性能

52、。</p><p>　　1.5本文研究的主要內(nèi)容及主要工作</p><p>　　本文主要針對基-2順序處理的FFT處理器的FPGA實現(xiàn)進行了研究,涉及算法</p><p>　　選取、處理器結(jié)構(gòu)設計、系統(tǒng)仿真、FPGA實現(xiàn)和系統(tǒng)測試。本論文共5章,各章的</p><p><b>　　具體內(nèi)容如下:</b></p>

53、;<p>　　第1章闡述了FFT的發(fā)展現(xiàn)狀及選題的意義和論文內(nèi)容。</p><p>　　第2章主要討論了FFT算法的基本原理、FPGA技術和FPGA主要結(jié)構(gòu)的相關內(nèi)容。</p><p>　　第3章探討了硬件描述語言Verilog HDL和FFT處理器的硬件實現(xiàn)結(jié)構(gòu),并在處理速度、硬件消耗和精度方面提出了優(yōu)化措施。</p><p>　　第4章闡述了應用F

54、PGA實現(xiàn)FFT的具體設計,包括蝶形運算單元設計、塊浮</p><p>　　點單元設計、地址產(chǎn)生單元設計、輸入與輸出RAM模塊設計、蝶形運算數(shù)據(jù)功數(shù)據(jù)切換模塊設計、旋轉(zhuǎn)因子的ROM模塊設計、減少ROM讀取操作設計、時序控制單元設計和數(shù)字時鐘管理器的設計。最后設計出512點數(shù)復數(shù)的FFT處理系統(tǒng)。</p><p>　　第5章介紹了FFT系統(tǒng)的仿真測試,給出了反映對芯片資源利用情況的實現(xiàn)報&l

55、t;/p><p>　　告。對信號進行測試并與MATLAB計算的理論結(jié)果進行了比較。</p><p>　　最后對整篇論文進行了總結(jié)和討論。</p><p>　　第二章 FFT算法研究和FPGA技術 </p><p>　　2.1 FFT算法基本原理</p><p>　　有限長序列{x（n）}及其頻域表示{X（k）}可由以

56、下離散傅里葉變換得出：</p><p>　　， （0≤k≤N-1） （2.1.1）</p><p>　　（0≤n≤N-1） （2.1.2）</p><p>　　其中，。式（2.1.1）成為離散傅里葉正變換，式（2.1.2）成為離散傅里葉反變換，x（n）與X(k)構(gòu)成了離散傅里葉變換對。</p>

57、<p>　　為減少運算量，提高運算速度，就必須改進算法。計算DFT過程中需要完成的運算的系數(shù)里，存在相當多的對稱性。通過研究這種對稱性，可以簡化計算過程中的運算，從而減少計算DFT的時間。</p><p><b>　　具有以下固有特性：</b></p><p>　　的周期性： (2.1.3)</p&g

58、t;<p>　　的對稱性： (2.1.4) </p><p>　　的可約性： (2.1.5)</p><p><b>　　另外，。</b></p><p>　　利用的上述特性，將x（n）或X（k）序列按一定規(guī)律分解成短序列進行運算，這樣

59、可以避免大量的重復運算，提高計算DFT的運算速度。算法形式有很多種，但基本上可以分為兩大類，即按時間抽?。―ecimation In Time，DIT）FFT算法和按頻率抽?。―ecimation In Frequency，DIF）FFT算法。本文選用按時間抽?。―IT）的基-2FFT算法。</p><p>　　先設序列點數(shù)為N=2L，L為整數(shù)。如果不滿足這個條件，可以人為地加上若干個零值點，使之達到這一要求，這

60、種N為2的整數(shù)冪的FFT也稱基-2 FFT。</p><p>　　式（2.1.1）中，采用基-2按時域抽選（DIT）分解辦法，在時域上按照奇偶關系的抽選分解可以得到：</p><p><b>　?。?.1.6）</b></p><p><b>　　令，則：</b></p><p><b>

61、　?。?.1.7）</b></p><p><b>　　再令，則：</b></p><p><b>　?。?.1.8）</b></p><p><b>　?。?.1.9）</b></p><p>　　根據(jù)基-2 分解方法，運用數(shù)值的計算方法表示的蝶形運算公式如下：&

62、lt;/p><p><b>　?。?.1.10）</b></p><p><b>　　（2.1.11）</b></p><p>　　以上兩式中物理意義為：l為級數(shù)表示運算到第幾級；m為分組數(shù)表示每一級內(nèi)運算到了第幾組；k為每組內(nèi)的運算次數(shù)。由此得到16點時域抽取FFT運算流圖如圖所示[5]：</p><p&

63、gt;　　圖2.1 16點DIT-FFT運算流程圖</p><p>　　從按時間抽選法FFT的流圖可見，當時，共有L級蝶形，每級都有個蝶形運算，每個蝶形有一次復乘、二次復加，因而每級運算都需次復乘和N次復加，這樣L級運算總共需要</p><p>　　復乘數(shù) （2.1.12）</p><p>　　復加

64、數(shù) （2.1.13） </p><p>　　可見，直接DFT復數(shù)乘法次數(shù)是，F(xiàn)FT復數(shù)乘法次數(shù)。直接計算DFT與FFT算法的計算量之比為</p><p><b>　　（2.1.14）</b></p><p>　　2.2 現(xiàn)場可編程門陣列FPGA技術</p>&

65、lt;p>　　2.2.1 FPGA器件簡介</p><p>　　隨著半導體技術的飛躍發(fā)展，數(shù)字系統(tǒng)應用基本經(jīng)歷了分立元件、小規(guī)模集成電路（SSI）、中規(guī)模集成電路（MSI）和大規(guī)模集成電路（LSI）乃至超大規(guī)模集成電路（VLSI）的應用過程。數(shù)字系統(tǒng)應用的基本特征乃由中小規(guī)模集成度的標準通用集成電路、向用戶定制的專用集成電路（ASIC）過渡。特別對于現(xiàn)代較復雜的數(shù)字系統(tǒng)，若采用SSI/MSI器件來設計某個特

66、定的用，不僅要占用很大的物理空間，反而功耗較大，可靠性差；而采用LSI/VLSI器件的專用電路設計，則具有相當高的系統(tǒng)集成度和相對小的功耗，但其開發(fā)周期長，開發(fā)費用高，具有較大的投資風險性，且有時仍需SSI/MSI器件來設計實現(xiàn)相應的接口邏輯。80年代出現(xiàn)的可編程邏輯器件（PLD-Programmable Logic Devices），在一定的程度上，為數(shù)字系統(tǒng)技術工程師的快捷、靈活設計提供了可能性，PLD器件的應用，使一系列功能強、速

67、度高、靈活性大的積木式系統(tǒng)設計得以成功[6]。</p><p>　　隨著現(xiàn)代數(shù)字系統(tǒng)設計的發(fā)展，PLD器件無論在集成容量，功耗，速度乃至邏輯設計的靈活性上、均不能滿足現(xiàn)代數(shù)字系統(tǒng)的大容量、高速度、現(xiàn)場靈活編程設計的要求?，F(xiàn)場可編程門陣列器件的產(chǎn)生正是由此而來，起源于美國Xilinx公司的創(chuàng)造，它的英文是Field Programmable Gate Array，簡寫為FPGA。它是在PAL、GAL、EPLD等可編

68、程器件的基礎上進一步發(fā)展的產(chǎn)物，從而顯示了誘人的應用前景。同時，F(xiàn)PGA即現(xiàn)場可編程門陣列，F(xiàn)PGA作為ASIC領域中的一種半定制電路，既解決了定制電路的不足，又克服了原有可編程器件門電路數(shù)有限的缺點。</p><p>　　2.2.2 FPGA的原理及優(yōu)點</p><p>　　FPGA運用了邏輯單元陣列LCA（Logic Cell Array）這個概念，其中包括可配置邏輯模塊 CLB（Co

69、nfigurable Logic Block）、輸入輸出模塊IOB（Input Output Block）和內(nèi)部連線（Interconnect）三個部分。工作時，首先將配置數(shù)據(jù)放于熔絲上或片內(nèi)SRAM上。基于STAM的FPGA器件，在器件工作之前先要將配置的數(shù)據(jù)從芯片外部加載，在芯片外部的EPROM或者其他存儲體上可以將配置數(shù)據(jù)進行存儲。用戶可以自行的對加載過程給予控制，同時對器件的邏輯功能進行現(xiàn)場的修改，這就是所謂的現(xiàn)場編程[1,7]

70、。</p><p>　　FPGA芯片從某種角度來看可以說是一種特殊的ASIC芯片，它除了具有ASIC的特點之外，還具備了以下優(yōu)點[1,8]。</p><p>　?。?）采用FPGA設計ASIC電路，用戶不用投片，就可以得到可用的芯片。</p><p>　?。?）FPGA可用作其他全定制或半定制ASIC電路中的試樣片。</p><p>　?。?

71、）FPGA內(nèi)部具有豐富的觸發(fā)器和輸入\輸出引腳資源。</p><p>　?。?）FPGA是ASIC中設計周期最短、開發(fā)費用最低、風險最低的器件之一。</p><p>　?。?）FPGA采用高速CHMOS工藝，功耗低，可與CMOSTTL電平兼容。</p><p>　?。?）用戶可以反復的進行編程、擦出、使用，或者在外圍電路不變的情況下用不同的軟件來實現(xiàn)不同的功能。&l

72、t;/p><p>　　2.2.3 FPGA的基本結(jié)構(gòu)</p><p>　　FPGA采用了邏輯單元陣列LCA（Logic Cell Array）這樣一種新概念，內(nèi)部通常是由可配置邏輯模塊CLB（Configurable Logic Block）、可編程輸入\輸出模塊IOB（Input/Output Block）和互連資源ICR（Interconnect Capital Resource）及一個用

73、于存放編程數(shù)據(jù)的靜態(tài)存儲器SRAM（Static Random Access Memory）組成[9]。</p><p>　　（1）CLB是實現(xiàn)用戶功能的基本單元，打個邏輯塊通常規(guī)則的排成一個陣列結(jié)構(gòu)，分布于整個芯片。</p><p>　?。?）IOB連接芯片內(nèi)部邏輯與外部管腳之間的接口，圍繞在邏輯單元陣列的四周。</p><p>　?。?）ICR包括這種長度的連線

74、線段和一些可編程連接的開關，它們將各個CLB或IOB連接起來，構(gòu)成特定功能的電路。</p><p>　?。?）SRAM型FPGA的比較突出的優(yōu)點是可以反復編程。</p><p>　　隨著制作工藝的進步和應用系統(tǒng)需求的發(fā)展，F(xiàn)PGA除了上述基本結(jié)構(gòu)的四中資源外，一般還可能包含以下可選資源：存儲器資源（塊RAM、分布式RAM、ROM）；數(shù)字時鐘管理單元（分頻/倍頻、數(shù)字延遲、時鐘鎖定）；算術運

75、算單元（高速硬件乘法器、乘加器）；多電平標準兼容高速串行的I/O接口；特殊功能模塊（以太網(wǎng)等硬IP核）；微處理器（PowerPC405等硬處理器IP核）。</p><p>　　第三章 FFT的算法設計與硬件實現(xiàn)結(jié)構(gòu)</p><p>　　3.1 基于FPGA的系統(tǒng)的開發(fā)</p><p>　　FPGA的設計步驟主要包括系統(tǒng)功能的設計定義、設計輸入、功能仿真、邏輯綜

76、合、前仿真、設計實現(xiàn)（包括翻譯、映射、布局布線）、時序仿真與驗證、下載配置與期間編程、測試驗證等幾個主要的步驟。</p><p>　　其主要的設計流程圖如下[1,8]：</p><p>　　圖 3.1 FPGA 設計流程</p><p>　　圖中各步驟的簡要分析如下：</p><p>　　系統(tǒng)功能定義：在進行設計之前，應該對設計的整體有一個全

77、面的認識，分析項目完成的功能和總體方案以及對整個項目初步的規(guī)劃。</p><p>　　設計輸入：功能仿真沒有器件內(nèi)部邏輯單元和連線的實際延時信息，只是初步的對系統(tǒng)的邏輯功能進行驗證。</p><p>　　功能仿真：主要對FPGA的功能進行仿真。</p><p>　　邏輯綜合：將設計描述變換成滿足要求的電路設計方案，并產(chǎn)生網(wǎng)表，供布局布線所使用。</p>

78、<p>　　前仿真：是接近真實器件運行的仿真，在布局布線之后，提取有關的器件延時、連線延時等時序參數(shù)，在此基礎上進行的仿真。</p><p>　　設計實現(xiàn)：實現(xiàn)包括轉(zhuǎn)換、布局布線、映射、時間參數(shù)提取、配置，同事產(chǎn)生各種報告和文件。</p><p>　　后仿真：是接近真實器件運行的仿真，在布局布線之后，提取有關的器件延時、連線延時等時序參數(shù)，在此基礎上進行的仿真。</p&g

79、t;<p>　　靜態(tài)時序分析：分析時序關系，檢查和消除競爭毛線、并對器件的實際工作性能進行評估。</p><p>　　期間編程與測試：設計實現(xiàn)以后，創(chuàng)建FPGA的可識別相應文件，并且把編程的數(shù)據(jù)載入器件中。</p><p>　　不同的FPGA公司針對自己的產(chǎn)品的各種環(huán)節(jié)都會提供與之對應的EDA工具。通常是由FPGA的廠家體統(tǒng)自己高集成度的開發(fā)環(huán)境，如Xilinx的ISE開發(fā)平

80、臺和Altera的開發(fā)平臺Quartos II。為了使設計的效率提高，優(yōu)化設計的結(jié)果，各個廠家都提供了針對自己產(chǎn)品的配套專業(yè)軟件，加以配合FPGA/CPLD（Complex Programmable Logic Device）廠家提供的工具，使設計更加高效的運行。其中較為常用的方式為：專業(yè)的邏輯綜合與專業(yè)的邏輯仿真軟件一起聯(lián)合使用，結(jié)合集成的開發(fā)環(huán)境，進行各種EDA工具協(xié)同設計。本設計運用ISE和ModelSim與Matlab聯(lián)合仿真的

81、設計方法。</p><p>　　ISE的簡稱為集成綜合的環(huán)境，是Xilinx公司的配套設計軟件，這種工具可完成上述FPGA/CPLD的整個開發(fā)過程；ModelSim作為Verilog的仿真工具，由Modeltech公司研發(fā)，ModelSim作為一種很好的仿真軟件，強大的防震功能和有好的界面圖形化操作等是其特有的優(yōu)點；Matlab是Math Works公司強大的數(shù)值計算與分析軟件，目前Matlab在FPGA設計中的

82、應用主要分為三種形式：一種是利用Matlab來進行FPGA設計時的前期系統(tǒng)算法仿真，最后一種是利用Matlab軟件將系統(tǒng)級的FPGA設計模型轉(zhuǎn)換成硬件描述語言。</p><p>　　3.2 硬件描述語言Verilog HDL</p><p>　　HDL是硬件描述語言(Hardware Description Language)的縮寫，是一種用形式方法來描述數(shù)字電路和系統(tǒng)的語言。利用這種語言

83、，數(shù)字電路系統(tǒng)的設計可以從抽到具體逐層描述自己的設計思想，用一系列分層次的模塊來表示極其復雜的數(shù)字統(tǒng)。隨著EDA技術的發(fā)展，使用HDL設計FPGA已成為一種趨勢。</p><p>　　硬件描述語言Verilog HDL具有以下特點[8,10]。</p><p>　　支持多級建模方式。數(shù)字系統(tǒng)設計是一種分層的設計方式，即從系統(tǒng)的算法到行為的描述，從行為描述到寄存器（RTL）級描述，最后由RT

84、L級再到門級、甚至開關電路級的描述。Verilog支持幾乎所有的數(shù)字系統(tǒng)設計層次的建模，包括算法、行為級建模、寄存器傳輸（RTL）級建模、門級建模、開關級建模。其中各抽象級分別構(gòu)造不同的模型。</p><p>　　支持多種建模方式，Verilog支持行為功能建模方式、結(jié)構(gòu)建模方式、數(shù)據(jù)流建模方式。</p><p>　　Verilog語言是并發(fā)的，基具有在同一時刻執(zhí)行多任務的能力。</

85、p><p>　　Verilog語言有時序的概念。由于在硬件電路中從輸入到輸出總會有延遲的存在，Verilog通過建立時序這一概念，來敘述這些特征。</p><p>　　3.3 FFT的硬件實現(xiàn)結(jié)構(gòu)</p><p>　　選擇合適的系統(tǒng)結(jié)構(gòu)，是提高FFT處理器性能的關鍵。根據(jù)蝶形單元的不同，算法的FFT處理器的實現(xiàn)形式大致分為四種：順序處理形式、并行迭代處理形式、級聯(lián)處理形

86、式和陣列處理形式 [11]。</p><p><b>　　（1）順序處理形式</b></p><p>　　順序處理作為專用FFT處理器最基本的形式之一，蝶形運算單元通過控制器的指令，以及FFT信號的標準流圖，按照時間的順序逐個進行運算。即從第1級開始，從上至下依次進行，先算第1個蝶形結(jié)，再算第2個，第3個…直至第個蝶形結(jié)，就完成了第一級的運算，之后開始第2級，第3級，

87、…，第級，直至算完，總共需要計算個蝶形結(jié)。</p><p><b>　　（2）級聯(lián)處理方式</b></p><p>　　若將N點FFT的每一級（列）的個蝶形結(jié)用一個獨立運算單元來處理，就構(gòu)成級聯(lián)處理，也稱為流水線處理。流水線處理是把一個重復的過程分解為若干個子過程，每個子過程可以與其他子過程并行進行．對一個N點的FFT變換，每一級的次蝶形運算安排一個獨立的蝶形處理器按

88、順序完成，總共采用個蝶形運算單元同時進行工作。</p><p>　?。?）并行迭代的處理形式</p><p>　　并行迭代的處理形式是對一級中的個蝶形結(jié)用個蝶形運算單元進行并行運算。例如，對于N=16，采用8個蝶形運算單元，同時首先計算第一級的個蝶形結(jié)，再依次算第二級、第三級和第四級的8個蝶形結(jié)，也就是說，每一列中的運算并行的進行，一列迭代至另一列是按順序的，故名并行迭代運算。</p

89、><p>　?。?）把級聯(lián)處理形式和并行迭代的處理形式相結(jié)合起來，實現(xiàn)全并行工作采用的蝶形運算單元數(shù)為個，稱為陣列處理。</p><p>　　從空間復雜度和設備使用量上看，順序處理最小，流水線處理次之，并行迭代和陣列處理則設備量最大，成本最昂貴。從處理速度上看，順序處理最慢，流水線次之，并行迭代和陣列處理速度最快，可應用于實時性要求很高的場合(如雷達信號處理系統(tǒng))。綜上所述，處理速度的提高是以

90、設備量和成本的增加為代價的。因此，在具體設計中，必須綜合考慮和適當采用上述的各種形式的處理器，根據(jù)實際需求確定具體的實現(xiàn)方案，以取得“速度/成本”的最佳值。本設計采用最基本的順序處理方案來實現(xiàn)512點16位復數(shù)的FFT運算系統(tǒng)。</p><p>　　3.4 提高FFT運算速度和精度的方法</p><p>　　3.4.1 提高FFT處理速度的方法</p><p>　　

91、實現(xiàn)形式不同的FFT處理器具有不同的運算速度，提高運算的速度要以硬件量的付出作為代價，當輸入數(shù)據(jù)點數(shù)較多的時候更是如此。在對處理速度要求比較高的應用中，可以考慮通過提高并行度來獲取速度。主要的幾種方法如下[11,12]：</p><p>　　采用多個乘法器和加法器并行運算</p><p>　　基-2時間抽取FFT的蝶形運算可分解成4次實數(shù)乘法和6次實數(shù)加(減)法運算，共分3步完成。如果將4

92、個乘法器和6個加(減)法器集中在一個蝶形運算單元內(nèi)進行并行工作，這樣3個時鐘周期內(nèi)就可完成一次蝶形運算。</p><p>　?。?）流水線結(jié)構(gòu)的蝶形單元運算流程</p><p>　　按順序執(zhí)行蝶形運算的過程中，蝶形運算單元開始工作經(jīng)過三個步驟：遵循讀數(shù)、進行計算與輸出。在蝶形運算進行時，存儲器的狀態(tài)一直處在暫停狀態(tài)；反之，在存儲器讀取數(shù)據(jù)或者將運算結(jié)果存入其中時，蝶形運算單元中的加法器與乘

93、法器都相繼停止工作。由于處理結(jié)構(gòu)工作的效率較低，為了使運算時間進一步的減少，使處理速度提高，可以使加法器與乘法器等運算單元和存儲器在工作時處于“匹配”狀態(tài)。因此蝶形運算單元采用流水線（Pipeline）工作方式，使運算結(jié)果連續(xù)輸出。</p><p>　　（3）采用兩組雙口RAM乒乓結(jié)構(gòu)</p><p>　　RAM是存儲輸入數(shù)據(jù)及中間運算結(jié)果的單元。每個蝶形單元運算的輸入、輸出數(shù)據(jù)均要經(jīng)過R

94、AM的讀寫操作，因此，RAM的頻繁讀寫操作對FFT處理器影響很大。為了加快FFT的運算速度，需要構(gòu)造雙口RAM來加快數(shù)據(jù)傳輸?shù)耐掏铝俊Ｍ瑫r，兩組雙口RAM采用乒乓結(jié)構(gòu)。在計算的過程中，兩組RAM始終保持一組讀一組寫，同步進行。FPGA芯片內(nèi)部集成大量的RAM，ROM等存儲器結(jié)構(gòu)，這種內(nèi)置結(jié)構(gòu)速度比任何片外存儲器都要快，并且擴展容易；其次，不需要占用片外電路板面積，可提高系統(tǒng)的可靠性。</p><p><b&

95、gt;　?。?）采用高基結(jié)構(gòu)</b></p><p>　　在FFT算法中，除了采用最簡單最常用的基-2算法，還可以采用基-4、基-8、分裂基等算法。隨著基數(shù)的增大，對于點數(shù)相同的輸入序列，需要處理的級數(shù)減少，每次蝶形運算中同時處理的數(shù)據(jù)量增加，可以縮短系統(tǒng)運算時間。但是，這樣會導致蝶形運算單元的復雜程度增大，系統(tǒng)的運算量和存儲的設備量增大。因此，必須在性能和成本之間進行折中考慮。目前，使用最多的高基結(jié)

96、構(gòu)也只是基-4處理。</p><p>　　本文采用多個乘法器和加法器并行運算的結(jié)構(gòu)，只需設計一個乘法器和一個加法器，就可以組合成一個蝶形運算單元。沒有采用高基算法結(jié)構(gòu)，而是采用了最簡單的基-2算法結(jié)構(gòu)來實現(xiàn)FFT。同時，蝶形運算單元中的乘法器采用FPGA內(nèi)嵌硬件資源實現(xiàn)，這樣既可合理利用芯片資源，并可簡化設計，提高設計的成功率。</p><p>　　3.4.2 FFT運算精度提高的方法&l

97、t;/p><p>　　在進行FFT的運算時，主要的誤差為：量化誤差、舍入誤差以及溢出誤差。因此，F(xiàn)FT運算中數(shù)據(jù)范圍和系統(tǒng)誤差有著十分緊密的聯(lián)系，數(shù)據(jù)動態(tài)范圍的擴大可以減少系統(tǒng)的誤差，從而將運算精度提高。</p><p>　　為了使FFT的運算精度提高，在具體實現(xiàn)過程中，需要處理數(shù)據(jù)動態(tài)范圍這一問題。因此，為了處理這一問題可以運用下面幾種不同的方案[2]：</p><p&g

98、t;　?。?）運用定點的運算方法；</p><p>　?。?）運用浮點的運算方法；</p><p>　?。?）運用塊浮點的運算方法。</p><p>　　從FFT的處理器來看，運用定點運算方法時，為了防止溢出，可以給每一級蝶形單元運算的輸入處加入的衰減系數(shù)。此類防止溢出方法的缺點為不論信號強度的大小，都一律會被衰減。運用浮點運算方法時，將嚴重占用系統(tǒng)資源，浮點尾數(shù)的

99、處理較為復雜。和定點系統(tǒng)比較，從量化誤差上來看，塊浮點誤差較小，但是塊浮點每一步的運算之后都要對溢出進行判斷，系統(tǒng)設備量被成倍的增加；和浮點系統(tǒng)比較，從運算精度上來看，塊浮點精度降低，但其特點可以滿足信號處理尤其是高性能處理方面的要求，并且結(jié)構(gòu)相對較為簡單。</p><p>　　本文將會采用定點運算的方法來完成整個系統(tǒng)設計。為了提高運算精度，進行數(shù)據(jù)處理時，將蝶形運算的輸出固定縮小2倍，即相當于在第一級后每級蝶形

100、運算的輸入處插入的衰減系數(shù)，每級結(jié)果固定縮小2倍，從而防止溢出。</p><p>　　第四章 FFT處理器的設計與實現(xiàn)</p><p>　　在分析了基-2DIT-FFT算法原理，數(shù)據(jù)流動特點以及實現(xiàn)方案的基礎上，采用順序處理結(jié)構(gòu)，塊浮點運算方案，利用FPGA完成16位字長512點復數(shù)FFT處理器的設計。整個設計分成多個功能模塊，采用Verilog HDL和IP核描述，并在virtex

101、-II系列器件上實現(xiàn)。</p><p>　　4.1 FFT處理器的設計結(jié)構(gòu)與工作過程</p><p>　　基-2FFT模塊設計主要由6部分組成：蝶形運算單元，存儲單元，地址產(chǎn)生單元，功能切換單元，塊浮點單元和時序控制單元，如圖所示。</p><p>　　圖4.1 FFT處理器結(jié)構(gòu)圖</p><p>　　各模塊的功能概述如下：</p>

102、;<p>　?。?）蝶形運算單元：采用DIT方式完成基-2蝶形運算，若數(shù)據(jù)從雙口RAM1中讀出，則計算結(jié)果存入雙口RAM2中，反之亦然；</p><p>　?。?）存儲單元：主要用來存儲輸入數(shù)據(jù)、中間結(jié)果（RAM），預置旋轉(zhuǎn)因子（ROM），以及最后的計算結(jié)果（RAM）；</p><p>　　（3）地址產(chǎn)生單元：產(chǎn)生RAM的讀、寫地址和ROM的讀地址；</p>&

103、lt;p>　?。?）功能切換單元：完成RAM1與RAM2間數(shù)據(jù)讀寫功能的切換；</p><p>　?。?）塊浮點單元：記錄蝶算單元輸出數(shù)據(jù)的位信息，并完成蝶算單元輸入數(shù)據(jù)的截位；</p><p>　?。?）時序控制單元：產(chǎn)生各模塊的使能、控制信號，使整個流程正常工作。</p><p>　　FFT處理器工作過程描述如下：</p><p>

104、　?。?）當收到來自片外控制模塊發(fā)出的啟動命令后，即進入正常工作狀態(tài)。</p><p>　　（2）進入FFT工作狀態(tài)后，首先啟動時序控制單元，產(chǎn)生讀數(shù)據(jù)地址及讀使能信號，讀取雙口RAM1中的2路18bits原始數(shù)據(jù)。</p><p>　?。?）將從RAM1中讀出的2路數(shù)據(jù)經(jīng)過數(shù)據(jù)切換模塊轉(zhuǎn)化為4路并行數(shù)據(jù)。</p><p>　　（4）在進行本級蝶形運算之前，塊浮點運

105、算單元會對上一級的18bits數(shù)據(jù)進行截位處理，取出16bits有效數(shù)據(jù)。同時，時序控制單元產(chǎn)生ROM的讀數(shù)據(jù)地址及讀使能信號，讀取旋轉(zhuǎn)因子的實部和虛部值。兩路數(shù)據(jù)一起輸出至蝶形運算單元。</p><p>　?。?）此時啟動FFT蝶形運算單元，3個時鐘周期后，蝶算結(jié)果輸出。</p><p>　?。?）將4路運算結(jié)果經(jīng)過數(shù)據(jù)切換模塊轉(zhuǎn)化為2路，然后寫入另一組雙口RAM中。同時，將每次蝶算結(jié)果

106、送入塊浮點的溢出檢測單元，由此判斷溢出狀態(tài)。</p><p>　?。?）在進行第2次蝶形運算的同時，參加下一次蝶形運算的數(shù)據(jù)正從存儲器中讀取，使蝶形運算結(jié)果連續(xù)輸出。</p><p>　　（8）當一級中所有蝶形運算結(jié)束后，延遲7個時鐘周期再進行下一級的操作。在下一級操作中，兩組RAM的讀寫功能交換。</p><p>　?。?）當最后一級運算結(jié)束后，產(chǎn)生輸出地址和輸出