以高氏/質因數演算法設計之離散傳立葉轉換處理器

Abstract

離散傳立葉轉換在許多數位信號處理的應用中扮演很重要的角色, 包括頻譜分析、數 位濾波器、影像處理、視頻傳輸等等。而大部分的應用中都是處理多點離散傳位立葉 轉換且要求具即時處理的能力。是故有必要設計一套具即時處理功能的多點離散傳立 葉轉換系統以滿足現實需要。本論文的目的就在於設計一個高速離散傳立葉轉換器, 它可以工作在千萬赫玆下來處理一千零八點連續輸入的實數離散傳立葉轉換。 通常解決一個大問題的有效辦法是將其拆成數個小問題來減少問題的複雜度。由固德 及湯瑪斯所提出的質因數演算法便是此類方法, 它利用中國餘數定理來重組輸入次序 , 將多點離散傳立葉轉換變換成多維的短長度離散傳立葉轉換。在本篇論文我們提出 了一個單一記憶體緩衝器架構來完成質因數演算法, 如此便比傳統雙記憶體緩衝器架 構大量減少了計憶體大小。至於短長度離散傅立葉轉換我們采用了高舍演算法來設計 陣列架構, 同時為求更快的速度我們將此陣列設計成兩層管線式架構。另外, 由於大 部分應用為實數輸入, 我們可利用實數離散傅立葉轉換的對稱性來減少所要設計的離 散傅立葉轉換長度, 也就是以一半長度的離散傅立葉轉換來完成全長度的離散傅立葉 轉換。最后, 再使用計算機輔助設計工具完成晶片布局及驗證。結果其運算速度比現 有數位信號處理器高出甚多且足以符合大部分的速度要求。