【正文】 處理中起著核心作用，而 DFT的快速算法快速傅立葉變換 FFT就成為了數(shù)字信號(hào)處理的最基本技術(shù)之一 。該設(shè)計(jì)采用 了 按時(shí)間 抽取基 2 算法 ， 使用改進(jìn) 的 順序 結(jié)構(gòu) 設(shè)計(jì)蝶形運(yùn)算單元 ， 同時(shí)采用雙端口 RAM存儲(chǔ)結(jié)構(gòu) ， 該設(shè)計(jì)方法 在保持處 理速度的優(yōu)勢(shì)下， 很可觀地 減少了運(yùn)算量， 經(jīng)驗(yàn)證 完成 64點(diǎn)輸入為 12位復(fù)數(shù)的 FFT需要 ， 基本上滿足了實(shí)時(shí)性的要求。隨著它的不斷應(yīng)用和發(fā)展，也使電子設(shè)計(jì)的規(guī)模和集成度不斷提高。 作者簽名： 日 期： I 目 錄 摘要 ............................................................Ⅱ Abstract..........................................................Ⅲ 第一章 緒論 ...................................................... 1 FFT 算法的研究現(xiàn)狀 ............................................................................................................ 1 FFT 處理器的研究現(xiàn)狀 ........................................................................................................ 1 FPGA 實(shí)現(xiàn) FFT 的優(yōu)越性 ...................................................................................................... 2 本文研究的主要內(nèi)容 ........................................................................................................... 3 第二章 FFT 算法原理簡(jiǎn)介 ........................................... 4 離散傅立葉變換及其實(shí)現(xiàn)的局限性 ......................................... 4 快速傅里葉變換 FFT 的原理 ............................................................................................... 4 基 2 時(shí)域抽取 FFT 算法 .................................................................................................... 5 基 4 時(shí)間抽取 FFT 算法 .................................................................................................. 8 時(shí)域抽取法和頻域抽取法的特點(diǎn) ....................................................................................... 9 第三章 FFT 處理器基于 FPGA 的設(shè)計(jì) ..................................10 FFT 處理器常用的實(shí)現(xiàn)形式 .............................................................................................. 10 FFT 處理器的總體設(shè)計(jì)方案 .............................................................................................. 11 基于 FPGA 的 FFT 處理器設(shè)計(jì)特點(diǎn) ................................................................................... 15 FPGA 器件的簡(jiǎn)單介紹 .................................................................................................... 15 基于 FPGA 的 FFT 處理器具有的特點(diǎn)： ........................................................................ 16 第四章 FFT 的硬件仿真 .............................................17 復(fù)數(shù)乘法器的時(shí)序仿真 ..................................................................................................... 17 蝶形運(yùn)算器的仿真 ............................................................................................................. 18 FFT 的整體 FPGA 實(shí)現(xiàn)和仿真 ........................................................................................... 19 結(jié)論 .............................................................21 致謝 .............................................................22 參考文獻(xiàn)： .......................................................23 附錄： ...........................................................24 II 基于 FPGA的 FFT處理器的設(shè)計(jì) 摘要 快速傅立葉變換 (FFT)作為時(shí)域與頻域轉(zhuǎn)換的基本工具，正被廣泛應(yīng)用于檢測(cè)、通信、圖像處理和多媒體等領(lǐng)域。畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文），是我個(gè)人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說明 本人完全了解安陽工學(xué)院關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)校可以采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉?jī)?nèi)容。 現(xiàn)場(chǎng)可編程門陣列 (FPGA)是 近年來迅速發(fā)展起來的新型可編程器件。 本文主要研究如何利用 FPGA實(shí)現(xiàn) FFT算法 。由數(shù)字信號(hào)處理的基本理論可知，卷積可以轉(zhuǎn)化為 DFT來實(shí)現(xiàn)，實(shí)際上其他許多算法，如相關(guān)、譜分析等也都可以轉(zhuǎn)化為 DFT來實(shí)現(xiàn)；此外，各種系統(tǒng)的分析、設(shè)計(jì)和實(shí)現(xiàn)中都會(huì)用到 DFT的計(jì)算問題。因此，如何更快速、更靈活地實(shí)現(xiàn) FFT變得越來越重要。 (2)N不等于 2的整數(shù)次冪的算法，以威諾格蘭德 (S． Winograd)為代表的一 類傅立葉變換算法 (Winograd Fourier Transform Algorithm，簡(jiǎn)稱 WFTA算法， Prime Factor Transform Algorithm，簡(jiǎn)稱 PFTA算法 )，利用下標(biāo)映射和數(shù)論 以及近代數(shù)學(xué)的知識(shí)，去掉級(jí)間的旋轉(zhuǎn)因子，從而減少運(yùn)算量。分裂基算法具有一定 的優(yōu)勢(shì)，綜合了基 4和基 2的運(yùn)算特點(diǎn)，但其蝶形運(yùn)算結(jié)構(gòu)在控制上要復(fù)雜一 些。但是，通用 DSP處理器構(gòu)成的 FFT處理機(jī) 2 采用循環(huán)編碼算法，程序量小，但存在大量的冗余運(yùn)算，需要許多跳轉(zhuǎn)操作， 并且 處 理速度較慢，難以滿足現(xiàn)代數(shù)字信號(hào)處理高速、大規(guī)模、實(shí)時(shí)性的要求 。因此，任何的線路改版都需要重新設(shè)計(jì)并且重新制造，這不僅增加開發(fā)成本，而且 阻礙了 產(chǎn)品 的 快 速上市，不太適合處理算法和參數(shù)經(jīng)常改變的場(chǎng)合 。 基于上述分析，采用 FPGA設(shè)計(jì)和實(shí)現(xiàn) FFT就具有了很大的價(jià)值。 FPGA所固有的靈活性和性能可讓設(shè)計(jì)者緊跟新標(biāo)準(zhǔn)的變化，并能提供可行的方法來滿足不斷變化的標(biāo)準(zhǔn)要求。 DSP內(nèi)部一般沒有大容量的存儲(chǔ)器，但是 FFT實(shí)時(shí)處理運(yùn)算需要存儲(chǔ)大量的數(shù)據(jù)，只能外接存儲(chǔ)器，這樣往往會(huì)使運(yùn)算速度下降，同時(shí)電路也會(huì)更復(fù)雜和不穩(wěn)定。 (4)在比較 FPGA和 DSP時(shí)，一個(gè)極為重要的系統(tǒng)參數(shù)是輸入 /輸出 (I/O)帶寬。而如何在保證系統(tǒng)對(duì)高速度、低成本的要求下，實(shí)現(xiàn)高精度的 FFT運(yùn)算，已經(jīng)成為各研發(fā)機(jī)構(gòu)的研究重點(diǎn)。 本次論文就是在這樣一個(gè)背景下提出 的 一種基于 FPGA的高速 FFT處理器設(shè)計(jì)方法 ，以期自主設(shè)計(jì)基于 FPGA芯片的 FFT，把 FFT實(shí)時(shí)性的要求和 FPGA芯片設(shè)計(jì)的靈活性結(jié)合起來 ，提高 FFT處理速度，滿足現(xiàn)代信號(hào)處理的高速度、高可靠性要求。 本次論文 對(duì) FFT 的 原理及其基于 FPGA 的設(shè)計(jì)進(jìn)行了闡述。 離散傅立葉變換 (DFT)是數(shù)字信號(hào)處理的一個(gè)工具，相當(dāng)于模擬信號(hào)分析的傅立葉變換。對(duì)信號(hào)而言， DFT提供的信息稱為信號(hào)的頻譜，對(duì)濾波器而言， DFT得到的信息稱為濾波器的頻率響應(yīng)，它由兩部分組成：幅度響應(yīng)和相位響應(yīng)，幅度響應(yīng)給出了濾波器的形狀 。實(shí)現(xiàn)一次復(fù)數(shù)乘法需要 4次實(shí)數(shù)乘法和 2次實(shí)數(shù)加法，一次復(fù)數(shù)加法需要兩次實(shí)數(shù)加法。 為減少運(yùn)算量，提高運(yùn)算速度，就必須改進(jìn)算法。其 基本思想就是 將 N 點(diǎn)序列分解成兩個(gè)或更多的較短序列，這些短序列的 DFT 可重新組合成原序列的 DFT，過程中利用 WnkN的周期性和對(duì)稱性來減少 DFT的運(yùn)算次數(shù)，使運(yùn)算量得到很大的改觀。信 號(hào) x(n)根據(jù)采樣信號(hào)分解為奇采樣點(diǎn)和偶采樣。同理將每個(gè) N/2點(diǎn)在分解成奇偶兩部分，則 N/2點(diǎn)的 DFT可以由兩個(gè) N/4點(diǎn)的 DFT求得，依次類推，一直分解到N/2個(gè) 2點(diǎn)的 DFT。與直接計(jì)算的 DFT 要做的 N2次復(fù)數(shù)乘法和 N(N1)次復(fù)數(shù)加法相比較，N 越大，計(jì)算量得到改觀越明顯。 ④位碼倒序：由圖 22所示可以看到 FFT 輸出的 X(k)的次序正好是順序排列的，即 X(0)，X(1)，? X(7)，而輸入 x(n)是按 x(0)， x(4)，? x(7)的倒序存入存儲(chǔ)單元，即為倒序輸入，正序輸出。 ⑤旋轉(zhuǎn)因子的確定：由 8 點(diǎn) FFT 的三次迭代運(yùn)算可以看出系數(shù) kNW 的變化。 基 4時(shí)間抽取 FFT算法 基四 FFT算法和基二 FFT算法原理相似，只是將分解的基數(shù)改為 4，使得在增加單個(gè)蝶形運(yùn)算單元復(fù)雜度的情況下，減少了蝶形單元的個(gè)數(shù)。 時(shí)域抽取法和頻域抽取法的特點(diǎn) 一般而言， FFT算法分為時(shí)間抽取 FFT和頻率抽取 FFT兩大類，時(shí)間抽取算法的特點(diǎn)是每一級(jí)處理都是在十余里把輸入序列依次按奇 /偶分解為較短的序列；頻率抽取 FFT算法的特點(diǎn)是在頻域里把序列依次按奇 /偶分解為較短的序列進(jìn)行計(jì)算。 而 如何在保證系統(tǒng)對(duì)高速度、低成本的要求下，實(shí)現(xiàn)高精度的 FFT運(yùn)算，已經(jīng)成為各研發(fā)機(jī)構(gòu)的研究重點(diǎn)。即從第 1級(jí)開始，從上至下依次進(jìn)行，第 1級(jí)算完后，然后進(jìn)行第 2級(jí)，第 3級(jí)， ??，直至算完為止。 流水線處理具有以下特點(diǎn) ： ①使用 M=log2N個(gè)蝶形運(yùn)算單元； ② M個(gè)蝶形運(yùn)算單元在各級(jí)間并行運(yùn)算，即級(jí)與級(jí)之間是并行工作的； ③每個(gè)蝶形運(yùn)算單元在每一級(jí) 中順序執(zhí)行 N/2個(gè)蝶形運(yùn)算，即每一級(jí)運(yùn)算的內(nèi)部是串行工作的； ④如果一次蝶形運(yùn)算時(shí)間為 T，則理論上總的運(yùn)算時(shí)間和每一級(jí)數(shù)據(jù)運(yùn)算時(shí)間一樣 (沒考慮級(jí)與級(jí)之間的數(shù)據(jù)緩沖 )，為 T 2N 。 陣列處理具有以下特點(diǎn)： ①使用 2N log2N個(gè)蝶形運(yùn)算單元并行完成全部蝶形運(yùn)算； ②由于采用流水線工作方式，使單位時(shí)間內(nèi)處理的數(shù)據(jù)增大了 log2N倍，也就是說數(shù)據(jù)的吞吐量增大了 log2N倍； ③總的運(yùn)算時(shí)間理論上等于一次蝶形運(yùn)算時(shí)間 T。 整個(gè)設(shè)計(jì)主要包括雙端口 RAM數(shù)據(jù)存儲(chǔ)單元、 FFT運(yùn)算單元、旋轉(zhuǎn)因子產(chǎn)生器 (ROM)、地址生成及控制單元、倒序單元五個(gè)模塊。為了加快 FFT的運(yùn)算速度，構(gòu)造雙端口 RAM，存儲(chǔ)與讀取同時(shí)進(jìn)行，實(shí)現(xiàn)乒乓操作。設(shè)計(jì)旋轉(zhuǎn)因子存儲(chǔ)器時(shí)，根據(jù)此規(guī)律減少 ROM的存儲(chǔ)空間，即生成的 ROM中只有 256個(gè)存儲(chǔ)單 元，利用對(duì)稱性映射出 512個(gè)旋轉(zhuǎn)因子。在被映射的 512個(gè)地址中， r=256的旋轉(zhuǎn)因子的地址比較特殊，它是所有旋轉(zhuǎn)因子的對(duì)稱