Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/7998
標題: 新的緊縮結構的遞迴離散傅利葉轉換
Novel Recursive Discrete Fourier Transform with Compact Architecture
作者: 蘇國安
關鍵字: recursive;遞迴;discrete;fourier transform;離散;傅利葉轉換
出版社: 電機工程學系
摘要: 
在本篇論文,我們提出一新的遞迴方式來計算離散傅利葉轉換,我們提出的遞迴結構的優點有減少迴圈數以及比已知的Goertzel所提出的方法有較高的信號量化雜訊比(SQNR)。在此Goertzel的方法需要N2個乘法器及2N2個加法器。
由Goertzel所提出的方法雖然比直接方式較有效率,但它的計算數仍然正比於N2。其他相關的遞迴演算法,例如DFR-DFT及FFR-DFT,分別需要2N2個以及N2個迴圈數來計算所有傅利葉轉換輸出X[k]。
對於減少計算量的目的,我們提出緊縮的遞迴離散傅利葉轉換利用頻率索引k分群組的分式來加速傅利業轉換的速度,故所需要的迴圈數比其他的方法少,我們也顯示在表一。我們所提出的遞迴傅利葉轉換首先把轉換基底 分成DCT和DST兩部份,雖然在求出所有的DCT 及所有DST值時所需的轉換基底皆為N個。但由cosine及sine週期性發現,在計算不同 k值的DCT 及DST時,會有轉換基底共用的情形發生,故我們把需要相同轉換基底的DCT輸出值和DST輸出值分成在相同群組中,以共用係數的方式來減少計算量,在此使用數論的數學概念來做為分群組的工具,藉由輸入長度N求公因數的方式,產生基底集合 ={0,1,2,..., },再由定義 可得 集合,最後可得頻率索引k的分群組集合 ,藉由 可把DCT和DST分成群組。最後傅利葉轉換的輸出X[k]可藉由組合DCT和DST轉換結果來得到。藉由共同核心迴圈係數及輸出係數,我們可用硬體共享的方式的實現遞迴離散傅利葉轉換。

In this paper, we propose the novel recursive method to compute discrete Fourier transforms (DFT). The advantages of proposed recursive structure are the reduction of the loop numbers and the signal to quantization noise ratio (SQNR) is greater than the well-known Goertzel's method which requires the numbers of N2 multiplications and the numbers 2N2 additions. The Goertzel's method is more efficient than the direct method, but the amounts of computations are still proportional to N2. The others algorithms of the recursive DFT, such as DFR-DFT and FFR-DFT, require 2N2 and N2 loop numbers to evaluate the all DFT outputs X[k].
For simplicity, the compact recursive DFT applied the grouped frequency indices to accelerate the computation of the DFT transformation. So we need less loop numbers than the others DFT transform, shown as Table I. The proposed recursive DFT transforms first separate the transform base into the two parts of the DCT and DST. During the computations of the DCT and DST, we require the amounts of the N transform bases. By the property of the period, we find the transform base to be repeated for the evaluating all DCT and DST. So we categorize the outputs of the DCT and DST into the same group which are required the same transform base. By using the shared coefficients, we can achieve to reduce the computation of the DCT and DST. We use the mathematical conceptions of the number theorem in order to group the transform outputs of the DCT and DST. By evaluating the factors of the input length N, we can first obtain the base set, shown as ={0,1,2,..., },then we can obtain the kernel number by the definition . Therefore we can achieve the grouped frequency indices in order to group the transform of the DCT and DST. Finally, the outputs of the DFT transform can be achieved by the combinations of the outputs of the DCT and DST. By sharing the loop coefficients and output coefficients, we can implement the recursive DFT with hardware sharing architectures.
URI: http://hdl.handle.net/11455/7998
Appears in Collections:電機工程學系所

Show full item record
 

Google ScholarTM

Check


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