超大型積體電路設計與計算機自動輔助設計---子計畫五：利用分散算術及質因數演算法設計之離散傅利葉轉換系統

Abstract

數位訊號處理的應用近十年來大幅地成長, 舉凡在語音處理、影像處理、視頻傳輸等各方 面都已逐漸取代傳統類比訊號處理的地位.而 在這些數位訊號處理的應用中,離散傅利葉轉 換一直扮演著很重要的角色.但是由於大部分 的應用都有即時處理的要求而且需要長點數的 運算,因此使得離散傅利葉轉換系統的設計變 得相當困難.所以本計畫的目的就是希望能設 計一個經濟且有效的演算法則與硬體架構並以 超大型積體電路來實現能處理一千零八點連續 輸入實數的高速離散傅利葉轉換系統.首先我 們利用離散傅利葉轉換的對稱特性將運算點數 減少一半,然後採用質因數演算法將一維的長 點數離散傅利葉轉換變換成多維的短點數離散 傅利葉轉換.如此一來所有的運算量就銳減成 實現數個短點數離散傅利葉轉換所需的運算, 因此我們就可針對短點數離散傅利葉轉換來設 計一個高速且適合於超大型積體電路實現的演算法則與硬體架構.由於乘法是離散傅利葉轉 換中最常用也最占晶片面積的運算,所以我們 以分散算術法為基礎來發展演算法則並配合管 線式設計來完成其硬體架構.因為不需要用到 乘法器而且架構非常規則,所以非常適合於超 大型積體電路實現.在計畫中,我們將完成這個 長點數高速離散傅利葉轉換系統演算法則與硬 體架構的設計,並且進行各項分析與模擬以驗 證其正確性.最後並完成其佈局設計,希望能以 單晶片超大型積體電路為目標來完成此傅利葉 轉換系統.