以分散式算術法設計之離散傅立葉轉換器

Abstract

離散傅利葉轉換常被廣泛應用於頻譜分析、數位濾波器、迴旋積分、資 料壓縮等方面。然而傳統的離散傅利葉轉換設計在速度及面積上已不符合 現今許多應用的要求，為因此解決的方法是發展一個經濟且實用的演算法 則與硬體架構來實現能處理長點數連續輸入複數的高速離散傅利葉轉換系 統。 在本論文中，我們設計一個可實現連續輸入六百三十點複數資料的 高速離散傅利葉轉換器，我們利用由固德與湯瑪斯所提出的質因數演算法 為基礎，把一維長點數的離散傅利葉轉換變換成三維短點數的離散傅利葉 轉換來處理，再利用列行分解法可將此三維離散傅利葉轉換當做是三個短 點數的離散傅利葉轉換來處理，而每一個短點數的離散傅利葉轉換再利用 分散式算數法來降低系統的運算複雜度與硬體花費。我們價硬體架構可有 效減低運算的數量且具有規則性、模組性、區域性和易於控制的優點。最 後，我們使用0.6微米的製程技術配合計算機輔助工具將晶片的佈局完成 並加以製造及驗證。 The discrete Fourier transform (DFT) is useful in a variety of applications in spectral analysis, digital filtering, convolution integrate and data compression. The speed of traditional DFT design is no longer fast enough for many applications nowadays. The solution for this problem is to develop an economical and practical hardware architecture to implement high speed DFT system. In this thesis, a high speed DFT processor with one-dimensional fully pipeline architecture are proposed. It can perform 630 complex-value DFT with nonstoped input. Based on prime factor algorithm, we map an one-dimensional 630-point complex-value DFT into a three- dimension DFT. Using the row column decomposition method, this three-dimension DFT can be treaded as three short-length DFTs whose lengths are 7, 9 and 10. In each short-length DFT we use distributed arithmetic method to reduce the complexity of computing and hardware cost. We use Verilog simulator to simulate our gate level circuit and it can work in 25 Mhz. Finally we use Cadence tools (OPUS) and COMPASS 0.6 (m standard cell library to implement our DFT processor.