Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/8118
標題: 定點快速傅立業轉換信號雜訊比之最佳化
Optimizing Signal-to-Noise Ratio for Fixed-Point Fast Fourier Transforms
作者: 蔡志佳
Tsai, Chih-Chia
關鍵字: fast fourier transform;快速傅立業轉換;bits allocation;optimum rule;noise propagation model;M.Q.C.D algorithm;位元分配;最佳化法則;雜訊傳遞模組;M.Q.C.D.演算法
出版社: 電機工程學系
摘要: 
隨著積體電路設計的進步,快速傅立業轉換處理器其電路架構亦發展成熟。為了得到快速傅立業轉換的最佳化訊號雜訊比,我們從位元重新分配的策略下分析並且試著求出於系統效能與硬體成本之間的取捨問題。
基本上,最佳化法則可分為兩部分:
一、將FFT每一級處理器的訊號與雜訊傳遞行為藉著一組功率放大器
結合可加成性雜訊源的方式進行模組化,透過這個模組能夠很快
速且有系統地估測定點FFT的雜訊效能。這個技術可以對定點FFT
中的每一級位元數任意指定並求出其信號雜訊比,接著根據不同
位元分配,計算出所需要的記憶體與算術單元的大小。最後,分
析所有訊號雜訊比與硬體需求量而找出最佳方案。
二、關於FFT的乘法部分,首先我們使用最少加法數表示式將乘法以
最少加法量與移位來實現達到降低硬體複雜度。接著引用Ying-Jui
Chen等人所提出的quasi-coordinate-descent based (Q.C.D.)演算
法,此演算法能夠將每一次的加法增量分配到各乘法中;亦即於
每一次的加法增量都能分配到對系統效能最好的乘法器上。但
是,Q.C.D.演算法所得到的最佳化配置並非在各加法數之所有分配
情形中取得;亦即Q.C.D.演算法無法紀錄所有分配的情形,進而
取得真正的最佳化分配。為了改善這個缺點,我們加入trellis
diagram的全記錄觀點,將可以提升原先Q.C.D.的效能,推出名為
Modified quasi-coordinate-descent (M.Q.C.D.)的演算法。接著配
合M.Q.C.D.演算法將每一個的加法作效能最佳的分配,使其在既有
硬體成本下具有最佳的訊號雜訊比。最後,我們以FPGA晶片設計驗證
所提出的M.Q.C.D.演算法使用的硬體資源的確是最少的。
所以,只要選定快速傅立業轉換的演算法及其架構然後配合本論文所提出的最佳化策略,即能設計出一個具有最佳化訊號雜訊比的快速傅立業轉換處理器。

As integrated circuit design keeps improving, fast fourier transform (FFT) hardware architectures also become mature. To optimize the signal-to-noise ratio (SNR) for fixed-point fast fourier transforms, we devised the strategy for the bit allocation and found out the trade-offs between system performance and hardware cost.
The optimization rules can be divided into two categories. The first part describes a technique for quick and systematic estimation of fixed-point FFT noise performance by modeling the signal and noise propagation in every processing stage of the FFT as a series of signal amplifier stages combined with additive noise sources. The technique can specify the number of bits at every stage arbitrarily and obtain SNR associated with a certain bits allocation. According to the various allocation we can calculate the size of memory and arithmetic units. Using these results, we find out the best solution given SNR and hardware cost.
The second part is to discuss the multiplication of the FFT. First, we used the minimum-adder representation to reduce hardware complexity by replacing an multiplication into minimal adders and shifters. Then, we used a quasi-coordinate-
descent based (Q.C.D.) algorithm proposed by Ying-Jui Chen, et al. It can obtain efficient allocation on a multiplication when increase adders one by one. Each adder can be allocated to the multiplication that will yield best system performance. However, the allocation by Q.C.D. algorithm is only locally optimal but not globally optimal. Therefore, we used trellis diagram to improve the Q.C.D. performance. We called it “Modified quasi-coordinate-descent” (M.Q.C.D.) algorithm. We used the M.Q.C.D. algorithm to allocate the adders for optimal system performance. At a given hardware cost, we can optimize the SNR. Then, we verified that the M.Q.C.D. algorithm did obtain the minimum hardware resource in FPGA chip design flow.
In conclusion, the methods proposed in the thesis can design a FFT processor with optimal SNR.
URI: http://hdl.handle.net/11455/8118
Appears in Collections:電機工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.